Doubt in composition of transpositions.

Question

Read article here to show importance of expressing permutation as product of disjoint transpositions.

Have a doubt regarding the notation used.
Have found that need an easy way, which is much less confusing

It states:

Proposition Every permutation $\sigma \in S_n$ can be written as a product of transpositions. Read the proposition carefully. It doesn’t mention uniqueness at all. Yes, we can write any permutation as a product of transpositions, but not in a unique way. For example $(13) = (12)(23)(12) = (23)(12)(23)$

The paper used an example to show notation (one row) as:

$$\sigma= \begin{pmatrix} 1 & 2 & 3 &4 \\ 2 & 4 & 1 & 3\end{pmatrix} \implies (1243)$$

For $(12)(23)(12)$, the corresponding two line permutation = $$ \begin{pmatrix} 1 & 2 \\ 2 & 1\end{pmatrix} \begin{pmatrix} 2 & 3 \\ 3 & 2\end{pmatrix} \begin{pmatrix} 1 & 2 \\ 2 & 1\end{pmatrix} \implies \begin{pmatrix} 1 & 3 \\ 3 & 1\end{pmatrix} $$

Though the paper doesn't state in which order the permutations are processed. But, given the symmetry in processing either from left or right ($(12)(23)(12), (23)(12)(23)$), makes no difference, and choose from right to left.

$$1 \rightarrow 2, 2\rightarrow 3\implies 1 \rightarrow 3; 2 \rightarrow 1$$ The last transposition is $(12)$, while there are elements $3,1$ to be transposed.

So, get: $$1 \rightarrow 3, 2\rightarrow (1)\rightarrow 2$$ So, get $(13)(2)\implies 1 \rightarrow 3$ or$(13)$.

Next is the rhs product of transpositions : $(23)(12)(23)$, or: $$ \begin{pmatrix} 2 & 3 \\ 3 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 2 & 3 \\ 3 & 2 \end{pmatrix} $$

First transposition on the right end is: $2 \rightarrow 3, 3 \rightarrow 2$.

The second transposition is $(12), 2 \rightarrow 1, 1 \rightarrow 2$, while there are elements $2,3$ to be transposed from the first transposition.

So, get by composition: $1 \rightarrow 2, 3 \rightarrow 1, 2 \rightarrow 3$.

Next, have last composition on the lhs. $$ 1 \rightarrow 3, 3\rightarrow 1, 2 \rightarrow 2 $$

(The last composition if processed will yield a different answer than $(13)$?)

Edit

Have removed error above, but is there any easy way rather than spending hours ? In fact, still get confused easily.

Better such an approach be easily programmable, that helps in larger number of transpositions, and number of members in each.

Answer 1

Hints:

1. Every permutation either a cycle Or product of disjoint cycles.

2. Any $r$-cycle $(a_1, a_2,...,a_r)$ can be expressed as a product of $r-1$ transpositions $(a_1, a_r) (a_1, a_{r-1}),... (a_1, a_2) $

3. Any two disjoint cycles commute.

Note: You can also express a $r$-cycle $(a_1, a_2,...,a_r)$ as a product of $r-1$ transpositions $(a_1, a_2) (a_2, a_3),... (a_{r-1}, a_r) $

So this decomposition is not unique. But number of transpositions for any decomposition is always same.

Method:

For an example choose $\sigma=\begin{pmatrix}1&2&3&4&5&6\\3&4&5&6&1&2\end{pmatrix}\in S_6$

Step $1$: Write $\sigma$ as product of disjoint cycles.

$$(135) (246) $$

Step $2$ : write cycles as product of transpositions

$$(15)(13)(16)(24)$$

Answer 2

As per response by @coffeemath (and modified it a bit, by adding subscripts, to achieve programmability) on non-unique representation, get for second set of transpositions: $$ \begin{pmatrix} 2 & 3 \\ 3 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 2 & 3 \\ 3 & 2 \end{pmatrix} $$ Have taken, as in post, transpositions from right to left. $$2_1\rightarrow 3_1, 3_1\rightarrow 2_1$$ $$1_2\rightarrow 2_2, 2_2\rightarrow 1_2$$ $$2_3\rightarrow 3_3, 3_3\rightarrow 2_3$$

Composition 1: $$2_1\rightarrow 3_1, 3_1\rightarrow 1_2, 1_2\rightarrow 2_2$$ $$2_3\rightarrow 3_3, 3_3\rightarrow 2_3$$

Composition 2: $$1_2\rightarrow 3_3, 2_1\rightarrow 2_3, 3_1\rightarrow 1_2$$

Here, need keep each transposition intact, if it's subscript number is lesser than other, and no RHS match occurs with a higher subscript LHS.