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

Homework Help: Show the Symmetric group is generated by the set of transpositions (12) (n-1 n).

  1. Mar 11, 2010 #1
    1. The problem statement, all variables and given/known data
    5.1: Prove that S_n is generated by the set {(1 2), (3 4),...,(n-1 n)}


    2. Relevant equations
    None that I know of


    3. The attempt at a solution
    Any element in S_n can be written as a product of disjoint n-cycles. So now I need to show any n-cycle can be written as a product of 2-cycles. So if my cycle is (a1 ... ak) = (a1 a2)(a1 a3)...(a1 ak).

    So now I've shown S_n can be generated by 2-cycles in general. I'm not sure how to extend this to say that S_n is generated by the set above.
     
  2. jcsd
  3. Mar 11, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Show the Symmetric group is generated by the set of transpositions (12)...(n-1 n)

    You started your set off wrong. It's not {(12),(34),...}, it's {(12),(23),...}. Now you need to show any 2 cycle is generated by your set.
     
  4. Mar 11, 2010 #3
    Re: Show the Symmetric group is generated by the set of transpositions (12)...(n-1 n)

    Oh, my bad. I wrote the set down wrong.

    WTS: Any 2-cycle is generated by the set {(12)(23)....(n-1 n)}

    So taking any 2-cycle (i j) where j > i (I'm going to work on the difference between j and i. I guess what follows is a sketch. I'll clean it up later.)

    If j-i=1, then (i j) = (i i+1). (Probably want to induct on j-i)
    Say the above is the base case, then we can assume its true for all (i j) where j-i [tex]\leq[/tex] k (for strong induction), where k [tex]\geq[/tex]1.
    There for any (i j) with j-i = k+1, then (i i+1)(i+1 j) and j-(i+1) = j-i-1[tex]\leq[/tex] k.
    Then (i+1 j) is a product of 2-cycles of consecutive integers (as in the above set). Then by induction, so is (i j).

    Then any (i j) in S_n is a product of consecutive integers. (Fin)
     
  5. Mar 12, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Show the Symmetric group is generated by the set of transpositions (12)...(n-1 n)

    That could use some clean up. I'm having a hard time following it. The basic fact you need is just (j,j+1)(j,k)(j,j+1)=(j+1,k), right?
     
    Last edited: Mar 12, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook