Proving the Birkhoff–von Neumann Theorem

The Decomposition Problem

A doubly stochastic matrix has nonnegative entries, with every row sum and every column sum equal to \(1\). The Birkhoff–von Neumann theorem says that every such matrix is a convex combination of permutation matrices. The proof has two central tasks: first find a permutation whose selected entries are all positive; then use those entries to make progress toward a permutation matrix without creating negative entries.

We use Hall’s theorem, established earlier in the material on Hall’s marriage theorem. In the form needed here, it says that a finite bipartite graph with vertex classes \(R\) and \(C\) has a matching covering every vertex of \(R\) if and only if every subset \(X\subseteq R\) has at least \(|X|\) neighbors. When \(|R|=|C|\), such a matching covers both classes.

Definition: A real \(n\times n\) matrix \(A=(a_{ij})\) is doubly stochastic if \(a_{ij}\ge 0\) for every \(i,j\), each row sums to \(1\), and each column sums to \(1\). A permutation matrix has exactly one entry equal to \(1\) in each row and column, and all other entries equal to \(0\). A convex combination of matrices \(P_1,\dots,P_k\) is a sum \(\sum_{r=1}^k \lambda_rP_r\), where every \(\lambda_r\ge 0\) and \(\sum_{r=1}^k\lambda_r=1\).

Finding a Positive Permutation Diagonal

The support graph records precisely which entries of a matrix are positive. Its left vertices represent rows, its right vertices represent columns, and an edge joins row \(i\) to column \(j\) exactly when \(a_{ij}>0\). A matching covering every row selects one positive entry in each row and each column. Those selected entries form a positive permutation diagonal, meaning a set of entries \(a_{i,\pi(i)}>0\) for a permutation \(\pi\) of the columns.

Lemma: Every doubly stochastic matrix has a positive permutation diagonal.

Proof. Let \(A=(a_{ij})\) be doubly stochastic, and form its support graph with row class \(R\) and column class \(C\). Take any subset \(X\subseteq R\), and let \(N(X)\subseteq C\) be its set of neighboring columns. Every positive entry in a row indexed by \(X\) lies in a column in \(N(X)\). Therefore, using nonnegativity and the row sums,

|X|=\sum_{i\in X}\sum_{j\in N(X)}a_{ij}.

For each \(j\in N(X)\), the sum of the entries in column \(j\) over rows in \(X\) is at most its full column sum \(1\), again because entries are nonnegative. Consequently,

|X|=\sum_{j\in N(X)}\sum_{i\in X}a_{ij} \le \sum_{j\in N(X)}1 =|N(X)|.

This holds for every \(X\subseteq R\), including \(X=\varnothing\), for which both sides are \(0\). Hall’s theorem gives a matching covering \(R\). There are \(n\) vertices in each class, so the matching also covers \(C\). Each matched pair is an edge of the support graph, hence corresponds to a positive entry. These \(n\) entries form a positive permutation diagonal. \(\square\)

Worked Example: Checking Hall’s Condition in a Support Graph

Consider the matrix

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

Each row sums to \(1\): the first two sums are \(\frac12+\frac12=1\), and the last two are \(\frac13+\frac23=1\). The column sums are also \(1\): columns 1 and 2 each sum to \(\frac12+\frac12=1\), while columns 3 and 4 each sum to \(\frac13+\frac23=1\). The matrix is doubly stochastic.

Write \(r_i\) for row \(i\) and \(c_j\) for column \(j\). Its support graph has vertex classes \(R=\{r_1,r_2,r_3,r_4\}\) and \(C=\{c_1,c_2,c_3,c_4\}\), with edge set \(\{r_1c_1,r_1c_2,r_2c_1,r_2c_2,r_3c_3,r_3c_4,r_4c_3,r_4c_4\}\). For any subset \(X\subseteq R\), let \(X_1=X\cap\{r_1,r_2\}\) and \(X_2=X\cap\{r_3,r_4\}\). If \(X_1\) is nonempty, its neighbors are both \(c_1,c_2\), so \(|N(X)\cap\{c_1,c_2\}|=2\ge |X_1|\). If \(X_1\) is empty, both quantities are \(0\). The same reasoning gives \(|N(X)\cap\{c_3,c_4\}|\ge |X_2|\). The two column blocks are disjoint, so adding these inequalities gives \(|N(X)|\ge|X|\).

For instance, the diagonal entries \(a_{11},a_{22},a_{33},a_{44}\) are all positive and select one entry from every row and column. Check: their values are \(\frac12,\frac12,\frac13,\frac13\), all strictly greater than \(0\), as required for a positive permutation diagonal.

The Induction Proof

Theorem (Birkhoff–von Neumann): Every finite doubly stochastic matrix is a convex combination of permutation matrices.

Proof. We prove the theorem for every order \(n\ge 1\) by strong induction on \(s(A)\), the number of strictly positive entries of \(A\). A doubly stochastic matrix has at least \(n\) positive entries, since each of its \(n\) rows has sum \(1\) and therefore contains a positive entry.

Base case, \(s(A)=n\). Each row must contain at least one positive entry. Since there are \(n\) positive entries altogether, each row contains exactly one. Its row sum is \(1\), so that entry equals \(1\). Each column also has sum \(1\); because its entries are nonnegative, it must contain exactly one of these \(1\)s. Thus \(A\) is a permutation matrix, and it is a convex combination consisting of itself with coefficient \(1\). This also handles order \(n=1\).

Inductive step. Suppose \(s(A)>n\), and assume the theorem holds for every doubly stochastic matrix of order \(n\) with fewer than \(s(A)\) positive entries. By the lemma, choose a positive permutation diagonal. Let \(P\) be the permutation matrix that has a \(1\) in each position of this diagonal. Define \(\alpha\) to be the smallest entry of \(A\) among those selected positions. There are finitely many selected entries, and each is positive, so \(\alpha>0\). Set \(A'=A-\alpha P\).

At each selected position, the entry of \(A'\) is the corresponding entry of \(A\) minus \(\alpha\), and hence is nonnegative by the definition of the minimum. Every unselected entry is unchanged and nonnegative. Since \(P\) has exactly one \(1\) in each row and column, every row sum and every column sum of \(A'\) is \(1-\alpha\). In particular, \(0<\alpha\le 1\). If \(\alpha=1\), every selected entry of \(A\) is at least \(1\). Each row sums to \(1\) and has nonnegative entries, so its selected entry is exactly \(1\), with all other entries \(0\). Hence \(A=P\), which is already the required decomposition.

It remains to handle \(0<\alpha<1\). Define \(B=A'/(1-\alpha)\). The denominator is positive, so \(B\) is well-defined. Its entries are nonnegative, and every row and column sum is \((1-\alpha)/(1-\alpha)=1\); hence \(B\) is doubly stochastic. At least one selected entry of \(A\) equals \(\alpha\), so that entry becomes \(0\) in \(A'\). No zero entry of \(A\) becomes positive, since subtraction only affects the selected positions, which were positive, and all other entries are unchanged. Dividing by the positive number \(1-\alpha\) does not change which entries are positive. Therefore \(s(B)<s(A)\).

By the induction hypothesis, \(B=\sum_{r=1}^k\lambda_rP_r\), where the \(P_r\) are permutation matrices, the coefficients are nonnegative, and \(\sum_{r=1}^k\lambda_r=1\). Since \(A=\alpha P+(1-\alpha)B\), substitution gives

A=\alpha P+\sum_{r=1}^k(1-\alpha)\lambda_rP_r.

These are permutation matrices with nonnegative coefficients. The coefficients sum to \(\alpha+(1-\alpha)\sum_{r=1}^k\lambda_r=\alpha+(1-\alpha)=1\), so this is a convex combination. The proof covers all cases and completes the induction. \(\square\)

Following One Inductive Step

Worked Example: A Positive Diagonal and Its Subtraction

Consider

A= \begin{pmatrix} \frac12&\frac12&0\\ \frac14&\frac12&\frac14\\ \frac14&0&\frac34 \end{pmatrix}.

The row sums are \(\frac12+\frac12=1\), \(\frac14+\frac12+\frac14=1\), and \(\frac14+\frac34=1\). The column sums are \(\frac12+\frac14+\frac14=1\), \(\frac12+\frac12+0=1\), and \(0+\frac14+\frac34=1\). Thus \(A\) is doubly stochastic. Its support graph has row vertices \(\{r_1,r_2,r_3\}\), column vertices \(\{c_1,c_2,c_3\}\), and edge set \(\{r_1c_1,r_1c_2,r_2c_1,r_2c_2,r_2c_3,r_3c_1,r_3c_3\}\).

The main diagonal is positive, with entries \(a_{11}=\frac12\), \(a_{22}=\frac12\), and \(a_{33}=\frac34\). It corresponds to the identity permutation matrix \(P=I\). The selected minimum is \(\alpha=\min\{\frac12,\frac12,\frac34\}=\frac12\). Subtracting \(\frac12P\) gives

A-\frac12P= \begin{pmatrix} 0&\frac12&0\\ \frac14&0&\frac14\\ \frac14&0&\frac14 \end{pmatrix}.

Each row and column of this residual sums to \(\frac12\): its row sums are \(\frac12,\frac14+\frac14=\frac12,\frac14+\frac14=\frac12\), and its column sums are \(\frac14+\frac14=\frac12,\frac12,\frac14+\frac14=\frac12\). Normalize by dividing by \(1-\alpha=\frac12\):

B=\frac{A-\frac12P}{\frac12} = \begin{pmatrix} 0&1&0\\ \frac12&0&\frac12\\ \frac12&0&\frac12 \end{pmatrix}.

The normalized matrix has row sums \(1,1,1\) and column sums \(\frac12+\frac12=1,1,\frac12+\frac12=1\). The original matrix has \(7\) positive entries; \(B\) has \(5\). The count follows directly: the rows of \(A\) have \(2,3,2\) positive entries, while those of \(B\) have \(1,2,2\). Thus this step has strictly reduced the support, as the induction requires. Check: the entries of \(B\) in positions \((1,2),(2,1),(3,3)\) are \(1,\frac12,\frac12\), all positive, so \(B\) still has a positive permutation diagonal.

Worked Example: The Induction Base Case

Let \(A\) be the \(3\times3\) identity matrix, with vertex-free matrix entries specified by

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

Each row and each column sums to \(1\), and there are exactly \(3\) positive entries, one per row and column. Thus \(s(A)=3=n\). The base-case argument applies: \(A\) is itself a permutation matrix, so \(A=1\cdot A\) is a convex combination. Check: the sole coefficient is nonnegative and sums to \(1\); the matrix on the right is exactly \(A\). This example illustrates why the induction must stop when the support reaches \(n\), rather than attempting another subtraction step.

Why the Minimum Matters

The proof depends on subtracting an amount that keeps every entry nonnegative. The smallest entry on the chosen diagonal is the largest amount that can be subtracted uniformly from all its selected entries without making any of them negative. At least one selected entry then becomes zero, which is what guarantees strict progress in the support count. Normalization is needed because the residual row and column sums are \(1-\alpha\), not \(1\).

Worked Example: A Subtraction That Fails

Use the matrix from the previous example and its positive main diagonal \(\frac12,\frac12,\frac34\). Subtracting \(\frac34 I\), the largest selected entry rather than the smallest, gives an entry in position \((1,1)\) equal to \(\frac12-\frac34=-\frac14\). The result is not nonnegative and therefore cannot be used as the residual in this proof.

The correct amount is \(\alpha=\min\{\frac12,\frac12,\frac34\}=\frac12\). Subtracting \(\frac12 I\) gives diagonal residual entries \(0,0,\frac34-\frac12=\frac14\), each nonnegative; the off-diagonal entries remain unchanged. Check: the residual row sums are \(\frac12,\frac12,\frac12\), as computed in the preceding example, so division by \(\frac12\) produces a doubly stochastic matrix.

A related mistake is to call the residual itself doubly stochastic. Before normalization its row and column sums are \(1-\alpha\), so it is not doubly stochastic when \(0<\alpha<1\). Dividing by \(1-\alpha\) makes the induction hypothesis applicable, while the factor \(1-\alpha\) in \(A=\alpha P+(1-\alpha)B\) restores the original scale.

The support-count induction is useful because it does not require a bound in advance on how many subtraction steps will be needed. Each step strictly decreases a nonnegative integer, and every doubly stochastic matrix has at least \(n\) positive entries. Thus the process must reach the base case or the endpoint \(\alpha=1\). The theorem is an existence result: it guarantees a convex decomposition, while the choice of positive diagonal at each stage may not be unique.

Check Your Understanding

Use the support-graph lemma and the induction proof to answer these questions.

Why does the total mass in the rows indexed by \(X\) imply \(|N(X)|\ge |X|\)? Identify where nonnegativity is used.
If a doubly stochastic matrix has exactly \(n\) positive entries, explain why it must be a permutation matrix.
Why does subtracting the minimum selected entry make at least one positive entry zero?
When \(0<\alpha<1\), what are the row and column sums of \(A-\alpha P\), and why is division by \(1-\alpha\) valid?
In the subtraction example, what negative entry results from subtracting \(\frac34 I\), and what amount should be subtracted instead?