A particular set of generators for $S_n$

Related to this question and this answer (to a different question) is the following, from Dummit & Foote $$\S$$ 3.5 # 3.

Prove that $$S_n$$ is generated by $$\left \{ (i \ \ \ i+ 1)| 1 \leq i \leq n - 1 \right \}$$ [Consider conjugates, viz. $$(2 \ \ 3)(1 \ \ 2)(2 \ \ 3)^{-1}$$ ]

The book claims that any permutation is a product of transpositions (without proof, but I can find that through the linked pages), and I think I am supposed to use that, but the hint is confusing me. Isn't $$(2 \ \ 3)^{-1}$$ just equal to $$(2 \ \ 3)$$ itself? Here is the proof linked to in the answer above:

Since, for $$1 \leq j < k < n$$ we have $$(j \ \ k + 1) = (k \ \ k+1)(j \ \ k)(k \ \ k+1)$$, ...
($$S_n =$$ the group generated y transposing adjacent points)

Is this sufficient? Don't we need to explicitly look at $$\sigma \in S_n$$?

• note: it should read $\{(i$ $i+1) | 1\leq i \leq n-1\}$ Commented Sep 21, 2011 at 3:19
• @Srivatsan Narayanan, I'm afraid that the significance of the conjugate in this context is lost on me. What is the immediate result of this? Commented Sep 21, 2011 at 3:23
• You have to worry only about transpositions, not all permutations explicitly, because transpositions generate the whole group. So as long as $(j \ k)$ is generated by those elements $\{ (i \ i+1) \}$ for all $j,k$, you are effectively done. Commented Sep 21, 2011 at 3:28
• @Sri: Please feel free to make this (or a beefed-up version of this) an answer. Thanks! Commented Sep 21, 2011 at 3:30

A transposition is just a $2$-cycle in $S_n$, i.e, $(j \ \ k)$ for some $1 \leq j < k \leq n$. The transpositions $\{ (i \ \ i+1) \}$ are also sometimes called simple transpositions. It's a standard theorem that the set $T$ of transpositions generate the whole group $S_n$. This exercise asks you to show that $S_n$ is also generated by the simple transpositions (which is a strict subset of $T$).
Indeed it seems that one has to show that every $\sigma \in S_n$ can be written as a product of simple transpositions. However, one need not worry about all $\sigma \in S_n$ explicitly. Noting that $T$ generates the group, it is sufficient to establish the result for every $\sigma \in T$. And, that's how the solution proceeds as well.
As for the notation $(2 \ \ 3)^{-1}$ instead of $(2\ \ 3)$ in the hint, I just think the author wants to convey the fact that $(2 \ \ 3) (1 \ \ 2) (2 \ \ 3)^{-1}$ is a conjugate of $(1\ \ 2)$. Why the notion of "conjugate" is useful for the problem is a different question; I do not want to reveal that here since I don't want to spoil the fun for the OP :-).