Birkhoff polytope

The Birkhoff polytope ${\displaystyle B_{n}}$ (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph ${\displaystyle K_{n,n}}$^[1]) is the convex polytope in ${\displaystyle \mathbb {R} ^{n^{2}}}$ whose points are the doubly stochastic matrices, that is, the ${\displaystyle n\times n}$ matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1. It is named after Garrett Birkhoff.

Properties

Vertices

The Birkhoff polytope has ${\displaystyle n!}$ vertices, one for each permutation on ${\displaystyle n}$items.^[1] This follows from the Birkhoff–von Neumann theorem, which 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,^[2] 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.^[3] Because all of the vertex coordinates are zero or one, the Birkhoff polytope is an integral polytope.

Edges

The edges of the Birkhoff polytope correspond to pairs of permutations differing by a cycle:

${\displaystyle (\sigma ,\omega )}$ such that ${\displaystyle \sigma ^{-1}\omega }$ is a cycle.

This implies that the graph of ${\displaystyle B_{n}}$ is a Cayley graph of the symmetric group ${\displaystyle S_{n}}$. This also implies that the graph of ${\displaystyle B_{3}}$ is a complete graph ${\displaystyle K_{6}}$, and thus ${\displaystyle B_{3}}$ is a neighborly polytope.

Facets

The Birkhoff polytope lies within an ${\displaystyle (n^{2}-2n+1)}$-dimensional affine subspace of the ${\displaystyle n^{2}}$-dimensional space of all ${\displaystyle n\times n}$ matrices. This subspace is determined by the linear equality constraints that the sum of each row and of each column must equal one. Within this subspace, it is defined by ${\displaystyle n^{2}}$ linear inequalities, one for each coordinate of the matrix, specifying that the coordinate must be non-negative. Therefore, for ${\displaystyle n\geq 3}$, it has exactly ${\displaystyle n^{2}}$ facets.^[1] For ${\displaystyle n=2}$, there are two facets, given by ${\displaystyle a_{11}=a_{22}=0}$, and ${\displaystyle a_{12}=a_{21}=0}$.

Symmetries

The Birkhoff polytope ${\displaystyle B_{n}}$ is both vertex-transitive and facet-transitive (i.e. the dual polytope is vertex-transitive). It is not regular for ${\displaystyle n>2}$.

Volume

An outstanding problem is to find the volume of the Birkhoff polytopes. This has been done for ${\displaystyle n\leq 10}$.^[4] It is known to be equal to the volume of a polytope associated with standard Young tableaux.^[5] A combinatorial formula for all ${\displaystyle n}$ was given in 2007.^[6] The following asymptotic formula was found by Rodney Canfield and Brendan McKay:^[7]

${\displaystyle \mathop {\mathrm {vol} } (B_{n})\,=\,\exp \left(-(n-1)^{2}\ln n+n^{2}-\left(n-{\frac {1}{2}}\right)\ln(2\pi )+{\frac {1}{3}}+o(1)\right).}$

For small values ${\displaystyle n\leq 15}$ the volume was estimated in 2014^[8] while similar estimations follow.^[9]

Ehrhart polynomial

Determining the Ehrhart polynomial of a polytope is harder than determining its volume, since the volume can easily be computed from the leading coefficient of the Ehrhart polynomial. The Ehrhart polynomial associated with the Birkhoff polytope is only known for small values.^[4] It is conjectured that all the coefficients of the Ehrhart polynomials are non-negative.

Generalizations

• The Birkhoff polytope is a special case of the transportation polytope, a polytope of nonnegative rectangular matrices with given row and column sums.^[10] The integer points in these polytopes are called contingency tables; they play an important role in Bayesian statistics.
• The Birkhoff polytope is a special case of the matching polytope, defined as a convex hull of the perfect matchings in a finite graph. The description of facets in this generality was given by Jack Edmonds (1965), and is related to Edmonds's matching algorithm.
• The Birkhoff polytope is a special case of the flow polytope of nonnegative flows through a network.^[11] It is related to the Ford–Fulkerson algorithm that computes the maximum flow in a flow network.

See also

• Birkhoff algorithm
• Permutohedron
• Stable matching polytope

References

1. Ziegler, Günter M. (2007) [2006], Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (7th printing of 1st ed.), New York: Springer, p. 20, ISBN 978-0-387-94365-7
2. 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.
3. 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.
4. Beck, Matthias; Pixton, Dennis (1 October 2003), "The Ehrhart Polynomial of the Birkhoff Polytope", Discrete and Computational Geometry, 30 (4): 623–637, arXiv:math/0202267, doi:10.1007/s00454-003-2850-8, S2CID 7164663
5. Pak, Igor (2000), "Four questions on Birkhoff polytope", Annals of Combinatorics, 4: 83–90, doi:10.1007/PL00001277, S2CID 1250478.
6. De Loera, Jesus A.; Liu, Fu; Yoshida, Ruriko (2007), "Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces", Journal of Algebraic Combinatorics, 30: 113–139, arXiv:math.CO/0701866, doi:10.1007/s10801-008-0155-y, S2CID 5837937.
7. Canfield, E. Rodney; McKay, Brendan D. (2007), "The asymptotic volume of the Birkhoff polytope", arXiv:0705.2422 [math.CO]
8. Emiris, Ioannis; Fisikopoulos, Vissarion (2014), "Efficient Random-Walk Methods for Approximating Polytope Volume", Annual Symposium on Computational Geometry - SOCG'14, ACM, pp. 318–327, arXiv:1312.2873, doi:10.1145/2582112.2582133, ISBN 9781450325943, S2CID 372936
9. Cousins, Ben; Vempala, Santosh (2016), "A practical volume algorithm", Mathematical Programming Computation, 8 (2): 133–160, doi:10.1007/s12532-015-0097-z, S2CID 10365756
10. Emelichev, V.A.; Kovalev, M.M.; Kravtsov, M.K. (1984), Polytopes, Graphs, and Optimization, Cambridge University Press
11. Baldoni-Silva, W.; De Loera, J. A.; Vergne, M. (2004), "Counting Integer Flows in Networks", Foundations of Computational Mathematics, 4 (3): 277–314, arXiv:math/0303228, doi:10.1007/s10208-003-0088-8, S2CID 2541019

External links

• Birkhoff polytope Web site by Dennis Pixton and Matthias Beck, with links to articles and volumes.