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

Thanks for the help.  After reading your reply, it wasn't immediately 
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 
you said. But if you had asked me last night (before your hint), I'm 
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 
helped me understand how you're thinking about this type of problem.

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

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