# Generating Set for the Symmetric Group - Question

1. Mar 7, 2005

### MattL

Explain why the permutations (1 2) and (1 2 ... n) generate all of Sn, the symmetric group (the group of all permutations of the numbers {1,2,...,n}?

Perhaps something to do with the fact that
(1 2 ... n) = (1 2) (1 3) ... (1 n)?
Other than that I haven't got a clue - help! (please!!!)

Thanks

2. Mar 7, 2005

### Hurkyl

Staff Emeritus
Try working it out directly for small n; that might give you ideas.

3. Mar 7, 2005

### MattL

After giving it a go, I've managed to get, for n = 5

(2 3) = (1 2 3 4 5)^4 (1 2) (1 2 3 4 5)
(3 4) = (1 2 3 4 5)^3 (1 2) (1 2 3 4 5)^2
(4 5) = (1 2 3 4 5)^2 (1 2) (1 2 3 4 5)^3

So I can get the transpositions (1 2), (2 3), (4 5), but I can't work out how to get all of the others that I am missing, these being (1 3), (1 4), (1 5), (2 4), (2 5), (3 5). Even if I could, I'm not sure I'd know how to generalise for n. Also, I'm not entirely sure why the compositions I've used above work or where the pattern comes from - I used my computer to do some guesswork for those.

ps if i don't reply, it's because I've gone to bed!

Last edited: Mar 7, 2005
4. Mar 8, 2005

### Hurkyl

Staff Emeritus
Doesn't there seem to be a pattern there? Does it apply for other n? Say, 4 or 6?

5. Mar 8, 2005

### matt grime

why don't you conjugate (12) by (1,..,n) and powers of (1,..,n)?

6. Mar 8, 2005

### MattL

Yep, there seems to be a pattern of
(m+1 m+2) = (1 2 ... n)^(n-m+1) (1 2) (1 2 ... n)^(m-1)
and after trying some in Maple, I think that it does hold for other n.
Still, that doesn't give me a complete set of transpositions.

(Another thing - would be ok to use the inverse of (1 2 ... n) in my answer? Not that I know how I would, but does the original question allow this?)

7. Mar 8, 2005

### matt grime

The inverse of (1,..,n) is a power of (1,..,n) (but usually one allows inverses as well, though for a finite group this is not explicitly needed - do you see why?).

What makes you think you should get a list of all transpositions from the expressions you've written down? You may then compose (indeed conjugate) the transpositions (m, m+1) and (m+1,m+2) and still be in the set generated by (12) and (1..n)

8. Mar 8, 2005

### MattL

how do I conjugate them? I've only recently started permutations and group theory (and yet I've been given this question ), so my knowledge is still quite basic ( )

EDIT: oh, I see...

9. Mar 8, 2005

### matt grime

To conjugate g by h one works out the product h**(-1)gh, where h**(-1) is h inverse. My caret key is broken on my laptop.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook