#jsDisabledContent { display:none; } My Account | Register | Help

# Arnold's cat map

Article Id: WHEBN0005732075
Reproduction Date:

 Title: Arnold's cat map Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Arnold's cat map

Picture showing how the linear map stretches the unit square and how its pieces are rearranged when the modulo operation is performed. The lines with the arrows show the direction of the contracting and expanding eigenspaces

In mathematics, Arnold's cat map is a chaotic map from the torus into itself, named after Vladimir Arnold, who demonstrated its effects in the 1960s using an image of a cat, hence the name.[1]

Thinking of the torus \mathbb{T}^2 as the quotient space \mathbb{R}^2/\mathbb{Z}^2 Arnold's cat map is the transformation \Gamma : \mathbb{T}^2 \to \mathbb{T}^2 given by the formula

\Gamma \, : \, (x,y) \to (2x+y,x+y) \bmod 1.

Equivalently, in matrix notation, this is

\Gamma \left( \begin{bmatrix} x \\ y \end{bmatrix} \right) = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \bmod 1 = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \bmod 1.

That is, with a unit size equal to the width of the square image, the image is sheared one unit up, then one unit to the right, and all that lies outside that unit square is shifted back by the unit until it's within the square.

## The discrete cat map

From order to chaos and back. Sample mapping on a picture of 150x150 pixels. The numbers shows the iteration step. After 300 iterations arriving at the original image
Sample mapping on a picture of a pair of cherries. The image is 74 pixels wide, and takes 114 iterations to be restored, although it appears upside-down at the halfway point.

It is possible to define a discrete analogue of the cat map. One of this map's features is that image being apparently randomized by the transformation but returning to its original state after a number of steps. As can be seen in the picture to the right, the original image of the cat is sheared and then wrapped around in the first iteration of the transformation. After some iterations, the resulting image appears rather random or disordered, yet after further iterations the image appears to have further order—ghost-like images of the cat, multiple smaller copies arranged in a repeating structure and even upside-down copies of the original image—and ultimately returns to the original image.

The discrete cat map describes the phase space flow corresponding to the discrete dynamics of a bead hopping from site qt (0 ≤ qt < N) to site qt+1 on a circular ring with circumference N, according to the second order equation:

q_{t+1} - 3q_{t} + q_{t-1} = 0 \mod N

Defining the momentum variable pt = qt - qt-1, the above second order dynamics can be re-written as a mapping of the square 0 ≤ q, p < N (the phase space of the discrete dynamical system) onto itself:

q_{t+1} = 2q_{t} + p_{t} \mod N
p_{t+1} = q_{t} + p_{t} \mod N

This Arnold cat mapping shows mixing behavior typical for chaotic systems. However, since the transformation has a determinant equal to unity, it is area-preserving and therefore invertible the inverse transformation being:

q_{t-1} = q_{t} - p_{t} \mod N
p_{t-1} = -q_{t} + 2p_{t} \mod N

For real variables q and p, it is common to set N = 1. In that case a mapping of the unit square with periodic boundary conditions onto itself results.

When N is set to an integer value, the position and momentum variables can be restricted to integers and the mapping becomes a mapping of a toroidial square grid of points onto itself. Such an integer cat map is commonly used to demonstrate mixing behavior with Poincaré recurrence utilising digital images. The number of iterations needed to restore the image can be shown never to exceed 3N.[4]

For an image, the relationship between iterations could be expressed as follows:

\begin{array}{rrcl} n=0: \quad & T^0 (x,y) &= & \mbox{Input Image}(x,y) \\ n=1: \quad & T^1 (x,y) &= & T^0 \left( \bmod(2x+y, N), \bmod(x+y, N) \right) \\ & &\vdots \\ n=k: \quad & T^k (x,y) &= & T^{k-1} \left( \bmod(2x+y, N), \bmod(x+y, N) \right) \\ & &\vdots \\ n=m: \quad & \mbox{Output Image}(x,y) &=& T^m (x,y) \end{array}

## References

1. ^
2. ^ Franks, John M (October 1977). "Invariant sets of hyperbolic toral automorphisms". American Journal of Mathematics (The Johns Hopkins University Press) 99 (5): 1089–1095.
3. ^ "Sloane's A004146 ", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
4. ^
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.