The Birkhoff–von Neumann Theorem

Doubly Stochastic Matrices as Weighted Averages

A permutation chooses one column for each row, using every column exactly once. Its matrix records those choices with one \(1\) in each row and column and \(0\)s elsewhere. The Birkhoff–von Neumann theorem says that every matrix of nonnegative entries whose row and column sums are all \(1\) can be expressed as a weighted average of such matrices. Thus a matrix that may have many fractional entries can be understood as a combination of whole permutations.

This tutorial focuses on the statement and interpretation of the theorem. We verify proposed decompositions directly in small cases. The theorem's converse—that every matrix satisfying the conditions has such a decomposition—is a standard result whose proof comes later in the course.

Definition: A real \(n\times n\) matrix \(A=(a_{ij})\) is doubly stochastic if \(a_{ij}\ge 0\) for every \(i,j\), every row sum is \(1\), and every column sum is \(1\). In symbols, \(\sum_{j=1}^n a_{ij}=1\) for each row \(i\), and \(\sum_{i=1}^n a_{ij}=1\) for each column \(j\).

In particular, each entry of a doubly stochastic matrix lies between \(0\) and \(1\): it is nonnegative, and it cannot exceed the sum \(1\) of the row containing it. The total sum of all entries is \(n\), since adding the \(n\) row sums gives \(n\). These are necessary checks, but the definition requires each individual row and column to sum to \(1\), not just the total.

Definition: Given a permutation \(\sigma\) of \(\{1,\ldots,n\}\), its permutation matrix \(P_\sigma\) is the \(n\times n\) matrix whose entry in row \(i\), column \(j\) is \(1\) if \(j=\sigma(i)\), and \(0\) otherwise. A convex combination of matrices \(P_{\sigma_1},\ldots,P_{\sigma_r}\) is a matrix \(\sum_{k=1}^r \lambda_kP_{\sigma_k}\), where \(\lambda_k\ge 0\) for each \(k\) and \(\sum_{k=1}^r\lambda_k=1\).

The convention for a permutation matrix means that the \(1\) in row \(i\) marks the column chosen by row \(i\). Because a permutation uses every column exactly once, each permutation matrix has exactly one \(1\) in every row and every column. In a convex combination, the coefficients are shared across the entire matrices: \(\lambda_k\) multiplies every entry of \(P_{\sigma_k}\).

The Theorem and What Its Coefficients Mean

Theorem (Birkhoff–von Neumann): For every positive integer \(n\), every doubly stochastic \(n\times n\) matrix \(A\) is a convex combination of permutation matrices. That is, there are a positive integer \(r\), permutations \(\sigma_1,\ldots,\sigma_r\) of \(\{1,\ldots,n\}\), and coefficients \(\lambda_1,\ldots,\lambda_r\ge 0\) with \(\sum_{k=1}^r\lambda_k=1\) such that \(A=\sum_{k=1}^r\lambda_kP_{\sigma_k}\). Conversely, every such convex combination is doubly stochastic.

The converse follows directly from the definitions; the existence of a convex combination for every doubly stochastic matrix is the substantive direction. The theorem is being stated here as a standard result, with its proof given later in the course. Keeping the two directions distinct is useful: checking a proposed combination verifies that it gives a doubly stochastic matrix, while the theorem guarantees that a suitable combination exists for any doubly stochastic matrix.

Entry by entry, the equation \(A=\sum_{k=1}^r\lambda_kP_{\sigma_k}\) says

a_{ij}=\sum_{\substack{1\le k\le r\\ \sigma_k(i)=j}}\lambda_k.

So \(a_{ij}\) is the total weight of the permutations in which row \(i\) is assigned to column \(j\). A coefficient does not generally equal one particular entry: each entry collects the weights of all permutations that make the corresponding assignment.

There is also a probability interpretation. Choose permutation \(\sigma_k\) with probability \(\lambda_k\). Then the probability that row \(i\) is assigned to column \(j\) is \(a_{ij}\). Indeed, the event consists exactly of the choices of \(k\) for which \(\sigma_k(i)=j\), and their probabilities add to the displayed sum. This interpretation allows coefficients equal to \(0\); such a permutation is never selected and can be omitted. The theorem does not say that the coefficients are unique.

Why the converse holds. Every permutation matrix has nonnegative entries, and each of its rows and columns sums to \(1\). A weighted average with nonnegative weights summing to \(1\) preserves nonnegativity and these row and column sums.

Proof. Let \(A=\sum_{k=1}^r\lambda_kP_{\sigma_k}\), where every \(\lambda_k\ge 0\) and \(\sum_{k=1}^r\lambda_k=1\). Each entry of each \(P_{\sigma_k}\) is either \(0\) or \(1\), so every entry of \(A\) is a sum of nonnegative terms and is nonnegative. Fix row \(i\). Since row \(i\) of each \(P_{\sigma_k}\) sums to \(1\), row \(i\) of \(A\) sums to \(\sum_{k=1}^r\lambda_k\cdot 1=1\). Fixing a column instead gives the same calculation, because every column of every permutation matrix sums to \(1\). Thus \(A\) is doubly stochastic. \(\square\)

Worked Decompositions

Worked Example: A Two-by-Two Matrix

Consider the matrix

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

The two permutations of \(\{1,2\}\) give the identity matrix \(I\) and the matrix \(S\) that swaps the two columns:

I=\begin{pmatrix}1&0\\0&1\end{pmatrix}, \qquad S=\begin{pmatrix}0&1\\1&0\end{pmatrix}.

Use weights \(\frac34\) and \(\frac14\), which are nonnegative and sum to \(\frac34+\frac14=1\). Multiplying each matrix by its weight and adding gives

\frac34 I+\frac14 S = \begin{pmatrix}\frac34&0\\0&\frac34\end{pmatrix} + \begin{pmatrix}0&\frac14\\\frac14&0\end{pmatrix} = \begin{pmatrix}\frac34&\frac14\\\frac14&\frac34\end{pmatrix} =A.

Check: each row sum is \(\frac34+\frac14=1\), and each column sum is \(\frac34+\frac14=1\). The probability interpretation says that the identity permutation is chosen with probability \(\frac34\), so row \(1\) is assigned to column \(1\) with probability \(\frac34\); the swap is chosen with probability \(\frac14\), so row \(1\) is assigned to column \(2\) with probability \(\frac14\). These are exactly the entries in the first row.

Worked Example: Three Permutations with Different Weights

Let \(I\) be the \(3\times3\) identity matrix. Let \(C\) represent the permutation \(1\mapsto2,\ 2\mapsto3,\ 3\mapsto1\), and let \(D\) represent \(1\mapsto3,\ 2\mapsto1,\ 3\mapsto2\). Their matrices are

I=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix},\quad C=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix},\quad D=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}.

Take weights \(\frac12,\frac13,\frac16\). They are nonnegative, and \(\frac12+\frac13+\frac16=\frac36+\frac26+\frac16=\frac96=1\). The weighted matrices are

\frac12 I=\begin{pmatrix}\frac12&0&0\\0&\frac12&0\\0&0&\frac12\end{pmatrix},\quad \frac13 C=\begin{pmatrix}0&\frac13&0\\0&0&\frac13\\\frac13&0&0\end{pmatrix},\quad \frac16 D=\begin{pmatrix}0&0&\frac16\\\frac16&0&0\\0&\frac16&0\end{pmatrix}.

Adding corresponding entries gives

A=\frac12I+\frac13C+\frac16D =\begin{pmatrix} \frac12&\frac13&\frac16\\ \frac16&\frac12&\frac13\\ \frac13&\frac16&\frac12 \end{pmatrix}.

Check: the row sums are \(\frac12+\frac13+\frac16=1\), \(\frac16+\frac12+\frac13=1\), and \(\frac13+\frac16+\frac12=1\). The column sums are \(\frac12+\frac16+\frac13=1\), \(\frac13+\frac12+\frac16=1\), and \(\frac16+\frac13+\frac12=1\). As a second check, each entry records the weight of the one listed permutation using that position: for instance, position \((2,1)\) occurs in \(D\), with weight \(\frac16\), and \(a_{21}=\frac16\).

Worked Example: One Matrix, Different Representations

Consider the \(3\times3\) matrix \(J\) with every entry equal to \(\frac13\). One representation uses the three matrices \(I,C,D\) just displayed:

J=\frac13 I+\frac13 C+\frac13 D =\begin{pmatrix} \frac13&\frac13&\frac13\\ \frac13&\frac13&\frac13\\ \frac13&\frac13&\frac13 \end{pmatrix}.

For a second representation, let \(T\) be the permutation \(1\mapsto2,\ 2\mapsto1,\ 3\mapsto3\); let \(U\) be \(1\mapsto3,\ 2\mapsto2,\ 3\mapsto1\); and let \(W\) be \(1\mapsto1,\ 2\mapsto3,\ 3\mapsto2\). Their matrices are

T=\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix},\quad U=\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix},\quad W=\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}.

Each position occurs in exactly one of \(T,U,W\): their first rows place the \(1\) in columns \(2,3,1\), respectively; their second rows place it in columns \(1,2,3\); and their third rows place it in columns \(3,1,2\). Thus adding their entries and dividing by \(3\) gives \(\frac13T+\frac13U+\frac13W=J\). In both representations the coefficients are nonnegative and sum to \(\frac13+\frac13+\frac13=1\).

Check: each row and column of \(J\) sums to \(\frac13+\frac13+\frac13=1\). The representations use different permutations, so a doubly stochastic matrix need not have a unique expression as a convex combination.

Support and the Meaning of Existence

The support of a nonnegative matrix is the set of positions \((i,j)\) where its entry is positive. A permutation matrix supported on the positive entries of \(A\) is one whose \(1\)s all occur at positions where \(a_{ij}>0\). In assignment language, it selects one positive position in every row and every column. Such a selection is often called a positive diagonal, even when its positions are not on the ordinary top-left to bottom-right diagonal.

If \(A=\sum_k\lambda_kP_{\sigma_k}\) and \(\lambda_k>0\), every \(1\) in \(P_{\sigma_k}\) must lie in the support of \(A\). Indeed, the entry of \(A\) at that position includes the positive summand \(\lambda_k\), and all other summands are nonnegative. Consequently, the theorem provides a way to view the entries as accumulated contributions from permutations allowed by the support. It does not assert that every positive position must occur in every permutation in a decomposition.

This distinction is useful in applications. A row might represent a person and a column a task; a permutation matrix describes a complete one-to-one assignment. A doubly stochastic matrix can then be read as assignment probabilities, with each row and column having total probability \(1\). The theorem says that these marginal probabilities can be realized by randomly choosing among complete assignments, rather than assigning each row independently.

Common Pitfall: Confusing Weights with Entries

For the two-by-two matrix in the first example, a tempting but incorrect claim is that it is \(\frac12 I+\frac12 S\), because there are two permutation matrices and two rows. Direct calculation gives

\frac12 I+\frac12 S = \begin{pmatrix}\frac12&0\\0&\frac12\end{pmatrix} + \begin{pmatrix}0&\frac12\\\frac12&0\end{pmatrix} = \begin{pmatrix}\frac12&\frac12\\\frac12&\frac12\end{pmatrix},

which is not the target matrix with diagonal entries \(\frac34\). The correct weights are \(\frac34\) for \(I\) and \(\frac14\) for \(S\). The coefficients are probabilities assigned to entire permutations; they are not automatically equal, and one coefficient is not copied into every entry of the matrix.

When checking any proposed decomposition, verify three separate facts: the matrices are permutation matrices, the coefficients are nonnegative and sum to \(1\), and the weighted sum equals the target in every position. If the target is claimed to be doubly stochastic, also check its row and column sums directly.

Check Your Understanding

Use the definitions and entry-by-entry interpretation to answer these questions.

What conditions must an \(n\times n\) matrix satisfy to be doubly stochastic?
For a convex combination of permutation matrices, what does the entry in row \(i\), column \(j\) represent?
Why does every convex combination of permutation matrices have row sums and column sums equal to \(1\)?
In the first worked example, what matrix results from using weights \(\frac12\) and \(\frac12\) instead of \(\frac34\) and \(\frac14\)?
Does the theorem assert that the coefficients in a decomposition are unique? Explain using the uniform \(3\times3\) example.