Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Modern Algebra
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search