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

### Generators for the Group S_n

```
Date: 10/08/2001 at 17:38:10
From: Julius Hodge
Subject: Abstract Algebra - generators for the group S_n

Show that S_n, the symmetric group on n elements, is generated by
the elements:

(1 2) and (1 2 3 ... n) for all n>=2.

I tried it for n = 3 and (by brute force) I see that it works in
that case. I wrote down all 24 of the permutations for n = 4 but
couldn't figure out how to write a random element in S_4 as a product
of (1 2)'s and (1 2 3 ... n)'s.

For example I picked the element (3 4).

I see I have to come up with a permutation that fixes 1 and 2 while
sending 3 to 4 and 4 to 3. But how to do this with the given elements
isn't clear to me. Perhaps if you could help me see how it works a
given element I could generalize the procedure to work for any element
in S_n for any n > 2.

Any help would be appreciated. Thanks.
Julius Hodge
```

```
Date: 10/09/2001 at 02:29:21
From: Doctor Schwa
Subject: Re: Abstract Algebra - generators for the group S_n

Hi Julius,

the (1 2 3 ... n) cycles the whole list.  So to swap 3 and 4, you

1) cycle the set till 3 and 4 are in the first two positions
(that is, apply (1 2 3 4) twice)

2) swap the first two positions (that is, apply (1 2) once)

and then

3) cycle the set to put everybody back where they came from
(that is, apply (1 2 3 4) twice more).

This general pattern - move stuff, do something, put it back where
you found it - is so common it has a special name: conjugation.

That is, x A x^-1 is called a "conjugate" of A.

Anyway, using this conjugation idea you can take the (1 2) and make
it flip any two adjacent elements; then you can put those together
to flip any two elements at all, which in turn generates the whole
set.

Thanks for the fun question!

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

```
Date: 10/09/2001 at 15:35:02
From: Julius Hodge
Subject: Re: Abstract Algebra - generators for the group S_n

clear to me how things worked out, but your hint about conjugation
really helped a lot. I let

a = (1 2 ... n)

and

b = (1 2)

and decided to see what would happen when I computed

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

a^2 * b * a^(n-2)

a^3 * b * a^(n-3)

.
.
.

a^i * b * a^(n-i)

I noticed that a^i * b * a^(n-i) is always equal to the two-cycle
(i+1 i+2) for i = 0 .. n-2 (and your explanation above explained why
this was occurring).

So then I was able to show that <a,b> =

< (1 2), (2 3), ... , (n-1 n) >

The previous exercise in the text we are using (Dummit and Foote) was
to show that this generated S_n. So I knew I was on the right track.

I was then able to show that every two-cycle of the form (i i+2) could
be made from these n-1 2-cycles by the following procedure:

(i i+1)(i+1 i+2)(i i+1) = (i i+2)

Then I showed that every 2-cycle of the form (i i+3) could be made
from the original n-1 2-cycles and from the n-2 2-cycles of the form
(i i+2) that I just created:

(i i+1)(i+1 i+3)(i i+1) = (i i+3)

Similarly, *every* 2-cycle can be obtained from the original n-1
2-cycles by a sort of inductive argument.

And that completed the proof. Since I had shown that

S_n = < (1 2), (2 3), ... , (n-1 n) >

and since I knew that

<a,b> = < (1 2), (2 3), ... , (n-1 n) >

I was able to conclude that S_n = <a,b>, which was to be shown.

Thanks for the nice hint - I don't know if I would have seen how to do
this problem without it.

Now that I see how to do it, I agree that this is a fun question - as
not so sure I would have agreed with you!

Regards,
Julius
```

```
Date: 10/10/2001 at 18:14:36
From: Doctor Schwa
Subject: Re: Abstract Algebra - generators for the group S_n

Julius,

Thanks very much for the note. I think your more detailed explanation
of this problem is better than mine! I'm glad my hint helped get you
started and you did a super job working things through on your own.

Also thanks for sharing your work with me: it was fun to read, and

Plus I now have a new convert to appreciate the power of conjugation!

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Modern Algebra

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