combinatorics - permutations question, possibly with pigeon hole

Question

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

Answer 1

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