Cycle notation in symmetric groups

There is a con­ve­nient way to rep­re­sent the el­e­ments of a sym­met­ric group on a finite set.

\(k\)-cycle

A \(k\)-cy­cle is a mem­ber of \(S_n\) which moves \(k\) el­e­ments to each other cycli­cally. That is, let­ting \(a_1, \dots, a_k\) be dis­tinct in \(\{1,2,\dots,n\}\), a \(k\)-cy­cle \(\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 com­pact no­ta­tion for \(\sigma\) in this case: we write \(\sigma = (a_1 a_2 \dots a_k)\). (If spac­ing is am­bigu­ous, we put in com­mas: \(\sigma = (a_1, a_2, \dots, a_k)\).) Note that there are sev­eral ways to write this: \((a_1 a_2 \dots a_k) = (a_2 a_3 \dots a_k a_1)\), for ex­am­ple. It is con­ven­tional to put the small­est \(a_i\) at the start.

Note also that a cy­cle’s in­verse is ex­tremely easy to find: the in­verse of \((a_1 a_2 \dots a_k)\) is \((a_k a_{k-1} \dots a_1)\).

For ex­am­ple, the dou­ble-row no­ta­tion

$$\begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{pmatrix}$$
is writ­ten as \((123)\) or \((231)\) or \((312)\) in cy­cle no­ta­tion.

How­ever, it is un­clear with­out con­text which sym­met­ric 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\).

Gen­eral el­e­ments, not just cycles

Not ev­ery el­e­ment of \(S_n\) is a cy­cle. For ex­am­ple, the fol­low­ing el­e­ment of \(S_4\) has or­der \(2\) so could only be a \(2\)-cy­cle, but it moves all four el­e­ments:

$$\begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{pmatrix}$$

How­ever, it may be writ­ten as the com­po­si­tion of the two cy­cles \((12)\) and \((34)\): it is the re­sult of ap­ply­ing one and then the other. Note that since the cy­cles are dis­joint (hav­ing no el­e­ments in com­mon), it doesn’t mat­ter in which or­der we perform them. It is a very im­por­tant fact that ev­ery per­mu­ta­tion may be writ­ten as the product of dis­joint cy­cles. If \(\sigma\) is a per­mu­ta­tion ob­tained by first do­ing cy­cle \(c_1 = (a_1 a_2 \dots a_k)\), then by do­ing cy­cle \(c_2\), then cy­cle \(c_3\), we write \(\sigma = c_3 c_2 c_1\); this is by anal­ogy with func­tion com­po­si­tion, in­di­cat­ing that the first per­mu­ta­tion to ap­ply is on the right­most end of the ex­pres­sion. (Be aware that some au­thors differ on this.)

Order of an element

Firstly, a cy­cle has or­der equal to its length. In­deed, the cy­cle \((a_1 a_2 \dots a_k)\) has the effect of ro­tat­ing \(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, sup­pose we have an el­e­ment in dis­joint cy­cle no­ta­tion: \((a_1 a_2 a_3)(a_4 a_5)\), say, where all the \(a_i\) are differ­ent. Then the or­der of this el­e­ment is \(3 \times 2 = 6\), be­cause:

  • \((a_1 a_2 a_3)\) and \((a_4 a_5)\) are dis­joint and hence com­mute, 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 iden­tity if and only if \((a_1 a_2 a_3)^n = (a_4 a_5)^n = e\) the iden­tity, be­cause oth­er­wise (for in­stance, if \((a_1 a_2 a_3)^n\) is not the iden­tity) it would move \(a_1\).

  • \((a_1 a_2 a_3)^n\) is the iden­tity if and only if \(n\) is di­visi­ble by \(3\), since \((a_1 a_2 a_3)\)’s or­der is \(3\).

  • \((a_4 a_5)^n\) is the iden­tity if and only if \(n\) is di­visi­ble by \(2\).

This rea­son­ing gen­er­al­ises: the or­der of an el­e­ment in dis­joint cy­cle no­ta­tion is equal to the least com­mon mul­ti­ple of the lengths of the cy­cles.

Examples

  • The el­e­ment \(\sigma\) of \(S_5\) given by first perform­ing \((123)\) and then \((345)\) is \((345)(123) = (12453)\). In­deed, the first ap­pli­ca­tion takes \(1\) to \(2\) and the sec­ond ap­pli­ca­tion does not af­fect the re­sult­ing \(2\), so \(\sigma\) takes \(1\) to \(2\); the first ap­pli­ca­tion takes \(2\) to \(3\) and the sec­ond ap­pli­ca­tion takes the re­sult­ing \(3\) to \(4\), so \(\sigma\) takes \(2\) to \(4\); the first ap­pli­ca­tion does not af­fect \(4\) and the sec­ond ap­pli­ca­tion takes \(4\) to \(5\), so \(\sigma\) takes \(4\) to \(5\); and so on.

This ex­am­ple sug­gests a gen­eral pro­ce­dure for ex­press­ing a per­mu­ta­tion which is already in cy­cle form, in dis­joint cy­cle form. It turns out that this can be done in an es­sen­tially unique way.

Cy­cle type

The cy­cle type of a per­mu­ta­tion is given by tak­ing the list of lengths of the cy­cles in the dis­joint cy­cle form.

Children:

Parents:

  • Symmetric group

    The sym­met­ric groups form the fun­da­men­tal link be­tween group the­ory and the no­tion of sym­me­try.