Logic for decomposing a permutation into different products composed of transpositions

Question

I know that any permutation cycle can be decomposed into transpositions as follows:

$(a_1,a_2...,a_n) = (a_1,a_{n-1})...(a_1,a_2)$

But in my book there is an example of the following form

$(1,2,3,4,5) = (5,4)(5,2)(2,1)(2,5)(2,3)(1,3)$

I verified that it holds true. But I cant seem to figure out how the author came up with that. Also, What is the generic algorithm to produce all decompositions of permutation in terms of transpositions.

Answer 1

The decomposition given in your question appears to just be an example. As amWhy has pointed out, thus is by no means unique.

In answer to how the author came up with the decompositions, then the one in the question may well have been found by listing a series of transpositions and then working out what their product was! However, here's a bit of intuition behind the two decompositions given in amWhy's answer.

Let $\theta=(a_{1},a_{2},\ldots,a_{n})$. Then for $\theta=(a_{1},a_{n})(a_{1},a_{n-1})\cdots(a_{1},a_{2})$ we start by seeing where $\theta$ maps $a_{n}$. It gets mapped to $a_{1}$, so we start with the transposition $(a_{1},a_{n})$. Then we add things before this transposition that don't include $a_{n}$. So where does $\theta$ map $a_{n-1}$? It gets mapped to $a_{n}$. Thus if we add $(a_{1},a_{n-1})$ to our decomposition we get $(a_{1},a_{n})(a_{1},a_{n-1})$ which maps $a_{n}\mapsto a_{1}$ and $a_{n-1}\mapsto a_{n}$ as we want. Continuing in this way, we get the telescoping series:

$\theta=(a_{1},a_{n})(a_{1},a_{n-1})\cdots(a_{1},a_{2})$

The decomposition $\theta=(a_{1},a_{2})(a_{2},a_{3}\cdots(a_{n-1},a_{n})$ is formed in exactly the same way, but you just start off by seeing where $\theta$ maps $a_{1}$.

Answer 2

Your first formula is "off" (missing a transposition): $$(a_1, a_2, \ldots, a_n) = {\bf (a_1, a_n)}(a_1, a_{n - 1}) \cdots (a_1, a_2)$$

Another algorithm is given by $$(a_1, a_2, \ldots, a_n) = (a_1, a_2)(a_2, a_3) \cdots(a_{n - 1}, a_n)$$ It might be helpful to recall that the decomposition of a permutation into transpositions is not unique. We are assured only that any valid decomposition of a given permutation will always yield either a product of an even number of transposition, or a product of an odd number of transpositions, never both. Indeed, an $n$-cycle must be decomposed into the product of $(n - 1) + 2k$ transpositions, for $k \in \{0, 1, 2, \ldots\}$. For example: $$(1,2,3,4,5) = \underbrace{(5,4)(5,2)(2,1)(2,5)(2,3)(1,3)}_{6\;\text{transpositions}} = \underbrace{(1, 2)(2, 3)(3, 4)(4, 5)}_{4 \;\text{transpositions}} = \underbrace{(1, 5)(1, 4)(1,3)(1,2)}_{4 \;\text{transpositions}} = \cdots$$

---

Let's evaluate $(5, 4)(5, 2)(2, 1)(2, 5)(2, 3)(1, 3)$ and verify that it is equal to $(1,2,3,4,5)$:

Given the operation on permutations is composition, and we compose from right to left:

(1) $1 \to 3 \to 2 \to 5 \to 5 \to 5\to 2\;\;$ giving us the start of a cycle $(1, 2 ... $.

(2) $2\to 2 \to 3 \to 3 \to 3\to 3 \to 3$ giving us the continued cycle $(1, 2, 3, ...$

(3) $3\to 1\to 1\to 1\to 2\to 5 \to 4,\;$ giving us the continued cycle $(1, 2, 3, 4...$

(4) $4\to 4\to 4\to 4\to 4 \to 4 \to 5,\;$ giving us the continued cycle $(1, 2, 3, 4, 5, ...$

(5) $5\to 5\to 5\to 2 \to 1 \to 1\to 1,\;$ giving us the continued cycle $1, 2, 3, 4, 5, 1...$

Since the composition brings $5$ back to $1$, we have a complete cycle $(1, 2, 3, 4, 5)$

So indeed, we see that $$(5, 4)(5, 2)(2, 1)(2, 5)(2, 3)(1, 3) = (1, 2, 3, 4, 5)$$

Answer 3

In his question and comments the OP keeps asking HOW did the author of his book come up with

$\tag a \sigma = (1,2,3,4,5) = (5,4)(5,2)(2,1)(2,5)(2,3)(1,3)$

But we have the transposition algebra rules:

\begin{align}(1) \quad (ab)(ab)&=1_{Id}\\ (2) \quad (ab)(cd)&=(cd)(ab)\\ (3) \quad (ab)(bc)&=(ca)(ab)\\ (4) \quad (ab)(bc)&=(bc)(ca)\end{align}

The first identity (1) can be used to expand a product of $n$ transpositions into another one with length $n+2$ - you can always employ this 'silly padding'. The other manipulations (2) thru (4) can be used to 'disguise' this 'silly padding'.

Observe that given a product of transpositions we can, step by step, 'move' any fixed transposition to a new position in the composition product, but other transpositions might have to be modified along the way.

Since $2$ occurs $4$ times in $(5,4)(5,2)(2,1)(2,5)(2,3)(1,3)$ we write

$\quad (1,2,3,4,5) = (3,4,5,1,2) = (2, 1) (2, 5) (2, 4) (2, 3) =$
$\quad \quad (5 ,4) (5 ,4) (2, 1) (2, 5) (2, 4) (2, 3) (1,3) (1,3) =$
$\quad \quad (5 ,4) (5 ,4) (2, 5) (5, 1) (2, 4) (1, 2) (2,3) (1,3) =$
$\quad \quad (5 ,4) (5 ,2) (2, 4) (5, 1) (2, 4) (1, 2) (2,3) (1,3) =$
$\quad \quad (5 ,4) (5 ,2) (5, 1) (1, 2) (2,3) (1,3) =$
$\quad \quad (5 ,4) (5 ,2) (2, 1) (2, 5) (2,3) (1,3) $