# symmetric group is generated by adjacent transpositions

###### Theorem 1.

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

 $(1,2),(2,3),\ldots,(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 $\phi$ be a permutation of $\{1,2,\ldots,n+1\}$. If $\phi(n+1)=n+1$, then the restriction of $\phi$ to $\{1,2,\ldots,n\}$ is a permutation of $n$ numbers, hence, by hypothesis, it can be expressed as a product of transpositions.

Suppose that, in addition, $\phi(n+1)=m$ with $m\neq n+1$. Consider the following product of transpositions:

 $(nn+1)(n-1n)\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)\cdots(m+1m+1)(mm+1)\phi$

produces $n+1$. Hence, the restriction of this permutation to $\{1,2,\ldots,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 $\phi$ may also be expressed as a product of transpositions. ∎

Title symmetric group is generated by adjacent transpositions SymmetricGroupIsGeneratedByAdjacentTranspositions 2013-03-22 16:49:02 2013-03-22 16:49:02 rspuzio (6075) rspuzio (6075) 11 rspuzio (6075) Theorem msc 20B30