3
$\begingroup$

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.

2 Answers 2

11

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$.

  • 0
    @MarcvanLeeuwen: Thank you!2011-12-21
3

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$.

  • 0
    True. I am just refuting the general statement made by the author of the question.2011-12-21