Birkhoff algorithm

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was developed by Garret Birkhoff.. 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. 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 element in the permutation set.
5. Let P[i] be a permutation matrix whose nonzero entries correspond to the positive permutation X.
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 5, the sum in each row and each column drops by z. Therefore, the matrix X remains scaled-bistochastic. Therefore, in step 2, a perfect matching always exists.

See also

• Birkhoff polytope
• Probabilistic-serial procedure
• The term "Birkhoff decomposition" is also used for a different concept called Birkhoff factorization.