Decomposition of permutation from disjoint cycle

Question

I am a beginner, so my notations could be wrong. Consider in disjoint cycle notation:

$ X = (1)(2, 3, 16, 8, 10, 5, 14, 4, 12, 13)(6, 9)(7)(11, 15) $,

$Y = (1, 10, 6, 12, 8, 9, 3)(2, 14, 16, 11, 13, 15, 4, 7) (5)$,

$Z = (1, 3, 14, 15, 16, 12, 11, 13, 7, 4, 6, 8)(2, 9, 10, 5)$.

It can be cross-checked that $X(\lambda) = Y(Z(\lambda))$ $\forall \lambda$. My question is, given $X$, how can we find such $Y$ and $Z$? I found this example after a lot of trial-and-error.

Answer 1

Here $X = \operatorname{id}$ so the usual problem would be more:
Find $Z$ such that $Z\circ Y = \operatorname{id}$.

This is just finding the inverse (if you look carefully Z and Y differ only from the change of direction of the cycles).

Finding inverse is not so hard, if $Z(i) = j$, $Y(j) = I$. Or just reverse the direction of cycles.

Answer 2

In any group $G$, (including the group $S_n$ of permutations of $n$ elements), for any $a,b\in G$ we have that the equations $ax=b$ and $ya=b$ each have a unique solution. Namely, $x=a^{-1}b$ and $y=ba^{-1}$.

That means that given a permutation $X\in S_n$, you can always pick any permutation $Y\in S_n$, and find a permutation $Z\in S_n$ such that $X=YZ$. How? By computing $Z=Y^{-1}X$.

And if you pick any permutation $Z$, then you can always find a permutation $Y\in S_n$ such that $X=YZ$. How? By computing $Y=XZ^{-1}$.

How to find $Y^{-1}$ given an expression for $Y$ in disjoint cycle notation? For a single cycle $(a_1,a_2,\ldots,a_r)$, the inverse if given by the cycle $(a_r,a_{r-1},\ldots,a_2,a_1)$. And for a product of disjoint cycles, the inverse is given by taking the product of the inverses of each cycle. So if $(a_1,\ldots,a_r)$ and $(b_1,\ldots,b_t)$ are disjoint, then the inverse of $(a_1,\ldots,a_r)(b_1,\ldots,b_t)$ is $(a_r,\ldots,a_1)(b_t,\ldots,b_1)$. Etc.