1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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