Birkhoff polytope
From Wikipedia, the free encyclopedia
The Birkhoff polytope Bn is the convex polytope in RN (where N = n²) whose points are the doubly stochastic matrices, i.e., the n × n matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1.
The Birkhoff-von Neumann theorem states that the extreme points of the Birkhoff polytope are the permutation matrices, and therefore that any doubly stochastic matrix may be represented as a convex combination of permutation matrices; this was stated in a 1946 paper by Garrett Birkhoff,[1] but equivalent results in the languages of projective configurations and of regular bipartite graph matchings, respectively, were shown much earlier in 1894 in Ernst Steinitz's thesis and in 1916 by Dénes Kőnig.[2]
An outstanding problem is to find the volume of the Birkhoff polytopes. This has been done for n ≤ 10.[3] It is known to be equal to the volume of a polytope associated with standard Young tableaux.[4] A combinatorial formula for all n was given in 2007.[5] Most recently, an asymptotic formula was found by Rodney Canfield and Brendan McKay:[6]
Contents |
[edit] See also
[edit] References
- ^ Birkhoff, Garrett (1946), "Tres observaciones sobre el algebra lineal [Three observations on linear algebra]", Univ. Nac. Tucumán. Revista A. 5: 147–151, MR0020547.
- ^ Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő 34: 104–119.
- ^ The Volumes of Birkhoff polytopes for n ≤ 10.
- ^ Pak, Igor (2000), "Four questions on Birkhoff polytope", Annals of Combinatorics 4: 83–90, doi:.
- ^ De Loera, Jesus A.; Liu, Fu; Yoshida, Ruriko (2007), Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces, arΧiv:math.CO/0701866.
- ^ Canfield, E. Rodney; McKay, Brendan D. (2007), The asymptotic volume of the Birkhoff polytope, arΧiv:0705.2422.
[edit] Additional reading
- Matthias Beck and Dennis Pixton (2003), The Ehrhart polynomial of the Birkhoff polytope, Discrete and Computational Geometry, Vol. 30, pp. 623-637. The volume of B9.
[edit] External links
- Birkhoff polytope Web site by Dennis Pixton and Matthias Beck, with links to articles and volumes.
