combinatorics - permutations question, possibly with pigeon hole Let $A \in Mat_n(\mathbb R)$ such that $\forall i,j: a_{ij}\geq 0$
We are given: $$\forall j: \sum_{i=1}^n a_{ij}=\sum_{i=1}^n a_{ji}=1$$
show there's a permutation $\pi \in S_n$ such that $$\forall i:  a_{i \pi(i)}>0$$
 A: Construct a bipartite graph with vertices $u_1,\ldots,u_n$ and $v_1,\ldots,v_n$ with $u_i$ adjacent to $v_j$ if (and only if) $a_{ij}>0$.
Then what we are attempting to prove is that there is some permutation $\pi\in S_n$ such that $u_i$ is adjacent to $v_{\pi(i)}$ for all $i$, i.e. there is a Perfect Matching.
Using Hall's Matching Theorem, if there is no Perfect Matching, then there is some set $S\subseteq[n]$ such that $S'=\{j:j\in[n]|\exists i\in S:a_i\sim b_j\}$ is of size smaller than $S$.
But this is impossible since $|S|=\Sigma_{i\in S}\Sigma_{j=1}^{n}a_{ij}=\Sigma_{i\in S}\Sigma_{j\in S'}a_{ij}\le\Sigma_{i=1}^{n}\Sigma_{j\in S'}a_{ij}=|S'|.$
A: My solution is not self contained but a solution nevertheless ;-)
Lets assume every permutation $\pi \in S_n$ contains a $0$. Then the product $\prod_{i=1}^{n} a_{i\pi (i)} = 0$. Hence the permanent of the doubly stochastic matrix (term used for such kind of matrices) equals $0$ which contradicts the well known van der waerden - Egorychev - Falikman theorem. This theorem asserts that the minimum of the permanent of doubly stochastic matrices is $\frac{n!}{n^n}$ and it occurs uniquely for the matrix with $\frac{1}{n}$ as all its entries. 
