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

  • Thread starter Edellaine
  • Start date
  • #1
11
0

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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619


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.
 
  • #3
11
0


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)
 
  • #4
Dick
Science Advisor
Homework Helper
26,260
619


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)

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:

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

Replies
4
Views
2K
Replies
12
Views
6K
Replies
6
Views
6K
  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
5
Views
1K
Replies
3
Views
3K
Top