TOPICS
Search

Birkhoff Polytope

The nth Birkhoff polytope B_n is the convex polytope of n×n doubly stochastic matrices. It has dimension (n-1)^2, and its vertices are exactly the n! permutation matrices by the Birkhoff-von Neumann theorem.

Its Ehrhart polynomial H_n(t) counts the nonnegative integer n×n matrices whose row and column sums all equal t. Thus H_1(t)=1, H_2(t)=t+1, and

H_3(t)=3(t+3; 4)+(t+2; 2).

For fixed n, H_n(t) has polynomial degree (n-1)^2 (Ehrhart 1973, Stanley 1973). Xin and Zhang (2026) study a difficult constant-term contribution to H_n(t) that is a variation of the Morris constant term.

See also

Doubly Stochastic Matrix, Ehrhart Polynomial, Permutation Matrix, Polytope

Explore with Wolfram|Alpha

References

Ehrhart, E. "Sur les carrés magiques." C. R. Acad. Sci. Paris Sér. A 277, 575-577, 1973.Stanley, R. P. "Linear Homogeneous Diophantine Equations and Magic Labelings of Graphs." Duke Math. J. 40, 607-632, 1973.Xin, G. and Zhang, C. "A Variation of the Morris Constant Term." Electron. J. Combin. 33, P3.75, 2026. https://doi.org/10.37236/13507.

Cite this as:

Weisstein, Eric W. "Birkhoff Polytope." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BirkhoffPolytope.html

Subject classifications