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

-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 $σ$ is such that $σ (a_{i}) = a_{i + 1}$ for $1 \leq i < k$ , and $σ (a_{k}) = a_{1}$ , and $σ (x) = x$ for any $x \notin {a_{1}, \dots, a_{k}}$ .

We have a much more compact notation for $σ$ in this case: we write $σ = (a_{1} a_{2} \dots a_{k})$ . (If spacing is ambiguous, we put in commas: $σ = (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{matrix} 1 & 2 & 3 2 & 3 & 1 \end{matrix})$ 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{matrix} 1 & 2 & 3 & 4 2 & 1 & 4 & 3 \end{matrix})$

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 $σ$ 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 $σ = 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:

$(a_{1} a_{2} a_{3})$ and $(a_{4} a_{5})$ are disjoint and hence commute, so $[(a_{1} a_{2} a_{3}) (a_{4} a_{5})]^{n} = (a_{1} a_{2} a_{3})^{n} (a_{4} a_{5})^{n}$

$(a_{1} a_{2} a_{3})^{n} (a_{4} a_{5})^{n}$ is the identity if and only if $(a_{1} a_{2} a_{3})^{n} = (a_{4} a_{5})^{n} = e$ the identity, because otherwise (for instance, if $(a_{1} a_{2} a_{3})^{n}$ is not the identity) it would move $a_{1}$ .

$(a_{1} a_{2} a_{3})^{n}$ is the identity if and only if $n$ is divisible by $3$ , since $(a_{1} a_{2} a_{3})$ 's order is $3$ .

$(a_{4} a_{5})^{n}$ is the identity if and only if $n$ is divisible by $2$ .

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

The element $σ$ of $S_{5}$ given by first performing $(123)$ and then $(345)$ is $(345) (123) = (12453)$ . Indeed, the first application takes $1$ to $2$ and the second application does not affect the resulting $2$ , so $σ$ takes $1$ to $2$ ; the first application takes $2$ to $3$ and the second application takes the resulting $3$ to $4$ , so $σ$ takes $2$ to $4$ ; the first application does not affect $4$ and the second application takes $4$ to $5$ , so $σ$ takes $4$ to $5$ ; and so on.

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.

AI ALIGNMENT FORUM
AF