Take the 2-minute tour ×
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.

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?

share|improve this question
    
I 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". –  coffeemath Oct 16 '12 at 23:58
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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