Cycle decomposition for permutations
For finite sets
Let be a set and be a permutation. A cycle decomposition for is an expression of as a product of disjoint cycles.
Here, a cycle is a permutation sending to for and to . 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 be an infinite set and be a finitary permutation -- a permutation that moves only finitely many elements. Then, a cycle decomposition for is an expression of 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 described above, we also need cycles of the form , i.e., sequences of elements parametrized by the integers, with the property that for all . 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
For an introduction to cycle decompositions, refer: Understanding the cycle decomposition
For finite sets
For instance, consider the permutation on given by . Then, the cycle decomposition of is:
In other words, is a product of three cycles: the cycle that sends to and to , the cycle that sends to and to , and the cycle that sends to itself.
Cycles of size one are usually ignored, so can be written as:
The ordering between permutations and the cyclic ordering within a permutation don't matter, so we can write in other equivalent ways, like:
Here's another example. Consider the permutation on the set given by . In other words, for and for .
Then the cycle decomposition of is given by:
The ordering among the cycles, and the cyclic ordering among elements in the same cycle, are irrelevant, so this can be rewritten as:
On the other hand, we cannot arbitrarily re-order elements within a cycle, so .
With the commas removed, this is written as:
For full lists of elements of symmetric groups with their cycle decompositions and other descriptions, see:
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 ), 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.