Every permutation of $n$ elements is a product of transpositions of the $n$ elements.

My work: We proceed by induction on $n$. Ovbiusly this stetement is true if $n=1,2$.
Now, suppose that $n\geq 3$ and the statement is true for all permutation on $n-1$ elements.

We need prove this is true for $n$ elements.

Let $\sigma\in S_n$.

Exists two cases, Suppose first that $\sigma(n)=n$. Then $\sigma |_{\{1,...,n-1\}}\in S_n$. is a product of transpositions by the inductive hypothesis, and then $\sigma$ is the product of the very same transpositions, regarded as permutations in $S_n$, fixing $n$.

Suppose next that $\sigma(n)\not = n$.

In this case i'm stuck. Can someone help me?

Moreover, if someone know other way to prove this please help me! Thanks.

  • 1
    $\begingroup$ What do you mean by transpositions of the $n$ elements? $\endgroup$ – GhD Dec 30 '17 at 17:42
  • $\begingroup$ They mean elements of $S_n$ that swap only two elements and fix the rest. $\endgroup$ – E-A Dec 30 '17 at 17:44
  • $\begingroup$ If you want to go on induction route, inducting on the sizes of cycles might be more helpful. Also, here is an answer that decomposes a cycle into transpositions. math.stackexchange.com/questions/319979/… $\endgroup$ – E-A Dec 30 '17 at 17:46

If $\sigma(n)\neq n$, consider the transposition $\tau$ which exchanges $n$ and $\sigma(n)$. Then $\tau\sigma$ fixes $n$ and you can apply the induction hypothesis to it.



Suppose $\sigma(n)=a_1$, $\sigma(a_1)=a_2$ until $\sigma(a_i)=n$. If $i\leq n-2$ then every this permutation is product of disjoint permutation of length less than $n$ and by induction it is true you claim. For $i=n-1$ it is easy to find the transpositions!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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