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

About these ads

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

1 Comment »

  1. [...] to each symbol in the cycle notation. In particular, any two conjugate permutations have the same cycle type. In fact, the converse is also true: given any two permutations with the same cycle type, we can [...]

    Pingback by Conjugates « The Unapologetic Mathematician | September 10, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 393 other followers

%d bloggers like this: