17
$\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 '14 at 18:38
  • $\begingroup$ @FelixGoldberg: Ok fixed. $\endgroup$ Mar 3 '14 at 18:41
  • 1
    $\begingroup$ I took the liberty of adding a tag. Hope u don't mind. $\endgroup$ Mar 3 '14 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 '14 at 18:28
27
$\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 '14 at 18:48
  • 1
    $\begingroup$ So van der Waerden's conjecture is an elaborate generalization of Hall's marriage theorem. Nice! $\endgroup$ Mar 3 '14 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 '14 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 '14 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 '14 at 15:28
16
$\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 '14 at 0:32
  • $\begingroup$ Nice! Sorry, I did not know that. You should restore the non-negativity condition though. $\endgroup$
    – Tony Huynh
    Mar 4 '14 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 '19 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 '14 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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