Q:

Show there exists a permutation $a_{i,\sigma (i)} > \frac 1{n^2}$, Hall theorem, doubly stochastic matrix

Question: 
Let $A = (a_{i,j} )$ be an n by n real matrix, where n > 1, $a_{i,j}$ ≥ 0 for all i, j and the sum of elements in each row of A and the sum of elements in each column of A is exactly 1. Show that there is a permutation σ of 1, 2, . . . , n so that $a_{i,σ(i)} > \frac 1{n^2}$ for all 1 ≤ i ≤ n.
Tries:
I really dug the internet and found that this is called a doubly stochastic matrix. I tried writing out some small examples but the answer always seemed trivial (to name a few - 2x2 matrix of 1 on the diagonal and 0 otherwise, or 0.25 on the diagonal and 0.75 otherwise) - by permutating actually all I need to do is find an element in row i which is bigger than 0.25 (on a 2x2 matrix for example)- and that will always be true because one of the elements in a row/column must be a complement to 1 of the other's. This is kind of a start of an inductive proof, but from the hint we got this should involve turning the matrix into some kind of graph and using Hall's theorem on it. (This was given in Graph theory class). So I'm a bit lost - I can't see the relation between this question and perfect matching. Any help?

A:

Create a bipartite graph $(V\uplus U, E)$ on $(n+n)$ vertices with an edge between $v_i$ and $u_j$ if and only if $a_{i,j}>\frac{1}{n^2}$. Now take any set $A \subseteq V$, consider its neighbor set $N(A) \subseteq U$ and calculate
\begin{align}
|N(A)| &= \sum_{j \in N(A)} 1 = \sum_{j \in N(A)}\sum_{i \in [n]} a_{i,j} \geq \sum_{i \in A} \sum_{j \in N(A)}a_{i,j} \\
&= \sum_{i \in A}\left(\sum_{j \in [n]}a_{i,j} - \sum_{j \notin N(A)} a_{i,j}\right)\\
&\geq \sum_{i \in A}\left(1 - \sum_{j \notin N(A)} \frac{1}{n^2}\right)
\geq\sum_{i \in A}\left(1-\frac{n-1}{n^2}\right)
=|A|\left(1-\frac{n-1}{n^2}\right)
\end{align}
However $|A| \leq n$, so rearranging we get
$$|N(A)| \geq |A| - \varepsilon \quad\text{ for }\quad \varepsilon < 1,$$
where both $|N(A)|$ and $|A|$ are integral, hence $|N(A)| \geq |A|$. In other words the Hall's condition is fulfilled and that graph has a perfect matching. Each perfect matching in this graph represents a permutation (it is a one-to-one correspondence between rows and columns) with the desired property.
I hope this helps $\ddot\smile$

