The Ehrhart polynomial of the Birkhoff polytope (Q1422230): Difference between revisions

The \(n\)th Birkhoff polytope is the set of all doubly stochastic \(n \times n\) matrices, i.e. those matrices with nonnegative real coefficients in which every row and column sums to one. Computing the volumes of these polytopes remains an open problem for \(n > 8\). As the volume of such a polytope occurs as the leading term of the Ehrhart polynomial, the authors introduce a new method to compute this polynomial. A formula established by the first author in an earlier paper leads to the following form of the Ehrhart polynomial: \[ H_n(t)=\frac{1}{(2 \pi i)^n} \int_{| z_1| =\varepsilon_1}\cdots \int_{| z_n| =\varepsilon_n}(z_1 \cdots z_n)^{-t-1} \biggl(\sum_{k=1}^n \frac{z_k^{t+n-1}}{\prod_{j\neq k}(z_k-z_j)}\biggr)^n dz_n \cdots dz_1. \] This formula is easily evaluated for \(n=3,4\) and, with the help of a computer for \(n\) up to 10. Finally, brief consideration is given to transportation polytopes, a generalization of the Birkhoff polytopes.