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 question about symmetric matrix
Your matrix $A$ is doubly stochastic (because of condition (2) and of its symmetry). The [Birkhoff-von Neumann theorem](http://en.wikipedia.org/wiki/Doubly_stochastic_matrix#Birkhoff_polytope_and_Birkhoff.E2.80.93von_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$.


