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