$(12)$ and $(123\dots n)$ are generators of $S_n$

Question

Show that $S_n$ is generated by the set $ \{ (12),(123\dots n) \} $.

I think I can see why this is true. My general plan is (1) to show that by applying various combinations of these two cycles you can get each transposition, and then (2) to show that each cycle is a product of transpositions.

I'm just having trouble on the first step. Any ideas?

Answer 1

Let $c = (1, 2, \dotsc, n)$. We see that \begin{align*} c (1, 2) c^{-1} &= (2, 3) \\ c (2, 3) c^{-1} &= (3, 4) \\ &\vdots \\ c (n-2, n-1) c^{-1} &= (n-1, n), \end{align*} so that $(i, i+1) \in \langle (1, 2), c \rangle$ for all $1 \leq i \leq n-1$. Next, we have \begin{align*} (2, 3) (1, 2) (2, 3)^{-1} &= (1, 3) \\ (3, 4) (1, 3) (3, 4)^{-1} &= (1, 4) \\ &\vdots \\ (n-1, n) (1, n-1) (n-1, n)^{-1} &= (1, n), \end{align*} so that $(1, i) \in \langle (1, 2), c \rangle$ for all $1 \leq i \leq n$. Choose any $1 \leq i < j \leq n$, then $$ (i, j) = (1, i) (1, j) (1, i)^{-1} \in \langle (1, 2), c \rangle. $$ Therefore, $\langle (1, 2), c \rangle$ contains all transpositions. Hence, $\langle (1, 2), c \rangle = S_n$.

Answer 2

A simpler proof:

We know $S_n=\langle(12),(23),\ldots,(n-1,n)\rangle$. As tylerc0816 has pointed out $$(12),(23),\ldots,(n-1,n)\in\langle(12),(12\ldots n)\rangle.$$

The smallest group containing all adjacent traspositions is $S_n$. Therefore, $S_n=\langle(12),(12\ldots n)\rangle$.