Doubt in composition of transpositions.

permutations

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.

Best Answer

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

Related Question