5.6 Discrete dynamical systems

Big idea

A discrete dynamical system is a state vector and a rule that produces the next state from the current one. When the rule is a matrix, $\mathbf{x}_{k+1} = A\mathbf{x}_k$, the state after $k$ steps is $A^k\mathbf{x}_0$. Populations split by age class, a machine moving between operating modes, an economy split into sectors: all the same shape.

Iterating the matrix by hand tells you nothing about the long run and gets expensive fast. Eigenvectors replace the iteration with a formula. Write the starting state as a combination of eigenvectors, and each piece evolves on its own: the piece along an eigenvector for $\lambda$ is multiplied by $\lambda$ at every step, so after $k$ steps it carries a factor $\lambda^k$.

The long run then reads off the eigenvalues without any computation. Pieces with $|\lambda| < 1$ fade, pieces with $|\lambda| > 1$ take over, and a piece with $\lambda = 1$ sits still. Whichever eigenvalue is largest in size decides the direction the state points in eventually, and whether the system grows, dies out, or settles.

Decoder

Provided $\mathbf{x}_0$ is written in an eigenvector basis, the solution of the system is $\mathbf{x}_k = c_1\lambda_1^k\mathbf{v}_1 + \cdots + c_n\lambda_n^k\mathbf{v}_n$.

In plain terms: find the weights $c_1, \dots, c_n$ that build $\mathbf{x}_0$ out of the eigenvectors, once, by solving one linear system. After that, every future state is the same combination with each eigenvector’s weight multiplied by its eigenvalue to the $k$. No matrix multiplication appears anywhere in the formula, and $k$ can be $3$ or $3$ million at the same cost.

Definitions and results

The system. A first-order linear difference equation $\mathbf{x}_{k+1} = A\mathbf{x}_k$ with a given initial state $\mathbf{x}_0$. The sequence $\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots$ is the trajectory. Since $\mathbf{x}_k = A^k\mathbf{x}_0$, everything about the system is a question about powers of $A$.

Eigenvector solutions. If $\mathbf{v}$ is an eigenvector for $\lambda$, then starting at $\mathbf{x}_0 = \mathbf{v}$ gives $\mathbf{x}_k = \lambda^k\mathbf{v}$. The state never leaves the line through $\mathbf{v}$; only its length and possibly its sign change.

General solution. If $A$ is diagonalizable with eigenvectors $\mathbf{v}_1, \dots, \mathbf{v}_n$ and eigenvalues $\lambda_1, \dots, \lambda_n$, write $\mathbf{x}_0 = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n$. Then

$$ \mathbf{x}_k = c_1\lambda_1^k\mathbf{v}_1 + \cdots + c_n\lambda_n^k\mathbf{v}_n $$

This is $A^k = PD^kP^{-1}$ applied to $\mathbf{x}_0$ and rewritten: $P^{-1}\mathbf{x}_0$ is the list of weights, $D^k$ scales each weight, and $P$ rebuilds the vector.

Finding the weights. Solve $P\mathbf{c} = \mathbf{x}_0$, where $P$ has the eigenvectors as columns. It is one ordinary linear system, solved once at the start.

Dominant eigenvalue. The eigenvalue largest in absolute value. If there is a single dominant eigenvalue and its weight in $\mathbf{x}_0$ is not zero, then for large $k$ its term swamps the others and $\mathbf{x}_k$ points nearly along its eigenvector. The direction settles down long before the length does.

Classifying the origin in the plane. For a $2 \times 2$ real system with real eigenvalues, the origin is:

• an attractor when both $|\lambda| < 1$, since every trajectory shrinks toward it;
• a repeller when both $|\lambda| > 1$, since every nonzero trajectory grows away from it;
• a saddle point when one eigenvalue exceeds $1$ in size and the other falls below, so trajectories come in along one eigenvector line and leave along the other.

Eigenvalue exactly one. The eigenvector line for $\lambda = 1$ is a line of fixed states: start there and nothing moves. If the other eigenvalue is smaller than $1$ in size, every trajectory converges to a point on that line, with the starting state deciding which point. This is the situation behind steady states later in the chapter.

Negative eigenvalues. A negative $\lambda$ flips the sign of its term at each step, so the trajectory alternates sides while its size follows $|\lambda|^k$. Complex eigenvalues rotate instead, spiralling in or out according to the modulus.

Reading a model. Entries of $A$ are usually rates: survival fractions, transfer proportions, growth factors. A dominant eigenvalue above $1$ means long-run growth, below $1$ means decline, and exactly $1$ means a population that holds steady. Its eigenvector gives the proportions the state settles into, which is often the more useful answer.

Worked examples

A system that grows, and the direction it picks

Let

$$ A = \begin{bmatrix} 4 & -2 \\ 1 & 1 \end{bmatrix}, \qquad \mathbf{x}_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$

The eigenvalues are $2$ and $3$, with eigenvectors $\mathbf{v}_1 = (1,1)$ and $\mathbf{v}_2 = (2,1)$. Write $\mathbf{x}_0$ in that basis: $c_1(1,1) + c_2(2,1) = (1,0)$ gives $c_1 + 2c_2 = 1$ and $c_1 + c_2 = 0$, so $c_2 = 1$ and $c_1 = -1$. The solution is

$$ \mathbf{x}_k = -2^k \begin{bmatrix} 1 \\ 1 \end{bmatrix} + 3^k \begin{bmatrix} 2 \\ 1 \end{bmatrix} $$

Check the first two steps against direct multiplication. The formula gives $\mathbf{x}_1 = -2(1,1) + 3(2,1) = (4,1)$, and $A(1,0) = (4,1)$. The formula gives $\mathbf{x}_2 = -4(1,1) + 9(2,1) = (14,5)$, and $A(4,1) = (16-2, \, 4+1) = (14,5)$. One more: the formula gives $\mathbf{x}_3 = -8(1,1) + 27(2,1) = (46,19)$, and $A(14,5) = (56-10, \, 14+5) = (46,19)$.

Both eigenvalues exceed $1$, so the origin is a repeller and the state grows without bound. The dominant eigenvalue is $3$, so the direction approaches that of $(2,1)$. The ratio of the entries confirms it: $4/1 = 4$, then $14/5 = 2.8$, then $46/19$, about $2.42$, heading for $2$.

Converging to a line of fixed states

Let

$$ A = \begin{bmatrix} 0.6 & 0.4 \\ 0.4 & 0.6 \end{bmatrix}, \qquad \mathbf{x}_0 = \begin{bmatrix} 10 \\ 0 \end{bmatrix} $$

The trace is $1.2$ and the determinant is $0.36 - 0.16 = 0.2$, so the characteristic polynomial is $\lambda^2 - 1.2\lambda + 0.2 = (\lambda - 1)(\lambda - 0.2)$. For $\lambda = 1$ the shifted matrix has rows $(-0.4, 0.4)$, giving the eigenvector $(1,1)$. For $\lambda = 0.2$ the rows are $(0.4, 0.4)$, giving $(1,-1)$.

Decompose: $c_1(1,1) + c_2(1,-1) = (10,0)$ forces $c_1 = c_2 = 5$. So

$$ \mathbf{x}_k = 5\begin{bmatrix} 1 \\ 1 \end{bmatrix} + 5(0.2)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix} $$

Check: the formula gives $\mathbf{x}_1 = (5,5) + (1,-1) = (6,4)$, and $A(10,0) = (6,4)$. It gives $\mathbf{x}_2 = (5,5) + 0.2(1,-1) = (5.2, 4.8)$, and $A(6,4) = (3.6 + 1.6, \; 2.4 + 2.4) = (5.2, 4.8)$.

The second term shrinks by a factor of $5$ each step, so the state converges to $(5,5)$. The total $10$ is preserved at every step, which you can see in the entries and also in the fact that the columns of $A$ each sum to $1$.

A saddle point

Let

$$ A = \begin{bmatrix} 1.25 & 0.75 \\ 0.75 & 1.25 \end{bmatrix}, \qquad \mathbf{x}_0 = \begin{bmatrix} 4 \\ 0 \end{bmatrix} $$

The trace is $2.5$ and the determinant is $1.5625 - 0.5625 = 1$, so the characteristic polynomial is $\lambda^2 - 2.5\lambda + 1 = (\lambda - 2)(\lambda - 0.5)$. The eigenvectors are again $(1,1)$ for $\lambda = 2$ and $(1,-1)$ for $\lambda = 0.5$. Decomposing $(4,0)$ gives $c_1 = c_2 = 2$, so

$$ \mathbf{x}_k = 2 \cdot 2^k \begin{bmatrix} 1 \\ 1 \end{bmatrix} + 2(0.5)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix} $$

Check: $\mathbf{x}_1 = 4(1,1) + 1(1,-1) = (5,3)$, and $A(4,0) = (5,3)$. Then $\mathbf{x}_2 = 8(1,1) + 0.5(1,-1) = (8.5, 7.5)$, and $A(5,3) = (6.25 + 2.25, \; 3.75 + 3.75) = (8.5, 7.5)$.

One eigenvalue above $1$, one below, so the origin is a saddle point. The trajectory swings away from the $(1,-1)$ direction it started near and bends toward the $(1,1)$ line, which the entries show: $(4,0)$, then $(5,3)$, then $(8.5, 7.5)$, with the two entries closing in on each other. Only a start exactly on the $(1,-1)$ line would move toward the origin instead, and any rounding would push it off.

Practice

Decompose the starting state, apply the powers, and read off the long-run behaviour.

The decomposition needs the eigenvectors first, so keep that step sharp.

Videos

Watch the section on powers of a matrix, especially the point where the eigenvalue terms are separated and the small ones are discarded. That discarding is the whole long-run analysis here.

Quiz

Five items on solving an iteration with eigenvectors and classifying the origin.