Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$. We want to find $n$ entries of the array $(x_1,y_1), \dots, (x_n,y_n)$ such that
How can we prove that such a set of entries always exists?
Here is an example solution with a $3\times3$ table.
The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result.
If you don't want to assume this theorem, you can use Hall's theorem directly. Given your table $A$, define a bipartite graph by having $n$ row-vertices, $n$ column-vertices, and connecting row $i$ and column $j$ if the $(i,j)$th entry is non-zero. Your goal is to find a perfect matching in the graph.
According to Hall's theorem, the graph contains a perfect matching if for all subsets $S$ of row vertices, the number of neighbors of $S$ is at least $|S|$. That is, given a set $S$ of rows, we need to show that the set $$T = \{ j : A_{ij} \neq 0 \text{ for some $i \in S$}\}$$ contains at least $|S|$ columns. Indeed, the sum of the entries in the rows in $S$ is exactly $|S|$, and the sum of the entries in the columns in $T$ is exactly $|T|$. Therefore the sum of entries in $S \times T$ is at most $|T|$. However, by definition this sum must equal $|S|$ (since all other entries in the rows in $S$ are zero), and so $|S| \leq |T|$, which is what we wanted.
This argument shows that you can use standard algorithms for finding maximum matchings in bipartite graphs to actually find your $n$ entries.
We are now at an excellent position to prove the Birkhoff–von Neumann theorem. The proof is by induction on the number of non-zero entries. The argument above shows that there are at least $n$ non-zero entries, and in that case it's not hard to see that the matrix must be a permutation matrix, completing the base case.
Now consider an arbitrary doubly stochastic $A$ with more than $n$ non-zero entries, and find a matching $(i,\pi(i))$ in $A$. This matching corresponds to sum permutation matrix $P$. Define $\alpha = \min_i A(i,\pi(i)) > 0$. The matrix $B = \frac{A - \alpha P}{1 - \alpha}$ is also doubly stochastic (since subtracting $\alpha P$ removes exactly $\alpha$ from each row and column), with at least one more zero entry. By induction, $B$ is a convex combination $\sum_t \beta_t P_t$ of permutation matrices. Hence so is $A$: $$A = \alpha P + (1-\alpha) \sum_t \beta_t P_t.$$
The Birkhoff–von Neumann theorem can be stated in many different ways. It states that the set of doubly stochastic matrices is the convex hull of the permutation matrices. It also states (with some more work) that the vertices in the polytope of doubly stochastic matrices are the permutation matrices.
As @YuvalFilmus says, this can be considered as the problem of finding a complete matching on a bipartite graph. The algorithm to do this is due to Hopcroft and Karp. Reference is Hopcroft and Karp, "An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs", SIAM Journal of Computing 2:4 (1973), pp. 225–231. DOI https://dx.doi.org/10.1137%2F0202019
