Getting a doubly stochastic matrix from a doubly substochastic matrix.

Question

In his lecture notes on Communication Network Analysis (Link to pdf, pg 52 , line 4), Bruce Hajek writes that

"If $\widetilde{M}$ is a non-negative matrix with all line sums less than or equal to one, then if some entries of $\widetilde{M}$ are increased appropriately, then a doubly stochastic matrix $M$ can be obtained."

By line sums, he refers to row sums or column sums.

I am a bit stuck trying to prove this result. I think I have some idea about why this is correct, but I can't formalize it. I know that $\widetilde{M}$ lies in the interior of the convex hull of all permutation matrices. I need to prove the existence of some direction along which I can move without reducing the value of any element. Then,when we hit the boundary that will give us the required $M$. Is this intuition correct?

I would like to prove this result. I also want to know if there is an actual contruction which performs this so that I can have an algorithm for doing this, or is it that we can only show the existence of such a matrix?

Answer 1

Let us call an entry $m_{ij}$ a double slack (this is a term I coin for convenience; it isn't standard) if both row $i$ and column $j$ have line sums strictly smaller than 1. You may try to prove that:

1. Every double slack has some (strictly positive) room for increment. Hence it is removable if we increase the value of the entry appropriately.
2. The removal of a double slack will not create any new one. If we remove a double slack, the total number of double slacks will strictly decrease.
3. $\widetilde{M}$ has only finitely many double slacks. So, eventually we remove them one by one, all double slacks will be removed in finite steps.
4. $\widetilde{M}$ is doubly stochastic if and only if it has no double slacks. (The "only if" part is trivial. The "if" part is not difficult, but it deserves some explanation.)