Writing Permutations as composition of transpositions
I am currently learning about, and I am also going to give a short presentation on, a theorem that states the following:
Theorem: The number of transpositions whose product is a given permutation of a finite set is either always even or always odd.
I would like to use a short example to illustrate this point, but I'm having a little trouble.
One permutation I was thinking of using was from my textbook:
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 2 & 4 & 3 & 1 \\ \end{pmatrix}
I have found one composition of transpositions by taking the product of it's disjoint cycles ( $(1, 6)$ $(2, 5, 3)$) and turned is into a composition of transpositions:
$(1, 6)(2, 5)(2, 3)$
However, I am having trouble finding different compositions of transpositions with this permutation. Any help here is greatly appreciated. Thanks in advance.
$\endgroup$ 52 Answers
$\begingroup$This can't be an exhaustive method to find all possible sequences of transpositions, but one way that comes to mind to find some more sequences of transpositions is the following.
Denote the permutation $\sigma$. Then look at all of the positions $i = 1, \dots, 6$ such that $\sigma(i) \not= i$. In this case this is all integers $1, \dots, 6$ except for $4$.
Then for each $i$, choose the transposition $\tau$ such that $\tau(i) = \sigma(i)$ to start with.
In this example, $$\begin{array}{rcl} i=1 & \quad & (1,6) \\ i =2 & \quad & (2,5) \\ i = 3 & \quad & (2,3) \\ i = 4 & \quad & NA \\ i = 5 & \quad & (3,5) \\ i = 6 & \quad & (1,6) \end{array} $$
Then, ideally, starting with each (different) transposition, you would require different subsequent transpositions to get the final permutation. To find the subsequent transpositions you could reiterate the method above.
In this case: $$\begin{array}{rclll} i=1 & \quad & (1,6)(2,5)(3,5) & (1,6)(2,3)(2,5) & (1,6)(3,5)(2,3) \\ i =2 & \quad & (2,5)(1,6)(3,5) & (2,5)(3,5)(1,6) & \\ i = 3 & \quad & (2,3)(2,5)(1,6) & (2,3)(1,6)(2,5) & \\ i = 4 & \quad & NA \\ i = 5 & \quad & (3,5)(1,6)(2,3) & (3,5)(2,3)(1,6) & \\ i = 6 & \quad & same\ as \ i=1 & & \end{array} $$
This leads to some different transpositions from the one you mentioned in the question, but it mostly leads to sequences of transpositions which are just re-orderings of each other (i.e., where to place (1,6) is a free choice, and then the rest just comes down to the various ways to decompose the cycle (2,5,3), as you said).
So if you want more exotic compositions of transpositions that contain something unexpected, then I agree with user49640 in the comments that their method is better for finding that.
$\endgroup$ $\begingroup$Before starting, using the usual right-to-left composition of functions, we have
$(1\, 6) (2 \, 5 \, 3) = (1\, 6)(2\, 3)(2\, 5)$
(compare with the OP's statement).
We have the following transposition relation algebra:
\begin{align}(1) \quad (ab)(ab)&=1_{Id}\\ (2) \quad (ab)(cd)&=(cd)(ab)\\ (3) \quad (ab)(ac)&=(bc)(ab)\\ (4) \quad (ab)(bc)&=(bc)(ac)\end{align}
So examining the OP's permutation $\sigma$,
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 2 & 4 & 3 & 1 \\ \end{pmatrix}
this is all about getting other representations for the 'meat' of the permutation, the mapping
$\qquad (2\, 3)(2\, 5)$
Applying (3), $(2\, 3)(2\, 5) = (5\, 3)(2\, 3)$
Applying (3), $(3\, 5)(3\, 2) = (5\, 2)(3\, 5)$
Applying (3) again brings us back to the start.
Applying (4), $(3\, 2)(2\, 5) = (5\, 2)(3\, 5)$, so nothing new.
The OP's permutation can be written in the following ways:
$\quad (1\, 6)(2\, 3)(2\, 5)$
$\quad (1\, 6)(3\, 5)(2\, 3)$
$\quad (1\, 6)(2\, 5)(3\, 5)$
Notice how we get the same answer as Chill2Macht but in a different way.
We can add 'padding', but the parity will not change. For example,
$\quad \sigma = (1\, 6) (4 \, 1) (2\, 3)(2\, 5)(4 \, 1)$
