The Symmetric Groups

In the last section we proved that every finite group is isomorphic to a subgroup of S_n for some n. Therefore, the symmetric groups play a much more fundamental role in group theory than it would appear at the outset. In this section we will begin an in depth study of these groups.

Before we begin discussing the properties of S_n, let us introduce some new notation. Suppose that i₁,...,i_r are distinct integers, 1 < i_j < n. Let

denote the permutation of S_n which maps i₁ onto i₂, i₂ onto i₃,..., and i_r onto i₁, and which leaves fixed the integers not expressly listed. Such a permutation is called an r-cycle. For example, the permutation (123) of S₃ would be written in our old notation as

.

Any 1-cycle is the identity permutation. Moreover,

We will say that two cycles are disjoint if they have no elements in common. For example, (123) and (456) are disjoint. It is clear that disjoint cycles commute with one another. Note, however, that the product of two cycles is not necessarily a cycle, but only a permutation. We say that an r-cycle is nontrivial if r 1.

Lemma 1: Let S_n, 1. Then can be written as a product on nontrivial disjoint cycles, This representation is unique up to the rearrangement of the cycles.

We will postpone the proof of Lemma 1 for a moment. The following should suggest a proof to the reader. Let S₈ be given by

=

Then, maps 1 into 7, 7 into 2, and 2 back to 1. Thus, (172) is a component of . Moreover, maps 3 into 4, 4 into 5, 5 into 8, and 8 back to 3. Thus, a second component cycle of is (3458). Finally, 6 is mapped into 6, so that = (172)(3458)(6). Moreover, since a 1-cycle is the identity, we have

= (172)(3458),

as an expression of as a product of nontrivial, disjoint cycles.

Proof of Lemma 1: We say that an integer i is fixed by if (i) = i. Let us show how to express as a product of nontrivial, disjoint cycles by using induction on the number of integers not left fixed by . Thus (i₁) = i₂, i₂ i₁. If (i₂) i₁,i₂, define i₃ by i₃ = (i₂). If (i₃) i₁,i₂,i₃, define i₄ by i₄ = (i₃), and so on. Thus we define a sequence of integers i₁,i₂,...i_s, all distinct, and such that (i_k) = i_k+1. Eventually, this process must stop, and (i_s) will be one of i₁,...i_s. But then (i_s) = i₁. For if (i_s) = i_k (1 < k < s), then maps both i_s and i_k-1 onto i_k, which contradicts the fact that is a bijection. Set = (i₁i₂,...i_s). Then ^-1 fixes precisely i₁,...,i_s and all the integers fixed by . Therefore, ^-1 has fewer integers not left fixed than . Thus by induction ^-1 = c₁...c_t, where c₁,...,c_t are nontrivial, disjoint cycles. Moreover integers appearing in c₁,...,c_t are just those not fixed by ^-1. Thus, c₁,...,c_t are disjoint from and = c₁,...,c_t is an expression of as a product of nontrivial, disjoint cycles. The uniqueness is left to the reader.

Definition 2: A transposition is a 2-cycle (ij), i j.

A simple inductive argument suffices to show that S_n contains n(n-1)/2 transpositions.

Proposition 3: S_n is generated by the set of transpositions.

Proof: Let S_n, 1. We will show that can be written as a product of transpositions. Let

= (i₁i₂...i_r)(j₁...j_s)(k₁...k_t)...

be the expression of as a product of disjoint, nontrivial cycles. Then

= (i₁i_r)(i₁i_r-1)...(i₁i₂)(j₁j_s)...(j₁j₂)(k₁k_t)...(k₁k₂)...

We see from the proof of proposition 3 that S_n, the identity, then can be written as a product of N() transpositions, where

N() = (r-1) + (s-1) + (t-1) + ...,

and is given by (2). Let us set

Note that although 1 can always be expressed as a product of N() transpositions, it will usually be possible to write as a product of some other number of transpositions. The next result will be used to prove that in any two such representations of , the number of transpositions is always even or odd.

Let , S_n. Then N() N() + N() (mod 2).

Theorem 4: Let , S_n. Then N() N() + N() (mod 2).

Proof: First we assert that it suffices to prove the theorem in the case = a transposition. For assume that we know this special case, and let and be arbitrary permutations; let

= ₁..._a, = ₁..._b

be expressions of and , respectively, as products of transpositions. Then, by induction and the assumed special case of the theorem, it is easy to verify that

N() (N(₁)+N(₂)+...+N(_a)) +

(N(₁)+...+N(_b)) (mod 2)

N() + N() (mod 2).

Thus, let us assume that = (ij), and let us assume that is given by (2) above. There are four cases to consider:

Case 1: Neither i nor j appears in the cycle decomposition (2). In this case, N() = (2 - 1) + (r - 1) + (s - 1) + (t - 1) +...= 1 + N() = N() + N().

Case 2: Exactly one of i and j appears in the cycle decomposition (2). Without loss of generality, let us assume that i = i₁. Then

(ij) = (jii₂...i_r)(j₁...j_s)(k₁...k_t)...

Therefore,

N() = 1 + N() = N() + N().

Case 3: Both i and j appear in the cycle decomposition (2), but they appear in different cycles. Without loss of generality, assume that i = i₁ and j = j₁. Then

(ij) = (jj₂...j_sii₂...i_r)(k₁...k_t)...

so that

N() = (r + s -1) + (t - 1)+... = N() + N().

Case 4: Both i and j appear in the same cycle. Without loss of generality, let i = i₁, j = i_k. Then

(ij) = (ii₂...i_k-1)(ji_k+1...i_r)(j₁...j_s)(k₁...k_t)...

so that

N() = (k - 2) + (r - k) + (s - 1) + (t - 1) + ...

= N() + N() - 2

N() + N() (mod 2).

Definition 5: Let S_n. Then is even (respectively, odd) if N() is even (respectively, odd).

Thus a permutation is even if, when is written in the standard way as a product of transpositions, the number of transpositions is even. However, if is even and if = ₁..._a is any expression of as a product of transpositions, Theorem 4 and a simple induction imply that

N() N(₁ + ... + N(_a) (mod 2)

a (mod 2),

and thus a is even. Thus, a permutation is even if and only if it can be expressed (in any manner) as a product of an even number of transpositions.

By Theorem 4 and the fact that N(^-1) = N(), we see that the set of even permutations of S_n form a subgroup. This subgroup is call the alternating group on n elements and is denoted A_n.

Theorem 6:

(1) A_n is a normal subgroup of S_n.

(2) If n > 2, the index of A_n in S_n is 2.

Proof: Let us consider the mapping

: S_n Z₂

() = N() (mod 2).

By Theorem 4, this mapping is a homomorphism. Its kernel is clearly A_n. Thus, part (1) is proved by Proposition 3 of the section on homomorphism. If n > 2, S_n contains the 2-cycle (12) and N((12)) = 1. Therefore, if n > 2, is surjective. By the first isomorphism theorem, S_n/A_nZ₂. Therefore, the index of A_n in S_n is 2.

Earlier we proved that S_n is generated by the set of all transpositions. Let us now prove an analogous statement for A_n.

Proposition 7: A_n is generated by the set of all 3-cycles (ijk).

Proof: Let S denote the set of all 3-cycles, G = [S]. If n < 2, S = , so that G = {1}. (The smallest subgroup of S_n containing S is just {1}.) But if n < 2, then A_n = {1}. Thus we may assume that n > 3. Since a 3-cycle is even, it is clear that G A_n. Let us prove the reverse inclusion. Since a permutation is even if and only if it can be written as a product of an even number of transpositions, we see that A_n is generated by all products of the form (i₁i₂)(i₃i₄) (i₁ i₂, i₃ i₄). Therefore it suffices to show that every such product is contained in the group G. There are three cases to examine:

Case 1: Only two of the integers i_j(j=1,2,3,4) are distinct. Without loss of generality, we may assume that i₁ = i₃, i₂ = i₄. Then

(i₁i₂)(i₃i₄) = 1 G.

Case 2: Three of the integers i₁, i₂, i₃, and i₄ are distinct. Without loss of generality, assume that i₁ = i₃. Then

(i₁i₂)(i₃i₄) = (i₁i₄i₂) G.

Case 3: All four of the integers, i₁, i₂, i₃, and i₄ are distinct. Then

(i₁i₂)(i₃i₄) = (i₁i₃i₂)(i₁i₃i₄) G.

Definition 8: A group G is said to be simple if G has no nontrivial normal subgroups. Equivalently, G is simple if the only normal subgroups N of G are N = G and N = {1}.

By Lagrange's theorem, if G = Z_p, p a prime, then G is simple. On the other hand, if G = Z_n, n 1, nor prime, then G is not simple. For if p is prime dividing n, then N = {0, p, 2p,..., (n - 1) · p} is a nontrivial normal subgroup of G.

Another example of a simple group is given by the following important result.

Theorem 9 (Abel): Assume that n 4. Then A_n is simple.

In order to prove this result, we require

Lemma 10: Let N be a normal subgroup of A_n (n > 5). If N contains a 3-cycle, then N = A_n.

Proof: By Proposition 7, it suffices to show that every 3-cycle belongs to N. Let (ijk) N and let (i'j'k') be an arbitrary 3-cycle. Let S_n be any permutation having the property

(i) = i',

(j) = j',

(k) = k'.

Then

(ijk)^-1 = (i'j'k').

If A_n, then (4) asserts that (i'j'k') N since N is normal. Therefore assume that A_n. Since n > 5, there exist integers a, a' (1 < a, a' < n) such that

{a, a'} {i', j', k'} = .

Then, since A_n, = (aa') A_n. However,

(ijk)^-1 = (aa')(ijk)^-1(aa')

Thus, again (i'j'k') N, so N = A_n and the lemma is proved.

Proof of Theorem 9: A_n has order 1,1,3 for n = 1,2,3 respectively. In these cases, A_n has no proper subgroups by Lagrange's theorem. Thus, let us now assume that n > 5. Let N A_n be a normal subgroup N {1}. We must show that N = A_n. By Lemma 10 it suffices to show that N contains a 3-cycle. For each S_n, let f() = the number of integers j (1 < j < n) such that (j) = j. Let us choose N - {1} for which f() is a maximum. Since 1, f() < n - 1. However, if (j) = j for n - 1 values of j then = 1, so that f() < n - 2. If f() = n - 2, then is a transposition, which contradicts the fact that A_n. Therefore, f() < n - 3. We assert that f() = n - 3. Assume the contrary. Then f() < n - 4, and there are at least four integers not mapped into themselves by . Let us examine the expression of as the product of nontrivial disjoint cycles. There are two possibilities. Either there exists an r-cycle (r > 3) in the expression or only transpositions occur. In the former case, looks like

while in the later is of the form

In the first case, if f() = n - 4, then is a 4-cycle, which contradicts the fact that is even. Therefore, in the first case, f() < n - 5. Therefore, there exist integers i₄, i₅ (1 < i₁, i₅ < n), distinct from i₁, i₂, i₃, and not left fixed by . Let = (i₃i₄i₅). Then

' = ^-1 = (i₁i₂i₄...)...,

and any integer left fixed by is also left fixed by '. Since N is normal, we have ' N. Moreover, ' 1, so that f(') < f() by the definition of . But '^-1 leaves fixed all integers which are not left fixed by and '^-1 leaves i₂ fixed as well. Therefore, f('^-1) < f() + 1. Thus, a contradiction is reached if is of the form (5). Assume that is of the form (6). Let i₅ be an integer left fixed by and set = (i₃i₄i₅). Then

' = ^-1 = (i₁i₂)(i₄i₅)...

is an element of N, which leaves every integer left fixed by , except for i₅. Moreover, ', so that '^-1 1. Further '^-1 leaves fixed the f() - 1 integers which are left fixed both by and ' and it leaves i₁ and i₂ fixed as well. Therefore, '^-1 leaves f() + 1 integers fixed, which is a contradiction to the choice of . We have finally proved that the assumption f() < n - 4 leads to a contradiction, and therefore f() = n - 3. But then there are exactly three integers not left fixed by , so is a 3-cycle. Thus, N contains a 3-cycle as claimed.