The Birkhoff polytope Bn 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 points of the Birkhoff polytope are the permutation matrices.

An outstanding problem is to find the volume of the Birkhoff polytopes. This has been done for n ≤ 10[1]. 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 [2]

References

1. ^ Volumes of Birkhoff polytopes

2. ^ http://www.math.ucdavis.edu/~fuliu/math/birkhoff.ps

* 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.

See also

* Permutohedron

Links

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

* The volumes of the Birkhoff polytopes for n ≤ 10.

Geometry