Prove the symmetric group is generated by

[Samuelb88]

Homework Statement

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

Homework Equations

Notation: [itex]e[/itex] = 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 [itex]n=2[/itex], we cite that the transposition [itex]s_1 = (12)[/itex] is sufficient to generate [itex]S_n[/itex] since [itex]s_1^2 = e[/itex]. Suppose now that the transpositions [itex]s_i = (i, i+1)[/itex], [itex]1 \leq i \leq n-1[/itex] generate [itex]S_n[/itex].

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

 

[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 [itex]S_{n+1}[/itex] using the permutations that are contained in [itex]S_n[/itex] plus the additional transposition [itex]s_{n+1} = (n, n+1)[/itex]. But how would I do this?

For example, say I was constructing elements in [itex]S_4[/itex] from the old transpositions [itex]s_1 = (12)[/itex], [itex]s_2 = (23)[/itex], and the newly acquired transposition [itex]s_3 = (34)[/itex]. Then the products [itex]s_1 s_2 s_3[/itex], [itex]s_1 s_3 s_2[/itex], and [itex]s_2 s_2 s_3[/itex] 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 [itex]\sigma \in S_{n+1}[/itex] and [itex]\sigma ' \in S_n[/itex], then we can write [itex]\sigma[/itex] in the form of either [itex]\sigma' s_{n+1}[/itex], or [itex]s_{n+1} \sigma'[/itex], or [itex]\sigma_1' s_{n+1} \sigma_2'[/itex]?

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!