Cycle type

The cycle type of a permutation is the multiset of lengths in its decomposition into disjoint permutation cycles, including one-cycles for fixed points. Two permutations in the same symmetric group are conjugate exactly when they have the same cycle type.

Conjugation preserves order of a group element, because $(gx{g}^{-1}{)}^k=g{x}^k{g}^{-1}$, and preserves the sign of a permutation, because sign is a group homomorphism into $\{1,-1\}$. These invariants do not determine cycle type. In $S_6$, $(123)$ and $(123)(456)$ both have order three and positive sign, but have three and zero fixed points respectively. Conjugation relabels cycles, so these permutations are not conjugate.

Squaring an odd-length permutation cycle retains its length, whereas an even-length cycle splits into two cycles of half its length. Thus if any even cycle is present, the number of cycles strictly increases, so the cycle type changes. Since conjugate permutations in a symmetric group have the same cycle type, a permutation is conjugate to its square precisely when all its cycle lengths are odd, equivalently when its order of a group element is odd.

Left multiplication of a permutation by a transposition $(ab)$ swaps the two target labels $a,b$. If they occur in different cycles, $(a{x}_1\dots x_p)(b{y}_1\dots y_q)$ becomes the single cycle $(a{x}_1\dots x_{p}b{y}_1\dots y_q)$. If they occur in the same cycle, that formula reverses and splits the cycle in two. All other cycles are unchanged, so the total number of cycles, including fixed points, decreases or increases by exactly one. Empty intermediate lists yield one-cycles and require no exceptional case.