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:
- 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?
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.