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. 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}}$

See also

• Birkhoff polytope
• Probabilistic-serial procedure