Question

Use induction on $\mathit{n}$to give an alternate proof of Theorem 7.26: Every element of ${\mathit{S}}_{\mathbf{n}}$is a product of transpositions.

Short answer

It is proved that every element of $S_n$ is a product of transpositions.

Step-by-step solution

Prove using induction

For $n=2$, the set for $S_2$is $\left\{\left(1\right),\left(12\right)\right\}$ , where $1=\left(12\right)\left(12\right)$, this implies that the theorem holds.

Let us assume that every element of$S_{n-1}$ is a product of transpositions and assume $\tau \in S_n$.

Prove the result\[\ta

Assume that$n$is fixed by$\tau$then $\tau$ is contained in the natural inclusion of$S_{n-1}$ into $S_n$ and therefore, by the inductive hypothesis$\tau$can be decomposed as product of transpositions.

Suppose $\tau \left(n\right)\ne n$ then$\left(n\tau \left(n\right)\right)\tau$fixes$n$, then by inductive hypothesis $\left(n\tau \left(n\right)\right)\tau$ can be decomposed as the product of transposition.

Assume that $\tau =\left(n\tau \left(n\right)\right)\left(n\tau \left(n\right)\right)\tau$, this implies that $\tau$ can be decomposed as the product of transposition.

Hence, it is proved that every element of $S_n$is a product of transpositions.