Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics I / 5 / b

For each symbol $a$, iterate the permutation $\sigma$. Since the symbol set is finite, some iterate repeats. Applying an inverse power of $\sigma$ shows that the first return is to $a$ itself, givingwith the displayed symbols distinct. This is a permutation cycle. If two such lists share a symbol, applying powers of $\sigma$ shows that they contain exactly the same symbols. Hence these group orbits form a partition of a set $\{1,\dots ,n\}$. On each group orbit, $\sigma$ acts as the corresponding permutation cycle, and these disjoint permutation cycles multiply to $\sigma$.

The disjoint cycle decomposition is unique up to reordering the cycles and cyclically rotating the entries within each cycle, with fixed points optionally omitted. Indeed, each cycle must consist of one of the uniquely determined group orbits, and its successive entries must follow the action of $\sigma$.

With products acting from right to left, a permutation cycle satisfiesThe right side sends $a_1$ to $a_2$, each $a_j$ to $a_{j+1}$ for $2\le j<k$, and $a_k$ to $a_1$, while fixing all other symbols. This verifies the formula. Applying it to every cycle in the disjoint cycle decomposition expresses any permutation as a product of transpositions. The identity is represented by the empty product.

Suppose $\sigma$ has order of a group element two. On a cycle of length $k$, ${\sigma }^2$ moves each entry two places. Since ${\sigma }^2=e$, every such $k$ divides two, so $k=1$ or $k=2$. After omitting the fixed points, the disjoint cycle decomposition is therefore a product of disjoint permutation cycles of length two, which are transpositions. There is at least one, because $\sigma \ne e$.