18
$\begingroup$

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?

$\endgroup$
4
  • 5
    $\begingroup$ The title sounds a bit misleading... $\endgroup$ Mar 3, 2014 at 18:38
  • $\begingroup$ @FelixGoldberg: Ok fixed. $\endgroup$ Mar 3, 2014 at 18:41
  • 1
    $\begingroup$ I took the liberty of adding a tag. Hope u don't mind. $\endgroup$ Mar 3, 2014 at 18:43
  • 4
    $\begingroup$ "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... $\endgroup$
    – Adam Davis
    Mar 4, 2014 at 18:28

3 Answers 3

28
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ 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.) $\endgroup$ Mar 3, 2014 at 18:48
  • 1
    $\begingroup$ So van der Waerden's conjecture is an elaborate generalization of Hall's marriage theorem. Nice! $\endgroup$ Mar 3, 2014 at 18:58
  • 15
    $\begingroup$ Any $n\times n$ doubly stochastic matrix is a positive linear combination of no more than $n^2-2n+2$ permutation matrices. $\endgroup$ Mar 3, 2014 at 22:19
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 4, 2014 at 22:09
  • 4
    $\begingroup$ @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. $\endgroup$
    – Suvrit
    Mar 11, 2014 at 15:28
17
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @Tony: the 0,1 condition is not needed, so I removed it. Please see, e.g., Thm. 2.2 here: books.google.com/… $\endgroup$
    – Suvrit
    Mar 4, 2014 at 0:32
  • $\begingroup$ Nice! Sorry, I did not know that. You should restore the non-negativity condition though. $\endgroup$
    – Tony Huynh
    Mar 4, 2014 at 0:38
  • $\begingroup$ In fact, when Van der Waerden originally posed his question, he noted that the positivity follows from König's theorem. $\endgroup$ Nov 17, 2019 at 19:48
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh, let me clarify my question a bit.. $\endgroup$ Mar 3, 2014 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.