Cycle decomposition for permutations

From Groupprops
Jump to: navigation, search

Definition

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


Examples

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:

.


Comprehensive listings

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