Or put it simply, for any $n$-by-$n$ doubly stochastic matrix $A$, you can always find $n$ non-zero entries in $A$, none of them lies in the same row or column. Why is that?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
According to the Birkhoff-von Neumann theorem the set of doubly stochastic $(n\times n)$ matrices is the convex hull of the set of $(n\times n)$ permutation matrices. For a simple proof see here (there are many proofs in the literature): http://mingus.la.asu.edu/~hurlbert/papers/SPBVNT.pdf Given that, for any doubly stochastic $(n\times n)$ matrix $D$ by Caratheodory's theorem there are $<n^2$ permutation matrices $P^{(\ell)}$ and numbers $\lambda_\ell>0$ summing to $1$ such that $$D=\sum_\ell\lambda_\ell P^{(\ell)}\ .$$ It follows that $d_{ik}>0$ whenever $P_{ik}^{(1)}>0$, and the latter happens exactly once in each row and each column. |
|||
|
|
