# 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, of which the extreme points are precisely the permutation matrices. It implies that any doubly stochastic matrix can be written as a convex sum of finitely many permutation matrices. But for a specified such matrix, is there a algorithm to compute the coefficients of a combination? For example, given that: $$A=\left[\begin{matrix}0.5&0.2&0.3\\0.1&0.6&0.3\\0.4&0.2&0.4\end{matrix}\right],$$

How do you know that: $$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]$$

And please 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. – Peter Shor Oct 16 '12 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)? – Voldemort Oct 16 '12 at 17:03
@Peter Shor: Forgot to notify. – Voldemort Oct 16 '12 at 17:14

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

-