Logic for decomposing a permutation into different products composed of transpositions

Solution 1:

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

Solution 2:

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}$.