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)=(241)(536)=(653)(124)$.

Comprehensive listings

For full lists of elements of symmetric groups with their cycle decompositions and other descriptions, see:

• Element structure of symmetric group:S3#Elements
• Element structure of symmetric group:S4#Elements
• Element structure of symmetric group:S5#Elements

Canonical notation for a cycle decomposition

As noted above, the cycle decomposition notation for a permutation is not unique: we can cyclically permute the elements within each cycle, and we can also write the cycles in any order. Further, we generally omit cycles of size one, but this is not necessary.

From a combinatorial or algorithmic perspective, it is hard to keep track of cycle decompositions this way. Therefore, when dealing with permutations combinatorially, we fix a canonical notation for writing the cycle decomposition. Specifically, for a finitary permutation of a totally ordered set (such as the set $\{1,2,3,\dots ,n\}$), the canonical notation for the permutation is as follows:

• We cyclically rearrange each cycle so that it begins with its largest element.
• We order the cycles in increasing order of their largest elements.

Note that this choice is not "canonical" in the usual group-theoretic sense (of being invariant under conjugations or automorphisms) but is canonical with respect to the total ordering on the underlying set. In fact, there cannot be a canonical choice in the group-theoretic sense because conjugation can be used to cyclically rearrange within each cycle arbitrarily.

Canonical notation may or may not include fixed points as cycles, but the choice of whether or not to include them should be made uniformly in order to force uniqueness.

The canonical notation (with inclusion of fixed points) serves as the starting point for the Foata correspondence, a bijection from the symmetric group on a finite set to itself that uses the "pun" between canonical notation for cycle decomposition and one-line notation for permutations.

Replacing largest with smallest

There are conflicting definitions of the canonical notation. Some definitions require that we use the smallest element, and decreasing order. Explicitly, they suggest that:

• We cyclically rearrange each cycle so that it begins with its smallest element.
• We order the cycles in decreasing order of their smallest elements.

The definitions are equivalent up to some other transformations, and are not conceptually too far apart, though there are cases where one definition is a little more useful than the other. We stick with the definition using largest elements, because it fixes the identity element of the symmetric group.