In an $n\times n$ nonnegative matrix, there are at least $n$ positive entries from distinct rows and from distinct columns. 
All entries of an $n \times  n$ matrix are non-negative. It is known that the sum of numbers in any row and in any column of this matrix is exactly $1$. Prove that you can choose $n$ positive entries such that all of them are from different rows and from different columns.

How do I solve this problem?  Below is an attempt to prove by contradiction.
Call the matrix $A$.  Suppose that the largest number of positive entries from distinct rows and from distinct columns is $m<n$.  Without loss of generality, we can assume that they are the entries $(k,k)$ for $k=1,2,\ldots,m$.
Let $B$ be the submatrix of $A$ consisting of entries $(i,j)$ where $i>m$ and $j>m$.  If $B$ has a positive entry $(i_0,j_0)$, then we can add that to the $m$ positive numbers we already have and get a contradiction.  Therefore, $B$ is the zero matrix.
 A: Write $M$ for the given $n$-by-$n$ matrix.  Let $R$ be the set of rows and $C$ the set of columns.  The edges of the bipartite $G(R\cup C,E)$ with bipartite sets $R$ and $C$ are joined between an element $r \in R$ and $c \in C$ such that the entry on the row $r$ and on the column $c$ of $M$ is positive.  We claim that, for any subset $X$ of $R$, the set $$N(X):=\big\{j\in C\,|\,\{r,c\}\in E\big\}$$ satisfies $$|X| \leq \big|N(X)\big|\,.$$  For a fixed $X\subseteq R$, consider the submatrix $M(X)$ indexed by rows in $X$ and columns in $N(X)$ of the given matrix.  The sum of the entries of each row of $M(X)$ is $1$, whence the sum of all rows of $M(X)$ is $|X|$.  As the sum of the entries of all rows of $M(X)$ is the same as the sum of the entries of all columns of $M(X)$ and the sum of each column of $M(X)$ at most $1$, we see that $$|X| \leq \big|N(X)\big|\,.$$  By Hall's Marriage Theorem, there is a matching of $G$ that covers $R$ (hence, this matching is a perfect matching).  A perfect matching of $G$ is equivalent to saying that there are $n$ positive entries of $M$  such that all of them are from different rows and from different columns.
