Birkhoff Algorithm

The Birkhoff algorithm, also called the Birkhoff-von Neumann algorithm, decomposes a bistochastic, or doubly stochastic, matrix, one whose entries are all non-negative and whose rows and columns each sum to 1, into a weighted sum of permutation matrices, each containing only 0s and 1s with exactly one 1 in every row and column. It was published by Garrett Birkhoff in 1946, and operates as a greedy procedure that repeatedly finds a perfect matching in the matrix's positivity graph, the graph connecting rows to columns wherever the matrix entry is positive, and removes it from the matrix, continuing until the whole matrix has been expressed as such a combination. A significant application is fair random assignment: when a randomized allocation of items among people has already been computed as a bistochastic matrix, Birkhoff's algorithm can decompose that matrix into a lottery over concrete, deterministic assignments, allowing a probabilistically fair allocation rule to actually be carried out in practice. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/