[Math] Prove that any element in $S_n$ can be written as a finite product of the following permutations

Question

Prove that any element in $S_n$ can be written as a finite product of the following
permutations:

$(a)\ (12),(13), . . . , (1n)$

$(b)\ (12),(23),…,(n−1,n)$

$(c)\ (12),(12\dots n)$.

I have no idea where to start. I know that the products from each category results an element of $S_n$, but no clue for the reverse. I think if some element is n-cycle it must be possible to write as products of transpositions in $(a)$ and depending on the cycle, just order in product varies.

Thank you for guidance.

Answer 1

Every permutation is a product of transpositions. Hence all you have to check is:

1. Any transposition $(k\,l)$ can be obtained as a product of transpositions of type (a).
2. Transpositions of type (a) can be obtained as a product of transpositions of type (b).
3. Transpositions of type (b) can be obtained as a product of permutations of type (c).

We'll use the fact that any two transpositions are conjugate by a transposition:

(1) is easy: $\,(k\,l)=(1\,k)(1\,l)(1\,k)$.

(2) is by induction on $k$: $(1\,2)$ is both of types (a) and (b). Suppose now $(1\,k)$ can be obtained from transpositions of type (b). Then $(1\,k)(k,\,k+1)(1\,k)=(1\,k+1)$ is likewise obtained from type (b).

(3) also by induction on $k$: let $\gamma=(1\,2\,\dots\,n)\,$. We have $\,(2\,3)= \gamma(1\,2)\,\gamma^{-1}$, and more generally: $\,(k\enspace k+1)=\gamma^{k-1}(1\,2)\,\gamma^{-(k-1)}$ for all $\,2\le k\le n-1$.