Make your own free website on Tripod.com
Let G1 and G2 be groups. An isomorphism from G1 to G2 is an injection phi:G1mapsG2 such that phi(a · b) = phi(a) · phi(b)  (a,b element ofG1 if phi is also surjective G1 is isomorphic to G2). Let H be a subgroup of G. If for every a element of G, we have aHa-1 = H, then H is called a normal subgroup of G. Let G be a group, and let H be a subgroup of G. The number of right cosets in H\G is called the index of H in G and is denoted [G:H]. If f:GmapsH is a homomorphism, then ker(f) is a normal subgroup of G. Let G be a finite group, H a subgroup of G. Then the order of H divides the order of G. If f : GmapsH is a homomorphism, then G/ker(f)isomorphic to im(f)

The Symmetric Groups

In the last section we proved that every finite group is isomorphic to a subgroup of Sn 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 Sn, let us introduce some new notation. Suppose that i1,...,ir are distinct integers, 1 < ij < n. Let

(i1i2...ir)

denote the permutation of Sn which maps i1 onto i2, i2 onto i3,..., and ir onto i1, and which leaves fixed the integers not expressly listed. Such a permutation is called an r-cycle. For example, the permutation (123) of S3 would be written in our old notation as

permutaion.

Any 1-cycle is the identity permutation. Moreover,

(1)
(i1,i2...ir)-1 = (irir-1...i1).

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 not equal 1.

Lemma 1: Let sigma element of Sn, sigma not equal 1. Then sigma 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 sigma element of S8 be given by

sigma = permutaion

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

sigma = (172)(3458),

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

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

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

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

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

Proof: Let sigma element of Sn, sigma not equal 1. We will show that sigma can be written as a product of transpositions. Let

(2)
sigma = (i1i2...ir)(j1...js)(k1...kt)...

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

(3)
sigma = (i1ir)(i1ir-1)...(i1i2)(j1js)...(j1j2)(k1kt)...(k1k2)...

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

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

and sigma is given by (2). Let us set

N(1) = 0.

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

Let eta, sigma element of Sn. Then N(etasigma) congruent to N(eta) + N(sigma) (mod 2).

Theorem 4: Let eta, sigma element of Sn. Then N(etasigma) congruent to N(eta) + N(sigma) (mod 2).

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

sigma = sigma1...sigmaa, eta = eta1...etab

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

N(sigmaeta) congruent to (N(sigma1)+N(sigma2)+...+N(sigmaa)) +
(N(eta1)+...+N(etab)) (mod 2)
congruent toN(sigma) + N(eta) (mod 2).

Thus, let us assume that eta = (ij), and let us assume that sigma 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(etasigma) = (2 - 1) + (r - 1) + (s - 1) + (t - 1) +...= 1 + N(sigma) = N(eta) + N(sigma).

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

(ij)sigma = (jii2...ir)(j1...js)(k1...kt)...

Therefore,

N(etasigma) = 1 + N(sigma) = N(eta) + N(sigma).

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 = i1 and j = j1. Then

(ij)sigma = (jj2...jsii2...ir)(k1...kt)...

so that

N(etasigma) = (r + s -1) + (t - 1)+... = N(eta) + N(sigma).

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

(ij)sigma = (ii2...ik-1)(jik+1...ir)(j1...js)(k1...kt)...

so that

N(etasigma) = (k - 2) + (r - k) + (s - 1) + (t - 1) + ...
= N(eta) + N(sigma) - 2
congruent to N(eta) + N(sigma) (mod 2).

Definition 5: Let sigma element of Sn. Then sigmais even (respectively, odd) if N(sigma) is even (respectively, odd).

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

N(sigma) congruent to N(sigma1 + ... + N(sigmaa) (mod 2)
congruent to 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(sigma-1) = N(sigma), we see that the set of even permutations of Sn form a subgroup. This subgroup is call the alternating group on n elements and is denoted An.

Theorem 6:

(1) An is a normal subgroup of Sn.

(2) If n > 2, the index of An in Sn is 2.

Proof: Let us consider the mapping

psi: Sn maps Z2
psi(sigma) = N(sigma) (mod 2).

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

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

Proposition 7: An 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 = empty set, so that G = {1}. (The smallest subgroup of Sn containing S is just {1}.) But if n < 2, then An = {1}. Thus we may assume that n > 3. Since a 3-cycle is even, it is clear that G subset of An. 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 An is generated by all products of the form (i1i2)(i3i4) (i1 not equal i2, i3 not equal i4). 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 ij(j=1,2,3,4) are distinct. Without loss of generality, we may assume that i1 = i3, i2 = i4. Then

(i1i2)(i3i4) = 1 element of G.

Case 2: Three of the integers i1, i2, i3, and i4 are distinct. Without loss of generality, assume that i1 = i3. Then

(i1i2)(i3i4) = (i1i4i2) element of G.

Case 3: All four of the integers, i1, i2, i3, and i4 are distinct. Then

(i1i2)(i3i4) = (i1i3i2)(i1i3i4) element of 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 = Zp, p a prime, then G is simple. On the other hand, if G = Zn, n not equal 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 not equal 4. Then An is simple.

In order to prove this result, we require

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

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

alpha(i) = i',
alpha(j) = j',
alpha(k) = k'.

Then

(4)
alpha(ijk)alpha-1 = (i'j'k').

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

{a, a'} intersection {i', j', k'} = empty set.

Then, since alpha not an element of An, beta = (aa')alpha element of An. However,

beta(ijk)beta-1 = (aa')alpha(ijk)alpha-1(aa')
= (aa')(i'j'k')(aa')
= (i'j'k').

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

Proof of Theorem 9: An has order 1,1,3 for n = 1,2,3 respectively. In these cases, An has no proper subgroups by Lagrange's theorem. Thus, let us now assume that n > 5. Let N subset of An be a normal subgroup N not equal {1}. We must show that N = An. By Lemma 10 it suffices to show that N contains a 3-cycle. For each sigma Sn, let f(sigma) = the number of integers j (1 < j < n) such that sigma(j) = j. Let us choose sigma element of N - {1} for which f(sigma) is a maximum. Since sigma not equal 1, f(sigma) < n - 1. However, if sigma(j) = j for n - 1 values of j then sigma = 1, so that f(sigma) < n - 2. If f(sigma) = n - 2, then sigma is a transposition, which contradicts the fact that sigma element of An. Therefore, f(sigma) < n - 3. We assert that f(sigma) = n - 3. Assume the contrary. Then f(sigma) < n - 4, and there are at least four integers not mapped into themselves by sigma. Let us examine the expression of sigma 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, sigma looks like

(5)
(i1i2i3...)...,

while in the later sigma is of the form

(6)
(i1i2)(i3i4)...

In the first case, if f(sigma) = n - 4, then sigma is a 4-cycle, which contradicts the fact that sigma is even. Therefore, in the first case, f(sigma) < n - 5. Therefore, there exist integers i4, i5 (1 < i1, i5 < n), distinct from i1, i2, i3, and not left fixed by sigma. Let eta = (i3i4i5). Then

sigma' = etasigmaeta-1 = (i1i2i4...)...,

and any integer left fixed by sigma is also left fixed by sigma'. Since N is normal, we have sigma' element of N. Moreover, sigmasigma' not equal 1, so that f(sigmasigma') < f(sigma) by the definition of sigma. But sigmasigma'-1 leaves fixed all integers which are not left fixed by sigma and sigmasigma'-1 leaves i2 fixed as well. Therefore, f(sigmasigma'-1) < f(sigma) + 1. Thus, a contradiction is reached if sigma is of the form (5). Assume that sigma is of the form (6). Let i5 be an integer left fixed by sigma and set eta = (i3i4i5). Then

sigma' = etasigmaeta-1 = (i1i2)(i4i5)...

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