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?
Why for any doubly stochastic matrix, there exist a permutation $\pi$, such that $A_{[i,\pi(i)]}\ne 0$?
3
$\begingroup$
matrices
-
0I had an "answer" to this that some criticized; I'm going to remove it. Basically I did some gyrations on A to get it into the format with a 1 at upper left, such that the result is still doubly stochastic. But this has no bearing on the question, since there is no relation between the choices of nonzero entries of the original A and where nonzero entries might be in the "gyrated A". – 2012-10-16