A Worked Birkhoff–von Neumann Decomposition

From a Matrix to Permutation Matrices

A doubly stochastic matrix can be viewed as a weighted combination of perfect assignments: each permutation matrix records one assignment, and its coefficient records the weight given to that assignment. In a concrete decomposition, the main work is to choose a permutation supported on positive entries, subtract as much of it as possible without making any entry negative, and repeat on the residual matrix.

Throughout, matrices are square of order \(n\), where \(n\ge 1\). A matrix is nonnegative if all its entries are at least zero. It is doubly stochastic if it is nonnegative and every row sum and every column sum equals \(1\). A permutation matrix has exactly one \(1\) in each row and each column and has \(0\) in every other position. A positive diagonal of a matrix means a selection of one positive entry in each row, with the selected entries in different columns. Thus it need not be the matrix's main diagonal.

Definition: A convex combination of permutation matrices is an expression \(\sum_{i=1}^k \alpha_iP_i\), where each \(P_i\) is a permutation matrix, each \(\alpha_i\ge 0\), and \(\sum_{i=1}^k\alpha_i=1\).

To subtract a permutation matrix \(P\), use only the entries where \(P\) has a \(1\). The largest coefficient that can be subtracted without producing a negative entry is the smallest matrix entry among those positions. After subtraction, every row sum and column sum decreases by the same coefficient. This common row and column sum is useful to track: the residual need not itself be doubly stochastic until it is divided by its row sum.

Why the Subtraction Process Works

Lemma: Let \(R\) be a nonnegative \(n\times n\) matrix whose row and column sums all equal \(r>0\). Let \(P\) be a permutation matrix whose \(1\)-entries occur only at positive entries of \(R\). Define \(\alpha\) to be the smallest entry of \(R\) at those positions. Then \(0<\alpha\le r\), and \(R-\alpha P\) is nonnegative with every row and column sum \(r-\alpha\). At least one positive entry of \(R\) becomes zero.

Proof. There are \(n\) selected entries, and each is positive, so their minimum \(\alpha\) is positive. Every entry of \(R\) is at most \(r\), since it is nonnegative and is part of a row whose sum is \(r\). In particular, \(\alpha\le r\). At each selected position, the entry of \(R\) is at least \(\alpha\), so subtracting \(\alpha\) leaves a nonnegative entry. Other entries do not change. Each row has exactly one selected position, so its sum decreases by \(\alpha\); the same argument applies to each column. Finally, a selected entry attaining the minimum \(\alpha\) becomes zero. \(\square\)

Apply the lemma repeatedly, selecting a positive diagonal in each nonzero residual. Such a diagonal exists whenever the residual has a positive common row sum: dividing by that sum gives a doubly stochastic matrix, and the earlier result on positive diagonals applies. Each subtraction removes at least one positive position and never makes a zero position positive. Since there are only \(n^2\) positions, the process must stop after finitely many steps. If the residual has row sum zero, nonnegativity forces every entry to be zero.

If the coefficients subtracted are \(\alpha_1,\dots,\alpha_k\), the residual after \(k\) steps has row sum \(1-\sum_{i=1}^k\alpha_i\). When it is zero, the original matrix is exactly \(\sum_{i=1}^k\alpha_iP_i\), and the row-sum identity gives \(\sum_{i=1}^k\alpha_i=1\). This justifies both the subtraction rule and the convex-combination check used below.

Three Explicit Decompositions

Worked Example: Three Different Subtraction Steps

Consider the matrix

A= \begin{pmatrix} \frac12&\frac12&0\\ \frac16&\frac12&\frac13\\ \frac13&0&\frac23 \end{pmatrix}.

Its row sums are \(\frac12+\frac12=1\), \(\frac16+\frac12+\frac13=1\), and \(\frac13+\frac23=1\). Its column sums are \(\frac12+\frac16+\frac13=1\), \(\frac12+\frac12=1\), and \(\frac13+\frac23=1\). Thus \(A\) is doubly stochastic.

First select the main diagonal, giving \(P_1=I\). Its entries in \(A\) are \(\frac12,\frac12,\frac23\), so the subtraction coefficient is their minimum, \(\alpha_1=\frac12\). Subtracting gives

R_1=A-\frac12I= \begin{pmatrix} 0&\frac12&0\\ \frac16&0&\frac13\\ \frac13&0&\frac16 \end{pmatrix}.

Each row and column of \(R_1\) sums to \(\frac12\). Next select positions \((1,2),(2,3),(3,1)\), which give the permutation matrix

P_2= \begin{pmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{pmatrix}.

The selected entries of \(R_1\) are \(\frac12,\frac13,\frac13\), so \(\alpha_2=\frac13\). The next residual is

R_2=R_1-\frac13P_2= \begin{pmatrix} 0&\frac16&0\\ \frac16&0&0\\ 0&0&\frac16 \end{pmatrix}.

Its nonzero entries lie at positions \((1,2),(2,1),(3,3)\). These form a permutation matrix \(P_3\), and each selected entry is \(\frac16\). Subtracting \(\frac16P_3\) leaves the zero matrix. Therefore

A=\frac12 \begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix} +\frac13 \begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix} +\frac16 \begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}.

Check: the coefficients sum to \(\frac12+\frac13+\frac16=1\). The first row of the combination is \((\frac12,\frac13+\frac16,0)=(\frac12,\frac12,0)\); the second is \((\frac16,\frac12,\frac13)\); and the third is \((\frac13,0,\frac12+\frac16)=(\frac13,0,\frac23)\). These are exactly the rows of \(A\).

Worked Example: A Matrix with Zeros in Its Support

Let

B= \begin{pmatrix} \frac12&\frac12&0\\ 0&\frac12&\frac12\\ \frac12&0&\frac12 \end{pmatrix}.

Each row sums to \(\frac12+\frac12=1\), and each column also sums to \(\frac12+\frac12=1\). Select the main diagonal. Its three entries are all \(\frac12\), so subtracting coefficient \(\frac12\) gives

B-\frac12I= \begin{pmatrix} 0&\frac12&0\\ 0&0&\frac12\\ \frac12&0&0 \end{pmatrix} =\frac12 \begin{pmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{pmatrix}.

The remaining positive entries select one position in every row and column, so the residual is \(\frac12\) times a permutation matrix. Thus \(B=\frac12I+\frac12P\), where \(P\) is the displayed matrix. Zeros in \(B\) cause no difficulty: the selected positive diagonal uses only positive positions, and the residual is allowed to contain additional zeros.

Check: the first row of \(\frac12I+\frac12P\) is \((\frac12,\frac12,0)\), the second is \((0,\frac12,\frac12)\), and the third is \((\frac12,0,\frac12)\). The two coefficients are nonnegative and sum to \(1\).

Worked Example: The Uniform Three-by-Three Matrix

Consider

C= \begin{pmatrix} \frac13&\frac13&\frac13\\ \frac13&\frac13&\frac13\\ \frac13&\frac13&\frac13 \end{pmatrix}.

Every row and column contains three entries of \(\frac13\), so each sum is \(3\cdot\frac13=1\). Choose \(P_1=I\). Each selected entry is \(\frac13\), giving coefficient \(\alpha_1=\frac13\) and residual

R_1=C-\frac13I= \begin{pmatrix} 0&\frac13&\frac13\\ \frac13&0&\frac13\\ \frac13&\frac13&0 \end{pmatrix}.

In \(R_1\), choose positions \((1,2),(2,3),(3,1)\), which form \(P_2\) from the first example. Their entries are all \(\frac13\), so subtract coefficient \(\frac13\):

R_2=R_1-\frac13P_2= \begin{pmatrix} 0&0&\frac13\\ \frac13&0&0\\ 0&\frac13&0 \end{pmatrix} =\frac13 \begin{pmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}.

The last displayed matrix is a permutation matrix \(P_3\). Hence

C=\frac13I+\frac13P_2+\frac13P_3.

Check: the coefficients sum to \(\frac13+\frac13+\frac13=1\). In row 1, the three permutation matrices place their \(1\)'s in columns 1, 2 and 3 respectively, so the combined row is \((\frac13,\frac13,\frac13)\). In row 2, the selected columns are 2, 3 and 1; in row 3, they are 3, 1 and 2. Each row is therefore also \((\frac13,\frac13,\frac13)\), verifying every entry of \(C\).

Common Pitfall: Choosing Too Large a Coefficient

In the first example, the main-diagonal entries are \(\frac12,\frac12,\frac23\). A tempting but invalid choice is to subtract \(\frac23 I\), perhaps by looking only at the third diagonal entry. At position \((1,1)\), this would produce \(\frac12-\frac23=-\frac16\), so the residual would not be nonnegative and the subtraction would fail.

The coefficient must be the minimum over all selected positions, not the maximum or a value taken from just one row. Here that minimum is \(\min\{\frac12,\frac12,\frac23\}=\frac12\). After every valid subtraction, check nonnegativity, the common row and column sums, and—at the end—that the coefficients sum to \(1\). These checks catch both an invalid subtraction and an incomplete decomposition.

Check Your Understanding

For each question, track the selected positions and verify the matrix arithmetic.

For the matrix in the first worked example, what would the residual be after subtracting \(\frac12I\), and what are its row sums?
In the second example, why is the residual a scalar multiple of a permutation matrix even though the original matrix has zero entries?
For the uniform three-by-three matrix, verify the entry in row 2, column 3 of the final convex combination.
Suppose a residual has common row and column sum \(r>0\), and a selected permutation uses entries \(\frac25,\frac12,\frac35\). What is the largest valid subtraction coefficient?
Explain why a zero residual row sum forces the entire residual matrix to be zero when all its entries are nonnegative.