The Theorem that Won the War: Part 2.3 – Cycle Notation

Author(s):
Jeff Suzuki (Brooklyn College)

To proceed, it will be convenient to introduce a second way to represent permutations, known as cycle notation. In a permutation like $N = \begin{pmatrix}a&b&c &d &e&f\\c&e&d&a&f&b\end{pmatrix},$ the letter $$a$$ is sent to $$c$$, the letter $$b$$ is sent to $$e$$, and so on; Cauchy two-line notation is essentially a description of the permutation in tabular form.

But now consider what would happen if we repeatedly applied $$N$$. From $$a$$ we would be sent to $$c$$; from $$c$$ we would be sent to $$d$$; and from $$d$$ we would be sent back to $$a$$, at which point we would cycle through $$c, d, a, c$$, and so on endlessly. This gives us the orbit $a \rightarrow c \rightarrow d \rightarrow a \rightarrow \ldots$, which we represent using cycle notation as $$(acd)$$. Since this cycle has three elements, it is called (unsurprisingly) a 3-cycle. Note that our permutation sends $$d$$ to $$a$$, so that when reading the cycle notation, the last letter is sent to the first letter.

What if we'd started with $$c$$? Then our orbit would be $c\rightarrow d \rightarrow a \rightarrow c \rightarrow \ldots$ and our cycle would be $$(cda)$$. But “things that do the same thing are the same thing,” so the cycle $$(acd)$$ sends $$a \rightarrow c$$, $$c \rightarrow d$$, and $$d\rightarrow a$$, while the cycle $$(cda)$$ sends $$c \rightarrow d$$, $$d \rightarrow a$$, and $$a \rightarrow c$$. So $$(acd)$$ and $$(cda)$$ do the same things to $$a, c$$, and $$d$$, we regard them as being the same cycle.

Note that $$N$$ also permutes the elements $$b, e, f$$. To account for these, we select one and find its orbit; thus the orbit of b will be $b \rightarrow e \rightarrow f \rightarrow b \rightarrow\ldots$ giving us another cycle $$(bef)$$. Since all letters have now been acounted for, we can write the cycle decomposition of our permutation $$N$$,$N =(acd)(bef).$Note that our two cycles have no elements in common; in general any permutation can be written as a product of disjoint cycles. One useful theorem about disjoint cycles:

Theorem. Disjoint cycles commute.

In other words, if we have two cycles with no elements in common, the order we apply them doesn't matter. Thus $(acd)(bef) = (acd)(bef).$

One special type of cycle is called a transposition: this is a cycle with two elements, and it corresponds to a permutation where two elements are switched. For example$M = \begin{pmatrix} a &b &c &d &e &f\\f &c &d &e &b &a \end{pmatrix}$ breaks into the transposition $$(af)$$ and the 4-cycle $$(bcde)$$, while $N = \begin{pmatrix} a &b &c &d &e &f\\e &d &f &b &a &c \end{pmatrix}$ breaks into three transpositions $$(ae)$$, $$(bd)$$, and $$(cf)$$.

We note that it's possible for a permutation to include a 1-cycle:$\begin{pmatrix} a &b &c &d &e &f\\c &d &b &f &e &a\end{pmatrix}.$ It's customary to omit the 1-cycles in the cycle decomposition, so we would write the cycle decomposition of $$P$$ as $$(acbdf)$$ instead of $$(acbdf)(e)$$.

To explore these ideas further, continue to the Activities for Part 2.3 (Cycle Notation).