- Birkhoff polytope
The Birkhoff polytope "B""n" is the
convex polytope in R"N" (where "N" = "n"²) whose points are the doubly stochastic matrices, i.e., the "n" × "n" matrices whose entries are nonnegative real numbers and whose rows and columns each add up to 1.The "Birkhoff-von Neumann theorem" states that the
extreme point s of the Birkhoff polytope are thepermutation matrices , and therefore that any doubly stochastic matrix may be represented as a linear combination of permutation matrices; this was stated in a 1946 paper byGarrett Birkhoff , [citation| last = Birkhoff | first = Garrett | title = Tres observaciones sobre el algebra lineal [Three observations on linear algebra] | journal = Univ. Nac. Tucumán. Revista A. | volume = 5 | year = 1946 | pages = 147–151 | id = MathSciNet | id = 0020547.] but equivalent results in the languages ofprojective configuration s and of regularbipartite graph matching s, respectively, were shown much earlier in 1894 inErnst Steinitz ' thesis and in 1916 byDénes Kőnig . [citation | last = Kőnig | first = Dénes | authorlink = Dénes Kőnig | title = Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére | journal = Matematikai és Természettudományi Értesítő | volume = 34 | year = 1916 | pages = 104–119.]An outstanding problem is to find the volume of the Birkhoff polytopes. This has been done for "n" ≤ 10 [The [http://www.math.binghamton.edu/dennis/Birkhoff/volumes.html Volumes of Birkhoff polytopes] for "n" ≤ 10.] . Extending the results even that far required new methods; solving larger values of "n" seems to need newer ideas. A paper has been submitted for publication that states an explicit combinatorial formula for all "n". [citation|title=Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces|first1=Jesus A.|last1=De Loera|first2=Fu|last2=Liu|first3=Ruriko|last3=Yoshida|id=arxiv|math.CO/0701866.]
ee also
*
Permutohedron References
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 "B"9.
External links
* [http://www.math.binghamton.edu/dennis/Birkhoff/ Birkhoff polytope] Web site by Dennis Pixton and Matthias Beck, with links to articles and volumes.
Wikimedia Foundation. 2010.
