A property of the Birkhoff polytope

Abstract

The Birkhoff polytope $B_n$ is the convex hull of all $n\times n$ permutation matrices in ${\mathbb{R}}^{n\times n}$. We compute the combinatorial symmetry group of the Birkhoff polytope. A representation polytope is the convex hull of some finite matrix group $G\le \mathrm{GL}(d,\mathbb{R})$. We show that the group of permutation matrices is essentially the only finite matrix group which yields a representation polytope with the same face lattice as the Birkhoff polytope.

10 pages, pdflatex (with biblatex). v2: Simplified proof of Lemma 4.1, other minor corrections. Accepted for publication in "Algebraic Combinatorics"

References in corpus (1)

• Affine Symmetries of Orbit Polytopes