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