proof of Birkhoff-von Neumann theorem
First, we prove the following lemma:
A convex combination of doubly stochastic matrices is doubly stochastic. Proof:
Let be a collection of doubly-stochastic matrices, and suppose is a collection of scalars satisfying and for each . We claim that is doubly stochastic.
Take any . Since is doubly stochastic, each of its rows and columns sum to 1. Thus each of the rows and columns of sum to .
By the definition of elementwise summation, given matrices , the sum of the entries in the th column of is clearly the sum of the sums of entries of the th columns of and respectively. A similar result holds for the th row.
Hence the sum of the entries in the th column of is the sum of the sums of entries of the th columns of for each , that is, . The sum of entries of the th row of is the same. Hence is doubly stochastic.
Observe that since a permutation matrix has a single nonzero entry, equal to 1, in each row and column, so the sum of entries in any row or column must be 1. So a permutation matrix is doubly stochastic, and on applying the lemma, we see that a convex combination of permutation matrices is doubly stochastic. This provides one direction of our proof; we now prove the more difficult direction: suppose is doubly-stochastic. Define a weighted graph with vertex set , edge set , where if , and edge weight , where . Clearly is a bipartite graph, with partitions and , since the only edges in are between and for some . Furthermore, since , then for every . For any define , the neighbourhood of , to be the set of vertices such that there is some such that . We claim that, for any , . Take any ; either or . Since is bipartite, implies , and implies . Now,
since is doubly stochastic. Now, take any . We have
Let . But then clearly , by definition of neighbourhood. So
Note that implies : if , then
, so , which implies .
Further, we claim that is a permutation matrix:
Let be any row of . Since is a perfect matching of , there exists such that is an end of . Let the other end be for some ; then .
Suppose with and for some . This implies , but this implies the vertex is the end of two distinct edges, which contradicts the fact that is a matching.
Hence, for each row and column of , there is exactly one nonzero entry, whose value is 1. So is a permutation matrix. Define . We see that since , and . Further, for some . Let . If , then and is a permutation matrix, so we are done. Otherwise, note that is nonnegative; this is clear since for any . Notice that . Note that since every row and column of and sums to 1, that every row and column of sums to . Define . Then every row and column of sums to 1, so is doubly stochastic. Rearranging, we have . Clearly implies that which implies that , so the zero entries of are a superset of those of . But notice that , so the zero entries of are a strict superset of those of . We have decomposed into a convex combination of a permutation matrix and another doubly stochastic matrix with strictly more zero entries than . Thus we may apply this procedure repeatedly on the doubly stochastic matrix obtained from the previous step, and the number of zero entries will increase with each step. Since has at most nonzero entries, we will obtain a convex combination of permutation matrices in at most steps. Thus is indeed expressible as a convex combination of permutation matrices.
G. Birkhoff, “Tres observaciones sobre el algebra lineal,” Univ. Nac. Tucumán Rev, Ser. A, no. 5, pp147–151. (1946)
|Title||proof of Birkhoff-von Neumann theorem|
|Date of creation||2013-03-22 13:10:03|
|Last modified on||2013-03-22 13:10:03|
|Owner||Andrea Ambrosio (7332)|
|Last modified by||Andrea Ambrosio (7332)|
|Author||Andrea Ambrosio (7332)|