Cycle notation in symmetric groups

https://arbital.com/p/cycle_notation_symmetric_group

by Patrick Stevens Jun 14 2016 updated Jun 15 2016

Cycle notation is a convenient way to represent the elements of a symmetric group.


There is a convenient way to represent the elements of a Symmetric group on a finite set.

$~$k$~$-cycle

A $~$k$~$-cycle is a member of $~$S_n$~$ which moves $~$k$~$ elements to each other cyclically. That is, letting $~$a_1, \dots, a_k$~$ be distinct in $~$\{1,2,\dots,n\}$~$, a $~$k$~$-cycle $~$\sigma$~$ is such that $~$\sigma(a_i) = a_{i+1}$~$ for $~$1 \leq i < k$~$, and $~$\sigma(a_k) = a_1$~$, and $~$\sigma(x) = x$~$ for any $~$x \not \in \{a_1, \dots, a_k \}$~$.

We have a much more compact notation for $~$\sigma$~$ in this case: we write $~$\sigma = (a_1 a_2 \dots a_k)$~$. (If spacing is ambiguous, we put in commas: $~$\sigma = (a_1, a_2, \dots, a_k)$~$.) Note that there are several ways to write this: $~$(a_1 a_2 \dots a_k) = (a_2 a_3 \dots a_k a_1)$~$, for example. It is conventional to put the smallest $~$a_i$~$ at the start.

Note also that a cycle's inverse is extremely easy to find: the inverse of $~$(a_1 a_2 \dots a_k)$~$ is $~$(a_k a_{k-1} \dots a_1)$~$.

For example, the double-row notation $$~$\begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{pmatrix}$~$$ is written as $~$(123)$~$ or $~$(231)$~$ or $~$(312)$~$ in cycle notation.

However, it is unclear without context which symmetric group $~$(123)$~$ lies in: it could be $~$S_n$~$ for any $~$n \geq 3$~$. Similarly, $~$(145)$~$ could be in $~$S_n$~$ for any $~$n \geq 5$~$.

General elements, not just cycles

Not every element of $~$S_n$~$ is a cycle. For example, the following element of $~$S_4$~$ has order $~$2$~$ so could only be a $~$2$~$-cycle, but it moves all four elements: $$~$\begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{pmatrix}$~$$

However, it may be written as the composition of the two cycles $~$(12)$~$ and $~$(34)$~$: it is the result of applying one and then the other. Note that since the cycles are disjoint (having no elements in common), it doesn't matter in which order we perform them. It is a very important fact that every permutation may be written as the product of disjoint cycles. If $~$\sigma$~$ is a permutation obtained by first doing cycle $~$c_1 = (a_1 a_2 \dots a_k)$~$, then by doing cycle $~$c_2$~$, then cycle $~$c_3$~$, we write $~$\sigma = c_3 c_2 c_1$~$; this is by analogy with function composition, indicating that the first permutation to apply is on the rightmost end of the expression. (Be aware that some authors differ on this.)

Order of an element

Firstly, a cycle has order equal to its length. Indeed, the cycle $~$(a_1 a_2 \dots a_k)$~$ has the effect of rotating $~$a_1 \mapsto a_2 \mapsto a_3 \dots \mapsto a_k \mapsto a_1$~$, and if we do this $~$k$~$ times we get back to where we started. (And if we do it fewer times - say $~$i$~$ times - we can't get back to where we started: $~$a_1 \mapsto a_{i+1}$~$.)

Now, suppose we have an element in disjoint cycle notation: $~$(a_1 a_2 a_3)(a_4 a_5)$~$, say, where all the $~$a_i$~$ are different. Then the order of this element is $~$3 \times 2 = 6$~$, because:

This reasoning generalises: the order of an element in disjoint cycle notation is equal to the Least common multiple of the lengths of the cycles.

Examples

This example suggests a general procedure for expressing a permutation which is already in cycle form, in disjoint cycle form. It turns out that this can be done in an essentially unique way.

Cycle type

The Cycle type of a permutation is given by taking the list of lengths of the cycles in the disjoint cycle form.


Comments

Alexei Andreev

Note also that a cycle's inverse is extremely easy to find: the inverse of $~$(a\_1 a\_2 \\dots a\_k)$~$ is $~$(a\_k a\_{k-1} \\dots a\_1)$~$\.

I'm curious if the inverse has any particular use in this field.

Patrick Stevens

None that I'm aware of, but I've found it convenient to know when I was doing exercises in a first course in group theory.