Cycle decomposition for permutations

Definition

For finite sets

Let $S$ be a set and $\sigma :S\to S$ be a permutation. A cycle decomposition for $\sigma$ is an expression of $\sigma$ as a product of disjoint cycles.

Here, a cycle $(a_1,a_2,\dots ,a_n)$ is a permutation sending $a_j$ to $a_{j+1}$ for $1\le j\le n-1$ and $a_n$ to $a_1$. Two cycles are disjoint if they do not have any common elements.

Any permutation on a finite set has a unique cycle decomposition. In other words, the cycles making up the permutation are uniquely determined. Note that the order in which we multiply the cycles, and the cyclic ordering of elements within the cycle, are not uniquely determined.

The product expression is typically written by writing the disjoint cycles side by side. Further, the commas separating elements in the same cycle are sometimes dropped if this does not create confusion.

For finitary permutations

Let $S$ be an infinite set and $\sigma :S\to S$ be a finitary permutation -- a permutation that moves only finitely many elements. Then, a cycle decomposition for $\sigma$ is an expression of $\sigma$ as a product of disjoint cycles.

Any finitary permutation admits a unique cycle decomposition, since it can be viewed as a permutation on the finite subset of elements that it actually moves.

For arbitrary permutations on infinite sets

For arbitrary permutations on infinite sets, cycle decompositions do exist provided we relax the meaning of a cycle. Thus, in addition to cycles of the form $(a_1,a_2,\dots ,a_n)$ described above, we also need cycles of the form $(\dots ,a_{-1},a_0,a_1,\dots )$, i.e., sequences of elements parametrized by the integers, with the property that $\sigma (a_j)=a_{j+1}$ for all $j$. With this, any permutation has a unique cycle decomposition.

For proof of the existence and uniqueness of cycle decompositions, refer: cycle decomposition theorem for permutations

Examples

For an introduction to cycle decompositions, refer: Understanding the cycle decomposition

For finite sets

For instance, consider the permutation $\sigma$ on $\{1,2,3,4,5\}$ given by $\sigma (x)=6-x$. Then, the cycle decomposition of $\sigma$ is:

$\sigma =(1,5)(2,4)(3)$

In other words, $\sigma$ is a product of three cycles: the cycle $(1,5)$ that sends $1$ to $5$ and $5$ to $1$, the cycle $(2,4)$ that sends $2$ to $4$ and $4$ to $2$, and the cycle $(3)$ that sends $3$ to itself.

Cycles of size one are usually ignored, so $\sigma$ can be written as:

$\sigma =(1,5)(2,4)$

The ordering between permutations and the cyclic ordering within a permutation don't matter, so we can write $\sigma$ in other equivalent ways, like:

$\sigma =(4,2)(1,5)=(5,1)(2,4)$

Here's another example. Consider the permutation on the set $\{1,2,3,4,5,6,7\}$ given by $\sigma (x)=2xmod7$. In other words, $\sigma (x)=2x$ for $1\le x\le 3$ and $\sigma (x)=2x-7$ for $4\le x\le 7$.

Then the cycle decomposition of $\sigma$ is given by:

$\sigma =(1,2,4)(3,6,5)$

The ordering among the cycles, and the cyclic ordering among elements in the same cycle, are irrelevant, so this can be rewritten as:

$\sigma =(2,4,1)(5,3,6)=(6,5,3)(1,2,4)$

On the other hand, we cannot arbitrarily re-order elements within a cycle, so $\sigma \ne (1,4,2)(3,6,5)$.

With the commas removed, this is written as:

$\sigma =(124)(365),\sigma =(241)(536)$.