Arnold's cat map
5732075
224329611
2008-07-08T11:00:44Z
Pokipsy76
466871
/* Properties */ +structural stability
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]].<ref>*{{fr icon}} {{cite book|author=V. I. Arnold|coauthors=A. Avez|title=Problèmes Ergodiques de la Mécanique Classique|location=Paris|publisher=Gauthier-Villars|year=1967}}; '''English translation:''' {{cite book|author=V. I. Arnold|coauthors=A. Avez|title=Ergodic Problems in Classical Mechanics|location=New York|publisher=Benjamin|year=1968}}</ref>
Thinking the torus <math>\mathbb{T}^2</math> as <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) \to (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 size equal to the width of the square image, the image is sheared one unit to the right, then one unit up, and all that lies without that unit square is wrapped around on the other respective side to be within it.
[[Image:Arnoldcatmap.svg|thumb|500px|center|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]]
==Properties==
* Γ is [[invertible function|invertible]] because the matrix has [[determinant]] 1 and therefore its 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 real numbers, one greater and the other smaller than 1, so they are associated respectively to an expanding and a contracting [[eigenspace]] which are also the [[stable manifold|stable and unstable manifolds]]. The eigenspace 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,
* The set of the points with a [[periodic orbit]] is [[dense set|dense]] on the torus. Actually a point has a periodic orbit 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 set of points with period ''n'' is λ<sub>1</sub><sup>''n''</sup>+λ<sub>2</sub><sup>–''n''</sup>-2 (where λ<sub>1</sub> and λ<sub>2</sub> are the eigenvalues of the matrix)
* Γ is [[ergodic]] and [[mixing]],
* Γ is an [[Anosov diffeomorphism]] and in particular it is [[Structural stability|structurally stable]].
== 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 numbers shows the
iteration step. After 300 iterations arriving at the original image]]
It is possible to define a discrete analogous 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 [[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—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]]:
:q<sub>t+1</sub> - 3q<sub>t</sub> + q<sub>t-1</sub> = 0 mod N
Defining the momentum variable p<sub>t</sub> = q<sub>t</sub> - 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:
:q<sub>t+1</sub> = 2q<sub>t</sub> + p<sub>t</sub> mod N
:p<sub>t+1</sub> = q<sub>t</sub> + p<sub>t</sub> mod N
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:
:q<sub>t-1</sub> = 2q<sub>t</sub> - p<sub>t</sub> mod N
:p<sub>t-1</sub> = -q<sub>t</sub> + p<sub>t</sub> 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 (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>Period of a discrete cat mapping , Freeman J. Dyson and Harold Falk, American Mathematical Monthly 99 603-614 (1992).</ref>
==See also==
* [[List of chaotic maps]]
==References==
<references/>
==External links==
*{{MathWorld|urlname=ArnoldsCatMap|title=Arnold's Cat Map}}
*[http://hypatia.math.uri.edu/~kulenm/diffeqaturi/victor442/index.html A description and demonstration], using an image of the [[Earth]] as an example
*[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://online.redwoods.cc.ca.us/instruct/darnold/maw/catmap3.htm Arnold's Cat Map], David Arnold.
[[Category:Chaotic maps]]
[[Category:Exactly solvable models]]
[[fi:Arnoldin kissa]]