## You are here

Homesymmetric group is generated by adjacent transpositions

## Primary tabs

# 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. ∎

## Mathematics Subject Classification

20B30*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections