Arnold's Cat Map: How Chaos Scrambles a Picture and Restores It

In the 1960s Vladimir Arnold drew a cat on a square and showed what a simple rule does to it Arnold's cat map, Wikipedia^[1]. Shear the picture, wrap the overhanging parts back into the square, repeat. Within a few steps the cat is smeared into stripes and then into apparent noise. Yet if the picture is made of pixels, keep going and the cat reappears, exactly as it started Arnold's cat map, Wikipedia^[1]. The map is on our Arnold's Cat tee, and it is one of the cleanest examples of chaos there is.

What is Arnold’s cat map?

Treat the unit square as a torus: leaving the right edge brings you back on the left, and leaving the top brings you back at the bottom. Arnold’s cat map sends the point (x, y) to Arnold's cat map, Wikipedia^[1]

Γ(x, y) = (2x + y, x + y) mod 1

Here x and y are dimensionless coordinates between 0 and 1, and “mod 1” keeps only the fractional part. The matrix of the map has entries 2, 1, 1, 1. It is the product of two shears: the image is sheared one unit in one direction, then again in the other, and everything outside the square is shifted back in Arnold's cat map, Wikipedia^[1]. The name comes from Arnold and Avez’s 1967 book on ergodic problems in classical mechanics, where a cat outline illustrated the action of the map Arnold's cat map, Wikipedia^[1].

Why is the cat map chaotic?

The matrix has determinant 1, so the map preserves area and is invertible Arnold's cat map, Wikipedia^[1]. Its eigenvalues are

λ_± = (3 ± √5)/2, λ₊ ≈ 2.618, λ₋ ≈ 0.382

One is greater than 1 and one smaller, so every small patch is stretched by a factor of about 2.618 along one direction and squeezed by the same factor along the perpendicular direction at each step Arnold's cat map, Wikipedia^[1]. The two directions are irrational lines that wrap densely around the torus Arnold's cat map, Wikipedia^[1]. This makes the cat map a standard example of a hyperbolic toral automorphism and an Anosov diffeomorphism, a map with clearly marked directions of expansion and contraction at every point Arnold's cat map, Wikipedia^[1] Anosov diffeomorphism, Wikipedia^[2].

The Lyapunov exponent measures how fast nearby trajectories separate: |δ(t)| ≈ e^λt|δ₀| Lyapunov exponent, Wikipedia^[3]. For the cat map the stretch is the same everywhere, so the exponent is ln λ₊ ≈ 0.962 per iteration. Two points that start 10⁻¹² apart are separated by about 2.618ⁿ × 10⁻¹² after n steps, which reaches the size of the whole square after roughly 29 iterations. The map is also ergodic and mixing Arnold's cat map, Wikipedia^[1]: any blob of points ends up spread evenly over the square. For chaos on the scale of the Solar System, see our Lyapunov Time of the Planets poster.

Why does the picture come back?

On a real torus, a point returns exactly only if its coordinates are rational, and the periodic points are dense Arnold's cat map, Wikipedia^[1]. A digital image is a grid of N × N pixels, so the discrete version of the map acts on integer coordinates Arnold's cat map, Wikipedia^[1]:

q_t+1 = 2q_t + p_t mod N, p_t+1 = q_t + p_t mod N

Because the map is invertible, it simply shuffles the N² pixels. A shuffle of a finite set, repeated, must eventually return every element to its place. Dyson and Falk showed that the number of iterations Π(N) needed to restore the image never exceeds three times its width Dyson and Falk 1992^[4] Arnold's cat map, Wikipedia^[1]:

Π(N) ≤ 3N

The actual period jumps around. A 150 × 150 image returns after 300 iterations, while a 74-pixel image takes 114 and appears upside-down at step 57 Arnold's cat map, Wikipedia^[1]. Our own count shows that a 124-pixel image returns after only 15 steps, and that the bound 3N is reached at N = 10, 50 and 250. The pattern is tied to Fibonacci numbers: the cat map’s matrix is the square of the Fibonacci matrix, so its period is half the Pisano period, the length of the repeating cycle of Fibonacci numbers modulo N Pisano period, Wikipedia^[5].

Is this Poincaré recurrence?

Partly. The Poincaré recurrence theorem says that a system with finite, conserved phase-space volume returns arbitrarily close to almost any starting state, infinitely often Poincaré recurrence theorem, Wikipedia^[6]. The pixel cat is an extreme, exact version of that: a finite set of states can only cycle. In the continuous map, a typical point with irrational coordinates never returns exactly, only arbitrarily close. And, for any real gas, recurrence times are astronomically long, which is part of why we never see entropy run backwards. That story is in why time only goes forward and what entropy really is.

The cat map also has a quantum version. Hannay and Berry studied the quantisation of linear maps on a torus in 1980 Hannay and Berry 1980^[7], which opened the way to quantum versions of the cat map.

Quick FAQ

Is the scrambled image random?

No. Every step is exact and reversible. The image only looks random because neighbouring pixels are sent far apart Arnold's cat map, Wikipedia^[1].

Can I use it to encrypt pictures?

It is often used to demonstrate mixing with images Arnold's cat map, Wikipedia^[1], but because anyone can run the map forward to the period, it is not secure on its own. More chaos lives in our Waves, Chaos & Matter collection.

References

1. Wikipedia, “Arnold's cat map”. https://en.wikipedia.org/wiki/Arnold%27s_cat_map
2. Wikipedia, “Anosov diffeomorphism”. https://en.wikipedia.org/wiki/Anosov_diffeomorphism
3. Wikipedia, “Lyapunov exponent”. https://en.wikipedia.org/wiki/Lyapunov_exponent
4. Freeman J. Dyson and Harold Falk (1992), “Period of a Discrete Cat Mapping,” The American Mathematical Monthly 99, 603–614 (DOI 10.2307/2324989; metadata verified via Crossref). https://doi.org/10.2307/2324989
5. Wikipedia, “Pisano period”. https://en.wikipedia.org/wiki/Pisano_period
6. Wikipedia, “Poincaré recurrence theorem”. https://en.wikipedia.org/wiki/Poincar%C3%A9_recurrence_theorem
7. J.H. Hannay and M.V. Berry (1980), “Quantization of linear maps on a torus-fresnel diffraction by a periodic grating,” Physica D: Nonlinear Phenomena 1, 267–290 (DOI 10.1016/0167-2789(80)90026-3; metadata verified via Crossref). https://doi.org/10.1016/0167-2789(80)90026-3

Written by Pixelated Physics. Every factual claim is linked to the source we checked; points that are still debated are labelled open.