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 true because the the group only consists of the identity and a single transposition.

Suppose, then, that we know permutations of $n$ numbers are generated by 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$. Consider the 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 transpositions produces $+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. ∎

Title	symmetric group is generated by adjacent transpositions
Canonical name	SymmetricGroupIsGeneratedByAdjacentTranspositions
Date of creation	2013-03-22 16:49:02
Last modified on	2013-03-22 16:49:02
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	11
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 20B30