6
$\begingroup$

Let $A= (a_{ij})_{ij}, 1 \leq i, j \leq n$ be a symmetric $n \times n$ matrix. Suppose

(1) $a_{ij} \geq 0$ are real numbers;

(2) The sum of each row $\sum_{j=1}^{n} a_{ij} = 1$ for $1 \leq i \leq n$.

Then I want to show the following: there must exists a nonzero $\prod_{i=1}^n a_{i, \sigma(i)}$, where $\sigma \in S_n$ is an element of the symmetric group $S_n$. In other words, there must exists a nonzero summand in the expression of $\det A$.

$\endgroup$
3
  • 3
    $\begingroup$ Google "Birkhoff-van Neumann theorem". $\endgroup$ Dec 6, 2014 at 16:22
  • $\begingroup$ @darij grinberg Thank you very very much! I would be very happy to accept your comments as an answer. $\endgroup$
    – Li Yutong
    Dec 6, 2014 at 16:33
  • 1
    $\begingroup$ OK, but on math.stackexchange. :P $\endgroup$ Dec 6, 2014 at 16:34

3 Answers 3

11
$\begingroup$

Your matrix $A$ is doubly stochastic (because of condition (2) and of its symmetry). The Birkhoff-von Neumann theorem yields that it is a convex combination of permutation matrices. Take any permutation matrix which enters into this combination with a nonzero coefficient. Then, the corresponding permutation $\sigma$ must satisfy $\prod_{i=1}^n a_{i,\sigma(i)} \neq 0$.

$\endgroup$
1
  • $\begingroup$ Actually, I wrote other books, but they are in Partial Differential Equations, my research topic. $\endgroup$ Dec 9, 2014 at 6:15
10
$\begingroup$

Darij Grinberg's answer is sufficient to answer the question. Also, a conjecture of Van der Waerden, which was proved around 1981, gives slightly stronger information. The permanent of an $n \times n$ doubly stochastic matrix is at least $\frac{n!}{n^{n}},$ so the mean contribution to the permanent across all $\sigma \in S_{n}$ is at least $n^{-n}$, and this is clearly best possible (on the other hand, the Birkhoff- von Neumann theorem at least shows that the permanent of a doubly stochastic matrix is strictly positive, which is a starting point for the Van der Waerden conjecture. In fact, it's clear that the Birkhoff-von Neumann theorem is equivalent to the fact that all doubly stochastic matrices have non-zero permanent).

$\endgroup$
1
  • $\begingroup$ Interesting! Thank you for point out this! $\endgroup$
    – Li Yutong
    Dec 6, 2014 at 16:54
2
$\begingroup$

An other solution (but Darij's is enough). It is classical that if all these products are zero, then $A$ contains a submatrix $k\times\ell$ of zeros, with $k+\ell>n$ (see for instance Exercise 7, Chapter 3 of my book, 2nd edition). Then an elementary calculus shows that the sums of entries in the opposite block equals $n-k-\ell$. This is negative, contradicting the fact that the entries are non-negative.

$\endgroup$
1
  • $\begingroup$ You sound like you have decided to never write more than one book. $\endgroup$ Dec 8, 2014 at 23:33

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.