1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mdp Apr 22 '14 at 13:49
  • $\begingroup$ 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...$ $\endgroup$ – eager2learn Apr 22 '14 at 13:58
  • 1
    $\begingroup$ 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)$). $\endgroup$ – mdp Apr 22 '14 at 14:04
  • $\begingroup$ Yes that was the mistake I made. Thanks a lot for your help. $\endgroup$ – eager2learn Apr 22 '14 at 14:33
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – eager2learn Apr 22 '14 at 14:26
  • $\begingroup$ 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. $\endgroup$ – Namaste Apr 22 '14 at 14:30
  • $\begingroup$ 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. $\endgroup$ – eager2learn Apr 22 '14 at 14:33
  • $\begingroup$ Ahhh, I see. Yes, that could easily confuse! $\endgroup$ – Namaste Apr 22 '14 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.