The Unapologetic Mathematician

Mathematics for the interested outsider

Cycle Type

One concept I’d like to introduce is that of the “cycle type” of a permutation. This simply counts the number of cycles of various length in a permutation. For example — using the sample permutations from last time — \alpha=(1\,2)(3\,4) has two cycles of length two, while \beta=(1\,4\,3)(2) has one cycle of length three and one “fixed point” — a cycle of length one. No cycle in a permutation in S_n can be longer than n, so we only need to count up to n. We collect the information in a cycle type into a tuple of the form (1^{m_1},2^{m_2},\dots,n^{m_n}). The cycle type of \alpha is (1^0,2^2,3^0), and that of \beta is (1^1,2^0,3^1).

It should be clear that the sum of the cycle lengths is n. In a formula:

\displaystyle\sum\limits_{k=1}^nkm_k=n

That is, the cycle type breaks up or “partitions” n into chunks whose total size adds up to n. In general, a partition \lambda of n is a sequence of numbers (\lambda_1,\dots,\lambda_l) in nonincreasing order, whose sum is n. Thus the cycle type of \alpha gives us the partition (2,2), while the cycle type of \beta gives us the partition (3,1).

One more example, from the beginning: the two-line notation

\displaystyle\left\lvert\begin{matrix}1&2&3&4&5\\2&3&1&4&5\end{matrix}\right\rvert

describing a permutation in S_5 has the cycle notation (1\,2\,3)(4)(5). Its cycle type is (1^2,2^0,3^1,4^0,5^0), which corresponds to the partition (3,1,1).

Advertisements

September 9, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 1 Comment