Generating Set for the Symmetric Group - Question

MattL
Messages
11
Reaction score
0
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
 
Physics news on Phys.org
Try working it out directly for small n; that might give you ideas.
 
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:
Doesn't there seem to be a pattern there? Does it apply for other n? Say, 4 or 6?
 
why don't you conjugate (12) by (1,..,n) and powers of (1,..,n)?
 
Hurkyl said:
Doesn't there seem to be a pattern there? Does it apply for other n? Say, 4 or 6?

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?)
 
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)
 
matt grime said:
why don't you conjugate (12) by (1,..,n) and powers of (1,..,n)?

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

EDIT: oh, I see...
 
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.
 

Similar threads

Back
Top