# How to prove that $\langle\{ (1,2),(1,2,\ldots,n) \}\rangle=\mathfrak{S}_n$

Let $n\geq 2, \tau=(1,2),\ c=(1,2,\ldots,n)$ two permutation of $\mathfrak{S}_n$

Prove that $$\biggl\langle\{ (1,2),(1,2,\ldots,n) \}\biggr\rangle=\mathfrak{S}_n$$

Indeed,

normally i will started with

$$\left\langle \left. (1,2),(1,2,3) \right\rangle \right.=\left\{ {{(1,2)}^{i}}{{(1,2,3)}^{j}}|\,i=\,0\,,1\,\,\,\,,\,\,j=0,1,2\, \right\}$$ but this is not gonna work since $\mathfrak{S}_{n}$ with the composition operator isn't an Abelian group for $n \geq 3$

so i will use the propriety :

The permutation group $\mathfrak{S}_n$ on $n$ things $\{1,2,\ldots,n\}$ is generated by transpositions transpositions. how can i use the following $$\biggl\langle \{(1,2),(2,3),\ldots,(n-1,n) \}\biggr\rangle=\mathfrak{S}_{n}$$ to prove that $$\biggl\langle\{ (1,2),(1,2,\ldots,n) \}\biggr\rangle=\mathfrak{S}_n$$

• Hint: let's say you want to switch the fourth and fifth element in a group of elements, but you can only cyclically permute all of them or interchange the first two. Then you can perform the cyclic permutation as many as you need to get the fourth and fifth element in the first two places, then interchange them, and then cyclically push them forward to the place where they started from again. This is the intuitive idea. – B. Pasternak Jun 15 '16 at 13:23

## 1 Answer

I'll try to explain the steps for the proof.

• Realize that every permutation can be written via transpositions.
• conjugation does not change the cycle structure, so...
• show by induction that the transposition $(i, i+1)$ $(i=1,..,n; n+1=1)$ can be constructed via $c$ and $\tau$. start with $c^{-1}*(1,2)*c=(3,2)=(2,3)$ (I calculate from left to right)
• now construct the rest of the transpositions with the transpositions $(i, i+1)$

Thus by the first bullet point, you have now constructed all the permutations of $S_n$.