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!