PlanetMath: proof of Birkhoff-von Neumann theorem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

proof of Birkhoff-von Neumann theorem

(Proof)

First, we prove the following lemma:
Lemma:
A convex combination of doubly stochastic matrices is doubly stochastic.

Proof:
Let $\{A_i\}_{i=1}^m$ be a collection of $n \times n$ doubly-stochastic matrices, and suppose $\{\lambda_i\}_{i=1}^m$ is a collection of scalars satisfying $\sum_{i=1}^m \lambda_i=1$ and $\lambda_i \geq 0$ for each $i=1,\ldots,m$ . We claim that $A=\sum_{i=1}^m \lambda_iA_i$ is doubly stochastic.
Take any $i \in \{1,\ldots,m\}$ . Since is doubly stochastic, each of its rows and columns sum to 1. Thus each of the rows and columns of $\lambda_iA_i$ sum to $\lambda_i$ .
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 $\lambda_kA_k$ for each , that is, $\sum_{k=1}^m \lambda_k=1$ . 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 $V=\{r_1,\ldots,r_n,c_1,\ldots,c_n\}$ , edge set , where $e_{ij}=(r_i,c_i) \in E$ if $B_{ij} \neq 0$ , and edge weight $\omega$ , where $\omega(e_{ij})=B_{ij}$ .

Clearly is a bipartite graph, with partitions $R=\{r_1,\ldots,r_n\}$ and $C=\{c_1,\ldots,c_n\}$ , since the only edges in are between and for some $i,j \in \{1,\ldots,n\}$ . Furthermore, since $B_{ij} \geq 0$ , then $\omega(e)>0$ for every $e \in E$ .

For any $A \subset V$ define , the neighbourhood of , to be the set of vertices $u \in V$ such that there is some $v \in A$ such that $(u,v) \in E$ .

We claim that, for any $v \in V$ , $\sum_{u \in N(\{v\})} \omega(u,v)=1$ . Take any $v \in V$ ; either $v \in R$ or $v \in C$ . Since is bipartite, $v \in R$ implies $N(\{v\}) \subset C$ , and $v \in C$ implies $N(\{v\}) \subset R$ . Now,

$\displaystyle \begin{array}{c} {\displaystyle v=r_i \implies \sum_{u \in N(r_i)... ...{\stackrel{i=1,}{B_{ij} \neq 0}}^n B_{ij}= \sum_{i=1}^n B_{ij}=1 } \end{array}$

since

is doubly stochastic. Now, take any $A \subset R$ . We have

$\displaystyle \sum_{\stackrel{v \in A}{w \in N(A)}} \omega(v,w) = \sum_{v \in A} \sum_{w \in N(\{v\})} \omega(v,w) = \sum_{v \in A} 1 = \vert A\vert$

Let

. But then clearly $A \subset N(B)$ , by definition of neighbourhood. So

$\displaystyle \vert N(A)\vert=\vert B\vert = \sum_{\stackrel{v \in B}{w \in N(B... ...\omega(v,w) = \sum_{\stackrel{w \in A}{v \in N(A)}} \omega(v,w) = \vert A\vert$

So $\vert N(A)\vert \geq \vert A\vert$ . We may therefore apply the graph-theoretic version of Hall's marriage theorem to

to conclude that

has a perfect matching.

So let $M \subset E$ be a perfect matching for . Define an $n \times n$ matrix by

$\displaystyle P_{ij} = \left\{ \begin{array}{ll} 1 & \text{if } e_{ij} \in M \\ 0 & \text{otherwise} \end{array} \right.$

Note that $B_{ij}=0$ implies $P_{ij}=0$ : if $B_{ij}=0$ , then $(r_i,c_j) \not \in E$ , so $(r_i,c_j) \not \in M$ , which implies $P_{ij}=0$ .

Further, we claim that is a permutation matrix:
Let be any row of . Since is a perfect matching of , there exists $e_0 \in M$ such that is an end of . Let the other end be for some ; then $P_{ij}=1$ .
Suppose $i_i,i_2 \in \{1,\ldots,n\}$ with $i_1 \neq i_2$ and $P_{i_1,j}=P_{i_2,j}=1$ for some . This implies $(r_{i_1},c_j),(r_{i_2},c_j) \in M$ , 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 $\displaystyle{\lambda=\min_{i,j \in \{1,\ldots,n\}} \{ B_{ij} \mid P_{ij} \neq 0\}}$ . We see that $\lambda>0$ since $B_{ij} \geq 0$ , and $P_{ij} \neq 0 \implies B_{ij} \neq 0$ . Further, $\lambda=B_{pq}$ for some .

Let $D=B-\lambda P$ . If , then $\lambda=1$ and is a permutation matrix, so we are done. Otherwise, note that is nonnegative; this is clear since $\lambda P_{ij} \leq \lambda \leq B_{ij}$ for any $B_{ij} \neq 0$ .

Notice that $D_{pq}=B_{pq}-\lambda P_{pq} = \lambda - \lambda \cdot 1 = 0$ .

Note that since every row and column of and sums to 1, that every row and column of $D=B-\lambda P$ sums to $1-\lambda$ . Define $B'=\frac{1}{1-\lambda}D$ . Then every row and column of sums to 1, so is doubly stochastic.

Rearranging, we have $B=\lambda P + (1-\lambda) B'$ . Clearly $B_{ij}=0$ implies that $P_{ij}=0$ which implies that $B'_{ij}=0$ , so the zero entries of are a superset of those of . But notice that $B'_{pq}=\frac{1}{1-\lambda} D_{pq}=0$ , 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.