Permutation Groups Generated by 3-Cycles

Date: 05/14/2003 at 19:22:32
From: Kim
Subject: Abstract Algebra

Prove A_n is simple for n >= 5,

 (a) Show A_n contains every 3-cycle if n >= 3.
 (b) Show A_n is generated by 3-cycles for n >= 3.
 (c) Let r and s be fixed elements of {1, 2,..., n} for n >= 3.  Show    
     that A_n is generated by the n "special" 3-cycles of the form 
     (r, s, i) for 1 <= i <= n.

I know (a,b)(c,d) = (a,c,b)(a,c,d) and (a,c)(a,b) = (a,b,c) and 
every 3-cycle is the product of "special" 3-cycles by computing 
(r,s,i)^2, (r,s,j)(r,s,i)^2, (r,s,j)^2(r,s,i), and 
(r,s,i)^2(r,s,k)(r,s,k)(r,s,j)^2(r,s,i). These products give all 
possible types of 3-cycles.

Date: 05/15/2003 at 08:33:40
From: Doctor Jacques
Subject: Re: Abstract Algebra

Hi Kim,

All the proofs I know of this are rather messy.

In the following, we will multiply permutations from right to left.

Since you have already proved parts (a), (b), and (c), I'll merely 
summarize these points.

Part (a) is obvious, since 3-cycles are even permutations.

For part (b), every element of A_n is a product of an even number of 
transpositions (2-cycles). As

  (a,b)(c,d) = (a,c,b)(a,c,d)
  (a,c)(a,b) = (a,b,c)

every pair of transpositions can be written as a product of 3-cycles, 
and so these cycles generate A_n.

For part (c), we must check that every 3-cycle can be expressed using 
the "special" 3-cycles. We check the various possible types 
separately:

Type (i) : (r,s,i)
------------------
These are already in the required form

Type (ii) : (r,i,s)
-------------------
(r,i,s) = (r,s,i)^(-1) = (r,s,i)^2

Type (iii) : (r,i,j)
--------------------
(r,i,j) = (r,j,s)(r,s,i)(r,s,j), and (r,j,s) can be further expanded 
as type (ii).

Type (iv) : (s,i,j)
-------------------
(s,i,j) = (r,s,i)(r,s,j)(r,i,s), and (r,j,s) can be further expanded 
as type (ii).

Type (v) : (i,j,k)
------------------
(i,j,k) = (r,k,s)(r,i,j)(r,s,k), where (r,k,s) is type (ii) and 
(r,i,j) is type (iii).

We can now come to the main part of the theorem: A_n is simple for 
n >= 5. Let N be a non-trivial normal subgroup of A_n. We must show 
that N = A_n.

Lemma 1
-------
All type (i) cycles are conjugate in A_n.

This results from:

 (r,s,k) = (i,k,j)^(-1)*(r,s,i)*(i,j,k)

Lemma 2
-------
All 3-cycles are conjugate in A_n.

We prove that every 3-cycle is conjugate to a type (i) cycle.

For type (ii), we have:

  (r,i,s) = f^(-1)*(r,s,i)*f

where f = (i,s)(j,k) belongs to A_n. Note that we used the fact than 
n >= 5.

For the other types, note that the relations above are already 
conjugation relations, since the permutation on the left is the 
inverse of the one of the right, and these permutations belong to A_n.

Lemma 3
-------
If N contains a 3-cycle, N = A_n

As N is normal, it must contain all the conjugates of the 3-cycle, 
and this includes all the type (i) cycles. As these cycles generate 
A_n, we have N = A_n.

It remains to show that N contains a 3-cycle. To make things more 
readable, we will use positive integers 1,2, ... to denote elements 
of the set A_n is acting on.

Let a be a non-identity permutation of N that moves the fewest 
possible number of elements, i.e. that fixes the greatest possible 
number of elements. As a is even, it must move at least 3 elements. 
We will assume by contradiction that a moves at least 4 elements.

Case 1
------
a contains a cycle of length at least 3, say (1,2,3...). In this case, 
a cannot move only 4 elements, since it would be a 4-cycle, which is 
an odd permutation. Therefore a moves at least 5 elements, and we can 
assume that they are {1,2,3,4,5}. We can write a as:

  a = (1,2,3,...)*u

(we do not exclude that the first cycle be of length 3). u does not 
move the elements 1,2,3.

Consider now:

 c = b^(-1)*a*b

where b = (3,5,4).

We have:

 c = (3,4,5)*(1,2,3,...)*u*(3,5,4)
   = (1,2,4,...)*...

since u does not contain 1,2,3.

Note that, as N is normal and c is a conjugate of a, N contains c. As 
N is a subgroup, it also contains:

 d = c*a^(-1) = (1,2,4,...)*...u^(-1)*(3,2,1,...)

and we note that d(2) = 2, since nothing between the first and last 
cycle contain 1 or 2. Note also that d is not the identity, since
d(3) = 4.

Now, we assumed that a moves at least 5 elements, so all the elements 
fixed by a are >= 6. These elements are also fixed by d; in addition, 
d fixes 2, and so fixes more elements than a, contrary to our 
assumption on the choice of a.

Case 2
------
a contains only transpositions (an even number of them, of course). 
We write a as:

  a = (1,2)(3,4)*v

In addition, if there are more than two transpositions, we number the 
elements to include 5 in one of the remaining transpositions. v moves 
none of the elements 1,2,3,4.

We proceed as in the previous case, with the same b. In this case, we 
have:

  c = (3,4,5)*(1,2)*(3,4)*v*(3,5,4)
    = (1,2)*(4,5)*...

since v does not contain 1,2,3,4

As in the previous case, we note that H also contains:

  d = c*a^(-1) = (1,2)*(4,5)*...*v^(-1)*(3,4)*(1,2)

and, as nothing between the first and last cycle contains 1, 2, or 4, 
we see that d fixes 1 and 2, and that d(3) = 5, so d is not the 
identity.

If a contains more than 2 transpositions, then a moves 5 (because of 
our choice of labelling) and we can use the same argument as before 
to show that d fixes more elements than a.

On the other hand, if a contains only two cycles, i.e. a = (1,2)(3,4) 
we have:

  c = (3,4,5)*(1,2)*(3,4)*(3,5,4)
    = (1,2)*(4,5)

  d = (1,2)*(4,5)*(1,2)*(3,4)
    = (3,5,4)

and again, d moves less elements than a.

Our initial assumption, that the smallest non-identity permutation in 
N moves more than 3 elements, has thus been proven false. This means 
that N contains a 3-cycle, and, by lemma 3, N = A_n. This shows that 
A_n does not contain a proper non-trivial normal subgroup, i.e. that 
A_n is simple.

Note that the proof above uses the fact that n >= 5, as we needed 
elements 1 through 5. Indeed, A_4 contains the Klein group as a normal 
subgroup.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/