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?

"So I walked into this very innocent-looking combinatorics problem"Sure, sure, that's what they all say buddy. Now face forward towards the camera, please... – Adam Davis Mar 4 '14 at 18:28