2

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.

Smeef
  • 361
  • 2
    Call the permutation $\alpha$. Here's a way that you can generate many new representations of $\alpha$ as a product of transpositions. Pick another permutation $\beta$. Now calculate the product $\alpha \beta = \gamma$. So you've got $\alpha = \gamma \beta^{-1}$. Do the same thing you did for $\alpha$, but now do it for $\gamma$ and $\beta^{-1}$, and put the two products you get together. Repeat this method for different choices of $\beta$. – user49640 Jun 14 '17 at 14:12
  • When you find the new permutation representations for $\gamma$ and $\beta^{-1}$ using this process, the product of these new permutations will you give a different permutation representation for $\alpha$? And from this new representation you can find different compositions of transpositions? Or am I reading this wrong? – Smeef Jun 14 '17 at 14:31
  • 2
    It may or may not give you a different representation, depending on whether there are cancellations. (By the way, you can always include gratuitous sequences like $(34)(34)$ anywhere you like in a product.) However, often you will get a new representation. – user49640 Jun 14 '17 at 14:35
  • Okay I will try this out, thank you very much – Smeef Jun 14 '17 at 14:36
  • Another thing to note is that you can always replace a transposition $(ab)$ with $(bc)(ac)(bc)$ if you need "padding." – user49640 Jun 14 '17 at 20:52

2 Answers2

1

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.

Chill2Macht
  • 20,920
0

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)$

CopyPasteIt
  • 11,366