Getting a doubly stochastic matrix from a doubly substochastic matrix. 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?
 A: You may use Birkhoff's theorem and its analog for doubly substochatic matrices. Let A be a DSS matrix, then A can be written as a convex combination of partial permutation matrices. Each partial permutation matrix can be converted to a permutation matrix by adding 1's in proper positions. Convert each partial permutation to a permutation matrix, then you have a DS matrix entrywisely greater than the original DSS matrix. 
A: 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:


*

*Every double slack has some (strictly positive) room for increment. Hence it is removable if we increase the value of the entry appropriately.

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

*$\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.

*$\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.)

