ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 31-39
Polytopes associated to dihedral groups
Barbara Baumeister *
Universität Bielefeld, Germany
Christian Haase f
Goethe-Universität Frankfurt, Germany
Benjamin Nill *
Case Western Reserve University, Cleveland, OH, USA
Andreas Paffenholz §
Technische Universität Darmstadt, Germany
Received 2 December 2011, accepted 30 October 2012, published online 8 January 2013
In this note we investigate the convex hull of those n x n permutation matrices that correspond to symmetries of a regular n-gon. We give the complete facet description. As an application, we show that this yields a Gorenstein polytope, and we determine the Ehrhart h*-vector.
Keywords: Permutation polytopes, dihedral groups, lattice polytopes. Math. Subj. Class.: 20B35, 52B12; 05E10, 52B05, 52B20
*The first author likes to thank for the support by the DFG through the SFB 701 "Spectral Structures and Topological Methods in Mathematics".
^The second author is supported by DFG Heisenberg (HA 4383/4).
* The third author is supported in part by the US National Science Foundation (DMS 1203162). §The last author is supported by the Priority Program 1489 "Algorithmic and Experimental Methods in Algebra, Geometry and Number Theory" of the German Research Council (DFG).
E-mail addresses: b.baumeister@math.uni-bielefeld.de (Barbara Baumeister), haase@math.uni-frankfurt.de (Christian Haase), benjamin.nill@case.edu (Benjamin Nill), paffenholz@mathematik.tu-darmstadt.de (Andreas Paffenholz)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
Abstract
31
ArsMath. Contemp. 7(2014)23-29
1 Introduction
To any finite group G of real n x n permutation matrices we can associate the permutation polytope P(G) given by the convex hull of these matrices in the vector space Rnxn. A well-known example of such a polytope is the Birkhoff polytope Bn, which is defined as the convex hull of all n x n permutation matrices [9, 8]. This polytope appears in various contexts in mathematics from optimization to statistics to enumerative combinatorics. (See, e.g., [24, 20, 21, 2, 1].) It is also a famous example of a Gorenstein polytope (see Section 5). Gorenstein polytopes turn up in connection to mirror symmetry in theoretical physics.
Guralnick and Perkinson [15] studied polytopes associated to general subgroups G of the symmetric group and proved results about their dimension, and about the diameter of their vertex-edge graph. A systematic exposition of general permutation polytopes is given in [5]. There, we studied which groups lead to affinely equivalent polytopes, we considered products of groups and polytopes, classified low-dimensional cases, and we formulated several open conjectures.
In order to get an intuition about what one can expect in general, it is instructive to consider some special classes of permutation groups. A seemingly very difficult case is when G equals the group of even permutation matrices. Just to exhibit exponentially many facets is already a daunting task, for this see [17]. Even for cyclic G we showed in [6] that these polytopes have a surprisingly complex and not yet fully understood facet structure.
In [12] Collins and Perkinson studied polytopes given by Frobenius groups. A special case is the dihedral group Dn for n odd, which was considered in more detail by Steinkamp [22]. Since Dn is the automorphism group of a regular n-gon, the cases where n is even and odd are quite different.
The most recent paper on permutation polytopes [11] focused on determining the volumes of permutation polytopes associated to cyclic groups, dihedral groups, and Frobenius groups. In order to compute the volume of P(Dn), the authors find a Gale dual combinatorial description, which they use to provide an explicit formula for the Ehrhart polynomial of P(Dn).
The dihedral group Dn is the automorphism group Aut(Cn) of a cycle Cn, and any permutation matrix M(a) of an element a G Dn commutes with the adjacency matrix A of Cn. So any point in P(Dn) commutes with A, and
P(Dn) C {M g Rnxn | M is doubly stochastic and MA = AM} .
Here, a matrix is doubly stochastic if all entries are non-negative and each row and column sum is 1. Tinhofer [24] asks, more generally, for a classification of those undirected graphs G where the two sets above are equal, i.e. where the commutation condition MA = AM already suffices to characterize the elements of P(Aut(G)) among all doubly stochastic matrices. The Birkhoff-von Neumann theorem is the special case where A is the unit matrix. Tinhofer shows that this also holds for the adjacency matrices of cycles and trees [24, Theorems 2&3].
In this note, we independently investigate P(Dn) in a more direct and elementary way. We give a complete list of its facet inequalities (Theorem 3.3, Theorem 4.1). As an application, we observe that these lattice polytopes are Gorenstein polytopes, and we get a nice description of the generating function of their Ehrhart polynomials (Theorem 5.3, Corollary 5.4).
Acknowledgments: Many results are based upon experiments and computations using
B. Baumeister et al.: Polytopes associated to dihedral groups
33
the package polymake [14] by Gawrilow and Joswig. We would like to thank the referees for carefully reading and improving the text.
2 Notation and preliminary results
Let Sn be the permutation group on n > 3 elements. Every permutation a e Sn can be represented by an n x n matrix Ma with entries ¿j,(j)CT. So the entries are in {0,1} and there
is exactly one 1 in each row and column. Notice that we apply matrices and permutations
2
from the right. We can view such a matrix as a vector in Rn . For a subgroup G of Sn we define the polytope
PG := conv(Mff | a e G).
This is a 0/1-polytope, so all matrices are in fact vertices of the polytope.
We denote by Dn the subgroup of Sn corresponding to the symmetry group of the regular n-gon, the dihedral group of order 2n. This group is generated by two elements. If n is odd, then these may taken to be the rotation p of the n-gon by 360/n degrees, and the reflection t along a line through one vertex and the midpoint of the opposite edge. If n is even, then the second generator t is instead the reflection along a line through two opposite vertices. Thus p is the permutation (1,2,..., n) and t the reflection (2, n)(3, n -1) •• • ((n + 1)/2, (n + 3)/2) if n is odd and (2,n)(3,n - 1) •• • (n/2, (n/2) + 2) if n is even.
The associated permutation polytope is the convex hull of the corresponding matrices,
DPn := conv(Mff | a e Dn). The dihedral group Dn has 2n elements
pW,
, pn 1,T, Tp, Tp2, Tp3, . . . , Tp" 1.
, wn-1 in this order. Let us give a
We label the vertices of DPn by v0,..., vn-1, w0, more convenient way to write these matrices.
Let I be the n-dimensional identity matrix and R be the n x n matrix that has 0's everywhere except at the n entries (i, j), where 0 < i, j < n — 1 and j = i +1 mod n:
R
0 1 0 0
00 00
10 01 00
Reading the matrices Ma row by row, we can identify Ma with a (row) vector in Rn . For instance, the 2 x 2 identity matrix would be identified with (10 0 1). Under this identification the vertices of DPn are (in the order given above) the rows of the 2n x n2 matrix
R0 R1 R0 R
1
R2 R
n— 1
2
R
R—1)
34
ArsMath. Contemp. 7(2014)23-29
Permuting the coordinates (corresponding to a linear automorphism of Rn ) we may write the vertices in the form
V
III ••• I
I R-2 R-4 ••• R-2(n-1)
(2.1)
Clearly, the first 2n coordinates of the vertices linearly determine the remaining coordinates. So we can project onto R2n without changing the combinatorics of the polytope. Hence, we observe that the dimension of DPn is at most 2n.
3 The situation for odd n
In this section we completely describe DPn for n odd. As it will turn out, it is useful to introduce a new polytope that will serve as a basic building block for both situations of even n and odd n.
Definition 3.1. Let Qn be the polytope defined as the convex hull of the rows of the 2n x n2 matrix
W :=
II I ... I
I R1 R2 ... Rn-1
(3.1)
While Qn differs from DPn for even n, for odd n the R2k for 0 < k < n — 1 are a permutation of the Rk for 0 < k < n — 1. So we deduce from (2.1) that, for n odd, Qn is up to a permutation of coordinates just the polytope DPn.
Proposition 3.2. For odd n, the polytopes DPn and Qn are affinely isomorphic.	□
The following theorem examines the structure of Qn for arbitrary n. For n odd, this result is a special case of Theorem 4.4 in [12].
Let us fix some convenient notation. We denote by Ar the r-dimensional simplex. We also use for any two integers s, k, the term [s]k G {0,..., k — 1} to denote the remainder of s upon division by k. The free sum of two polytopes P and P' of dimensions d and d' is the polytope
P © P' := conv({(p, 0) G Rd+d' | p G P} U {(0,p') G Rd+d' | p' G P'}).
Theorem 3.3 (Collins&Perkinson [12]). Let n be odd or even. The polytope Qn has dimension 2n — 2 and is a free sum of two copies of An_i. Taking coordinates x0,..., xn2_! for Rnxn, its affine hull is given by the equations
(l + 1)n_1
1= ^ xi	(aff)
i=ln
0 = xkn+[j]„ — x(k + 1)n+[j]„ — x(k+1)n+[j + 1]„ + x(k+2)n+[j+1]„	(Aj,k)
for 0 < l < n — 1, 0 < j < n — 2, 0 < k < n — 3.
An irredundant system of inequalities defining the polytope inside its affine hull is given by the inequalities
for 0 < i < n2 - 1.
x,> 0
B. Baumeister et al.: Polytopes associated to dihedral groups
35
Proof. All the given equations are satisfied by the vertices of Qn. There are n equations of type (aff) and n2 - 3n + 2 equations of type (Aj,k). They are easily seen to be linearly independent, so the dimension of Qn is at most 2n - 2. On the other hand, deleting any row of W leaves us with a linearly (and hence affinely) independent set of row vectors. (Observe that deleting a row leaves us with a column that contains exactly one 1.) Hence, dim(Qn) = 2n - 2 and the given equations define the affine hull of Qn in Rn .
Further, we see that every 2n - 1 of the 2n rows of W span the affine hull of Qn. So any facet of Qn has 2n - 2 vertices. Since the inequalities xj > 0 are 0 on exactly 2n - 2 of the rows, they all define facets.
In order to prove that Qn is a free sum of simplices we observe that the first n and the last n vertices define (n - 1)-dimensional simplices sitting in transversal subspaces (intersecting in the matrix corresponding to the row vector (1/n,..., 1/n)). Therefore, the combinatorial dual of Qn corresponds to the product of An—1 with itself. In particular, Qn has precisely n2 facets, so the facet description given above is complete.	□
4 The situation for even n
Recall that the join P * Q of two polytopes P and Q is the convex hull of P U Q after embedding P and Q in skew affine subspaces. The dimension of P * Q equals dim(P) + dim(Q) + 1. For instance, the join of two intervals is a tetrahedron.
Theorem 4.1. Let n be even. The polytope DPn is a join of two copies of Qn/2. In particular, its dimension is 2n - 3.
Combined with Theorem 3.3, this result gives a complete description of the facet inequalities and the affine hull equations of DPn for n even.
Proof. Permuting the coordinates, we can transform V (see (2.1)) into
III ■■■ I	III ■■■ I "
E>0 E>2 t?4	Tin—2	n0 T?2 T?4	Tin —2
R R R • • • R	R R R • • • R
Clearly, projecting onto the first nr coordinates yields an affine isomorphism of DPn onto
2
the convex hull of the rows of the 2n x ^ matrix
I I I ... I
R0 R2 R4 ... Rn-2
In the representation given by this matrix let us partition the set of 2n vertices (labelled from 0 to 2n - 1) into two sets: consisting of the n rows with even index and the n rows with odd index.
sort rows
sort columns
Then we permute the nr coordinates in such a way that in the first set of rows (correspond-
2
ing to even vertices) all nonzero entries are in the first half (i.e. in the first ^ columns).
36
ArsMath. Contemp. 7(2014)23-29
Then all nonzero entries in the second set of rows (corresponding to the odd vertices) will
2
be in the second half (i.e. in the last columns). By a permutation of the coordinates within the first half we get that the rows of even vertices yield precisely the vertex set of
Qn/2 x {0} (for 0 g R). In the same way, the coordinates in the second half can be
n2
permuted so that the rows of odd vertices equal the vertices of {0} x Qn/2 (for 0 g Rt ). Since 0 is not in the affine hull of Qn/2, we deduce that DPn is a join of two copies of Qn/2. Hence, its dimension equals 2dim(Qn/2) + 1 = 2(n - 2) + 1 = 2n - 3 by Theorem 3.3.	□
5 Lattice properties
2
DPn and Qn are lattice polytopes, i.e. their vertices lie in the lattice Zn of integral vectors. It is readily checked that all above affine isomorphisms respect lattice points. In this section, we will show that these lattice polytopes have especially nice properties which allow us to completely describe their Ehrhart h*-vectors.
A d-dimensional lattice polytope P containing 0 in its interior is reflexive, if its polar (or dual) polytope
P* := {x G Rd | (x,v) > -1 V v G P}
is again a lattice polytope (in the dual lattice). This notion was introduced by Batyrev in [3]. A generalization of this is the class of Gorenstein polytopes. A lattice polytope is a Gorenstein polytope ofcodegree k, if there is a positive integer k and an interior lattice point m in kP such that kP - m is a reflexive polytope. Such polytopes play an important role in the classification of Calabi-Yau manifolds for string theory. See [4] for basic properties. The next proposition tells us that the polytopes Qn belong to this class. The normalized volume of Rn is the volume form which assigns to the standard simplex the volume 1.
Proposition 5.1. Let n be odd or even. The polytope Qn is Gorenstein ofcodegree n and normalized volume n.
Proof. By Theorem 3.3, the point n (1,1,..., 1) is an interior point of Qn with equal integral distance 1/n to all facets, and m := (1,1,..., 1) is the unique interior lattice point in nQn. Hence nQn - m is a reflexive polytope.
By Theorem 3.3, all facets of Qn are simplices of facet width 1, hence they are all unimodular. As we have seen, multiplying by n gives (up to translation) a reflexive polytope with the unique interior lattice point m = (1, 1, . . . , 1). The normalized volume of nQn is the sum of the volumes of n2 pyramids over facets with apex m. But in nQn each facet has normalized volume n2n-3, and the apex has lattice distance 1 from the facet, so each pyramid has normalized volume n2n-3. There are n2 of these pyramids, so the normalized volume of nQn equals n2n-1. Dividing by n2n-2 to get from nQn back to Qn gives the normalized volume n of Qn.	□
A polytope P is compressed if every so-called pulling triangulation is regular and uni-modular. Equivalently, P is compressed if for any supporting inequality a4x < b with a primitive integral normal a, i.e. with a normal vector whose entries are integers and which is not an integral multiple of some other integer vector, the polytope is contained in the set {x | b - 1 < a1 x < b}. For a more detailed explanation of these terms we refer to [13].
B. Baumeister et al.: Polytopes associated to dihedral groups
37
This property has strong implications on the associated toric ideal, see e.g. [23]. The next proposition follows immediately from Theorem 1.1 of [19] and Theorem 3.3.
Proposition 5.2. Let n be odd or even. The polytope Qn is compressed.	□
The Ehrhart polynomial LP (k) := |kP nZd| ofa d-dimensional lattice polytope counts the number of integral points in integral dilates of P. It is well known that the generating function of LP is given by
E Lp (m)tm =
m> 0	V	'
for some polynomial h* of degree at most d with integral non-negative coefficients, see [7]. Hence, determining the Ehrhart polynomial is equivalent to finding the h*-vector (also called the ¿-vector) of coefficients of h* (t). As is well-known, P is Gorenstein if and only if the h*-vector is symmetric. The following theorem shows that in our case this vector has a particularly nice form.
Theorem 5.3. Letn be oddor even. The h*-vectorof Qn satisfies h* = 1 for 0 < i < n —1 and h* =0 otherwise.
Proof. Since the codegree of Qn is n and its dimension is 2n — 2 by Theorem 3.3, the maximal non-zero entry of the h*-vector has to be hn_i, see [7]. By a theorem of Bruns and Römer [10] we know that the h* -vector of a Gorenstein polytope that has a regular unimod-ular triangulation is symmetric and unimodal. In particular, h* > 1 for i = 0,..., n — 1. Since by Proposition 5.1 the sum of the entries of the h*-vector equals n, the statement follows.	□
In particular, if n is odd, the previous result describes the h*-vector of DPn. Finally, let us deal with the even case.
Corollary 5.4. Let n be even. The h*-vector of DPn equals
(1,2,3,...,n — i,n,n — 1,..., 2,1).
In particular, the polytope DPn is Gorenstein of codegree n and normalized volume n2/4.
Proof. By the proof of Theorem 4.1, DPn convex hull of the rows of
is given up to coordinate permutation as the
W 0
^ 0 W
where W is the n x (f)2 matrix whose rows are the vertices of Qn as given in (3.1). The integral linear functional which sums the first f coordinates evaluates to 1 on the first
f rows, and to 0 on the second half. Hence, the two copies of Q n (say, Pi x {0} and
n 2
{0} x P2) have lattice distance 1 in the lattice Zn aff DPn. In other words, there is
an affine isomorphism respecting lattice points which maps DPn onto the convex hull of
n
P1 x {0} x {1} and {0} x P2 x {0} in R+1. Therefore, the statement follows from the well-known fact [7, Example 3.32] that in this case the h*-polynomial equals the product of the h* -polynomials of P1 and P2.	□
39
ArsMath. Contemp. 7(2014)23-29
6 Substructures
In [5] the authors discussed which subgroups of a permutation group yield faces of P (G). An obvious class of such subgroups are stabilizers:
Take a partition [n] := {1,... ,n} = [J Ii. Then the polytope of the stabilizer of the subsets Ii
stab(G; (Ii)i) := {a G G | a(Ii) = Ii for all i} < G
is a face of P(G). The authors conjecture that there are no other examples.
Conjecture 5.8 [5] Let G < S„. Suppose H < G is a subgroup such that P(H) ^ P(G) is a face. Then H = stab(G; (Ii)i) for a partition [n] = [J Ii.
We have verified the conjecture for G = Sn as well as for cyclic subgroups G < Sn, see Proposition 5.9 of [5]. Meanwhile Jessica Nowack and Daniel Heinrich studied this question for the dihedral groups in their Diploma theses.
Proposition 6.1. (Heinrich, Nowack [16, 18]) Conjecture 5.8 holds for G = Dn < Sn for every n.
Sketch of the proof. For n odd Heinrich first shows that, if H is the subgroup of all rotations of G, then PH is not a face of PG. The remaining subgroups are precisely the stabilizers of their orbits, see Theorem 7.1.1 of [16].
For n even the main work is to show that the subgroup of all rotations, the subgroup of the squares of the rotations and finally the subgroup generated by the squares of the rotations and by the reflections through two edges are precisely those subgroups H of G for which PH is not a face of PG. Nowack shows that the remaining subgroups are precisely the stabilizers of their orbits, see Section 4.2 of [18].	□
References
[1]	C. A. Athanasiadis, Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, J. Reine Angew. Math. 583 (2005), 163-174.
[2]	A. Barvinok and T. Stephen, The distribution of values in the quadratic assignment problem, Math. Oper. Res. 28(1) (2003), 64-91.
[3]	V. V. Batyrev, Dual polyhedra and mirror symmetry for Calabi-Yau hypersurfaces in toric varieties, J. Algebraic Geom. 3(3) (1994), 493-535.
[4]	V. Batyrev and B. Nill, Combinatorial aspects of mirror symmetry, in: M. Beck et al. (eds.), Integer points in polyhedra—geometry, number theory, algebra, optimization, statistics, Proceedings of the AMS-IMS-SIAM joint summer research conference (Contemporary Mathematics 452), Snowbird, UT, USA, June 11-15, 2006, American Mathematical Society, Providence, RI, 2008, 35-66.
[5]	B. Baumeister, C. Haase, B. Nill and A. Paffenholz, On permutation polytopes, Adv. Math., 222(2) (2009), 431-452.
[6]	B. Baumeister, C. Haase, B. Nill and A. Paffenholz, Permutation polytopes of cyclic groups, September 2011, preprint, arXiv:1109.0191.
[7]	M. Beck and S. Robins, Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2007.
B. Baumeister et al.: Polytopes associated to dihedral groups
38
[8]	L. J. Billera and A. Sarangarajan, The combinatorics of permutation polytopes, in: L. J. Billera et al. (eds.), Formal power series and algebraic combinatorics, Séries formelles et combinatoire algébrique 1994, Invited lectures presented at the 6th international DIMACS workshop, May 23-27, 1994, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 24, American Mathematical Society, Providence, RI, 1996, 1-23.
[9]	R. A. Brualdi and P. M. Gibson, Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function, J. Comb. Theory, Ser. A 22, (1977) 194-230.
[10]	W. Bruns and T. Römer, h-vectors of Gorenstein polytopes, J. Comb. Theory, Ser. A 114(1) (2007), 65-76.
[11]	K. Burggraf, J. De Loera and M. Omar, On volumes of permutation polytopes, 2011, preprint, arXiv:1103.0039.
[12]	J. Collins and D. Perkinson, Frobenius polytopes, January 2004, preprint arXiv: 1102.0988.
[13]	J. A. De Loera, J. Rambau and F. Santos, Triangulations. Structures for algorithms and applications, Algorithms and Computation in Mathematics 25, Springer, Berlin, 2010.
[14]	E. Gawrilow and M. Joswig, polymake: a framework for analyzing convex polytopes, in: Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser, Basel, 2000, 43-73.
[15]	R. M. Guralnick and D. Perkinson, Permutation polytopes and indecomposable elements in permutation groups, J. Comb. Theory, Ser. a 113(7) (2006), 1243-1256.
[16]	D. Heinrich, Beweis der Seitenvermutung für Permutationspolytope vom Type D2n mit ungeradem n, Diploma thesis, FU Berlin, October 2011.
[17]	J. Hood and D. Perkinson, Some facets of the polytope of even permutation matrices, Linear Algebra Appl. 381 (2004), 237-244.
[18]	J. Nowack, Beweis der Seitenvermutung für Permutationspolytope vom Typ D2n mit geradem n, Diploma thesis, FU Berlin, Mai 2011.
[19]	H. Ohsugi and T. Hibi, Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, Proc. Am. Math. Soc. 129(9) (2001), 2541-2546.
[20]	S. Onn, Geometry, complexity, and combinatorics of permutation polytopes, J. Comb. Theory, Ser. a 64(1) (1993), 31-49.
[21]	I. Pak, Four questions on Birkhoff polytopes, Ann. Comb. 4(1) (2000), 83-90.
[22]	H. Steinkamp, Convex polytopes of permutation matrices, Bachelor thesis, The Division of Mathematics and Natural Sciences, Reed College, 1999.
[23]	B. Sturmfels, Gröbner bases and convex polytopes, University Lecture Series (vol. 8), American Mathematical Society, Providence, RI, 1996.
[24]	G. Tinhofer, Graph isomorphism and theorems of Birkhoff type, Computing 36 (1986), 285300.