# Cycle decomposition for permutations

## 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: