Birkhoff polytope

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

The Birkhoff polytope Bn, also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph K_{n,n},[1] 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.

Properties

Vertices

The Birkhoff polytope has n! vertices, one for each permutation on 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]

Edges

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

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

This implies that the graph of Bn is a Cayley graph of the symmetric group Sn. This also implies that the graph of B3 is a complete graph K6, and thus B3 is a neighborly polytope.

Facets

The Birkhoff polytope lies within an (n2 − 2n + 1)-dimensional affine subspace of the n2-dimensional space of all n × n matrices: this subspace is determined by the linear equality constraints that the sum of each row and of each column be one. Within this subspace, it is defined by n2 linear inequalities, one for each coordinate of the matrix, specifying that the coordinate be non-negative. Therefore, it has exactly n2 facets.[1]

Symmetries

The Birkhoff polytope Bn is both vertex-transitive and facet-transitive (i.e. the dual polytope is vertex-transitive). It is not regular for n>2.

Volume

An outstanding problem is to find the volume of the Birkhoff polytopes. This has been done for n ≤ 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 n was given in 2007.[6] The following asymptotic formula was found by Rodney Canfield and Brendan McKay:[7]

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


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, and it is only conjectured that all the coefficients of the Ehrhart polynomials are non-negative.

Generalizations

See also

References

  1. 1.0 1.1 1.2 Lua error in package.lua at line 80: module 'strict' not found.
  2. Lua error in package.lua at line 80: module 'strict' not found..
  3. Lua error in package.lua at line 80: module 'strict' not found..
  4. The Volumes of Birkhoff polytopes for n ≤ 10.
  5. Lua error in package.lua at line 80: module 'strict' not found..
  6. Lua error in package.lua at line 80: module 'strict' not found..
  7. Lua error in package.lua at line 80: module 'strict' not found..

Additional reading

External links

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