Difference between revisions of "Cycle type of a permutation"

From Groupprops
Jump to: navigation, search
(New page: ==Definition== Let <math>S</math> be a finite set and <math>\sigma:S \to S</math> be a permutation. The '''cycle type''' of <math>\sigma</math> is the data of how many cycles of each leng...)
 
 
Line 12: Line 12:
  
 
This permutation has cycle type <math>(3,2,1,2)</math>. Since this is an unordered list, this can also be written as <math>(1,2,2,3)</math> or <math>(1,2,3,2)</math>.
 
This permutation has cycle type <math>(3,2,1,2)</math>. Since this is an unordered list, this can also be written as <math>(1,2,2,3)</math> or <math>(1,2,3,2)</math>.
 +
 +
Note that the sum of all the cycle sizes must equal the size of the whole set <math>S</math>. Thus, the cycle type of a permutation is an ''unordered'' integer partition of the size of the set.
  
 
===Definition as information of how many cycles of each length there are===
 
===Definition as information of how many cycles of each length there are===
Line 25: Line 27:
 
==Facts==
 
==Facts==
  
* [[Cycle type determines conjugacy class]]: Two permutations are conjugate in the symmetric group if and only if they have the same cycle type.
+
* [[Cycle type determines conjugacy class]]: Two permutations are conjugate in the symmetric group if and only if they have the same cycle type. In particular, this means that the set of conjugacy classes in the symmetric group on a finite set is in bijection with the [[set of unordered integer partitions]] of the size of the set.

Latest revision as of 23:00, 6 January 2009

Definition

Let S be a finite set and \sigma:S \to S be a permutation. The cycle type of \sigma is the data of how many cycles of each length are present in the cycle decomposition of \sigma. There are two typical ways of specifying the cycle type.

The definition also applies for infinite sets; here, we also need to include cycles of infinite length, i.e., the chains.

Definition as an unordered list of cycle sizes

The cycle type of a permutation is defined as the unordered list of the sizes of the cycles in the cycle decomposition of \sigma. For instance, consider the permutation with cycle decomposition:

(1,3,5)(2,4)(6)(7,8)

This permutation has cycle type (3,2,1,2). Since this is an unordered list, this can also be written as (1,2,2,3) or (1,2,3,2).

Note that the sum of all the cycle sizes must equal the size of the whole set S. Thus, the cycle type of a permutation is an unordered integer partition of the size of the set.

Definition as information of how many cycles of each length there are

This decsribes the cycle type as an ordered sequence i_1, i_2, i_3, \dots where i_j is the number of cycles of size (length) j. Thus, the permutation:

(1,3,5)(2,4)(6)(7,8)

has i_1 = 1, i_2 = 2, i_3 = 1 and i_j = 0, j \ge 4.

Note that give the cycle type in either form, it can be converted to the other form.

Facts