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$ Commented 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
    Commented Dec 6, 2014 at 16:33
  • 1
    $\begingroup$ OK, but on math.stackexchange. :P $\endgroup$ Commented 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$ Commented 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
    Commented 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$ Commented Dec 8, 2014 at 23:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .