2
$\begingroup$

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

  • each $A[x_i,y_i]>0$ and
  • no pair $(x_i,y_i),(x_j,y_j)$ are in the same row or column (i.e., $i\neq j$ implies that $x_i\neq x_j$ or $y_i\neq y_j$ or both).

How can we prove that such a set of entries always exists?

Here is an example solution with a $3\times3$ table.

enter image description here

$\endgroup$
  • $\begingroup$ 1. I encourage you to edit the question to clarify it, based on the comments here, and to clarify what set the table elements come from (natural numbers? real numbers?). 2. I don't see how this is a question about computer science. This looks like a question about pure math. This is a site for questions about computer science. (While we don't have an absolute prohibition on pure math questions, we expect the question to explain why it needs to be answered from a CS perspective, and that doesn't seem applicable here.) Would you like to see this migrated to Math.SE, once it's edited? $\endgroup$ – D.W. Dec 31 '15 at 4:08
  • 1
    $\begingroup$ @D.W. I've clarified the question based on the comments. I've voted to reopen, since the close reason has been dealt with but I agree that math.se seems more appropriate. $\endgroup$ – David Richerby Dec 31 '15 at 10:45
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.