# 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\}$ –  Deven Ware Sep 21 '11 at 3:19
Thanks @Deven.. –  Altar Ego Sep 21 '11 at 3:22
@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? –  Altar Ego Sep 21 '11 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. –  Srivatsan Sep 21 '11 at 3:28
@Sri: Please feel free to make this (or a beefed-up version of this) an answer. Thanks! –  Altar Ego Sep 21 '11 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 :-).