Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S_n$ be the group of all permutations of the set {$1, 2, \dots,n$}.

The question is whether $S_n$ is generated by a maximum of $n-2$ of its transpositions or not.

Definitions: A permutation of a set $X$, which is a bijective function $\sigma :X\to X$, is called a cycle if the action on $X$ of the subgroup generated by $\sigma$ has exactly one orbit with more than a single element.

A cycle with only two elements is called a transposition.

share|cite|improve this question
up vote 10 down vote accepted

If $\mathcal T$ is a set of transpositions, let $\Gamma(\mathcal T)$ be the graph with vertices $1$, $\dots$, $n$ and in which two vertices $i$ and $j$ are connected by an edge iff $(ij)\in\mathcal T$.

Then $\mathcal T$ generates $S_n$ iff $\Gamma(\mathcal T)$ is connected.

Now, since $\Gamma(\mathcal T)$ has $n$ vertices, one needs at least $n-1$ edges if it is to be connected, so one needs at least $n-1$ transpositions to generate $S_n$.

share|cite|improve this answer
Is there some elementary proof that $\Gamma(\mathcal T)$ is connected implies $\mathcal T$ generates $S_n$? – user641 Dec 21 '11 at 6:27
@SteveD: Yes. Induction on $n$ with $n\leq1$ trivial. First reduce to the case $\Gamma(T)$ is a spanning tree by dropping superfluous edges. Finite trees of size $n>1$ have (at least $2$) leaves, choose one $x$ with remaining tree $R$. If $x$ is a fixed point of the sought permutation apply induction to $R$. If not, permute $R$ (again induction) so that the element that should map to $x$ becomes its neighbour, interchange it with $x$, and finish by another permutation of $R$ supplied by the induction hypothesis. – Marc van Leeuwen Dec 21 '11 at 14:11
@MarcvanLeeuwen: Thank you! – user641 Dec 21 '11 at 16:06

Assume it is true that $S_n$ is generated by a maximum of $n-2$ transpositions. Then $S_3$ would be generated by $1$ transposition. But this is impossible because any transposition has order $2$ and so the cyclic group it generates has only two elements. But $S_3$ has $6$ elements.

Try proving that $S_n$ is generated by exactly $n-1$ transpositions. Use induction. For $S_2$ it is obvious. Then show that $S_n$ can be obtained from $S_{n-1}$ by introducing a transposition that contains the symbol $n$.

share|cite|improve this answer
Your first paragraph leaves the possibility that $S_n$ is generated by $n-2$ transpositions for all $n>3$ :) – Mariano Suárez-Alvarez Dec 21 '11 at 14:47
True. I am just refuting the general statement made by the author of the question. – Manos Dec 21 '11 at 19:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.