Show that every $\sigma \in S_n$ is of the form $\sigma = \prod_i (1 \; \; x_i)$

Question

Let $n \in \Bbb N$ and let $S_n$ denote the group of permutations of $\{1,2,...,n\}$.

Prove that for all $\sigma \in S_n$, we have:

$$\sigma = \prod_{i=1}^m (1 \ \ x_i), \text{ for some $x_1,...,x_m \in \{1,...,n\}$}$$

here, $(1 \ \ x_i)$ denotes a transposition of $1$ and $x_i$.

I understand why this is true.

If, for instance,

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 3 & 5 & 2 \end{pmatrix}$$

Then, we can write:

$$\sigma = (1 \ \ 2)(1 \ \ 5)(1 \ \ 4)$$

However, I am unable to construct an algorithm for writing a general $\sigma$ in this form.

Can someone offer a proof of that?

Answer 1

If $(a \;\; b)$ is a transposition with $a,b \neq 1$ then $$ (a \;\; b) = (1 \;\; a) (1 \;\; b) (1 \;\; a). $$ So every transposition can be written as such a product. Now every cycle $(a_1 \;\; \cdots \;\; a_n)$ can be written as the product of transpositions $$ (a_1 \;\; \cdots \;\; a_n) = (a_1 \;\; a_2) (a_2 \;\; a_3) \dotsm (a_{n-2} \;\; a_{n-1}) (a_{n-1} \;\; a_n). $$ Lastly, every permuation can be written as the product of (disjoint) cycles.

Combining this we can write every permutation as the product of transpositions of the form $(1 \;\; a)$.

(We can also decompose a cycle $(a_1 \;\; \cdots \;\; a_n)$ as $$ (a_1 \;\; \cdots \;\; a_n) = (a_1 \;\; a_n) (a_1 \;\; a_{n-1}) \dotsm (a_1 \;\; a_3) (a_1 \;\; a_2). $$ If then $a_1 = 1$ then the transpositions $(1 \;\; a_i)$ are already of the desired form, and no further decomposition is needed.)

PS: As an example take your permutation $$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 3 & 5 & 2 \end{pmatrix}. $$ We have $$ \sigma = (1 \;\; 4 \;\; 5 \;\; 2) = (1 \;\; 2) (1 \;\; 5) (1 \;\; 4). $$ Another examples would be $$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 7 & 1 & 2 & 3 & 8 & 4 & 6 \end{pmatrix}, $$ for which we have \begin{align*} \tau &= (1 \;\; 5 \;\; 3) (2 \;\; 7 \;\; 4) (6 \;\; 8) \\ &= (1 \;\; 3) (1 \;\; 5) (2 \;\; 7) (7 \;\; 4) (6 \;\; 8) \\ &= (1 \;\; 3) (1 \;\; 5) (1 \;\; 2) (1 \;\; 7) (1 \;\; 2) (1 \;\; 7) (1 \;\; 4) (1 \;\; 7) (1 \;\; 6) (1 \;\; 8) (1 \;\; 6). \end{align*}