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

[Edellaine]

Homework Statement

5.1: Prove that S_n is generated by the set {(1 2), (3 4),...,(n-1 n)}

Homework Equations

None that I know of

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.

 

[Dick]

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.

 

[Edellaine]

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 \leq k (for strong induction), where k \geq1.
There for any (i j) with j-i = k+1, then (i i+1)(i+1 j) and j-(i+1) = j-i-1\leq 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)

 

[Dick]

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 \leq k (for strong induction), where k \geq1.
There for any (i j) with j-i = k+1, then (i i+1)(i+1 j) and j-(i+1) = j-i-1\leq 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)

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?