Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

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

3 Answers 3

up vote 25 down vote accepted

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.

share|improve this answer
2  
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 at 18:48
1  
So van der Waerden's conjecture is an elaborate generalization of Hall's marriage theorem. Nice! –  darij grinberg Mar 3 at 18:58
14  
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 at 22:19
2  
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 at 22:09
2  
@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 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$.

share|improve this answer
    
@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 at 0:32
    
Nice! Sorry, I did not know that. You should restore the non-negativity condition though. –  Tony Huynh Mar 4 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.

share|improve this answer
    
Oh, let me clarify my question a bit.. –  Per Alexandersson Mar 3 at 18:42

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.