A generating function for all semi-magic squares and the volume of the Birkhoff polytope

DOI10.1007/S10801-008-0155-YzbMATH Open1187.05009arXivmath/0701866OpenAlexW1974073189WikidataQ56003271 ScholiaQ56003271MaRDI QIDQ735404FDOQ735404

D. Kharzeev

Publication date: 21 October 2009

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0701866

Recommendations

• The Ehrhart polynomial of the Birkhoff polytope
• Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley
• On the Volume of the Polytope of Doubly Stochastic Matrices
• On the number of lattice points in \(n\)-dimensional space with an application
• Some remarks about acyclic and tridiagonal Birkhoff polytopes
• \(h^\ast \)-polynomials of zonotopes
• Some facets of the polytope of even permutation matrices.
• Permutohedra, Associahedra, and Beyond
• The Ehrhart polynomial of a lattice polytope
• Mini-workshop: Ehrhart quasipolynomials: Algebra, combinatorics, and geometry

zbMATH Keywords

generating functionBirkhoff polytopelattice pointsEhrhart polynomialarborescencesemi-magic squareTodd polynomial

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Orthogonal arrays, Latin squares, Room squares (05B15)

Cites Work

• Effective lattice point counting in rational convex polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Ehrhart polynomial of the Birkhoff polytope
• Proof of a conjecture of Chan, Robbins, and Yuen
• Introduction to Toric Varieties. (AM-131)
• Computing the Continuous Discretely
• The asymptotic volume of the Birkhoff polytope
• Lectures on Polytopes
• On the Volume of a Certain Polytope
• Title not available (Why is that?)
• On the Volume of the Polytope of Doubly Stochastic Matrices
• Triangulations. Structures for algorithms and applications
• Points entiers dans les polyèdres convexes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polytope Volume Computation
• Title not available (Why is that?)
• Polynômes arithmétiques et méthode des polyedres en combinatoire
• The volume of duals and sections of polytopes
• Computing the volume, counting integral points, and exponential sums
• Asymptotic enumeration of integer matrices with large equal row and column sums
• Counting integer flows in networks
• A generalization of Filliman duality

Cited In (20)

• Characteristic classes of affine varieties and Plücker formulas for affine morphisms
• The Ehrhart polynomial of the Birkhoff polytope
• Four questions on Birkhoff polytopes
• A practical volume algorithm
• Secular coefficients and the holomorphic multiplicative chaos
• On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope
• Algebraic and geometric structures inside the Birkhoff polytope
• On superalgebras of matrices with symmetry properties
• Unconditional reflexive polytopes
• The asymptotic volume of the Birkhoff polytope
• Unistochastic Matrices and Related Problems
• Deformation cones of Tesler polytopes
• Restricted Birkhoff polytopes and Ehrhart period collapse
• Ehrhart positivity of Tesler polytopes and Berline-Vergne's valuation
• A Chinese remainder theorem for partitions
• Computing with an algebraic-perturbation variant of Barvinok's algorithm
• Faces of Birkhoff Polytopes
• The diameter of the Birkhoff polytope
• On permutation polytopes: notions of equivalence
• Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley

Uses Software

• LattE

This page was built for publication: A generating function for all semi-magic squares and the volume of the Birkhoff polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q735404)