A Generating Function for all Semi-Magic Squares and the Volume of the Birkhoff Polytope

Abstract

We present a multivariate generating function for all n x n nonnegative integral matrices with all row and column sums equal to a positive integer t, the so called semi-magic squares. As a consequence we obtain formulas for all coefficients of the Ehrhart polynomial of the polytope B_n of n x n doubly-stochastic matrices, also known as the Birkhoff polytope. In particular we derive formulas for the volumes of B_n and any of its faces.

24 pages, 1 figure. To appear in Journal of Algebraic Combinatorics

References in corpus (2)

• Lectures on 0/1-polytopes
• Asymptotic enumeration of integer matrices with constant row and column sums

Cited by in corpus (18)

• Efficient Random-Walk Methods for Approximating Polytope Volume
• Rational Generating Functions and Integer Programming Games
• Properties of Uniform Doubly Stochastic Matrices
• Perturbation of transportation polytopes
• Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method
• Random Bistochastic Matrices
• A new approach to the characteristic polynomial of a random unitary matrix
• Decomposable functors and the exponential principle, II
• On the Geometry of the Birkhoff Polytope. I. The operator ${\ell }_n^p$-norms
• Algebraic and geometric structures inside the Birkhoff polytope
• Restricted Birkhoff polytopes and Ehrhart period collapse
• A Basis for Slicing Birkhoff Polytopes
• $c$-Birkhoff polytopes
• Birkhoff polytopes of different type and the orthant-lattice property
• A note on higher-dimensional magic matrices
• Ehrhart positivity of Tesler polytopes and Berline-Vergne's valuation
• On Superalgebras of Matrices with Symmetry Properties
• Constrained Triangulations, Volumes of Polytopes, and Unit Equations