symmetric group is generated by adjacent transpositions

Theorem 1.

The symmetric group on $\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{\dots }\mathrm{,}n\mathrm{\}}$ is generated by the permutations

$$(1,2),(2,3),\mathrm{\dots },(n-1,n).$$

Proof.

We proceed by induction on $n$. If $n=2$, the theorem is trivially truebecause the the group only consists of the identity and a single transposition.

Suppose, then, that we know permutations of $n$ numbers are generatedby transpositions of successive numbers. Let $\varphi$ be a permutation of$\{1,2,\mathrm{\dots },n+1\}$. If $\varphi (n+1)=n+1$, then the restriction of$\varphi$ to $\{1,2,\mathrm{\dots },n\}$ is a permutation of $n$ numbers, hence,by hypothesis, it can be expressed as a product of transpositions.

Suppose that, in addition, $\varphi (n+1)=m$ with $m\ne n+1$. Considerthe following product of transpositions:

$$(nn+1)(n-1n)\mathrm{\cdots }(m+1m+1)(mm+1)$$

It is easy to see that acting upon $m$ with this product of transpositionsproduces $+1$. Therefore, acting upon $n+1$ with the permutation

$$(nn+1)(n-1n)\mathrm{\cdots }(m+1m+1)(mm+1)\varphi$$

produces $n+1$. Hence, the restriction of this permutation to$\{1,2,\mathrm{\dots },n\}$ is a permutation of $n$ numbers, so,by hypothesis, it can be expressed as a product of transpositions.Since a transposition is its own inverse, it follows that$\varphi$ may also be expressed as a product of transpositions.∎