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

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?

• What do you mean by transpositions of the $n$ elements? – GhD Dec 30 '17 at 17:42
• They mean elements of $S_n$ that swap only two elements and fix the rest. – E-A Dec 30 '17 at 17:44
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!