Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

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|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
1  
@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|improve this answer
1  
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

 
discard

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.