Tour:Cycle decomposition for permutations

From Groupprops
Jump to: navigation, search

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 groups
Expected 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.

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,\ldots,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.


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) = 2x \mod 7. 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).

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

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,\ldots,a_n) described above, we also need cycles of the form (\ldots, a_{-1},a_0,a_1, \ldots), 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

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 groups
Expected time for this page: 5 minutes
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part