Prove that $\{(1 2),(1 2 ... n)\}$ can generate $S_n$

Question

I am self-studying group theory, and find it frustrating that problems on my books do not have solutions provided, here is one:

Show that the symmetry group $S_n$ can be generated by the set $\{(1 2),(1 2 \cdots n)\}$ of a transposition and a n-cycle

My thoughts:

To prove that elements in this set actually generate $S_n$, I shall show that every permutation $\sigma \in S_n$ can be written as a combination of $(1 \ 2)$ and $(1 \ 2 \ \cdots \ n)$. How shall I proceed to solve this problem?

Answer 1

Filling in the details for my comment:

Let $\sigma = (1\;2\;3\cdots n)$ and $\tau=(1\;2)$. We will first show that using $\sigma$ and $\tau$, we can generate all transpositions of the form $(k\enspace k+1)$. The main idea is that we can use the cycle $\sigma^{-1}$ to "shift up" the numbers which we are permuting so that the pair that we want to transpose end up in the $1$ and $2$ places, use the transposition $\tau$ to swap these two elements, and then use $\sigma$ to "shift everything back".

More explicitly, we can generate the transposition $(k\enspace k+1)$ as follows:

• We shift the numbers up $k-1$ spaces so that $k$ occupies the position of $1$. This is accomplished by applying the permutation $\sigma^{-(k-1)}$.
• We swap the numbers in the first and second position (now equal to $k$ and $k+1$) by applying the transposition $\tau$.
• We move the numbers back up by $k-1$ positions so that all of the numbers except $k$ and $k+1$ are in their original places. This is accomplished by applying the permutation $\sigma^{k-1}$.

The above argument leads us to expect that $$ (k\enspace k+1) = \sigma^{k-1} \tau \sigma^{1-k} $$

Alternatively, we could show that we can generate the transposition $(k\enspace k+1)$ by building up the set of transpositions inductively. Specifically, we already know that we can generate $(1\; 2)$ since it is just equal to $\tau$. We can then show that if we can generate the transposition $(k\enspace k+1)$, then we can also generate the transposition $(k+1\enspace k+2)$. The key step here is to use the identity $$ (k+1\enspace k+2) = \sigma (k\enspace k+1) \sigma^{-1} $$

We now show that we can generate all transpositions of the form $(1\; k)$ for $k$ from $1$ to $n$. We can build up this set of transpositions inductively too. We know, as the base case, that we can generate the transposition $(1\; 2)$ since it is just equal to $\tau$. Now suppose that we know that we can generate $(1\; k)$ for some $k<n$. Then we can also generate $(1\enspace k+1)$ since we have that $$(1\; k+1) = (1\;k)(k\enspace k+1)(1\;k) $$ and we know already that we can generate the transpositions $(1\; k)$ and $(k\enspace k+1)$.

Finally, we can show that (using $\sigma$ and $\tau$) we can generate arbitrary transpositions. If $(m\; k)$ is any transposition, then we have that $$ (m\; k) = (1\; m)(1\; k)(1\; m)$$

Thus the group generated by $\sigma$ and $\tau$ includes all transpositions. Since we know that $S_n$ itself is generated by transpositions, we see that $\sigma$ and $\tau$ must in fact generate all of $S_n$.