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.
Best Answer
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.