Show that every $\sigma \in S_n$ is of the form $\sigma = \prod_i (1 \; \; x_i)$ 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?

 A: 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*}
