Two-dimensional maps

Linear 2D Maps

We reviewed the basics of eigenvectors and eigenvalues in the chapter on planar flows, which are the main tools for studying linear 2D maps. For a system

$\left ( \begin{array}{c} x_{n+1} \\ y_{n+1} \end{array} \right ) = A \left ( \begin{array}{c} x_{n} \\ y_{n} \end{array} \right )$

if the matrix $A$ is diagonalizable with eigenvalue $\lambda_1$ and $\lambda_2$ , then we can explicitly solve the system as

$\left ( \begin{array}{c} x_{n} \\ y_{n} \end{array} \right ) = P \left ( \begin{array}{cc} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{array} \right ) P^{-1} \left ( \begin{array}{c} x_{0} \\ y_{0} \end{array} \right )$

where $P$ is a matrix whose columns are the eigenvectors of $A$ .

Example: Fibonacci system

An interesting application of 2D linear maps arises from the study of the Fibonacci sequence of numbers, which is defined by

$F_{n+1} = F_{n} + F_{n-1}$

along with the initial condition $F_0 = 0$ , $F_1 = 1$ . We can view this as a linear map of the last two iterates of the sequence, meaning it is equivalent to

$\left ( \begin{array}{c} x_{i+1} \\ y_{i+1} \end{array} \right ) = \left ( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right ) \left ( \begin{array}{c} x_{i} \\ y_{i} \end{array} \right )$

where $x_n = F_n$ and $y_n = F_{n-1}$ . We can use the general formula from above once we find the eigenvalues and eigenvectors of the coefficient matrix $A = \left ( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right )$ .

The characteristic equation for $A$ is

$\det (A - \lambda I) = \lambda^2 - \lambda -1 = 0$

which has roots $\lambda_1 = \phi = \frac{1 + \sqrt{5}}{2}$ and $\lambda_2 = -1/\phi$ ; where $\phi$ is the famous 'golden ratio'.

The eigenvalues can be chosen as

$v_1 = \left ( \begin{array}{c} \phi \\ 1 \end{array} \right ), \ \ v_2 = \left ( \begin{array}{c} -1 \\ \phi \end{array} \right )$

so the matrix of eigenvalues and its inverse are

$P = \left ( \begin{array}{cc} \phi & -1 \\ 1 & \phi \end{array} \right ), \ \ \ P^{-1} = \left ( \begin{array}{cc} \phi & -1 \\ 1 & \phi \end{array} \right )$

Singular Value Decomposition

In addition to eigenvectors, eigenvalues, and matrix similarity, it is often useful to know how much a linear map will possibly stretch or contract its input. The main tool for this analysis is the Singular Value Decomposition (SVD) of a matrix.

Every matrix $A$ has a Singular Value Decomposition:

$A = U S V^T$

where $U$ and $V$ are unitary matrices, and the only nonzero entries of $\Sigma$ are on its diagonal with $S_{i,i} \ge S_{i+1,i+1} \ge 0$ . These diagonal values of $S$ are called the singular values of $A$ . The singular values have a very nice geometric interpretation: the image of a unit sphere (each point thought of as a vector) under multiplication by a matrix $A$ is an ellipsoid (in the appropriate dimension) with semi-axes lengths given by the singular values. This is shown below for the particular example of

$A = \left(\begin{array}{rr} -3 & 3 \\ 0 & 2 \end{array} \right)$

for which the singular values are

$\sigma_1 = \sqrt{11 + \sqrt{85}} \approx 4.5,$

$\sigma_2 = \sqrt{11 - \sqrt{85}} \approx 1.3$

In the image, the shorter bright green and purple vectors are the columns of $V$ , the right-singular vectors. They are sent by $A$ (multiplying from the left) to the darker vectors $\sigma_1 u_1$ and $\sigma_2 u_2$ . Note that $v_1$ and $v_2$ are orthogonal, and so are $u_1$ and $u_2$ .

The SVD is not cheap to compute, but with it in hand we can compute almost anything else we might want regarding the matrix $A$ .

A simple way to compute the SVD (not the best way for larger matrices) is to form the matrix $A^T A = V \Sigma^T \Sigma V^T$ , which is symmetric. Its eigenvectors are the $v_i$ (the columns of $V$ ), and its eigenvalues are the squares of the singular values.

Henon map

In 1976 Michel Hénon introduced a model 2-D system that seemed to have a fractal strange attractor (a nonperiodic attracting set) for some values of its parameters. The system can be written in various ways; we follow the conventions of the text by Alligood, Sauer, and Yorke which is slightly different from the original:

$x_{n+1} = a - x_{n}^2 + b y_n$

$y_{n+1} = x_n$

The Jacobian matrix of the Hénon map in this form is

$\left ( \begin{array}{cc} -2 x & b \\ 1 & 0 \end{array} \right )$

and from this we can see that the determinant of the Jacobian matrix is always $-b$ . So for $b=1$ or $b=-1$ the map is area-preserving.

The fixed points are fairly simple to compute, starting from

$x = a - x^2 + b y$

$y = x$

we can immediately eliminate $y$ and we have a quadratic equation in $x$ , so the fixed points are

$x = \frac{b - 1 \pm \sqrt{(b-1)^2 + 4a}}{2}$

which are real when $4a > -(b-1)^2$ (the Hénon map has mostly been studied on the real plane).

Similarly we can find the period-2 points by eliminating $y$ from the equations

$A -(x^2 - b y - A)^2 + b x = x$

$a - x^2 + b y = y$

and then factor to find

$[x^2 + (b-1)x + (b-1)^2 - a] [a - x^2 + (b-1)x] = 0$

The second factor in the above equation is for the fixed points, so the $x$ -coordinate of the period-2 points is determined from $x^2 + (b-1)x + (b-1)^2 - a = 0$ . For each $x$ value there is a unique $y$ value given by

$$ y = \frac{x^2 - a}{b-1}. $$

Hyperbolic toral automorphisms

The topology of the underlying space has important implications for the possible maps and flows on that space. One important class of examples are the torii, which are topologically equivalent to products of circles. The two dimensional torus already has some interesting maps and flows.

The Cat map

A famous example of a map on a 2D torus $\mathcal{T}$ is the "cat map" of V. I. Arnold. We consider the torus to be the plane quotiented by the integer lattice, so that a point $(x,y)$ is identified with a point $(u,v)$ in $[0,1) \times [0,1)$ if both $x-u$ and $y-v$ are in $\mathbb{Z}$ . Lets call $P$ the projection function that takes the plane to the torus with this quotient.

The cat map can be written as $Cx$ where $x$ is a 2d vector and

$C = \left ( \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right )$

which is the square of the Fibonacci matrix $\left ( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right )$ discussed earlier. Since the determinant of $C$ is $1$ , the matrix is not only invertible but the inverse has integer entries:

$C^{-1} = \left ( \begin{array}{cc} 1 & -1 \\ -1 & 2 \end{array} \right )$

Because of their integer entries, both $Cx$ and $C^{-1}x$ are well defined on the torus - i.e. if we have plane points $x = (x_1, x_2)$ and $u = (u_1, u_2)$ whose components differ by integers, then $\pi(C(x)) = \pi(C(u))$ .

The periodic points of the map $Cx$ on $\mathcal{T}$ are simply the points with rational coordinates. To see this, suppose that we have a rational point $x = (p_1/q_1, p_2/q_2)$ . It is mapped by $C$ to a point that also must have rational entries, and the denominators will never increase since we are multiplying by integers. Since the set of rational points with bounded denominators is a finite set, the map must eventually return to the same value. The point cannot be pre-periodic since we are considering an invertible map.

In the other direction, if a point is periodic with period $m$ then $C^m x = x$ on the torus, which means in the plane we have

$C^m x = x + \left ( \begin{array}{c} p \\ q \end{array} \right )$

where $p$ and $q$ are integers. Solving for $x$ we see that

$x = (C^m - I)^{-1} \left ( \begin{array}{c} p \\ q \end{array} \right )$

which must be rational since $C^m - I$ is an integer matrix.

Arnold Cat map diagram — Rectangles for the cat map aligned with stable and unstable manifolds

Covering maps

The projection $P$ in the cat map example is an example of a covering map. A map $f:X \rightarrow Y$ is a covering map if for every point in $Y$ there is a neighborhood that has a fixed number of preimages under $f$ , and those preimages are homeomorphic to the neighborhood. If the space $X$ is simply-connected, then the map $f$ is a universal covering map and $X$ is the universal cover of $Y$ .

Skinny Baker Map

$B(x,y) = \left \{ \begin{array}{l} (x/3, 2y) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le y \le 1/2 \\ (x/3 + 2/3, 2y -1) \ \ \ \ \ 1/2 < y \le 1 \end{array} \right .$

The Smale Horseshoe

Twist Maps

Twist maps are an important type of 2-D map that arise in a variety of applications. They are usually defined on an annulus such as $S^1 \times [-1,1]$ . A function $F(x,y) = (X,Y)$ on the annulus is a positive twist map if it is area-preserving and if $X$ is a monotone increasing function of $y$ for every fixed $x$ . If the map is differentiable than these conditions can be written as $|DF| = 1$ and $\frac{\partial X}{\partial y} > 0$ .

Exercises

For what values of the parameter $a$ does the matrix

$\left(\begin{array}{rr} a & 0 \\ 1 & 1 \end{array}\right)$

have repeated eigenvalues?
Diagonalize the coefficient matrix of the system to find explicit solutions $(x_{n}, y_{n})$ for

$x_{n+1} = \frac{1}{2} x_{n} + \frac{1}{2} y_n$

$y_{n+1} = \frac{1}{4} x_n + \frac{3}{4} y_n$

if $x_0 = 1$ and $y_0 = 0$ .
Find the fixed points of the planar map $f(x,y) = (x^2 - 5x + y, x^2)$ and determine if they are sinks, sources, saddles, or non-hyperbolic.
The Henon map with $b=0$ is

$x_{n+1} = a - x_n^2$

$y_{n+1} = x_n$

Sketch the image of the square $[-1,1] \times [-1,1]$ under this map, assuming that $a > 0$ .
For the Henon map with $b = 1/2$ :

$x_{n+1} = a - x_n^2 + \frac{1}{2} y_n$

$y_{n+1} = x_n$
- Find the range of parameters $a$ for which the map has two fixed points, one of which is a sink and the other a saddle.
- Find the range of parameters $a$ for which the map has a period-2 sink.

License

This work (text, mathematical images, and javascript applets) is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Biographical images are from Wikipedia and have their own (similar) licenses.