04/01/2017

## Proof: every cycle expresses as a product of transpositions

To show that a cycle $(a_1~a_2~\dots~a_{r-1}~a_r)$ can be written as a product of one or more transpositions, it suffices to prove the validity of the identity $(a_1~a_2~\dots~a_{r-1}~a_r)=(a_r~a_{r-1})\dots (a_r~a_2)(a_r~a_1)$, which will be done by using mathematical induction.

Assume that the identity holds for $k$. It will be shown that it also holds for $k+1$, as in $(a_1~a_2~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_2)(a_{k+1}~a_1)$.

Start by noticing that $(a_1~a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})(a_{k+1}~a_1)$.

Due to the induction assumption, which says that a $k$-length cycle can be decomposed into a product of transpositions, $(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})$ can be written as $(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_3)(a_{k+1}~a_2)$.

By combining the last two equations, the conclusion follows for $k+1$.