[Math] Expressing Permutation as a product of disjoint cycles and transpositions

abstract-algebra

Given this:

\begin{pmatrix}
1& 2& 3& 4&5&6\\
2& 4& 1& 5&6&3
\end{pmatrix}

How would you express as a product of disjoint cycles and transpositions? I believe disjoint cycle would be (1 2)(2 4) but Im having trouble finding how to express as a product of transpositions?

Best Answer

As for the disjoint cycle, first pick any element in $\{1,2,3,4,5,6\}$. For simplicity, we'll pick $1$. So we'll start our cycle by writing, $$(1$$

Now, we see what element $1$ gets sent to. We look for $1$ in the top row and see that $2$ is the corresponding element in the bottom row, so $1 \to 2$, so continuing our cycle, $$(12$$

Next, we look for $2$ in the top row and see that $4$ is the corresponding element in the bottom row, so $2 \to 4$, thus our cycle so far is, $$(124$$

Then just keeping continuing in this fashion until we run into an element we've already seen. Notice that $4 \to 5, 5 \to 6, 6 \to 3$ so our cycle is, $$(124563$$

Since $3 \to 1$ and $1$ is already in the cycle, that is our cue to end the cycle at $3$, $$(124563)$$

Notice that we've exhausted all the elements in the permutation, so we're done. If we weren't done, we'd just pick an element not yet in any of our cycles, and start again using the same process.

As for transpositions, notice that each transposition is a two-cycle, or in other words, a "swap". So you can think of writing a product of transpositions as the sequence of swaps you need to make to rearrange the numbers $1, 2, 3, 4, 5, 6$ as $2, 4, 1, 5, 6, 3$.