So I walked into this very innocent-looking combinatorics problem,
and quite soon I ended up with the problem to prove that any doubly stochastic $n \times n$ matrix has a non-zero permanent.
Now clearly, this follows from the Van der Waerden conjecture (which is now a theorem), which give a lower (positive) bound for the permanent..
However, in my case, it feels like overkill to reference this theorem, so I wonder if there is some elementary argument that shows that the permanent of a doubly stochastic matrix is positive. (Although, the lower bound mentioned above converges to 0, as the matrix size grows, so it must be non-trivial…).
Or, is proving that the permanent is non-zero "as hard as" proving the lower bound?
Best Answer
It's known (again using Hall's theorem, or using convex analysis) that the doubly stochastic matrices are a convex combination of the permutation matrices (these are the extreme points of the collection of doubly stochastic matrices). Accordingly each doubly stochastic matrix is a finite positive linear combination of permutation matrices. Then that the permanent is non-zero is immediate.