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

In summary: But then the induction uses a different ordering for the consecutive integers, and I don't understand why.In summary, S_n is generated by the set {(1 2), (3 4),...,(n-1 n)}
  • #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.
 
Physics news on Phys.org
  • #2


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


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


Edellaine said:
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:

1. What is the Symmetric group?

The Symmetric group, denoted as Sn, is a group consisting of all possible permutations of n elements. In other words, it is the group of all ways in which n objects can be arranged or ordered.

2. What are transpositions?

Transpositions are permutations that swap the positions of two elements while leaving all other elements in their original positions. In the context of the Symmetric group, transpositions refer to the swapping of two elements in the group's permutations.

3. How do we show that the Symmetric group is generated by the set of transpositions (12) and (n-1 n)?

To show that the Symmetric group is generated by a set of elements, we must prove that every permutation in the group can be written as a combination (or product) of those elements. In this case, we can show that any permutation in Sn can be written as a combination of (12) and (n-1 n) using the fact that these two transpositions generate all possible transpositions in the group.

4. Why is it important to show that the Symmetric group is generated by a set of elements?

Showing that the Symmetric group is generated by a set of elements allows us to understand the group's structure and properties better. It also helps us solve problems and make predictions about the group's behavior. In this case, showing that Sn is generated by (12) and (n-1 n) provides us with a more efficient way to express and manipulate the group's permutations.

5. Can the Symmetric group be generated by other sets of elements besides (12) and (n-1 n)?

Yes, the Symmetric group can be generated by other sets of elements besides (12) and (n-1 n). In fact, any set of transpositions that generates all possible transpositions in Sn can be used to show that the group is generated by that set. However, (12) and (n-1 n) are commonly used as they provide a simple and concise way to express the entire set of transpositions in Sn.

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

Back
Top