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$$

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'|.$
