# 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).

Return to the overview of Part 2 (The Algebra of Enigma).

Skip to the overview of Part 2.4 (The Message Key).

Jeff Suzuki (Brooklyn College), "The Theorem that Won the War: Part 2.3 – Cycle Notation," Convergence (October 2023)