Silly me & Van der Waerden conjecture 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?
 A: 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.
A: Let me cite here a famous result that is equivalent to Hall's theorem, and from which the positivity of the permanent of a DS matrix follows.

Theorem (Frobenius-König). The permanent of an $n\times n$ nonnegative matrix $A$ is zero if and only if $A$ has an $r\times s$ zero submatrix with $r+s=n+1$.

From this theorem a brief argument shows that for a DS matrix $A$, we must have $\text{per}\ A > 0$.
A: The ($n \times n$) matrix represents a bipartite graph (with $2n$ vertices) which is basically its zero-nonzero pattern. If you can show the graph has a perfect matching (by Hall's theorem or some other way) you're done.
