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

• There's always the brute force way: (1) Find some permutation matrix $P_\pi$ such that none of the entries $A[i,\pi(i)]$ are zero. (2) Subtract $\min_i A[i,\pi(i)] P_\pi$ from A. (3) Repeat until you're left with the 0 matrix. Oct 16, 2012 at 16:45
• Yes, you're right. To prove the correctness, simply notice that (1) Each time you are guaranteed to get one more zero entry; (2) Each time you're left with a multiple of a doubly stochastic matrix; (3) For any doubly stochastic matrix, $\exists \pi$ such that none of the entries $A[i,\pi(i)]$ are zero. (1) and (2) are obvious, how do you prove (3)?
– xzhu
Oct 16, 2012 at 17:03

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

The coefficients can be computed using the Birkhoff-Von-Neumann algorithm. The algorithm is guaranteed to have support on less than $$n^2-2n+2$$ permutation matrices 1.

1 Johnson, Diane M.; Dulmage, A. L.; Mendelsohn, N. S. (1960-09-01). "On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices". Canadian Mathematical Bulletin.