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

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