, , November 27, 2006

Let

G

be a subgroup of

S_{n}

, the symmetric group on

{1, 2, . . ., n}

. Via the usual representation of

G

as a group of

n \times n

permutation matrices, each element of

G

may be considered as an element of

R^{n^{2}}

. The convex hull in

R^{n^{2}}

of the elements of

G

P (G)

, the permutation polytope associated with

G

. Permutation polytopes and their linear projections have been studied extensively due to their connection to problems in combinatorial optimization [5] , [6] , [20] , [24] . The most well-known example is the case where

G = S_{n}

with corresponding permutation polytope called the

n

-th Birkhoff polytope or the

n

-th assignment polytope [9] , [10] , [24] . Even here there are open problems [22] ; for instance, its volume is known only up to

n = 10

[7] . Some newer applications of permutation polytopes are to group resolutions [13] and communications networks [17] , [23] .

The main concern of this paper is to establish links between (algebraic) properties of an arbitrary permutation group

G

and (geometric) properties of its corresponding permutation polytope

P (G)

. We are especially interested in ways in which the transitivity of

G

is reflected in its polytope. First, Theorem 2.1 , shows that every element of a transitive permutation group can be written as a product of at most two so-called indecomposable elements (see § 2 for definitions). The geometric consequence is Corollary 3.7 : if

G

has

t

non-trivial orbits, then the diameter of

P (G)

, i.e., the diameter of the edge graph of

P (G)

, is bounded by

min {2 t, ⌊ n / 2 ⌋}

. Thus, if

G

is transitive, the diameter of

P (G)

is at most

2

. This generalizes previous work establishing the diameters of the Birkhoff polytopes [4] , [25] and the diameters of the polytopes corresponding to the groups of even permutations [11] . In the language of Babai et al. [3] , we have bounded the diameter of the group

G

with respect to the set of generators consisting of its indecomposable elements.

Corollary 3.7 relies on Theorem 3.5 characterizing the smallest face of a permutation polytope containing two prescribed vertices (group elements) in terms of their cycle structure. In particular, we characterize the edges of a permutation polytope, as previously known for the Birkhoff polytopes [21] and for the polytopes corresponding to the groups of even permutations [11] . The special case

G = S_{n}

in Theorem 3.5 is Proposition 2.1 in [8] .

The other main result concerning transitivity is Corollary 3.4 , showing that the dimension of

P (G)

is bounded by

(n - 1)^{2}

with equality if and only if

G

2

-transitive. The dimension of the

n

-th Birkhoff polytope is known to equal the maximum value,

(n - 1)^{2}

, by an easy calculation in linear algebra. With more work, one may similarly show that the maximum dimension is achieved when

G

is the collection of all even permutations and

n \geq 4

[11] . Corollary 3.4 generalizes these results and provides a conceptual explanation.

In the final section of the paper, we generalize the results of [22] about the mixing time of random walks on these polytopes. This says that random products of indecomposable elements tend to the uniform distribution very quickly for

G

primitive (Pak [22] handles the case of the Birkhoff polytope).

The results in this paper stem from systematic experimentation using the computer programs GAP [14] for group theory and Polymake [15] for polytopes.

2 Permutation Groups

Let

G

be a permutation group acting faithfully on a (finite) set

X

We say

g \in G

is indecomposable if

g \neq x y

where

x, y

are nontrivial elements of

G

and

M (x) \cap M (y)

is empty, where

M (x)

is the set of points of

X

moved by

x

. Let

F (x)

be the set of fixed points of

x

and

f (x) = | F (x) |

We shall prove:

Theorem 2.1. Let

G

be transitive on

X

. Then every element of

G

is a product of at most

2

indecomposable elements.

In fact, for inductive purposes, it is better to prove a slightly stronger result:

Theorem 2.2. Let

G

be transitive on

X

. Then every element of

G

is a product of two elements, each indecomposable and at least one fixed point free.

We will prove this result in the next few subsections. We first show that it suffices to assume that

G

acts primitively on the set

X

(i.e.

preserves no nontrivial partition of

X

We then show that the result holds when the group is primitive and not almost simple (recall a group is almost simple if it has a unqiue minimal normal subgroup that is a nonabelian simple group).

Finally, we show that in the almost simple case, aside from the case that

G

contains

A l t (X)

, every element is indecomposable (whence the result follows since fixed point free elements in a finite transitive permutation group always exist). The result in the case

G = A l t (X)

S y m (X)

is elementary.

We do have to invoke the classification of finite simple groups to handle the case that

G

is almost simple. The key result we use is the classification of primitive permutation groups containing a nontrivial element with

f (x) \geq | X | / 2

We first point out some easy consequences.

Lemma 2.3. Suppose that

X = Y \cup Z

is a finite

G

-set with

Y

and

Z

invariant under

G

. Let

N

be the normal subgroup of

G

acting trivially on

Y

. If every element of

G / N

acting on

Y

can be written as a product of

r

indecomposables and every element of

N

can be written as a product of

s

indecomposables, then every element of

G

is a product of

r + s

indecomposables.

Proof. If $g \in G$ , let $g_{Y}$ denote $g$ considered as permutation on $Y$ .
We claim that if $g \in G$ and $g_{Y}$ is indecomposable, then $g n$ is indecomposable for some $n \in N$ . Proof of Claim: If $g$ is indecomposable, we are done. If not, write $g = h u$ where $M (h) \cap M (u)$ is empty and $h$ is not in $N$ . Since $g_{Y}$ is indecomposable, $h_{Y} = g_{Y}$ and $u \in N$ . Thus, $h \in g N$ is indecomposable.
The claim implies that we can write $g \in G$ as a product of $r$ indecomposables (or fewer) times an element of $N$ . By assumption, the element in $N$ can be written as a product of $s$ indecomposables (in $N$ and thus also in $G$ ). □

Corollary 2.4. If

G \leq S_{n}

, then every element of

G

can be written as a product of

2 t

indecomposables where

t

is the number of nontrivial orbits of

G

Corollary 2.5. If

G \leq S_{n}

, then every element of

G

can be written as a product of

⌊ n / 2 ⌋

indecomposables.

Proof. By induction and the lemma above, it suffices to consider the case that $G$ is transitive. By the theorem, the result holds for $n \geq 4$ .
Inspection shows that for $n \leq 3$ , every nontrivial element is indecomposable.
□

2.1 Reduction to the Primitive Case

Let

G

be a group acting faithfully and transitively on the finite set

X

. Let

n = | X | > 1

Lemma 2.6. Let

Y : = {X_{1}, \dots, X_{m}}

be a nontrivial

G

-invariant partition of

X

. Let

N

be the normal subgroup of

G

preserving each

X_{i}

. Let

g \in G

(1) If $g N$ is fixed point free and indecomposable on $Y$ , then every element in $g N$ is fixed point free and indecomposable on $X$ .
(2) If $g N$ is indecomposable on $Y$ , then there is some element in $g N$ that is indecomposable on $X$ .

Proof. We prove both statements simultaneously. Reordering if necessary, we may assume that $g$ moves the sets $X_{1}, \dots, X_{e}$ and fixes the other $X_{i}$ . Assume also that $g N$ is indecomposable on $Y$ .
Suppose that $g = x y$ where $M (x) \cap M (y)$ is empty. Then $g N = x N y N$ and $x N$ and $y N$ cannot move a common $X_{i}$ . Since $g N$ is indecomposable, we may assume that $g N = x N$ and $y N = N$ . Thus, $x \in g N$ and the second statement holds.
Moreover, since $x$ and $y$ share no moved points, $y$ must be trivial on each block moved by $g$ . So if $g N$ has no fixed points on $Y$ , then $y = 1$ and $g = x$ is indecomposable. □

An immediate consequence is:

Corollary 2.7. Suppose that

G

is a counterexample to Theorem 2.2 and that

Y : = {X_{1}, \dots, X_{m}}

is a nontrivial

G

-invariant partition of

X

. Let

N

be the normal subgroup of

G

acting trivially on

Y

. Then

G / N

acting on

Y

is also a counterexample to the Theorem 2.2 .

Note that it is possible that the partition exists and

N = 1

. This shows that a minimal counterexample (with respect to

| X |

) must be a primitive group. We deal with this case in the next two subsections.

2.2 Primitive Groups I

In this subsection, we assume that

G

is not almost simple and acts primitively (and faithfully) on the finite set

X

of cardinality

n

The structure of finite primitive groups is quite constrained. See [2] for a detailed description.

Theorem 2.8. Assume that

G

contains a regular normal subgroup

N

. Then one of the following holds:

(1) Every element of $G$ is indecomposable.
(2) $N$ is an elementary abelian $2$ -group of order $2^{a} \geq 4$ and $G = N H$ where $H$ is a subgroup of $G L (a, 2) = A u t (N)$ acting irreducibly on $N$ and containing transvections.

Moreover,

G

satisfies the conclusion of Theorem 2.2 .

Proof. It follows by [2] that $N$ is a direct product of isomorphic copies of a simple group $L$ . If $g \in G$ has a fixed point, then as $g$ -set, we can identify $X$ with $N$ and the fixed points of $g$ are identified with $C_{N} (g)$ . Unless $| L | = 2$ , any proper subgroup of $N$ has index at least $3$ , so for $1 \neq g$ , the proportion of fixed points is at most $1 / 3$ . Thus, $M (x) \cap M (y)$ is nonempty for any two nontrivial elements in $G$ . This proves (1).
So $N$ is an elementary abelian $2$ -group of order $2^{a}$ . If $a = 1$ , then $G$ is cyclic of order $2$ and the result hold. If $a > 1$ , the argument of the previous paragraph applies and we see that $f (g) \leq n / 2$ with equality if and only if $g$ induces a transvection acting on $N$ . This proves (2).
So it suffices to prove the last statement in the case $G = N H$ where $| N | = n = 2^{a} \geq 4$ and $G = N H$ with $H$ acting irreducibly and faithfully on $N$ and containing transvections. Note that if $x \in G$ is decomposable, then $x = u v$ where $u, v$ are involutions fixing precisely one half the points of $X$ . Moreover, $u$ and $v$ commute and the fixed point sets of $u$ and $v$ must be disjoint. Thus, $x$ is a fixed point free involution.
If $a = 2$ , then $G = S_{4}$ and the result holds by inspection. So assume that $a > 2$ .
So let $g \in G$ . Choose $h \in G$ with $h$ of order $4$ and $h^{2} \in N$ with $h N$ a transvection in $G / N$ . So $h$ is fixed point free (since $h^{2}$ is) and indecomposable (since it has order greater than $2$ ).
Now write $g = h (h^{- 1} g)$ . So $h$ is indecomposable and fixed point free. We just have to ensure that $h^{- 1} g$ is indecomposable. If this is decomposable, then in particular $h^{- 1} g$ is an involution and so $h$ inverts $g$ modulo $N$ . If $g N$ is nontrivial, there is certainly some $h$ not inverting $g N$ . If $g = 1$ , any $h$ works. So assume that $g$ is a nontrivial element of $N$ . Since $H$ acts irreducibly on $N$ and contains transvection, we can choose two noncommuting transvections $h_{1}$ and $h_{2}$ . It follows that $h_{1} h_{2}$ has order $3$ and centralizes a subgroup $N_{0}$ of $N$ of index $4$ . Now set $h = h_{1} h_{2} v$ where $1 \neq v \in N_{0}$ .
So $h^{3} = v$ is fixed point free. Thus, $h$ is indecomposable and fixed point free. Moreover, $h^{- 1} g$ has order a multiple of $3$ and so is indecomposable.
This completes the proof. □

There are few irreducible groups containing transvections. See [19] .

We can now handle all primitive groups other than the almost simple groups.

Theorem 2.9. Assume that

G

acts faithfully and primitively on the set

X

of cardinality

n > 1

. Assume that

G

is not almost simple. Every element of

G

can be written as a product of two indecomposable elements, one of which is fixed point free.

Proof. By the previous result, we may assume that $G$ does not contain a regular normal subgroup. We may also assume that some nontrivial element of $G$ fixes at least $n / 2$ points. It follows by the structure of primitive groups [2] , the previous result and [16] that $G$ preserves a Cartesian product structure on $X$ .
More precisely, we can write $X = X_{1} \times \dots \times X_{m},$ where $m > 1$ , $| X_{i} | = e \geq 5$ and $G \leq T : = S_{e} ≀ S_{m} = W . S_{m}$ where $W = S_{e} \times \dots \times S_{e}$ acting coordinatewise on $X$ and $S_{m}$ permutes the coordinates. Furthermore, $G$ has a unique minimal normal subgroup $N : = L_{1} \times \dots \times L_{m}$ where $L_{i} \sim = L$ is a nonabelian simple and $L_{i}$ acts on $X_{i}$ and trivially on $X_{j}$ for $j \neq i$ .
Let $W_{i}$ be the $i$ th copy of $S_{e}$ in $W$ .
We claim that $g \in G$ is decomposable implies $g \in W_{i}$ for some $i$ . It suffices to show that this is the case for $T$ . Suppose that $x, y \in T$ are nontrivial elements and $M (x) \cap M (y)$ is empty. Suppose that $x$ acts on an $X_{i}$ and $y$ on an $X_{j}$ with $j \neq i$ . Choose $a \in X_{i}$ moved by $x$ and $b \in X_{j}$ moved by $y$ . Then any point of $X$ whose $i$ th coordinate is $a$ and $j$ th coordinate is $b$ is moved by $x$ and $y$ , a contradiction.
This shows that if $x$ and $y$ are both in $W$ , then they are both in $W_{i}$ for some $i$ and so also $x y$ . If neither $x$ nor $y$ is in $W$ , then $x$ and $y$ each move at least $n - n / e > n / 2$ points and so $M (x) \cap M (y)$ is nonempty. Finally, suppose that $x$ is not in $W$ and $y \in W$ . Arguing as above, we see that it suffices to consider the case that $x$ permutes the $X_{i}$ transitively. Say $y$ is nontrivial on $X_{1}$ and moves $a \in X_{1}$ . Then $x$ cannot fix all points of $X$ with first coordinate $a$ and so $M (x) \cap M (y)$ is empty.
This proves the claim.
We now complete the proof of the result.
Let $g \in G$ . If $g$ is not in $W$ , then choose $h \in N$ with $h$ not in $N \cap W_{i} = L_{i}$ for any $i$ and $h$ fixed point free (just choose $h_{1} \in L_{1}$ fixed point free and $h_{2}$ nontrivial). Then $g = h (h^{- 1} g)$ is the desired decomposition ( $h^{- 1} g$ is not in $W$ and so indecomposable). If $g \in W$ , we choose a similar $h$ guaranteeing that $h^{- 1} g$ is not in $W_{i}$ for any $i$ .
□

2.3 Almost Simple Groups

We now consider almost simple groups. So

G

is almost simple group and has socle

S

and acts transitively on

X

of cardinality

n > 1

We first deal with the cases

G = A_{n}

S_{n}

. Note that the lemma is just the theorem for these groups.

Lemma 2.10.

(1) Any element of $S_{n}$ can be written as a product of an $n$ -cycle and a $k$ -cycle for some $k$ .
(2) If $n$ is even, then every element of $A_{n}$ can be written as product $x y$ where $x$ has exactly two orbits each of even length and $y$ is a $k$ -cycle or $y$ has precisely two nontrivial orbits each of even length.

Proof. Suppose that $g$ has $k$ orbits.
Let $h$ be a $k$ -cycle moving precisely one point in each $g$ -orbit. Then $g h$ is an $n$ -cycle, whence (1) holds.
Now suppose that $n$ is even and $g \in A_{n}$ . If $g = 1$ , the result is clear. Otherwise, write $g = x y$ where $x$ is an $n$ -cycle and $y$ is a $k$ -cycle.
Necessarily $k$ is even and the construction above shows that we can take $k < n$ .
Let $t$ be a transvection moving at least $1$ point fixed by $y$ . Then $x t$ has precisely $2$ orbits and we can pick $t$ so that each of the orbits is even. Then $t y$ is either a $k + 1$ cycle (if $t$ and $y$ are not disjoint) or has two nontrivial orbits (of length $2$ and $k$ ). So $g = (x t) (t y)$ , whence (2) holds. □

There are a few other special cases that we want to separate out.

Lemma 2.11. Let

G = A_{n}

S_{n}

with

n \geq 5

acting on

X

, the set of

k

-sets for some

k

with

1 < k < n / 2

. Then every element of

G

is indecomposable.

Proof. We show that for $x, y$ nontrivial, $M (x)$ and $M (y)$ have a nonempty intersection. Let $Y = {1, 2, \dots, n}$ . If $x \in G$ and $j \in Y$ , we write $x j$ for the image of $j$ under $x$ .
First suppose that $x$ and $y$ move a common point in the natural representation. So we may assume that $x$ and $y$ each move $1$ . Let $D$ be a $k$ -set containing $1$ but missing $x 1$ and $y 1$ . Then $x$ and $y$ both move $D$ .
Suppose that $x$ and $y$ move no common point in $Y$ . So we may assume that $x$ moves $1$ and $y$ moves $2$ . Let $D$ be a $k$ -set containing $1, 2$ but not containing $x 1$ and $y 2$ . Then $x$ and $y$ both move $D$ . □

Lemma 2.12. Let

G = S p (2 d, 2)

with

d \geq 3

. Let

X

be the coset space

G / H

where

H = O^{-} (2 d, 2)

(note that this is the set of nondegenerate hyperplanes of

-

type in the

2 d + 1

dimensional orthogonal module for

G

). Every element of

G

is indecomposable on

X

Proof. Suppose that $M (x) \cap M (y)$ for $x, y$ nontrivial in $G$ . It is easy to see (cf [16] ) that every nontrivial element other than a transvection moves more than $| X | / 2$ elements. So we choose notation so that $x$ is a transvection and $y \neq x$ . Let $P = C_{G} (x)$ . Then $P$ is a maximal parabolic subgroup of $G$ . Then $y$ fixes each coset of $H$ moved by $x$ .
The same is true for any $P$ -conjugate of $y$ and so $J : = 〈 y^{P} 〉$ does as well.
So $P$ normalizes $J$ . Now $J$ is proper in $G$ and so as $G$ is simple and $P$ is maximal, $J$ is a nontrivial normal subgroup of $P$ . The subgroup generated by $x$ is the unique minimal normal subgroup of $P$ and so $x \in J$ . However, $x$ certainly moves all the points of $M (x)$ and this contradiction completes the proof. □

Lemma 2.13. Let

G^{ε} = O^{ε} (2 d, 2)

with

d > 2

. Let

X

be the set of singular vectors (if

ε = -

) or the set of nonsingular vectors (if

ε = +)

. Every element of

G^{ε}

is indecomposable on

X

Proof. Let $J = S p (2 d, 2)$ and $Y$ the $J$ -set described in the previous lemma. Note that $G^{ε}$ is a subgroup of $J$ and so acts on $Y$ . If $ε = +$ , then $Y \sim = X$ at $G^{+}$ -sets. Also, $G^{-}$ fixes one point of $Y$ and the remaining orbit is isomorphic to $X$ as a $G^{-}$ set. Thus, the result follows from the previous lemma. □

Now, we can apply [16] which asserts that if

G

is an almost simple group acting primitively on a set

X

and some element fixes at least half the points, then

(G, X)

is one of the cases listed in the lemmas above.

Theorem 2.14. Let

B

be an almost simple group acting primitively on

X

. Then either every element of

G

is indecomposable or

G

contains

A l t (X)

We can push this a bit further by weakening the primitive assumption.

Theorem 2.15. Let

G

be an almost simple group acting transitively and faithfully on a set

X

. Let

H

be a point stabilizer. Then either every element of

G

is indecomposable or

G = A_{m}

S_{m}

for some

m \geq 5

Proof. If $G$ is primitive on $X$ , this is the previous result. Suppose that $G$ is not primitive on $X$ and so element is decomposable on $X$ . Let $S$ be the socle of $G$ . If $G \neq H S$ , then every element outside $H S$ is fixed point free and we can replace $G$ by $H S$ . Let $Y = {X_{1}, \dots, X_{t}}$ be a nontrivial $G$ -invariant partition of $X$ with $G$ primitive on $Y$ . Then $g$ decomposable on $X$ implies that $g$ is indecomposable on $Y$ , whence $G = A l t (Y)$ or $S y m (Y)$ by the previous result. This completes the proof. □

Note that the previous result actually gives more information with a little more effort – when

G

is an alternating or symmetric group, essentially the only maximal subgroup containing

H

is unique and is the the stabilizer of a point in the natural permutation representation (being slightly careful when

m = 6

Combining the result on almost simple groups allows us to state a more precision version of Theorem 2.9 . Note that in the proof of that theorem, we saw that the only decomposable elements were contained in a component

L

G

and in particular, the component would have to be a simple group that admits an action with decomposable elements.

Indeed, it follows by [2] that this action corresponds to a primitive action of

N_{G} (L) / C_{G} (L)

and so by the result on almost simple groups

L = A_{d}

This result will be useful in the final section.

Theorem 2.16. Let

G

be a primitive subgroup of

S_{n}

. One of the following holds:

(1) Every element of $G$ is indecomposable;
(2) $G = A_{n}, n > 3$ or $S_{n}, n > 2$ ;
(3) $n = d^{t}$ with $d \geq 5$ and $t \geq 2$ , $G \leq S_{d} ≀ S_{t}$ and $G$ contains ${A_{d}}^{t}$ ;
(4) $n = 2^{a}, a > 2$ , $G$ contains a regular normal elementary abelian subgroup $N$ and $G = N H$ where $H$ is a point stabilizer and $H$ is an irreducible subgroup of $A u t (N)$ containing transvections.

3 Permutation Polytopes

Now let

G

be any finite group, and let

ν : G \to G L (R^{n})

be a representation.

The representation polytope associated with

ν

is the convex hull of the image of

ν

, a subset of

E n d_{R} (R^{n}) \approx R^{n^{2}}

P (ν) : = c o n v {ν (g) \in R^{n^{2}} | g \in G} .

For each

g \in G

, left multiplication by

ν (g)

defines a linear automorphism of

R^{n^{2}}

sending

P (ν)

to itself and sending the image of the identity element of

G

ν (g)

. Hence, the vertices of

P (ν)

are symmetric and are precisely the images of elements of

G

G

a subgroup of the symmetric group,

S_{n}

, we write

P (G)

for

P (ν_{G})

where

ν_{G}

is the natural representation of

G

as a group of

n \times n

permutation matrices. In this case, we also identify each

g \in G

with its image,

ν (g) \in R^{n^{2}}

. The polytope,

P (G)

, is called the permutation polytope associated with the permutation group

G

In this part of the paper, we establish two main results. First, we show that as

G

varies over subgroups of

S_{n}

, the corresponding polytope has maximal dimension

(n - 1)^{2}

exactly when

G

2

-transitive. Next, we characterize some faces of

P (G)

and give a bound on the diameter of the edge graph of

P (G)

3.1 Dimension

We use the following standard theorem from representation theory:

Theorem 3.1 (Frobenius and Schur [12] , §27.8). Let

G

be a finite group,

K

an algebraically closed field, and

ρ_{i} : G \to G L (K^{n_{i}})

for

i = 1, . . ., k

a collection of pairwise non-isomorphic irreducible matrix representations of

G

. Let

x_{i j}^{(r)}

denote the coordinate functions of

ρ_{r}

for each

r

. Then the set

{x_{i j}^{(r)}}_{i, j, r}

of all coordinate functions is linearly independent over

K

Let

ν = \oplus ν_{i}^{a_{i}}

be the irreducible decomposition of

ν

over the complex numbers.

Theorem 3.2. The dimension of the representation polytope

P (ν)

dim P (ν) = \sum_{ν_{i} \neq 1} (deg ν_{i})^{2},

the sum taken over all non-trivial components

ν_{i}

, not counting multiplicities.

Proof. Let

C [G]

denote the group algebra, and let

ν_{i}

be a representation of

G

on a complex vector space

V_{i}

for each

i

. There is a natural algebra homomorphism

Γ_{ν} : C [G] \to \oplus_{i} E n d_{C} (V_{i})^{a_{i}} \subset E n d_{C} (C^{n})

determined by

g \mapsto ν (g)

for each

g \in G

and extending linearly. The mapping

Γ_{ν}

further factors through the inclusion

\begin{matrix} \oplus_{i} E n d_{C} (V_{i}) & \to & \oplus_{i} E n d_{C} (V_{i})^{a_{i}} \end{matrix}

\begin{matrix} \oplus_{i} φ_{i} & \mapsto & \oplus_{i} φ_{i}^{a_{i}} \end{matrix}

The resulting mapping of

C [G]

into

\oplus_{i = 1}^{k} E n d (V_{i})

is a surjection by Theorem 3.1 .

Restricting

Γ_{ν}

R [G]

, the polytope

P (ν)

is the convex hull of the image of

G

. Hence, the dimension of

P (ν)

will be the dimension of the image of

Γ_{ν}

if the polytope contains the zero vector in its affine span and will be one less, otherwise. So it suffices to show that

P (ν)

does not contain

\vec{0}

in its affine span,

a f f (P (ν))

, if and only if

ν

contains the trivial representation as an irreducible factor.

First, suppose

\vec{0} \notin a f f (P (ν))

. The vector

\frac{1}{| G |} \sum_{g \in G} ν (g)

is an element of

P (ν)

, hence nonzero, and its linear span is clearly

G

-invariant; thus,

ν

contains the trivial representation. Conversely, suppose that

ν

contains the trivial representation. Then there exists a nonzero

w \in C^{n}

such that

ν (g) (w) = w

for all

g \in G

. Given an arbitrary element

x = \sum_{g \in G} a_{g} ν (g)

a f f (P (ν))

, we have

x (w) = (\sum a_{g}) w = w

, hence,

x \neq \vec{0}

, as required. □

Corollary 3.3. If

ν

is a faithful representation,

P (ν)

is a simplex if and only if each irreducible representation of

G

appears up to isomorphism as a component in the irreducible decomposition of

ν

Proof. Let $ν = \oplus ν_{i}^{a_{i}}$ be the irreducible decomposition of $ν$ over $C$ .
The polytope $P (ν)$ is a simplex if and only if its dimension is one less then the number of vertices. In light of Theorem 3.2 , the condition is equivalent to $| G | - 1 = \sum_{ν_{i} \neq 1} (deg ν_{i})^{2}$ . However, a basic theorem of representation theory says that $| G | = \sum_{τ} (dim τ)^{2}$ where the sum is over a full set of representatives of the isomorphism classes of irreducible representations of $G$ (including the trivial representation). □

ν

is not faithful, let

H = {g \in G | ν (g) = 1}

. In this case,

P (ν)

is a simplex if and only if the irreducible decomposition of

ν

over

C

contains each irreducible representation of

G

trivial on

H

Corollary 3.4. Let

G \leq S_{n}

be a subgroup having

t

orbits.

(1) $dim P (G) \leq (n - t)^{2}$ with equality if and only if $ν_{G}$ has at most one non-trivial factor in its irreducible decomposition;
(2) $dim P (G) \leq (n - 1)^{2}$ with equality if and only if $G$ is $2$ -transitive.
(3) The dimension of the Birkhoff polytope, $B_{n}$ , is $(n - 1)^{2}$ for all $n \geq 1$ .
(4) The dimension of the polytope of even permutation matrices, $A_{n}$ , is $(n - 1)^{2}$ for $n \geq 4$ .

Proof. Consider the irreducible decomposition of the permutation representation $ν_{G} = \oplus_{i} ν_{i}^{a_{i}}$ over $C$ . It is well-known from representation theory that the number of copies of the trivial representation appearing in $ν$ is the number of orbits, $t$ ([12] §32.3). Let $ν_{1}, . . ., ν_{k}$ be the non-trivial factors of $ν_{G}$ . Then $\sum_{i = 1}^{k} deg ν_{i} = n - t$ and by Theorem 3.2 , the dimension of $P (G) = \sum_{ν_{i} \neq 1} (deg ν_{i})^{2}$ . The sum is maximized when $k \leq 1$ . This proves part 1 .
For part 2 , by standard representation theory of permutation groups, $G$ is $2$ -transitive if and only if $ν_{G} = 1 + {\tilde{ν}}_{G}$ for some irreducible ${\tilde{ν}}_{G}$ ([12] §32.5). Parts 3 and 4 then follow since the relevant groups are $2$ -transitive. □

3.2 Faces

Let

G \leq S_{n}

be a permutation group, and identify elements of

G

with

n \times n

permutation matrices as usual. For

g, h \in G

, write

h ≼ g

if the set of cycles of

h

is a subset of the set of cycles of

g

(so

M (h) \cap M (h^{- 1} g)

is empty). The element

g

is indecomposable when

h ≼ g

always implies

h

is the identity or

g

Theorem 3.5. The smallest face of

P (G)

containing

g, h \in G

F_{{g, h}} : = c o n v {h k \in G | k ≼ h^{- 1} g} .

In particular, there is an edge connecting

g

and

h

if and only if

h^{- 1} g

is indecomposable.

Proof. By symmetry, we may assume that $h$ is the identity, $e$ , and show that the smallest face containing $g$ and $e$ is $c o n v {k \in G | k ≼ g}$ . If $k ≼ g$ , let $k^{'} = k^{- 1} g$ . From $g = k k^{'}$ with $k, k^{'} ≼ g$ , it follows that
$\begin{matrix} e + g = k + k^{'} . \end{matrix}$ (1)
Let $c \in R^{n^{2}}$ and $b \in R$ with Euclidean inner products $〈 c, g 〉 = 〈 c, e 〉 = b$ and $〈 c, f 〉 \leq b$ for all $f \in G$ ; so $c$ defines a face of $P (G)$ containing $g$ and $e$ . Equation 1 then implies that $〈 c, k 〉 = 〈 c, k^{'} 〉 = b$ , too. Hence, any face containing $g$ and $e$ must also contain $k$ and $k^{'}$ .
For any matrix $m \in R^{n^{2}}$ , define the support of $m$ by $s u p p (m) = {(i, j) \in {1, . . ., n}^{2} | m_{i j} \neq 0} .$ Define the matrix $c \in R^{n^{2}}$ by $c_{i j} = {\begin{matrix} 1 & if (i, j) \in s u p p (g + e), \\ 0 & otherwise. \end{matrix}$ It follows that $〈 c, g 〉 = 〈 c, e 〉 = n$ and for any $f \in G$ , $〈 c, f 〉 = \sum_{(i, j) \in s u p p (g + e)} f_{i j} \leq n$ with equality if and only if $f ≼ g$ . Hence, $c$ defines a face—the smallest face, $F_{{g, e}}$ —containing both $g$ and $e$ . □

Note that if

g = g_{1} . . . g_{t}

with

g, g_{1} \dots, g_{t} \in G

and such that the cycles of

g_{1}, . . ., g_{t}

are disjoint, then

g - e = \sum_{i = 1}^{t} (g_{i} - e),

hence,

g

is affinely dependent on

g_{1}, . . ., g_{t}

A direct computation based on the theorem establishes the following known results [4] , [25] , [11] :

Corollary 3.6.

(1) The diameter of $P (S_{n})$ is $1$ for $n < 4$ and is $2$ for $n \geq 4$ .
(2) The diameter of $P (A_{n})$ is $1$ for $n < 6$ and is $2$ for $n \geq 6$ .

Corollaries 2.4 and 2.5 translate into bounds on the diameter of a permutation polytope.

Corollary 3.7. Let

G \leq S_{n}

. The diameter of the polytope

P (G)

is at most

min {2 t, ⌊ n / 2 ⌋}

, where

t

is the number of nontrivial orbits of

G

. In particular, if

G

is transitive, the diameter of

P (G)

is at most

2

The bound is sharp. For example, take

G

to be the direct product of

t

copies of the dihedral group on

4

elements, naturally considered as a subgroup of

S_{4 t}

4 Mixing Times

In this section, we consider random walks on permutation polytopes or equivalently on the Cayley graph of the permutation group

G

with the corresponding generating set consisting of the indecomposable elements of

G

. This problem was suggested to us by Pak. The question about the mixing time of random walks on 0-1 polytopes goes back some time.

See the survey article [26] .

We generalize his result here. First we recall some notation. (see [22] ).

Let

G

be a finite group and

S

a symmetric generating set for

G

(i.e.

G = 〈 S 〉

and

S = S^{- 1}

). Let

Q^{k} (g)

be the probability that a random product of

k

elements of

S

is equal to

g

. Similarly, define

Q^{k} (A)

to be the probability that a random product of

k

elements of

S

is in the subset

A

G

. Let

U

denote the uniform distribution on

G

. Define the total variation distance,

d (k) : = (1 / 2) \sum_{g \in G} | Q^{k} (g) - 1 / | G | | = {max}_{A \subseteq G} | Q^{k} (A) - U (A) | .

d (k)

measures how far the probability distribution

Q^{k}

is from the uniform distribution on

G

We now consider the case that

G

is a subgroup of

S_{n}

and

S

is the set of indecomposable elements in

G

. Clearly,

S

is symmetric,

1 \in S

and

G = 〈 S 〉

. We note that

Q^{k} \to U

k \to \infty

(i.e.

d (k) \to 0

; this is standard since

S = S^{- 1}

and the Cayley graph is not bipartite – see for example [1] ).

Theorem 4.1. Assume that

G

is primitive of degree

n

. If

G

does not contain

A_{n}

, then

d (1) \to 0

n \to \infty

. In all cases,

d (2) \to 0

n \to \infty

Pak [22] proves this for the special case

G = S_{n}

. The proof of this theorem follows easily from § 2.3 and Pak's result. Namely, by Theorem 2.16 one of the following holds:

(1) $G = A_{n}$ or $S_{n}$ ;
(2) $n = 2^{a}$ , $G$ contains a regular normal subgroup $N$ (elementary abelian of order $2^{a}$ ) and a point stabilizer $H \leq A u t (N)$ contains transvections and acts irreducibly on $N$ ;
(3) $n = d^{t}$ with $d \geq 5$ , $t \geq 2$ , $G$ has a unique minimal normal subgroup $N = L \times \dots \times L$ where $L \sim = A_{d}$ and all decomposable elements of $G$ are contained in one of the $t$ minimal normal subgroups of $N$ ; or
(4) Every element of $G$ is indecomposable.

First note, that if

d (1) \to 0

, it follows easily that

d (2) \to 0

In the first case, Pak [22] proved the result for

S_{n}

. A trivial modification of his proof shows that the result also holds for

A_{n}

. As Pak points out, his proof used a well-known but unpublished result of Lulov about the sum of the inverses of the degrees of the irreducible representations of the symmetric groups. A stronger version of this theorem is in Corollary 2.7 of [18] .

Set

Y : = G \ S

. So we only need prove that

| Y | / | G | \to 0

n \to \infty

in cases 2,3 and 4.

In the fourth case,

Y

is empty.

Consider the second case.

In the second case, the only decomposable elements are fixed point free involutions (for they must be the product of two elements each moving precisely

1 / 2

the points and moving no common points). Let

T

be the set of involutions in

G

which have a fixed point and induce a transvection on

N

. Note that if

x \in T

, then

| x N \cap T | = 2

(indeed,

x N \cap T = x [x, N]

and since

x

acts as a transvection on

N

| [x, N] | = 2

The list of possible

H

was determined by McLaughlin [19] . It follows easily from this that

{lim}_{a \to \infty} | T \cap H | / | G |^{1 / 2} = 0 .

Thus,

| Y | \leq 4 | T \cap H |^{2}

and so

{lim}_{a \to \infty} | Y | / | G | \to 0

as required.

Finally, consider the third case. As we saw, the only decomposable elements are in one of the

t

normal subgroups of

N

. Thus,

| Y | \leq t (d!)

and

| G | \geq (d!)^{t}

. Since

t > 1

| Y | / | G | \to 0

as either

d

t

increases.

This completes the proof of the theorem.

We now give two examples to show that if

G

is not primitive, the previous theorem need not hold. More precisely, we produce a sequence of groups

G_{p}

for

p

an odd prime such that for fixed

k

d (k)

is bounded away from

0

. In the first sequence, the Cayley graph is close to bipartite and in the second sequence,

Q^{1}

is very small outside a proper normal subgroup.

Let

n = 2 p

. Let

x

and

y

p

-cycles in

S_{n}

that are disjoint. Let

u

be an involution in

S_{n}

with

u x u = y

. Set

G_{p} = 〈 x, y, u 〉

. So

| G | = 2 p^{2}

and has a normal elementary abelian subgroup

N : = 〈 x, y 〉

. So

G

is a transitive subgroup of

S_{n}

. Let

S

be the set of indecomposable elements in

G

Note that

x N \subset S

and

N \cap S = {x^{i}, y^{i} | i = 0, 1, \dots p - 1}

. So

| S \cap N | = 2 p - 1

. Thus, the probability that a random element of

S

is in

N

(2 p - 1) / (p^{2} + 2 p - 1) < 2 / p

. In particular, we see that

Q^{k} (N) > (1 - 2 / p)^{k}

k

is even and

Q^{k} (x N) > (1 - 2 / p)^{k}

k

is odd.

This shows that

d (k) \to 1 / 2

p \to \infty

. In particular, the mixing time is unbounded. Indeed, in the example, we see that the mixing time is linear in

p

Pak [22] did show that this could happen for some

0, 1

polytopes—his example is essentially

Z / 2 \times S_{n}

We give another example that is similar in flavor to Pak's example.

Let

J

be a nonabelian group of order

q r

with

q > r

primes (so

r (q - 1)

Note that

D

embeds in

S_{q}

. Let

p

be a third distinct prime and consider

G = Z / p ≀ J

acting on

n : = p q

. Let

N

be the normal subgroup of

G

of index

r

. Note that the number of indecomposable elements in

N

(q - 1) p^{q} + q (p - 1) + 1

while the number of indecomposable elements outside

N

(r - 1) p^{q - 1}

. So the probability that a random indecomposable element is not in

N

is less than

1 / p

. Thus, the probability that a random product of

k

indecomposable elements is in

N

is at least

(1 - 1 / p)^{k}

. So for

p

large compared to

k

Q^{k}

is far from uniform. Again, we see that the mixing time is linear in

p

References

D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. preprint.
M. Aschbacher and L. Scott. Maximal subgroups of finite groups. J. Algebra, 92(1):44–80, 1985.
L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, and Á. Seress. On the diameter of finite groups. In 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), pages 857–865. IEEE Comput. Soc. Press, Los Alamitos, CA, 1990.
M. L. Balinski and Andrew Russakoff. On the assignment polytope. SIAM Rev., 16:516–525, 1974.
A. I. Barvinok. Combinatorial complexity of orbits in representations of the symmetric group. In Representation theory and dynamical systems, volume 9 of Adv. Soviet Math., pages 161–182. Amer. Math. Soc., Providence, RI, 1992.
A. I. Barvinok and A. M. Vershik. Methods of representations theory in combinatorial optimization problems. Izv. Akad. Nauk SSSR Tekhn. Kibernet., (6):64–71, 205, 1988.
Matthias Beck and Dennis Pixton. The Ehrhart polynomial of the Birkhoff polytope. Discrete Comput. Geom., 30(4):623–637, 2003.
Louis J. Billera and A. Sarangarajan. The combinatorics of permutation polytopes. In Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994), volume 24 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 1–23. Amer. Math. Soc., Providence, RI, 1996.
Garrett Birkhoff. Three observations on linear algebra. Univ. Nac. Tucumán. Revista A., 5:147–151, 1946.
Richard A. Brualdi and Peter M. Gibson. Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function. J. Combinatorial Theory Ser. A, 22(2):194–230, 1977.
Richard A. Brualdi and Bo Lian Liu. The polytope of even doubly stochastic matrices. J. Combin. Theory Ser. A, 57(2):243–253, 1991.
Charles W. Curtis and Irving Reiner. Representation theory of finite groups and associative algebras. Pure and Applied Mathematics, Vol. XI. Interscience Publishers, a division of John Wiley & Sons, New York-London, 1962.
Graham Ellis. Computing group resolutions. J. Symbolic Comput., 38(3):1077–1118, 2004.
The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.4, 2004. GAP homepage: http://www.gap-system.org.
Ewgenij Gawrilow and Michael Joswig. Polymake: a framework for analyzing convex polytopes. In Gil Kalai and Günter M. Ziegler, editors, Polytopes — Combinatorics and Computation, pages 43–74. Birkhäuser, 2000. Homepage for Polymake: http://www.math.tu-berlin.de/polymake/.
Robert Guralnick and Kay Magaard. On the minimal degree of a primitive permutation group. J. Algebra, 207(1):127–145, 1998.
S. Lakshmivarahan, Jung Sing Jwo, and S. K. Dhall. Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey. Parallel Comput., 19(4):361–407, 1993.
M. Liebeck and A. Shalev. Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks. J. Algebra, 276 :552–601, 2004.
J. McLaughlin. Some subgroups of $S L_{n} (F_{2})$ . Illinois J. Math., 13:108–115, 1969.
Shmuel Onn. Geometry, complexity, and combinatorics of permutation polytopes. J. Combin. Theory Ser. A, 64(1):31–49, 1993.
Manfred W. Padberg and M. R. Rao. The travelling salesman problem and a class of polyhedra of diameter two. Math. Programming, 7:32–45, 1974.
Igor Pak. Four questions on Birkhoff polytope. Ann. Comb., 4(1):83–90, 2000.
Gottfried Tinhofer. Cayley graphs in computer science. Notes for minicourse given at ALCCAL'2000 meeting in Varna, 2000. http://www-m9.ma.tum.de/algograph/homepages/tinhofer/.
V. A. Yemelichev, M. M. Kovalëv, and M. K. Kravtsov. Polytopes, graphs and optimisation. Cambridge University Press, Cambridge, 1984. Translated from the Russian by G. H. Lawden.
H. P. Young. On permutations and permutation polytopes. Math. Programming Stud., (8):128–140, 1978. Polyhedral combinatorics.
G. M. Ziegler. Lectures on $0 / 1$ -polytopes., Polytopes—combinatorics and computation (Oberwolfach, 1997), 1–41, DMV Sem., 29, Birkhuser, Basel, 2000.

Robert M. Guralnick, Department of Mathematics, University of Southern California, 3620 S. Vermont Ave., Los Angeles CA 90089-2532 E-mail address : guralnic@usc.edu David Perkinson, Department of Mathematics, Reed College, Portland, OR 97202 E-mail address : davidp@reed.edu

November 27, 2006

Robert Guralnick and David Perkinson