Birkhoff algorithm

Birkhoff's algorithm is an algorithm for decomposing a doubly stochastic 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 doubly-stochastic matrix 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 doubly-stochastic 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 of a doubly-stochastic 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 doubly-stochastic matrix and returns as output a Birkhoff decomposition.

Tools

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

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

The positivity graph of 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 doubly-stochastic matrix admits a perfect matching.

See also

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