A generating function for all semi-magic squares and the volume of the Birkhoff polytope (Q735404): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:19, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A generating function for all semi-magic squares and the volume of the Birkhoff polytope |
scientific article |
Statements
A generating function for all semi-magic squares and the volume of the Birkhoff polytope (English)
0 references
21 October 2009
0 references
The famous Birkhoff polytope \(B_n\) is the convex polytope of \(n\times n\) doubly stochastic matrices, with vertices at the permutation matrices. The Ehrhart polynomial of \(B_n\) is a polynomial in a variable \(t\) that records the number of lattice points within the dilation \(tB_n\). The authors find exact formulae for the coefficients of the Ehrhart polynomial, including the leading coefficient which gives the volume of \(B_n\). The formulae involve sums over all permutations of \(n\) and over all arborescences (rooted trees) on \(n\) nodes and hence seem impractical to evaluate except for very small \(n\). However, \textit{E. R. Canfield} and \textit{B. D. McKay} [Online J. Anal. Comb. 4, Article 2, 4 p., electronic only (2009; Zbl 1193.15034)] have recently found asymptotic formulae which yield practical approximations for large \(n\). The authors' formulae are corollaries of a multivariate rational generating function they find for the \(n\times n\) non-negative integer matrices with row and column sums all equal to \(t\). Such matrices are sometimes called semi-magic squares. The coefficients of the Ehrhart polynomial of \(B_n\) are found after expressing this generating function in terms of Todd polynomials. To demonstrate that their methods have wider applicability, the authors finish by explicitly computing the Ehrhart polynomials of a facet of \(B_n\) for \(3\leq n\leq 6\) and of the Chan-Robbins-Yuen polytope \(CRY_n\) for \(3\leq n\leq 7\).
0 references
Birkhoff polytope
0 references
generating function
0 references
lattice points
0 references
Ehrhart polynomial
0 references
Todd polynomial
0 references
semi-magic square
0 references
arborescence
0 references