A question about symmetric matrix 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$.
 A: 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.
A: 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$.
A: 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).
