ALGEBRAIC COMBINATORICS

A property of the Birkhoff polytope
Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 275-281
The Birkhoff polytope B n is the convex hull of all n×n permutation matrices in ℝ n×n . We compute the combinatorial symmetry group of the Birkhoff polytope. A representation polytope is the convex hull of some finite matrix group G≤GL(d,ℝ). 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.
Received : 2017-09-20
Revised : 2017-10-12
Accepted : 2017-10-12
DOI : https://doi.org/10.5802/alco.6
Classification:  52B15,  05E18,  20B25,  20C15,  52B05,  52B12
Keywords: Birkhoff polytope, representation polytope, permutation polytope, combinatorial symmetry 
@article{ALCO_2018__1_2_275_0,
     author = {Baumeister, Barbara and Ladisch, Frieder},
     title = {A property of the Birkhoff polytope},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     pages = {275-281},
     doi = {10.5802/alco.6},
     language = {en},
     url = {http://alco.centre-mersenne.org/item/ALCO_2018__1_2_275_0}
}

Baumeister, Barbara;Ladisch, Frieder. A property of the Birkhoff polytope. Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 275-281. doi : 10.5802/alco.6. https://alco.centre-mersenne.org/item/ALCO_2018__1_2_275_0/

[1] Baumeister, Barbara; Grüninger, Matthias On Permutation Polytopes: Notions of Equivalence, J. Algebraic Combin., 41 (2015) no. 4, p. 1103 -1114 MR 3342715 | Zbl 1322.52010 | Zbl 1185.52006 | Article

[2] Baumeister, Barbara; Haase, Christian; Nill, Benjamin; Paffenholz, Andreas On Permutation Polytopes, Adv. Math., 222 (2009) no. 2, p. 431 -452 MR 2538016 | Zbl 1185.52006 | Article

[3] Baumeister, Barbara; Haase, Christian; Nill, Benjamin; Paffenholz, Andreas Permutation Polytopes of Cyclic Groups (2011) (preprint, https://arxiv.org/abs/1109.0191v1 ) MR 2538016 | Zbl 1185.52006

[4] Chermak, Andrew; Delgado, Alberto A Measuring Argument for Finite Groups, Proc. Amer. Math. Soc., 107 (1989) no. 4, p. 907 -914 MR 994774 | Zbl 0687.20022 | Article

[5] Friese, Erik; Ladisch, Frieder Affine Symmetries of Orbit Polytopes, Adv. Math., 288 (2016), p. 386 -425 MR 3436389 | Zbl 1330.52017 | Article

[6] Guralnick, Robert M.; Perkinson, David Permutation Polytopes and Indecomposable Elements in Permutation Groups, J. Combin. Theory Ser. A, 113 (2006) no. 7, p. 1243 -1256 MR 2259059 | Zbl 1108.52014 | Article

[7] Isaacs, I. Martin Finite Group Theory, American Mathematical Society, Providence, RI, Graduate Studies in Mathematics (2008) no. 92 MR 2426855 | Zbl 1169.20001 | Article

[8] Li, Chi-Kwong; Spitkovsky, Ilya; Zobin, Nahum Finite Reflection Groups and Linear Preserver Problems, Rocky Mountain J. Math., 34 (2004) no. 1, p. 225 -251 MR 2061128 | Zbl 1060.15007 | Article

[9] Li, Chi-Kwong; Tam, Bit-Shun; Tsing, Nam-Kiu Linear Maps Preserving Permutation and Stochastic Matrices, Linear Algebra Appl., 341 (2002), p. 5 -22 MR 1873605 | Zbl 0998.15004 | Article

[10] Lovász, László; Plummer, Michael D. Matching Theory, North-Holland, North-Holland Mathematics Studies (1986) no. 121 (Annals of Discrete Mathematics 29) MR 859549 | Zbl 0618.05001