# Permutations expressed as product of transpositions

There is a theorem that states that all permutations can be expressed as a product of transpositions. I have a couple of questions about this theorem:

1. Does the product which is equal to the permutation always start from the identity permutation?

In the proof for this theorem our professor has argued that every permutation can be transformed into the identity permutation by applying a certain number of transpositions, e.g. if $\sigma$ is a permutation not equal to the identity permutation then you can apply, say l transpositions, so that you get: $\tau_l \circ \tau_{l-1} \circ .... \circ \tau_1 \circ \sigma = id \Rightarrow \tau_1^{-1} \circ \tau_2^{-1} \circ ... \circ \tau_l^{-1}=\tau_1 \circ \tau_2 \circ .... \circ \tau_l$.

Is this product of transpositions always unique, or can you start from any arbitrary permutation and perform the required number of transpositions to get your permutation?

2 If I form the composition of two permutations, say $\sigma_1$ and $\sigma_2$ given by: $$\sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 &5 &6 &1 &2 \\ \end{pmatrix}$$

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

I can express them in terms of the following transpositions $$\sigma_1 = (1,5)\circ (2,6) \circ (3,5) \circ (4,6)$$ $$\sigma_2 = (1,4) \circ (2,4) \circ (3,6)$$

When I form the composition $\sigma_1 \circ \sigma_2$ I get:

$$\sigma_1 \circ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 &2 &3 &1 &5 \\ \end{pmatrix}$$

But since the product of the transpositions is equal to the permutations, I should get the same result when I use:

$$\sigma_1 \circ \sigma_2 = (1,5)\circ (2,6) \circ (3,5) \circ (4,6) \circ (1,4) \circ (2,4) \circ (3,6)$$

but I get:

$$\sigma_1 \circ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 &5 &3 &2 &4 \\ \end{pmatrix}$$

Why doesn't this work?

• I'm not sure I understand your first question - but for the second one, you're just reading the transpositions in the wrong order. Your convention for $\sigma_1\circ\sigma_2$ is that $\sigma_2$ is applied first, so with the transpositions you need to start from $(3,6)$ and read from right to left. So $1\mapsto 4\mapsto 6\mapsto 2$ etc.
– mdp
Apr 22, 2014 at 13:49
• Thanks for your comment, but I did start from the right side: $\begin{pmatrix} 1 & 2 & 3&4&5&6\end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 2 & 6&4&5&3\end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 4 & 6&2&5&3\end{pmatrix} \Rightarrow \begin{pmatrix} 2 & 4 & 6&1&5&3\end{pmatrix} \Rightarrow \begin{pmatrix} 2 & 4 & 6&3&5&1\end{pmatrix} \Rightarrow \begin{pmatrix} 2 & 4 & 5&3&6&1\end{pmatrix} \Rightarrow \begin{pmatrix} 2 & 1 & 5&3&6&4\end{pmatrix} \Rightarrow \begin{pmatrix} 6 & 1 & 5&3&2&4\end{pmatrix}$ I'm not sure what you mean by $1 \rightarrow 4 \rightarrow 6 \rightarrow 2...$ Apr 22, 2014 at 13:58
• Ah, you made a different mistake that gives the same result as doing the transpositions backwards - on the third arrow you should be swapping the numbers $1$ and $4$ over, wherever they appear, not the first position with the fourth. (I was drawing my way of doing this calculation; put $1$ in on the right and see where it goes - it first gets mapped to $4$ (by $(1,4)$), then $4$ is mapped to $6$ by $(4,6)$, and finally $6$ is mapped to $2$ by $(2,6)$).
– mdp
Apr 22, 2014 at 14:04
• Yes that was the mistake I made. Thanks a lot for your help. Apr 22, 2014 at 14:33

## 1 Answer

Note that the product of transpositions that you used to express $\sigma_1$, when composed, does not again yield $\sigma_1$; I.e., you did not correctly express $\sigma_1$ as a product of transpositions.

Rather, $\sigma_1$ can be written $(1,5)\circ (1, 3)\circ (2, 6)\circ (2, 4)$, or $(1, 3)\circ (3, 5)\circ (2, 4)\circ(4, 6)$...

Similarly, $\sigma_2$ is incorrectly decomposed. Two correct decompositions include $(1, 4)\circ (1, 2)\circ (3, 6)$ and $(1, 2)\circ (2, 4) \circ (3, 6)$...

...which answers your question about uniqueness. When writing a permutation as a product of transpositions, there are many such ways to do this. What does not vary is the parity: an "odd" permutation is one that can only be decomposed to a product of an odd number of transpositions, and "even" permutations can only be decomposed into a product of an even number of transpositions. So, for example, $\sigma_1$ is even, and $\sigma_2$ is odd.

• I don't understand this. If I apply $(1,5)\circ (1,3) \circ (2,6) \circ (2,4)$ on the id permutation I get the permutation $\begin{pmatrix} 5 &6&1&2&3&4 \end{pmatrix}$ Why is this a transposition for $\sigma_1$? I think this goes back to my original question, from which permutation do I start when applying those transpositions? Apr 22, 2014 at 14:26
• You start from the rightmost permutation. Where does it send $1$?. If it sends $1$ to $a$, then you move to the next transposition to its left to see where it sends $a$. Etc. Apr 22, 2014 at 14:30
• Thanks I figured my problem out. I thought that a transposition of the form (1,5) e.g. would exchange the elements in the first and fifth position of the permutation, not the actual numbers 1 and 5. Apr 22, 2014 at 14:33
• Ahhh, I see. Yes, that could easily confuse! Apr 22, 2014 at 14:34