Prove the symmetric group is generated by

[Samuelb88]

Homework Statement

Use induction of n to prove that the transpositions s_i = (i, i+1), 1 \leq i \leq n - 1 generate S_n.

Homework Equations

Notation: e = Identity permutation.

Any permutation can be written as a disjoint product of transpositions.

The Attempt at a Solution

Proof. We proceed by induction on n. As our base case for n=2, we cite that the transposition s_1 = (12) is sufficient to generate S_n since s_1^2 = e. Suppose now that the transpositions s_i = (i, i+1), 1 \leq i \leq n-1 generate S_n.

I'm not really sure where to go next. I know that S_n has n! elements and want to use that fact along with the transposition (i+1,i+2) to somehow show that S_{n+1} will have (n+1)! elements but I am not sure if that is sufficient to prove that the s_i's generate S_n.

 

[Dick]

Try to show you can write an element s of S_n+1 as an element of S_n times some transpositions. Label which elements of the permutation s map to and from n+1.

 

[Samuelb88]

Dick,

Thanks for your response. It makes sense that I should be able to generate the elements of S_{n+1} using the permutations that are contained in S_n plus the additional transposition s_{n+1} = (n, n+1). But how would I do this?

For example, say I was constructing elements in S_4 from the old transpositions s_1 = (12), s_2 = (23), and the newly acquired transposition s_3 = (34). Then the products s_1 s_2 s_3, s_1 s_3 s_2, and s_2 s_2 s_3 are all different. Here's what confusing me: How can I work around the problem of generalizing a product when the newly acquired transposition is wedged in between two old permutations. Does this make sense? Would it suffice to say that if \sigma \in S_{n+1} and \sigma ' \in S_n, then we can write \sigma in the form of either \sigma' s_{n+1}, or s_{n+1} \sigma', or \sigma_1' s_{n+1} \sigma_2'?

Also, I don't understand what you mean by label which elements of the permutation s map to and from n+1. Can you explain further, please?

 

[Dick]

If s is in S_n+1 there is some l in {1...n+1} such that s(l)=n+1 and some k in {1...n+1} such that s(n+1)=k. For the rest of the i in {1...n} s(i) is in {1...n}. So yes, what you say makes perfect sense. You do some transpositions, apply an element in S_n then do some more transpositions so the result is s in S_n+1. You just have to spell out what those initial and final transpositions are.

 

[Samuelb88]

Great. It makes perfect sense to me now. Thanks again!