# 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?

• The title sounds a bit misleading... – Felix Goldberg Mar 3 '14 at 18:38
• @FelixGoldberg: Ok fixed. – Per Alexandersson Mar 3 '14 at 18:41
• I took the liberty of adding a tag. Hope u don't mind. – Felix Goldberg Mar 3 '14 at 18:43
• "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

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.

• Moreover this argument gives a (very bad, but very elementary) lower bound on the permanent: there are at most $n!$ terms in the sum describing a doubly stochastic matrix as a convex combination of permutation matrices, so at least one such term has coefficient at least $\frac{1}{n!}$, and hence there is a contribution to the permanent of size at least $\frac{1}{(n!)^n}$. (This is addressing the "lower bound... converges to $0$... so it must be nontrivial" part of the OP.) – Qiaochu Yuan Mar 3 '14 at 18:48
• So van der Waerden's conjecture is an elaborate generalization of Hall's marriage theorem. Nice! – darij grinberg Mar 3 '14 at 18:58
• Any $n\times n$ doubly stochastic matrix is a positive linear combination of no more than $n^2-2n+2$ permutation matrices. – Gerry Myerson Mar 3 '14 at 22:19
• See my paper with David Leep, Marriage, Magic, and Solitaire, Amer Math Monthly, Vol. 106, No. 5, May, 1999, pages 419-429 (but especially page 423), or the paper we cribbed it from, Marcus and Ree, Diagonals of doubly stochastic matrices, Quart J Math 10 (1959) 295-302. – Gerry Myerson Mar 4 '14 at 22:09
• @AnthonyQuas: The $n^2-2n+2$ follows immediately from Carathéodory's theorem (if $X$ is a subset of an $m$-dimensional linear variety in $R^d$, then any point in the convex hull of $X$ can be expressed as a convex combination of at most $d+1$ points of $X$). I guess it is the "positive" part that sets apart Gerry's statement. – Suvrit Mar 11 '14 at 15:28

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$.

• @Tony: the 0,1 condition is not needed, so I removed it. Please see, e.g., Thm. 2.2 here: books.google.com/… – Suvrit Mar 4 '14 at 0:32
• Nice! Sorry, I did not know that. You should restore the non-negativity condition though. – Tony Huynh Mar 4 '14 at 0:38

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.

• Oh, let me clarify my question a bit.. – Per Alexandersson Mar 3 '14 at 18:42