Birkhoff algorithm

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garret Birkhoff at 1946.. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.

Terminology

A bistochastic matrix (also called: doubly-stochastic) is a matrix in which all elements are weakly-positive, and the sum of each row and column equals 1. An example is the following 3-by-3 matrix:

${\begin{pmatrix}0.2&0.3&0.5\\0.6&0.2&0.2\\0.2&0.5&0.3\end{pmatrix}}$

A permutation matrix is a special case of a bistochastic matrix, in which each element is either 0 or 1 (so there is exactly one "1" in each row and each column). An example is the following 3-by-3 matrix:

${\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}$

A Birkhoff decomposition (also called: Birkhoff-von-Neumann decomposition) of a bistochastic matrix is a presentation of it as a sum of permutation matrices with non-negative weights. For example, the above matrix can be presented as the following sum:

$0.2{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}+0.2{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}+0.1{\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}+0.5{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$

Birkhoff's algorithm receives as input a bistochastic matrix and returns as output a Birkhoff decomposition.

Tools

A permutation set of an n-by-n matrix X is a set of n entries of X containing exactly one entry from each row and from each column. A theorem by Dénes Kőnig says that:

Every bistochastic matrix has a permutation-set in which all entries are positive.

The positivity graph of an n-by-n matrix X is a bipartite graph with 2n vertices, in which the vertices on one side are n rows and the vertices on the other side are the n columns, and there is an edge between a row and a column iff the entry at that row and column is positive. A permutation set with positive entries is equivalent to a perfect matching in the positivity graph. A perfect matching in a bipartite graph can be found in polynomial time, e.g. using any algorithm for maximum cardinality matching. Kőnig's theorem is equivalent to the following:

The positivity graph of any bistochastic matrix admits a perfect matching.

A matrix is called scaled-bistochastic if all elements are weakly-positive, and the sum of each row and column equals c, where c is some positive constant. In other words, it is c times a bistochastic matrix. Since the positivity graph is not affected by scaling:

The positivity graph of any scaled-bistochastic matrix admits a perfect matching.

Algorithm

Using the tools above, Birkhoff's algorithm works as follows.

1. Let i = 1.
2. Construct the positivity graph G_X of X.
3. Find a perfect matching in G_X, corresponding to a positive permutation set in X.
4. Let z[i] > 0 be the smallest entry in the permutation set.
5. Let P[i] be a permutation matrix with 1-s in the positive permutation set.
6. Let X := X - z[i] P[i].
7. If X contains nonzero elements, Let i = i+1 and go back to step 2.
8. Otherwise, return the sum: z[1] P[1] + ... + z[2] P[2] + ... + z[i] P[i].

The algorithm is correct because, after step 6, the sum in each row and each column drops by z[i]. Therefore, the matrix X remains scaled-bistochastic. Therefore, in step 3, a perfect matching always exists.

Run-time complexity

By the selection of z[i] in step 4, in each iteration at least one element of X becomes 0. Therefore, the algorithm must end after at most n² steps. However, the last step must simultaneously make n elements 0, so the algorithm ends after at most n²-n+1 steps.

In 1960, Joshnson, Dulmage and Mendelsohn showed that Birkhoff's algorithm actually ends after at nost n²-2n+2 steps, which is tight in general (i.e., in some cases n²-2n+2 permutation matrices may be required).

Extensions

The problem of computing the Birkhoff decomposition with the minimum number of terms has been shown to be NP-hard, but some heuristics for computing it are known. This theorem can be extended for the general stochastic matrix with deterministic transition matrices.

See also

• Birkhoff polytope
• Probabilistic-serial procedure
• Birkhoff decomposition (disambiguation)