Tiny VoltBirkhoff-von-Neumann algorithm
The Birkhoff-von Neumann theorem states that every doubly stochastic matrix can be written as a convex sum of permutation matrices. Here we look at the algorithm to find such a convex sum. The idea is focused on the number of zeros in the matrix.
0. Zeros in a doubly stochastic matrix
We start with a few observations:
- Each permutation matrix has exactly one non-zero entry in each row and each column.
- Number of zeros in a doubly stochastic matrix is maximum when it is a permutation matrix. In other words, a
n-by-ndoubly stochastic matrix cannot have fewer thannnon-zero entries, which happens when the matrix is a permutation matrix.
The six permutation matrices of a length-3 vector sit at the vertices of a hexagon, the Birkhoff polytope for . Of these, are the even permutations, singled out in teal, and they form a triangle inscribed in the hexagon.
An amber point starts at , and a on the right always shows exactly the matrix the point currently represents, initially itself, a pure permutation matrix with 6 zeros.
Each vertex is labeled, and moving along an edge sweeps out exactly , the convex combination of that edge's two endpoint permutation matrices.
Watch the as the point moves along the triangle: 6 zeros at a vertex, a pure permutation matrix, dropping to only 3 zeros along the interior of an edge.
If we interpolate along the edge , the amber point slides across the polytope and the matrix on the right morphs continuously from to . Away from the two endpoints it is no longer a permutation matrix at all, and the number of zeros drops from 6 down to 3.
Continuing, interpolating retraces the same pattern along the second edge of the triangle: 6 zeros at , dropping to 3 in the interior, climbing back toward 6 as the point approaches .
Finally, closing the triangle completes the loop. Along every edge of the Birkhoff polytope the story repeats: the number of zeros in the resulting matrix stays high (6) exactly at the vertices, the permutation matrices, and drops to 3 along the interior of an edge.
This forms the basis for the Birkhoff-von Neumann theorem, which states that every doubly stochastic matrix can be written as a convex sum of permutation matrices. The idea is to increase the number of zeros in the matrix gradually. We use induction on the number of zeros in the matrix to prove it while also generating a convex sum.
0.1. Outline of the proof
We begin with the following observation: in any doubly stochastic matrix of size n x n, one can always pick n non-zero entries such that each row and each column contains exactly one of these entries. Another way to say it is:
For any doubly stochastic matrix
D, there exists a permutation matrixPsuch that .
An example is shown below (taken from Wikipedia). The three boxed non-zero values correspond to the permutation matrix shown to their right:
The proof of it comes from Hall's Marriage Theorem. One can create a bipartite graph where the rows form one set of vertices and the columns form the other set of vertices. An edge exists between a row and a column if the corresponding entry in the matrix is non-zero. It can be shown that there exists a perfect matching in this graph for a doubly stochastic matrix.
0.2. Example
The algorithm finds a matching that includes the smallest element of the matrix and its corresponding permutation matrix. Subtracting the permutation matrix scaled by the smallest element results in a new matrix with at least one more zero than the original matrix. This new matrix also has the same row and column sums, and is therefore a scaled doubly stochastic matrix. An example of this procedure for the above matrix is shown below:
Thus, we were able to express a doubly stochastic matrix as a sum of another (scaled) doubly stochastic matrix and a (scaled) permutation matrix. Using induction, we can show that continuing this process will eventually yield a convex sum of permutation matrices (how can you use induction to show that the sum of coefficients is 1?).
Now we look into how to convert (almost) any non-negative square matrix into a doubly stochastic matrix. This is where the Sinkhorn-Knopp algorithm comes into play.