# Tour:Cycle decomposition for permutations

**This article adapts material from the main article:** cycle decomposition for permutations

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)PREVIOUS: understanding the cycle decomposition|UP: Introduction five (beginners)|NEXT: subset containment gives inclusion of symmetric groupsExpected time for this page: 5 minutes

General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

WHAT YOU NEED TO DO:

- Understand the definition given here. This should be a consolidation of what you saw in the previous page.
- If you have difficulty with this, review the previous page.

## Contents

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

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

.

WHAT'S MORE: More exploration of the meaning of cycle decomposition for infinite sets.

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

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)PREVIOUS: understanding the cycle decomposition|UP: Introduction five (beginners)|NEXT: subset containment gives inclusion of symmetric groupsExpected time for this page: 5 minutes

General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part