I have been researching doubly stochastic matrix properties, but didn't find proof of pretty known fact, so I would like to ask it here. How to prove the following?
A doubly stochastic matrix
Cannot have exactly $n+1$ positive entries.
If it is not permutation matrix, then it has no more than $n^2 - n - 2$ zero entries.
Suppose that a doubly stochastic matrix $A$ has exactly $n+1$ positive entries. A doubly stochastic matrix must have at least one positive entry in each row (and each column). It follows that $A$ has $n-1$ rows with exactly one nonzero entry and one row with two nonzero entries, and the same can be said of the columns. The singular nonzero entry in the aforementioned $n-1$ rows must be a $1$, and, since no column has more than one nonzero entry, none of these $1$'s have another nonzero entry in their column. This leaves one row in which the remaining two nonzero entries must lie and also one column where they must lie. But a row and a column intersect in only one place, so we have a contradiction.
A doubly stochastic matrix with more than $n^2-n-2$ zero entries has fewer than $n+2$ nonzero entries, meaning it has at most $n+1$ nonzero entries. By the prior paragraph, it has at most $n$ nonzero entries. As mentioned before, there must be at least one nonzero entry in each row, whence there is in fact exactly one. Further, that nonzero entry must in fact equal $1$. This implies that any such matrix is a permutation matrix.