Note: The Outer Automorphism of S_{6}

Koji Nuida

April 13, 2015

Abstract In this note, we describe an explicit construction of the outer automorphism of the symmetric group S_{6} on six letters. We also explain the fact that S_{n} for n ≠ 6 has no outer automorphisms.

1 The Map

We briefly say (by postponing the detailed explanation) that, the group automorphism F: S_{6} → S_{6} uniquely determined by the following conditions

F ((12)) = (12)(34)(56)
F ((23)) = (16)(24)(35)
F ((34)) = (14)(23)(56)
F ((45)) = (16)(25)(34)
F ((56)) = (13)(24)(56)

is the outer automorphism of S_{6} which is the subject of this note. See Section 4 for some more properties of the map.

2 Preliminaries

In this note, n denotes a positive integer. The symmetric group of degree n, denoted by S_{n}, is the set of permutations of integers from 1 to n. This set is endowed with a binary operator defined by the composition of two permutations as maps. Then S_{n} forms a group with respect to this operator. We use notations like f · g and fg for the binary operator, rather than the notation f ∘ g for composite maps.

Each element of S_{n} can be visualized by using an “Amida diagram” (“Amida-kuji” in Japanese) with n vertical axes (see Figure 1 for example).

1  2  3  4 f(3) f(4) f(2) f(1)

Figure 1: Amida diagram representing the permutation f ∈ S_{4} defined by f(1) = 4, f(2) = 3, f(3) = 1 and f(4) = 2

Here, the vertical axes correspond to integers 1, …, n from left to right. To determine the image f(i) of a number i by a given Amida diagram, we start from the top of i-th vertical axis and follow the line downward, where if we meet an endpoint of a horizontal edge joining the current vertical axis with one of the adjacent vertical axes, we move to the opposite vertical axis (by crossing the horizontal edge) and then continue to go downward.^{1} Then we determine f(i) = j, if we finally reach to the bottom of j-th vertical axis. By the definition, distinct numbers are mapped to different numbers, therefore f is a permutation; f ∈ S_{n}.^{2} When f, g ∈ S_{n} are determined by Amida diagrams as above, we can construct another Amida diagram by concatenating the two Amida diagrams, with the one for f combined at the bottom of the one for g; the resulting Amida diagram defines the product f · g ∈ S_{n}. On the other hand, we can construct another Amida diagram by turning the Amida diagram for f upside down, which corresponds to the inverse f^{−1} of f.

Conversely, given an element f of S_{n}, we can construct an Amida diagram which determines the f as follows. First, for the number (say, i) which is mapped by f to n, we join i-th and (i + 1)-th vertical axes by a horizontal edge, join (i + 1)-th and (i + 2)-th vertical axes by a horizontal edge, and so on, and join (n − 1)-th and n-th vertical axes by a horizontal edge. These edges let the number i go to n-th vertical axis correctly. Secondly, we let the number mapped by f to n − 1 go to (n − 1)-th vertical axis correctly, by joining vertical axes except for n-th vertical axis by horizontal edges in a similar way. Now these two numbers have correctly moved to (n − 1)-th and n-th vertical axes, respectively. Iterating this process recursively, we finally obtain the desired Amida diagram corresponding to f.

1We should not draw two horizontal edges from the same point in an Amida diagram, because the choice of an edge to follow becomes ambiguous. We also suppose the total number of horizontal edges to be finite.

2A rigorous proof can be given by a recursive argument with respect to the total number of horizontal edges.

Instead of drawing such Amida diagrams, we usually use the following notations for specifying elements of S_{n}. For distinct numbers a_{1}, …, a_{k} in {1, …, n}, let (a_{1} a_{2} … a_{k}) denote the element of S_{n} which maps a_{1} to a_{2}, a_{2} to a_{3},..., a_{k−1} to a_{k}, and a_{k} to a_{1}, and fixes any other number. Such an element of S_{n} is called a cyclic permutation (or simply a cycle), and k is called the length of the cycle. We note that, for an index i with 1 ≤ i ≤ k, the cyclic permutation (a_{i} a_{i+1} … a_{k} a_{1} a_{2} … a_{i−1}) is equal to (a_{1} a_{2} … a_{k}). By observing the orbits generated by applying an element f of S_{n} to each number repeatedly, the following well-known fact is derived:

Proposition 1. Any element of S_{n} can be expressed as a product of cyclic permutations (a_{1}a_{2} … a_{k}) for which the sets {a_{1}, a_{2}, …, a_{k}} are disjoint to each other.

For an element f of S_{n}, if an expression of f as a product of disjoint cycles as in Proposition 1 involves m_{i} cycles of length i for each i, we say that f has cycle type (1^{m_{1}}2^{m_{2}} …). Here, by supplying cycles (j) of length one (i.e., identity permutation) for numbers j fixed by f if necessary, we may assume without loss of generality that an expression of f as a product of disjoint cycles always involves every number from 1 to n, each of which appears exactly once. Namely, we assume that ∑_{j≥1} m_{j} · j = n holds for the type of an element of S_{n}. This requirement makes the type of f ∈ S_{n} uniquely determined, independent of such an expression of f as a product of disjoint cycles.^{3} Moreover, the following property is well-known:

Proposition 2. For elements f, g of S_{n}, f and g are conjugate (i.e., g = hfh^{−1} for some h ∈ S_{n}) if and only if f and g have the same cycle type.

A cyclic permutation (a_{1} a_{2}) of length two is called a transposition, and such a transposition with a_{2} = a_{1} +1 is called an adjacent transposition. For example, the permutation f ∈ S_{4} given in Figure 1 is a cyclic permutation f = (1423), and it can be written as f = (23)(12)(34)(23)(12) by a product of adjacent transpositions. By the correspondence between permutations and Amida diagrams mentioned above, adjacent transpositions correspond to Amida diagrams with only one horizontal edge. By combining this fact with the above-mentioned construction of an Amida diagram for a given permutation, we have the following well-known result:

3In fact, such an expression of f is essentially unique.

Proposition 3. Any element of S_{n} can be expressed as a product of adjacent transpositions.

We note, however, that the way of expressing an element of S_{n} as a product of adjacent transpositions is not necessarily unique (even if we do not use obviously redundant adjacent transpositions like (12)(12)). For example, the transposition (13) can be expressed as (12)(23)(12) and also as (23)(12)(23). More generally, adjacent transpositions satisfy the following relations. Here, id denotes the identity permutation (i.e., the element of S_{n} that fixes every number), and the adjacent transposition (i i + 1) is denoted by s_{i}.

For 1 ≤ i ≤ n − 1 : s_{i}s_{i} = id .  (1)
For 2 ≤ i ≤ n − 1 : s_{i−1}s_{i}s_{i−1}s_{i}s_{i−1}s_{i} = id .  (2)
For 1 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 1 with |i − j| ≥ 2 : s_{i}s_{j}s_{i}s_{j} = id . (3)

Moreover, it is remarkable and well-known that, if an element of S_{n} can be expressed as a product of adjacent transpositions in two different ways, then the difference of the expressions is deduced from the three kinds of relations above (a rigorous explanation of this fact is omitted here).^{4}

If a bijection F: S_{n} → S_{n} from the group S_{n} to itself satisfies that F (f · g) = F (f) · F (g) for any f, g ∈ S_{n}, we call the F an automorphism of S_{n}. The set Aut(S_{n}) of all automorphisms of S_{n} also forms a group with respect to composition of maps, which is called the automorphism group of S_{n}. For example, for each element f of S_{n}, the map that maps an element g ∈ S_{n} to fgf^{−1} ∈ S_{n} is an automorphism of S_{n}. Such an automorphism is called an inner automorphism; and the other automorphisms are called outer automorphisms. The following property of inner automorphisms is derived from Proposition 2:

Proposition 4. For any inner automorphism F of S_{n}, any element of S_{n} and its image by F have the same cycle type.

3 No Outer Automorphisms Exist Except for S_{6}

In this section, we show that, for n ≠ 6, every automorphism of S_{n} is an inner automorphism. We note that, the results in this section are also valid for n = 6 unless we explicitly specify that n ≠ 6.

4Namely, by choosing the set of all adjacent transpositions as a generating set of S_{n}, the above-mentioned three kinds of relations form the fundamental relations for S_{n}.

Lemma 1. If an automorphism F of S_{n} maps every transposition to a transposition, then F is an inner automorphism.

Proof. It is sufficient to show that, for some distinct numbers a_{1}, a_{2}, …, a_{n} ∈ {1, 2, …, n}, we have F ( (i i + 1) ) = (a_{i} a_{i+1}) for every index i with 1 ≤ i ≤ n − 1. Indeed, in this case, by choosing the element f ∈ S_{n} satisfying f(j) = a_{j} for each j ∈ {1, 2, …, n}, we have F (s_{i}) = fs_{i}f^{−1} for each adjacent transposition s_{i} = (i i + 1), while Proposition 3 implies that every g ∈ S_{n} can be written as a product of the elements s_{i}, therefore we have F (g) = fgf^{−1}.

From now, we verify the above-mentioned property. We consider the case n ≥ 2, since the case n = 1 is trivial. First, by the assumption of this lemma, F ( (12) ) is a transposition, which can be written as F ( (12) ) = (a_{1}a_{2}). This proves the claim when n = 2; we consider the case n ≥ 3 from now on. Secondly, by the assumption of this lemma, we have F ( (23) ) = (b_{1}b_{2}) for some b_{1} and b_{2}. Then F ( (12)(23) ) = F ( (12) )F ( (23) ) = (a_{1}a_{2})(b_{1}b_{2}). Now if two sets {a_{1}, a_{2}} and {b_{1}, b_{2}} are disjoint, then we have ((a_{1}a_{2})(b_{1}b_{2}))^{3} ≠ id, while ((12)(23))^{3} = id; this is a contradiction. Therefore, {a_{1}, a_{2}} and {b_{1}, b_{2}} have a common element, say (by symmetry) a_{2} = b_{1}. We rewrite b_{2} as a_{3}. This proves the claim when n = 3; we consider the case n ≥ 4 from now on. By the assumption of this lemma, we have F ( (34) ) = (c_{1}c_{2}) for some c_{1} and c_{2}. Now, owing to the fact ((23)(34))^{3} = id, a similar argument implies that {a_{2}, a_{3}} and {c_{1}, c_{2}} have a common element, while the fact ((12)(34))^{2} = id implies that {a_{1}, a_{2}} and {c_{1}, c_{2}} should be disjoint. Therefore, we have a_{3} ∈ {c_{1}, c_{2}}, and (c_{1}c_{2}) can be written as (c_{1}c_{2}) = (a_{3}a_{4}) for some a_{4}. By iterating this argument, we finally have the above-mentioned property. Hence, this lemma holds.

By combining Proposition 4 with Lemma 1, we have the following property:

Corollary 1. For an automorphism F of S_{n}, F is an inner automorphism if and only if a transposition in S_{n} is always mapped by F to a transposition.

Lemma 2. For an automorphism F of S_{n} and any possible cycle type of elements of S_{n}, the cycle type of F (f) for any element f ∈ S_{n} of the fixed cycle type is uniquely determined, regardless of the choice of such an element f.

Proof. Let g ∈ S_{n} be any element with the same cycle type as f. By Proposition 2, f and g are conjugate, namely g = hfh^{−1} for some h ∈ S_{n}. Now we have F (g) = F (hfh^{−1}) = F (h)F (f)F (h)^{−1}, therefore F (f) and F (g) are conjugate to each other as well. By Proposition 2, this implies that F (f) and F (g) have the same cycle type. Hence, this lemma holds.

Lemma 3. For any integer a with 0 ≤ a ≤ n/2, the number of elements of S_{n} having cycle type (1^{n−2a}2^{a}) is n(n − 1) ⋯ (n − 2a + 1)/(a! · 2^{a}).

Proof. Let Z be the set of elements of S_{n} with cycle type (1^{n−2a}2^{a}), let X be the set of sequences [b_{1}, …, b_{2a}] of 2a distinct numbers in {1, …, n}, and let Y be the set of sequences [B_{1}, …, B_{a}] of a disjoint subsets B_{1}, …, B_{a} ⊂ {1, …, n} of size two. We define maps F: X → Y and G: Y → Z by

F ([b_{1}, …, b_{2a}]) = [{b_{1}, b_{2}}, {b_{3}, b_{4}}, …, {b_{2a−1}, b_{2a}}] ,
G([{b_{1}, b_{2}}, {b_{3}, b_{4}}, …, {b_{2a−1}, b_{2a}}]) = (b_{1} b_{2})(b_{3} b_{4}) ⋯ (b_{2a−1} b_{2a}) .

(For the definition of G, note that (x y) = (y x) as transpositions.) Then, the elements of X mapped by F to a given [B_{1}, B_{2}, …, B_{a}] ∈ Y are nothing but the sequences obtained by first arranging the two elements of B_{1}, secondly arranging the two elements of B_{2}, and so on, and finally arranging the two elements of B_{a}. Since there are two ways of ordering the elements of each B_{i}, the total number of such sequences is 2^{a}. Therefore |Y | = |X|/2^{a} holds. On the other hand, the elements of Y mapped by G to a given (b_{1} b_{2})(b_{3} b_{4}) ⋯ (b_{2a−1} b_{2a}) ∈ Z are nothing but the sequences obtained by rearranging the a subsets in the sequence [{b_{1}, b_{2}}, {b_{3}, b_{4}}, …, {b_{2a−1}, b_{2a}}]. The total number of such sequences is a!, therefore |Z| = |Y |/a! holds. Moreover, we have |X| = n(n − 1) ⋯ (n − 2a + 1). This implies that

|Z| = |X|/(a! · 2^{a}) = n(n − 1) ⋯ (n − 2a + 1)/(a! · 2^{a}) .

Hence, this lemma holds.

For an automorphism F of S_{n}, the square of the image of any transposition by F is the identity permutation (since the transposition has the same property), therefore its cycle type can be written as (1^{n−2a}2^{a}) (where a is an integer with 1 ≤ a ≤ n/2). Owing to Lemma 2, the cycle type does not depend on the choice of the original transposition. By applying Lemma 2 to F^{−1} as well, it follows that every element of S_{n} with cycle type (1^{n−2a}2^{a}) is the image by F of some transposition. This implies that the transpositions in S_{n} are in one-to-one correspondence via F to the elements of S_{n} with cycle type (1^{n−2a}2^{a}). Therefore, the number of transpositions in S_{n} is equal to the number of elements of S_{n} with cycle type (1^{n−2a}2^{a}). By this and Lemma 3, we have the following equality:

\frac{n(n − 1)}{2} = \frac{n(n − 1) ⋯ (n − 2a + 1)}{a! · 2^{a}} .  (4)

Lemma 4. For integers n, a with 2 ≤ a ≤ n/2, the condition (4) holds if and only if (n, a) = (6, 3).

Proof. Let f_{a}(n) = (n − 2)(n − 3) ⋯ (n − 2a + 1). Then the condition (4) is equivalent to the condition f_{a}(n) = a! · 2^{a−1}. Now for each fixed a, the function f_{a}(n) is monotonically increasing in n. When a = 2, we have a! · 2^{a−1} = 4, f_{2}(4) = 2 and f_{2}(5) = 6, therefore the above-mentioned monotonicity of f_{a}(n) implies that the condition (4) does not hold. From now on, we consider the case a ≥ 3. Now we have

f_{a}(2a) = (2a − 2)(2a − 3) ⋯ 2 · 1
= 2^{a−1}(a − 1)! · (2a − 3)(2a − 5) ⋯ 3 · 1
≥ 2^{a−1}(a − 1)! · a = 2^{a−1} · a! ,

where the equality holds if and only if a = 3. Therefore, by the monotonicity of f_{a}(n), the condition (4) does not hold for a ≥ 4; while, for the case a = 3, the condition (4) holds if and only if n = 2a = 6. Hence, this lemma holds.

Theorem 1. For n ≠ 6, every automorphism of S_{n} is an inner automorphism.

Proof. By Lemma 4 and the argument just before the lemma, if n ≠ 6, then for any automorphism F of S_{n}, the image by F of any transposition in S_{n} has cycle type (1^{n−2}2^{1}), i.e., it is a transposition as well. Therefore, F is an inner automorphism by Lemma 1. Hence, this theorem holds.

4 The Outer Automorphism of S_{6}

In this section, we show that an outer automorphism of S_{6} exists, and it is “essentially” unique. Here, the “essentially” means that the outer automorphism of S_{6} is uniquely determined except the difference of inner automorphisms; more precisely, we have the following result:

Theorem 2. If F and G are outer automorphisms of S_{6}, then we have G = F ∘ I for some inner automorphism I.

Proof. First, in a way similar to the proof of Theorem 1, Lemma 4 and the argument just before the lemma imply that the images by F and by G of a transposition have cycle type (1^{4}2^{1}) (i.e., it is a transposition) or (1^{0}2^{3}). Now in the first case, Lemma 1 implies that either F or G is an inner automorphism, contradicting the assumption of the theorem. Hence, the images of any transposition by F and by G have cycle type (1^{0}2^{3}). Moreover, by the argument just before Lemma 4, the transpositions in S_{6} are in one-to-one correspondence with the elements of S_{6} with cycle type (1^{0}2^{3}) via both F and G. Now the automorphism F^{−1} ∘ G of S_{6} maps any transposition to a transposition, therefore F^{−1} ∘G is an inner automorphism by Lemma 1. By writing the F^{−1} ∘ G as I, we have F ∘ I = G, therefore this theorem holds.

From now on, we show that the automorphism F mentioned in Section 1 indeed exists. Once it is done, the F is an outer automorphism by definition, and Theorem 2 implies that this is the unique outer automorphism except the difference of inner automorphisms. Now we note that, if such an F exists, then the property of the automorphism F implies the following:

(*) For any f ∈ S_{6}, if f = t_{1}t_{2} ⋯ t_{k} with adjacent transpositions t_{i}, then F (f) = F (t_{1})F (t_{2}) ⋯ F (t_{k}) holds, where each F (t_{i}) is the element of S_{6} specified in Section 1.

We are going to define the desired map F by the condition (*). Owing to Proposition 3, such an element f ∈ S_{6} can be written as f = t_{1}t_{2} ⋯ t_{k} as in the condition (*). The remaining task is to verify that, for any other expression f = t′_{1}t′_{2} ⋯ t′_{k′} as above, the resulting images of f defined by the two expressions of f coincide with each other. As mentioned in Section 2, the difference of the two expressions of f is deduced from combinations of the three kinds of relations (1), (2) and (3). On the other hand, a straightforward calculation using the precise values of F (s_{i}) specified in the definition of F implies that, the left-hand sides of these relations are all mapped by the F to the identity permutation id. Namely,

for (1): F (s_{i})F (s_{i}) = id ,
for (2): F (s_{i−1})F (s_{i})F (s_{i−1})F (s_{i})F (s_{i−1})F (s_{i}) = id ,
for (3): F (s_{i})F (s_{j})F (s_{i})F (s_{j}) = id .

Then, the difference of the two expressions of f vanishes when these are mapped by F, therefore we have

F (t_{1})F (t_{2}) ⋯ F (t_{k}) = F (t′_{1})F (t′_{2}) ⋯ F (t′_{k′}) .

Hence, it follows that the automorphism F specified in Section 1 indeed exists.^{5} The argument above has derived the following theorem:

5This argument can of course be formalized by using terminology of group theory, but we omit it here for the sake of simplicity.

Theorem 3. An outer automorphism of S_{6} exists, and it is essentially unique in the sense as in Theorem 2.

From now, we give some calculation results about the outer automorphism F. We quote the definition of F here for the sake of convenience (where we abbreviate the relation F (x) = y to x ↦ y):

(12) ↦ (12)(34)(56)
(23) ↦ (16)(24)(35)
(34) ↦ (14)(23)(56)
(45) ↦ (16)(25)(34)
(56) ↦ (13)(24)(56)

First, we calculate the images by F of the other transpositions:

(13) = (12)(23)(12) ↦ (12)(34)(56) · (16)(24)(35) · (12)(34)(56) = (13)(25)(46)

(24) = (23)(34)(23) ↦ (16)(24)(35) · (14)(23)(56) · (16)(24)(35) = (13)(26)(45)

(35) = (34)(45)(34) ↦ (14)(23)(56) · (16)(25)(34) · (14)(23)(56) = (12)(36)(45)

(46) = (45)(56)(45) ↦ (16)(25)(34) · (13)(24)(56) · (16)(25)(34) = (12)(35)(46)

(14) = (12)(24)(12) ↦ (12)(34)(56) · (13)(26)(45) · (12)(34)(56) = (15)(24)(36)

(25) = (23)(35)(23) ↦ (16)(24)(35) · (12)(36)(45) · (16)(24)(35) = (15)(23)(46)

(36) = (34)(46)(34) ↦ (14)(23)(56) · (12)(35)(46) · (14)(23)(56) = (15)(26)(34)

(15) = (12)(25)(12) ↦ (12)(34)(56) · (15)(23)(46) · (12)(34)(56) = (14)(26)(35)

(26) = (23)(36)(23) ↦ (16)(24)(35) · (15)(26)(34) · (16)(24)(35) = (14)(25)(36)

(16) = (12)(26)(12) ↦ (12)(34)(56) · (14)(25)(36) · (12)(34)(56) = (16)(23)(45)

Secondly, for each possible cycle type of elements of S_{6}, we calculate the image by F of an element of S_{6} having the cycle type:

(12)(34) = (12) · (34) ↦ (12)(34)(56) · (14)(23)(56) = (13)(24)
(12)(34)(56) = (12)(34) · (56) ↦ (13)(24) · (13)(24)(56) = (56)
(123) = (12) · (23) ↦ (12)(34)(56) · (16)(24)(35) = (154)(236)
(123)(45) = (123) · (45) ↦ (154)(236) · (16)(25)(34) = (124653)
(123)(456) = (123)(45) · (56) ↦ (124653) · (13)(24)(56) = (263)
(1234) = (123) · (34) ↦ (154)(236) · (14)(23)(56) = (2645)
(1234)(56) = (1234) · (56) ↦ (2645) · (13)(24)(56) = (13)(2546)
(12345) = (1234) · (45) ↦ (2645) · (16)(25)(34) = (14356)
(123456) = (12345) · (56) ↦ (14356) · (13)(24)(56) = (15)(234)

By these results and Lemma 2, the cycle types of elements of S_{6} are changed by applying the map F as follows: Types (1^{4}2^{1}) and (2^{3}) are exchanged; types (1^{3}3^{1}) and (3^{2}) are exchanged; types (1^{1}2^{1}3^{1}) and (6^{1}) are exchanged; and any other type is not changed.

Acknowledgements. This note is motivated by a calculation during a discussion with Dr. Yasuhide Numata at Shinshu University (I remember that the explicit calculation to derive the outer automorphism was fairly complicated), so I would like to thank him.