Previous
Next

Cycles, and the cycle decomposition of a permutation

November 28, 2011, 7:45 am

Last week’s installment on columnar transposition ciphers described a formula for the underlying permutation for a CTC. If we assume that the number of columns being used divides the length of the message, we get a nice, self-contained way of determining where the characters in the message go when enciphered. Now that we have the permutation fully specified, we’ll use it to learn a little about how the CTC permutation works — in particular, we’re going to learn about cycles in permutations and try to understand the cycle structure of a CTC.

First, what’s a cycle? Let’s go back to a simpler permutation to get the basic concept. Consider the bijective function \(p\) that maps the set \(\{0,1,2,3,4, 5\} \) onto itself by the rule
$$p(0) = 4 \quad p(1) = 5 \quad p(2) = 0 \quad p(3) = 3 \quad p(4) = 2 \quad p(5) = 1$$
If you look carefully at the numbers here, you’ll see that some of these numbers are moved or shuffled by \(p\) in “clusters” that never interact with other clusters. The function sends 0 to 4, 4 to 2, and 2 to 0. It sends 1 to 5 and 5 to 1. And it sends 3 to itself. Schematically, we could diagram this as:

$$0 \to 4 \to 2 \to 0 \qquad 1 \to 5 \to 1 \qquad 3 \to 3$$

These disjoint clusters are properly called cycles. Rather than write them like diagrams, we use parentheses. The cycle of 0, 4, 2 is written \((0, 4, 2)\). Since there are three numbers involved, it’s called a 3-cycle. The cycle containing 1 and 5 is written \((1,5)\) and is a 2-cycle or transposition. The single number 3 that doesn’t interact with any of the others would be written (3) and called a 1-cycle, except those cycles are not very interesting and therefore usually aren’t considered or written at all.

The entire function \(p\) can be written as a produce of these permutations: \(p = (0,4,2)(1,5)\), and this notation specifies the entire rule of assignment for \(p\). That is, if we can take \(p\) and write it as a product of disjoint cycles like this, it’s tantamount to making a table of values for \(p\) because we know exactly where to send each point in \(p\)’s domain.

A couple of things that are important about cycles for this whole business with columnar transposition ciphers:

First of all, every permutation on a finite set admits a unique decomposition into disjoint cycles. Here’s a very simple proof. In particular, a columnar transposition cipher — being a special kind of finite permutation — has a disjoint cycle decomposition.

Second – Remember that one of the main questions we would like to answer about CTC’s is, how many applications of a CTC will it take to get back to the “identity” permutation? The cycle decomposition will help us determine that. To see why, consider the permutation \(\sigma\) on the set \(\{0, 1, 2\}\) that consists only of the cycle \( (0, 2, 1) \). That is, after one application of \(\sigma\), we have \(\sigma(0) = 2, \sigma(2) = 1, \) and \( \sigma(1)= 0\). With two applications — \(\sigma\) followed by another \(\sigma\), which we might denote \(\sigma^2\) — we have \(\sigma^2(0) = 1\) (because 0 goes to 2 on the first application and then to 1 on the second), \(\sigma^2(2) = 0, \) and \( \sigma^2(1)= 2\). After three applications, we have \(\sigma^3(0) = 0\) , \(\sigma^3(2) = 2, \) and \( \sigma^3(1)= 1\). In other words, \(\sigma^3\) is just the identity permutation.

For any permutation \(p\), the smallest positive integer \(n\) such that \(p^n\) is the identity permutation is called the order of \(p\). For example, the order of \((0, 2, 1\) is 3. You might note that this is a 3-cycle. That the length of the cycle equals the order or the cycle is no coincidence — in fact, it is a mathematical truth that the order of any single \(n\)-cycle is \(n\).

But as we saw with the permutation \(p = (0, 4, 2)(1,5)\) earlier, permutations are often products of disjoint cycles and not just single cycles. Can we determine the order of such a permutation from its cycle decomposition? Yes, and it’s easy to understand why. The permutation \(p = (0, 4, 2)(1,5)\) is composed of a 3-cycle and a 2-cycle. The 3-cycle reverts to the identity every three applications (that is, in \(p^3\), \(p^6\), etc.). The 2-cycle reverts to the identity every two applications (\(p^2, p^4, p^6\), etc.). So if we were to start repeatedly applying \(p\) to itself, the first time that both cycles would “be in sync” and revert to the identity at the same time would be after the sixth time — that is, at the least common multiple of 2 and 3. In general, it’s true that:

The order of a finite permutation is the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.

This fact gives us a way to think about the order of a columnar transposition cipher: (1) Determine its cycle decomposition, and then (2) find the LCM of the cycle lengths. Let’s briefly begin to think about how to do (1). Basically, the formula we came up with in the last post does all the work on this.

First of all, notice that in a CTC, the very first character in the message is always fixed — it never moves position. You can see this because when you put the message into column form, the first character goes in the top-left corner and hence is also the first character read off in the cipher text. Or you can plug 0 into the formula:

$$\pi_{C,L}(0) = \frac{0 + 0(L-1)}{C} = 0$$

So the first character in the message that could possibly change position is the second one, which has the position number 1. The character in position 1 must be in cycle, but what are all the other elements of that cycle? It depends on \(L\) and \(C\). For example, if \(L = 20\) and \(C = 5\), then:

$$\pi_{5,20}(1) = \frac{1 + 1(19)}{5} = 4$$

Likewise, \(\pi_{5, 20}(4) = \frac{4 + 4(19)}{5} = \frac{80}{5} = 16\). Continuing to recycle output back into the formula (and noting that the \(n’\) in the formula is \(n \, \textrm{mod} \, 5\), we get

$$\begin{align*}
\pi_{5,20}(16) &= \frac{16 + 1(19)}{5}= 7 \\
\pi_{5,20}(7) &= \frac{7 + 2(19)}{5} = 9 \\
\pi_{5,20}(9) &= \frac{9 + 4(19)}{5} = 17 \\
\pi_{5,20}(17) &= \frac{17 + 2(19)}{5} = 11 \\
\pi_{5,20}(11) &= \frac{11 + 1(19)}{5} = 6 \\
\pi_{5,20}(6) &= \frac{6 + 1(19)}{5} = 5 \\
\pi_{5,20}(5) &= \frac{5 + 0(19)}{5} = 1
\end{align*}$$

So for \(C = 5, L = 20\), the cycle containing 1 is \( (1, 4, 16, 7, 9, 17, 11, 6, 5) \). By contrast, if \( C = 4\) and \(L=20\) — same message length but one fewer columns used — the cycle containing 1 is \( (1, 5, 6, 11, 17, 9, 7, 16, 4)\). Both are length 9, and in fact both contain the same elements, but the order in which things appear has changed.

But back to the case with \(C = 5, L = 20\) for a moment, what happens to the other elements of the set \( \{0, 1, \dots, 19\}\) — the ones that are not contained in that 9-cycle we computed? Interestingly, it turns out that with the exception of 19 — which is a fixed point in this permutation (plug it into the formula to see this) — all the other elements of the set belong to a second, parallel 9-cycle: \( (2, 8, 13, 14, 18, 15, 3, 12, 10) \). This gives us important information about \( \pi_{5, 20}\), namely that its order is 9, since it decomposes into two disjoint 9-cycles.

So we’ve seen that learning about the order of a CTC can be thought of as a matter of its disjoint cycle decomposition. In the next article, we’ll explore how the CTC factors into disjoint cycles and take an especially close look at the rail fence cipher. Some interesting number-theoretical stuff awaits.

This entry was posted in Abstract algebra, Crypto, CTCs, Math, Math Monday, Number theory, Scholarship and tagged , , , , , , . Bookmark the permalink.