Cycle notation

For the cyclic decomposition of graphs, see Cycle decomposition (graph theory). For cycling terminology, see glossary of bicycling.

In combinatorial mathematics, the cycle notation is a useful convention for writing down a permutation in terms of its constituent cycles.

Definition

Let $S$ be a finite set, and

$a_{1},\ldots ,a_{k},\quad k\geq 2$

be distinct elements of $S$. The expression

$(a_{1}\ \ldots \ a_{k})$

denotes the cycle σ whose action is

$a_{1}\mapsto a_{2}\mapsto a_{3}\mapsto \ldots \mapsto a_{k}\mapsto a_{1}.$

For each index i,

$\sigma (a_{i})=a_{i+1},$

where $a_{k+1}$ is taken to mean $a_{1}$.

There are $k$ different expressions for the same cycle; the following all represent the same cycle:

$(a_{1}\ a_{2}\ a_{3}\ \ldots \ a_{k})=(a_{2}\ a_{3}\ \ldots \ a_{k}\ a_{1})=\cdots =(a_{k}\ a_{1}\ a_{2}\ \ldots \ a_{k-1}).\,$

A 1-element cycle is the same thing as the identity permutation and is omitted. It is customary to express the identity permutation simply as $()\,$.

Permutation as product of cycles

Let $\pi$ be a permutation of $S$, and let

$S_{1},\ldots ,S_{k}\subset S,\quad k\in \mathbb {N}$

be the orbits of $\pi$ with more than 1 element. Consider an element $S_{j}$, $j=1,\ldots ,k$, let $n_{j}$ denote the cardinality of $S_{j}$,$|S_{j}|$ =$n_{j}$. Also, choose an $a_{1,j}\in S_{j}$, and define

$a_{i+1,j}=\pi (a_{i,j}),\quad i\in \mathbb {N} .\,$

We can now express $\pi$ as a product of disjoint cycles, namely

$\pi =(a_{1,1}\ \ldots a_{n_{1},1})(a_{1,2}\ \ldots \ a_{n_{2},2})\ldots (a_{1,k}\ \ldots \ a_{n_{k},k}).\,$

Note that the usual convention in cycle notation is to multiply from left to right (in contrast with composition of functions, which is normally done from right to left). For example, the product $(1\ 2)(2\ 3)$ is equal to $(1\ 3\ 2)$ not $(1\ 2\ 3)$.

Example

There are the 24 elements of the symmetric group on $\{1,2,3,4\}$ expressed using the cycle notation, and grouped according to their conjugacy classes:

$()\,$

$(12),\;(13),\;(14),\;(23),\;(24),\;(34)$ (transpositions)

$(123),\;(132),\;(124),\;(142),\;(134),\;(143),\;(234),\;(243)$

$(12)(34),\;(13)(24),\;(14)(23)$

$(1234),\;(1243),\;(1324),\;(1342),\;(1423),\;(1432)$

See also

• Cyclic permutation
• Cycles and fixed points

cycle notation at PlanetMath.

References

• Fraleigh, John (2002), A first course in abstract algebra (7th ed.), Addison Wesley, ISBN 978-0201763904