Arnold's cat map

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] It is a simple and pedagogical example for hyperbolic toral automorphisms.

Contents

• Name
• Properties
• The discrete cat map
• Models
• Python code for Arnold's Cat Map
• See also
• References
• External links

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

${\displaystyle \Gamma (x,y)=(2x+y,x+y){\bmod {1}}.}$

Equivalently, in matrix notation, this is

${\displaystyle \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 equal to the width of the square image, the image is 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, ^[1] 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,

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" (Russian : окрошка из кошки), 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". ^[2]

Properties

• Γ is invertible because the matrix has determinant 1 and therefore its inverse has integer entries,
• Γ is area preserving,
• Γ has a unique hyperbolic fixed point (the vertices of the square). The linear transformation which defines the map is hyperbolic: its eigenvalues 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 and unstable manifolds. The eigenspaces are orthogonal because the matrix is symmetric. Since the eigenvectors have rationally independent components both the eigenspaces 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. ^[3]
• The set of the points with a periodic orbit is dense on the torus. Actually a point is periodic if and only if its coordinates are rational.
• Γ is topologically transitive (i.e. there is a point whose orbit is dense).
• The number of points with period ${\displaystyle n}$ is exactly ${\displaystyle |\lambda _{1}^{n}+\lambda _{2}^{n}-2|}$ (where ${\displaystyle \lambda _{1}}$ and ${\displaystyle \lambda _{2}}$ are the eigenvalues of the matrix). For example, the first few terms of this series are 1, 5, 16, 45, 121, 320, 841, 2205 .... ^[4] (The same equation holds for any unimodular hyperbolic toral automorphism if the eigenvalues are replaced.)
• Γ is ergodic and mixing,
• Γ is an Anosov diffeomorphism and in particular it is structurally stable.
• The mapping torus of Γ is a solvmanifold, and as with other Anosov diffeomorphisms, this manifold has solv geometry.

The discrete cat map

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 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 q_t (0 ≤ q_t < N) to site q_t+1 on a circular ring with circumference N, according to the second order equation:

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

Defining the momentum variable p_t = q_t − q_t−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:

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

${\displaystyle 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:

${\displaystyle q_{t-1}=q_{t}-p_{t}\mod N}$

${\displaystyle 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. ^[5]

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

${\displaystyle {\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}}}$

Models

importosfromPIL.Imageimportopenasload_pic,newasnew_picdefmain(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=0whilecounter<iterations:withload_pic(path)asimage:dim=width,height=image.sizewithnew_pic(image.mode,dim)ascanvas:forxinrange(width):foryinrange(height):nx=(2*x+y)%widthny=(x+y)%heightcanvas.putpixel((nx,height-ny-1),image.getpixel((x,height-y-1)))ifcounter>0andnotkeep_all:os.remove(path)counter+=1print(counter,end="\r")path=name.format(name=title,index=counter)canvas.save(path)returncanvasif__name__=="__main__":path=input("Enter the path to an image:\n\t")whilenotos.path.exists(path):path=input("Couldn't find your chosen image, please try again:\n\t")result=main(path,3)result.show()

See also

• List of chaotic maps
• Recurrence plot

Related Research Articles

In geometry, a torus is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanar with the circle. The main types of toruses include ring toruses, horn toruses, and spindle toruses. A ring torus is sometimes colloquially referred to as a donut or doughnut.

In topology, a covering or covering projection is a map between topological spaces that, intuitively, locally acts like a projection of multiple copies of a space onto itself. In particular, coverings are special types of local homeomorphisms. If is a covering, is said to be a covering space or cover of , and is said to be the base of the covering, or simply the base. By abuse of terminology, and may sometimes be called covering spaces as well. Since coverings are local homeomorphisms, a covering space is a special kind of étale space.

In mathematics, the adjoint representation of a Lie group G is a way of representing the elements of the group as linear transformations of the group's Lie algebra, considered as a vector space. For example, if G is , the Lie group of real n-by-n invertible matrices, then the adjoint representation is the group homomorphism that sends an invertible n-by-n matrix to an endomorphism of the vector space of all linear transformations of defined by: .

In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form

In mathematics, the modular group is the projective special linear group of 2 × 2 matrices with integer coefficients and determinant 1. The matrices A and −A are identified. The modular group acts on the upper-half of the complex plane by fractional linear transformations, and the name "modular group" comes from the relation to moduli spaces and not from modular arithmetic.

In mathematics, a submersion is a differentiable map between differentiable manifolds whose differential is everywhere surjective. This is a basic concept in differential topology. The notion of a submersion is dual to the notion of an immersion.

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.

In geometric topology, a branch of mathematics, a Dehn twist is a certain type of self-homeomorphism of a surface.

In mathematics, in the subfield of geometric topology, the mapping class group is an important algebraic invariant of a topological space. Briefly, the mapping class group is a certain discrete group corresponding to symmetries of the space.

The dyadic transformation is the mapping

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number p, then this root can be lifted to a unique root modulo any higher power of p. More generally, if a polynomial factors modulo p into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of p.

In mathematics, the Teichmüller space of a (real) topological surface is a space that parametrizes complex structures on up to the action of homeomorphisms that are isotopic to the identity homeomorphism. Teichmüller spaces are named after Oswald Teichmüller.

In mathematics, more particularly in the fields of dynamical systems and geometric topology, an Anosov map on a manifold M is a certain type of mapping, from M to itself, with rather clearly marked local directions of "expansion" and "contraction". Anosov systems are a special case of Axiom A systems.

In the study of dynamical systems, a hyperbolic equilibrium point or hyperbolic fixed point is a fixed point that does not have any center manifolds. Near a hyperbolic point the orbits of a two-dimensional, non-dissipative system resemble hyperbolas. This fails to hold in general. Strogatz notes that "hyperbolic is an unfortunate name—it sounds like it should mean 'saddle point'—but it has become standard." Several properties hold about a neighborhood of a hyperbolic point, notably

The Okamoto–Uchiyama cryptosystem is a public key cryptosystem proposed in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the multiplicative group of integers modulo n, , where n is of the form p²q and p and q are large primes.

In mathematics, the Abel–Jacobi map is a construction of algebraic geometry which relates an algebraic curve to its Jacobian variety. In Riemannian geometry, it is a more general construction mapping a manifold to its Jacobi torus. The name derives from the theorem of Abel and Jacobi that two effective divisors are linearly equivalent if and only if they are indistinguishable under the Abel–Jacobi map.

In the mathematical subject of geometric group theory, a train track map is a continuous map f from a finite connected graph to itself which is a homotopy equivalence and which has particularly nice cancellation properties with respect to iterations. This map sends vertices to vertices and edges to nontrivial edge-paths with the property that for every edge e of the graph and for every positive integer n the path fⁿ(e) is immersed, that is fⁿ(e) is locally injective on e. Train-track maps are a key tool in analyzing the dynamics of automorphisms of finitely generated free groups and in the study of the Culler–Vogtmann Outer space.

In mathematics, and more precisely in topology, the mapping class group of a surface, sometimes called the modular group or Teichmüller modular group, is the group of homeomorphisms of the surface viewed up to continuous deformation. It is of fundamental importance for the study of 3-manifolds via their embedded surfaces and is also studied in algebraic geometry in relation to moduli problems for curves.

In mathematics, a profinite integer is an element of the ring

In mathematics, a Cannon–Thurston map is any of a number of continuous group-equivariant maps between the boundaries of two hyperbolic metric spaces extending a discrete isometric actions of the group on those spaces.

References

External links

• Weisstein, Eric W. "Arnold's Cat Map". MathWorld .
• Effect of randomisation of initial conditions on recurrence time
• Arnold's Cat Map by Enrique Zeleny, The Wolfram Demonstrations Project.
• Arnold's Cat Map: An interactive graphical exploration