What's the algorithm of finding the convex combination of permutation matrices for a doubly stochastic matrix?

According to Birkhoff, $n$-by-$n$ stochastic matrices form a convex polytope whose extreme points are precisely the permutation matrices. It implies that any doubly stochastic matrix can be written as a convex combination of finitely many permutation matrices. Given a doubly stochastic matrix, is there an algorithm to compute the coefficients of a convex combination?

For example, given

$$A = \begin{bmatrix} 0.5&0.2&0.3\\ 0.1&0.6&0.3\\ 0.4&0.2&0.4\end{bmatrix},$$

how do you know the following?

$$A=0.4\left[\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}\right]+0.2\left[\begin{matrix}0&1&0\\0&0&1\\1&0&0\end{matrix}\right]+0.1\left[\begin{matrix}0&0&1\\1&0&0\\0&1&0\end{matrix}\right]+0.1\left[\begin{matrix}1&0&0\\0&0&1\\0&1&0\end{matrix}\right]+0.2\left[\begin{matrix}0&0&1\\0&1&0\\1&0&0\end{matrix}\right]$$

Please do briefly prove the correctness of the algorithm.

Solution 1:

I'm expanding my comment to an answer.

You can always do it the brute force way.

1. Find some permutation matrix $P_\pi$ such that none of the entries $A[i,\pi(i)]$ are $0$.

2. Subtract $(\min_i A[i,\pi(i)])\, P_\pi$ from $A$.

3. Repeat steps (1) and (2) until you're left with the $0$ matrix.

As the OP comments, to prove that it terminates, you can note that each time you are left with a multiple of a double stochastic matrix, and step (2) always adds at least one more zero entry.

We still need to show that step (1) is always possible. This follows from Hall's marriage theorem. This theorem states that such a permutation $\pi$ exists unless there is a set $R$ of rows and a set $C$ of columns such that $|R|+|C| < n$ and $A[i,j] = 0$ unless $i \in R$ or $j \in C$. In other words, all the non-zero entries are either in a row in $C$ or a column in $R$.

We will show by contradiction that such a matrix cannot be doubly stochastic. Look at the the sum of all elements $A[i,j]$ with $i \in R$ and $j \in \bar{C}$. Since each of the column sums is $1$, $$\sum_{i\in R, j\in \bar{C}} A[i,j] = \sum_{j\in \bar{C}} A[i,j] = |\bar{C}|.$$ Also, each of the row sums is $1$, so $$\sum_{i\in R, j\in \bar{C}} A[i,j] \leq \sum_{i\in R} A[i,j] = |R|.$$ But $|R| < |\bar{C}|$, so $$\sum_{i\in R, j\in \bar{C}} A[i,j]\leq |R| < |\bar{C}|= \sum_{i\in R, j\in \bar{C}} A[i,j],$$ a contradiction.

Note that this gives a proof of Birkhoff's theorem. To turn it into a real algorithm, you still need an algorithm for step (1) that finds a permutation in Hall's marriage theorem. There are lots of algorithms to do this; I don't know which is the simplest one. (It's a special case of the bipartite maximum matching problem, which in turn is a special case of the assignment problem, so any bipartite maximum matching algorithm, or any algorithm solving the assignment problem, will work.).