Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generating Set for the Symmetric Group - Question

  1. Mar 7, 2005 #1
    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. jcsd
  3. Mar 7, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Try working it out directly for small n; that might give you ideas.
     
  4. Mar 7, 2005 #3
    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
  5. Mar 8, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Doesn't there seem to be a pattern there? Does it apply for other n? Say, 4 or 6?
     
  6. Mar 8, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    why don't you conjugate (12) by (1,..,n) and powers of (1,..,n)?
     
  7. Mar 8, 2005 #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?)
     
  8. Mar 8, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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)
     
  9. Mar 8, 2005 #8
    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...
     
  10. Mar 8, 2005 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Generating Set for the Symmetric Group - Question
Loading...