Back  Table of Contents 

The Symmetric GroupsIn 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_{1}i_{2}...i_{r})
denote the permutation of S_{n} which maps i_{1} onto i_{2}, i_{2} onto i_{3},..., and i_{r} onto i_{1}, and which leaves fixed the integers not expressly listed. Such a permutation is called an rcycle. For example, the permutation (123) of S_{3} would be written in our old notation as
.
Any 1cycle is the identity permutation. Moreover, (1)
(i_{1},i_{2}...i_{r})^{1} = (i_{r}i_{r1}...i_{1}).
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 rcycle is nontrivial if
Lemma 1: Let We will postpone the proof of Lemma 1 for a moment. The following should suggest a proof to the reader. Let
=
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),
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
Definition 2: A transposition is a 2cycle (ij), A simple inductive argument suffices to show that S_{n} contains n(n1)/2 transpositions. Proposition 3: S_{n} is generated by the set of transpositions. Proof: Let
= (i_{1}i_{2}...i_{r})(j_{1}...j_{s})(k_{1}...k_{t})...
be the expression of as a product of disjoint, nontrivial cycles. Then (3)
= (i_{1}i_{r})(i_{1}i_{r1})...(i_{1}i_{2})(j_{1}j_{s})...(j_{1}j_{2})(k_{1}k_{t})...(k_{1}k_{2})...
We see from the proof of proposition 3 that
N() = (r1) + (s1) + (t1) + ...,
and is given by (2). Let us set
N(1) = 0.
Note that although
Theorem 4: Let 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
= _{1}..._{a}, = _{1}..._{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(_{1})+N(_{2})+...+N(_{a})) +
(N(_{1})+...+N(_{b})) (mod 2)
N() + N() (mod 2).
Thus, let us assume that Case 1: Neither i nor j appears in the cycle decomposition (2). In this case, Case 2: Exactly one of i and j appears in the cycle decomposition (2). Without loss of generality, let us assume that
(ij) = (jii_{2}...i_{r})(j_{1}...j_{s})(k_{1}...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
(ij) = (jj_{2}...j_{s}ii_{2}...i_{r})(k_{1}...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
(ij) = (ii_{2}...i_{k1})(ji_{k+1}...i_{r})(j_{1}...j_{s})(k_{1}...k_{t})...
so that
N() = (k  2) + (r  k) + (s  1) + (t  1) + ...
= N() + N()  2
N() + N() (mod 2).
Definition 5: Let 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
N() N(_{1} + ... + 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 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_{2}
() = 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 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 3cycles (ijk). Proof: Let S denote the set of all 3cycles, Case 1: Only two of the integers i_{j}
(i_{1}i_{2})(i_{3}i_{4}) = 1 G.
Case 2: Three of the integers i_{1}, i_{2}, i_{3}, and i_{4} are distinct. Without loss of generality, assume that
(i_{1}i_{2})(i_{3}i_{4}) = (i_{1}i_{4}i_{2}) G.
Case 3: All four of the integers, i_{1}, i_{2}, i_{3}, and i_{4} are distinct. Then
(i_{1}i_{2})(i_{3}i_{4}) = (i_{1}i_{3}i_{2})(i_{1}i_{3}i_{4}) 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 By Lagrange's theorem, if Another example of a simple group is given by the following important result.
Theorem 9 (Abel): Assume that In order to prove this result, we require
Lemma 10: Let N be a normal subgroup of A_{n} Proof: By Proposition 7, it suffices to show that every 3cycle belongs to N. Let
(i) = i',
(j) = j',
(k) = k'.
Then (4)
(ijk)^{1} = (i'j'k').
If
{a, a'} {i', j', k'} = .
Then, since
(ijk)^{1} = (aa')(ijk)^{1}(aa')
= (aa')(i'j'k')(aa')
= (i'j'k').
Thus, again 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
(i_{1}i_{2}i_{3}...)...,
while in the later is of the form (6)
(i_{1}i_{2})(i_{3}i_{4})...
In the first case, if
' = ^{1} = (i_{1}i_{2}i_{4}...)...,
and any integer left fixed by is also left fixed by '. Since N is normal, we have
' = ^{1} = (i_{1}i_{2})(i_{4}i_{5})...
is an element of N, which leaves every integer left fixed by , except for i_{5}. Moreover, 
Back  Table of Contents 