View source for Arnold's cat map

{{short description|Chaotic map from the torus into itself}}
[[Image:Arnoldcatmap.svg|thumb|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 [[eigenspace]]s]]

In [[mathematics]], '''Arnold's cat map''' is a [[chaos theory|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.<ref name="Arnold"/> It is a simple and pedagogical example for [[hyperbolic toral automorphism]]s.

Thinking of the torus <math>\mathbb{T}^2</math> as the [[Quotient space (topology)|quotient space]] <math>\mathbb{R}^2/\mathbb{Z}^2</math>, Arnold's cat map is the transformation <math>\Gamma : \mathbb{T}^2 \to \mathbb{T}^2</math> given by the formula

:<math>\Gamma (x,y) = (2x+y,x+y) \bmod 1.</math>

Equivalently, in [[matrix (mathematics)|matrix]] notation, this is

:<math>\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.</math>

That is, with a unit equal to the width of the square image, the image is [[Shear mapping|sheared]] one unit up, then two units to the right, and all that lies outside that unit square is shifted back by the unit until it is within the square.

==Name==

The map receives its name from Arnold's 1967 manuscript with André Avez, ''Problèmes ergodiques de la mécanique classique'',<ref name="Arnold"/> in which the outline of a cat was used to illustrate the action of the map on the torus. In the original book it was captioned by a humorous footnote,
{{Blockquote
|text=The [[Société Protectrice des Animaux]] has given permission to reproduce this image, as well as others.
}}
In Arnold's native Russian, the map is known as "[[okroshka]] (cold soup) from a cat" ({{langx|ru|окрошка из кошки}}), in reference to the map's mixing properties, and which forms a play on words. Arnold later wrote that he found the name "Arnold's Cat" by which the map is known in English and other languages to be "strange".<ref>{{cite book |last1=Arnold |first1=V. I. |title=Lectures and Problems: A Gift to Young Mathematicians |date=2015 |publisher=Mathematical Sciences Research Institute |location=Berkeley, CA, USA}}</ref>

==Properties==
* Γ is [[invertible function|invertible]] because the matrix has [[determinant]] 1 and therefore its [[Integer matrix#Properties|inverse has integer entries]],
* Γ is [[Measure-preserving dynamical system|area preserving]],
* Γ has a unique [[hyperbolic fixed point]] (the [[Vertex (geometry)|vertices]] of the square). The linear transformation which defines the map is hyperbolic: its [[eigenvalue]]s are irrational numbers, one greater and the other smaller than 1 (in absolute value), so they are associated respectively to an expanding and a contracting [[eigenspace]] which are also the [[stable manifold|stable and unstable manifolds]]. The eigenspaces are orthogonal because the matrix is [[symmetric matrix|symmetric]]. Since the eigenvectors have [[rational dependence|rationally independent]] components both the eigenspaces [[dense set|densely]] cover the torus.  Arnold's cat map is a particularly well-known example of a ''hyperbolic toral automorphism'', which is an [[automorphism]] of a [[torus]] given by a square [[unimodular matrix]] having no [[eigenvalues]] of absolute value 1.<ref name="Franks"/>
* The set of the points with a [[periodic orbit]] is [[dense set|dense]] on the torus. Actually a point is periodic if and only if its coordinates are [[rational number|rational]].
* Γ is [[Topological transitivity|topologically transitive]] (i.e. there is a point whose orbit is [[dense set|dense]]).
* The number of points with period <math>n</math> is exactly <math>|\lambda_1^n+\lambda_2^n-2|</math> (where <math>\lambda_1</math> and <math>\lambda_2</math> are the eigenvalues of the matrix). For example, the first few terms of this series are 1, 5, 16, 45, 121, 320, 841, 2205 ....<ref>{{Cite OEIS|sequencenumber=A004146}}</ref> (The same equation holds for any unimodular hyperbolic toral automorphism if the eigenvalues are replaced.)
* Γ is [[ergodic]] and [[Mixing (physics)|mixing]],
* Γ is an [[Anosov diffeomorphism]] and in particular it is [[Structural stability|structurally stable]].
* The mapping torus of Γ is a [[solvmanifold]], and as with other Anosov diffeomorphisms, this manifold has [[solv geometry]].

== The discrete cat map ==
[[Image:Arnold cat.png|right|frame|From order to chaos and back. Sample mapping on a picture of 150x150 pixels. The number shows the iteration step; after 300 iterations, the original image returns.]]
[[File:Arnold's Cat Map animation (74px, zoomed, labelled).gif|right|frame|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 (the 57th iteration).]]

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 adjacent picture, the original image of the cat is [[shear mapping|sheared]] and then wrapped around in the first iteration of the transformation. After some iterations, the resulting image appears rather [[randomness|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 ''q''<sub>''t''</sub> (0 ≤ ''q''<sub>''t''</sub> < ''N'') to site ''q''<sub>''t''+1</sub> on a circular ring with circumference ''N'', according to the [[second order equation]]:

:<math>q_{t+1} - 3q_t + q_{t-1} = 0 \mod N</math>

Defining the momentum variable ''p''<sub>''t''</sub> = ''q''<sub>''t''</sub>&nbsp;−&nbsp;''q''<sub>''t''−1</sub>, 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:

:<math>q_{t+1} = 2q_{t} + p_t \mod N</math>
:<math>p_{t+1} = q_{t} + p_t \mod N</math>

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

:<math>q_{t-1} = q_t - p_t \mod N</math>
:<math>p_{t-1} = -q_t + 2p_t \mod N</math>

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 (physics)|mixing]] behavior with [[Poincaré recurrence theorem|Poincaré recurrence]] utilising digital images. The number of iterations needed to restore the image can be shown never to exceed 3N.<ref name="DysonFalk"/>

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

:<math>
\begin{array}{rrcl}
n=0: \quad  &  T^0 (x,y) &= & \text{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  & \text{Output Image}(x,y) &=& T^m (x,y)
\end{array}
</math>

==Models==
===Python code for Arnold's Cat Map===
<syntaxhighlight lang="python">
import os

from PIL.Image import open as load_pic, new as new_pic

def main(path, iterations, keep_all=False, name="arnold_cat-{name}-{index}.png"):
    """
    Params
        path:str
            path to photograph
        iterations:int
            number of iterations to compute
        name:str
            formattable string to use as template for file names
    """
    title = os.path.splitext(os.path.split(path)[1])[0]
    counter = 0
    while counter < iterations:
        with load_pic(path) as image:
            dim = width, height = image.size
            with new_pic(image.mode, dim) as canvas:
                for x in range(width):
                    for y in range(height):
                        nx = (2 * x + y) % width
                        ny = (x + y) % height

                        canvas.putpixel((nx, height-ny-1), image.getpixel((x, height-y-1)))

        if counter > 0 and not keep_all:
            os.remove(path)
        counter += 1
        print(counter, end="\r")
        path = name.format(name=title, index=counter)
        canvas.save(path)

    return canvas

if __name__ == "__main__":
    path = input("Enter the path to an image:\n\t")
    while not os.path.exists(path):
        path = input("Couldn't find your chosen image, please try again:\n\t")
    result = main(path, 3)
    result.show()
</syntaxhighlight>

==See also==
{{Portal|Mathematics}}
* [[List of chaotic maps]]
* [[Recurrence plot]]

==References==
<references>
<ref name="Arnold">{{cite book
  | author= Vladimir I. Arnold
  | author-link= Vladimir I. Arnold
  |author2=A. Avez
  | title=Problèmes Ergodiques de la Mécanique Classique
  | location=Paris
  | publisher=Gauthier-Villars
  | year=1967|language=fr}};
'''English translation:''' {{cite book
  |author=V. I. Arnold
  |author2=A. Avez
  |title=Ergodic Problems in Classical Mechanics
  |location=New York
  |publisher=Benjamin
  |year=1968
}}</ref>
<ref name="Franks">{{cite journal
  | last1       = Franks
  | first1      = John M
  | title       = Invariant sets of hyperbolic toral automorphisms
  | journal     = American Journal of Mathematics
  | volume      = 99
  | issue       = 5
  |date=October 1977
  | pages       = 1089&ndash;1095
  | doi         = 10.2307/2374001
  | issn        = 0002-9327
  | publisher   = The Johns Hopkins University Press
| jstor = 2374001
 }}</ref>
<ref name="DysonFalk">{{cite journal
  | title       = Period of a Discrete Cat Mapping
  | first1      = Freeman John
  | last1       = Dyson
  | authorlink1 = Freeman Dyson
  | first2      = Harold
  | last2       = Falk
  | journal     = The American Mathematical Monthly
  | volume      = 99
  | issue       = 7
  | year        = 1992
  | pages       = 603–614
  | issn        = 0002-9890
  | jstor         = 2324989
  | doi         = 10.2307/2324989
  | publisher   = Mathematical Association of America
}}</ref>
</references>

==External links==
*{{MathWorld|urlname=ArnoldsCatMap|title=Arnold's Cat Map}}
*[https://web.archive.org/web/20071102050824/http://www.mpipks-dresden.mpg.de/mpi-doc/kantzgruppe/wiki/projects/Recurrence.html Effect of randomisation of initial conditions on recurrence time]
* [http://demonstrations.wolfram.com/ArnoldsCatMap/ Arnold's Cat Map] by Enrique Zeleny, [[The Wolfram Demonstrations Project]].
*[http://gerdbreitenbach.de/arnold_cat/cat.html Arnold's Cat Map: An interactive graphical exploration ]
{{Chaos theory}}

{{DEFAULTSORT:Arnold's Cat Map}}
[[Category:Chaotic maps]]
[[Category:Exactly solvable models]]