I am reading from Linear Algebra in Action by Dym and am working through the proof of the BvN Theorem. For the sake of clarity, ill write up everything until the point where I get lost.
Theorem: Let $P\in\mathbb{R}^{n\times n}$ be a doubly stochastic matrix.Then $P$ is a convex combination of finitely many permutation matrices.
Proof: If $P$ is a permutation matrix, then the assertion is self-evident. IF $P$ is not a permutation matrix, them, in the view of Lemma 23.13
Lemma 23.13: Let $A\in\mathbb{R}^{n\times n}$ be a doubly stochastic matrix. Then $per(A)>0$.
and the fact that $P$ is doubly stochastic, there exists a permutation $\sigma$ of the integers $\{1,\dots,n\}$ such that $1>p_{1\sigma(1)}p_{2\sigma(2)}\cdots p_{n\sigma(n)}>0.$ Let $$\lambda_1=\min\{p_{1\sigma(1)},p_{2\sigma(2)},\dots, p_{n\sigma(n)}\}$$ and let $\Pi_1$ be the permutation matrix with 1's in the $i\sigma(i)$ position for $i=1,\dots,n$. Then it is readily checked that $$P_1=\frac{P-\lambda_1\Pi_1}{1-\lambda_1}$$ is a doubly stochastic matrix with at least one more zero entry than $P$ and that ...
I do not see how that is clearly the case? Can someone explain that to me?
When we subtract $P-\lambda_1\Pi_1$ we are only subtracting $\lambda_1$ from entries which are $\ge\lambda_1$, so the result still has nonnegative entries. Furthermore every row and column has $\lambda_1$ taken from its sum total, i.e. all rows and columns sum to $1-\lambda_1$. When we divide by $1-\lambda_1$ (which is possible since $0<\lambda_1<1$) the result is thus a matrix whose rows and columns simply sum to $1$, and whose entries are still nonnegative, i.e. the result is a doubly stochastic matrix. Any matrix entry which was already $0$ remains $0$, but out of the entries corresponding to the $1$s in $\Pi_1$ the minimal entry, i.e. where $p_{r\sigma(r)}=\lambda_1$, is now $0$ where it wasn't before.