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.[1] 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:
0.2 , 0.3 , 0.5
0.6 , 0.2 , 0.2
0.2 , 0.5 , 0.3
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:
0 , 1 , 0
0 , 0 , 1
1 , 0 , 0
Algorithm
References
- ^ Birkhoff, Garrett (1946), "Tres observaciones sobre el algebra lineal [Three observations on linear algebra]", Univ. Nac. Tucumán. Revista A., 5: 147–151, MR 0020547.