Question

Prove that the decomposition of a permutation as a product of disjoint cycles is unique except for the order in which the cycles are listed.

Short answer

The decomposition of a permutation as a product of disjoint cycles is unique.

Step-by-step solution

Product of disjoint cycles

Let $\tau \in S_n$ and$\prod _{i=1}^k{\sigma }^i$ , $\prod _{j=1}^l{\beta }^j$ be the decompositions of the product of disjoint cycles.

τ is unique

Here, ${\sigma }^i=(a_1^i\dots a_{r_i}^i)$ where $1\le i\le k$ then for any $b\in (a_1^i\dots a_{r_i}^i)$, ${\sigma }^{i}b=\tau b$.

Similarly, for $1\le j\le l$, ${\beta }^{i}b=\tau b={\sigma }^{i}b$which implies ${\beta }^i={\sigma }^i$ and each cycle in $\prod _{j=1}^l{\beta }^j$ is a cycle in $\prod _{i=1}^k{\sigma }^i$.

Thus, k=l and for each ${\sigma }^i$ there is a unique ${\beta }^j$ such that ${\beta }^i={\sigma }^i$.

Therefore, the decomposition of a permutation as a product of disjoint cycles is unique.