Discrete Dynamical Systems

Main idea

A system $\vec x_{k+1} = A\vec x_k$ moves forward one step at a time. Split the starting state into eigenvectors and each piece just gets multiplied by its own eigenvalue every step, so the piece with the largest $|\lambda|$ ends up running the show.

\vec x_k = c_1{\htmlData{sym=0}{\lambda_1^k}}\vec v_1 + c_2\lambda_2^k\vec v_2 + \cdots

What the symbols mean

$\lambda_1^k$
Growth per step
Components with |λ| > 1 grow, |λ| < 1 shrink, λ = 1 persist.

Explanation

A discrete dynamical system is simply a rule that takes the state of something now and gives you its state one step later, applied over and over. It's "discrete" because time moves in separate steps (year 1, year 2, and so on) instead of flowing continuously, and "dynamical" just means it changes over time. That covers anything you measure in steps: populations year to year, bikes moving between stations each day, people clicking from page to page. All we're really saying in $\vec x_k = c_1\lambda_1^k\vec v_1 + c_2\lambda_2^k\vec v_2 + \cdots$ is: $\vec v_1, \vec v_2$ (the eigenvector directions), $c_1, c_2$ (how much of each direction the starting state has) and $\lambda_1^k$ (that piece gets multiplied by its eigenvalue once per step, so after $k$ steps it's been multiplied $k$ times). It's just a few pieces, each growing or shrinking at its own rate; bear with it.

Where the formula comes from. It's the diagonalization idea again. Write $\vec x_0 = c_1\vec v_1 + c_2\vec v_2$ . One step gives $A\vec x_0 = c_1\lambda_1\vec v_1 + c_2\lambda_2\vec v_2$ , because $A$ just scales each eigenvector. Another step multiplies each piece by its eigenvalue again, and so on.

Long-run behavior: if $|\lambda_1|$ is strictly the largest, then $\vec x_k \approx c_1\lambda_1^k\vec v_1$ for large $k$ . The system lines up with $\vec v_1$ and grows (or shrinks) by $\lambda_1$ per step.

A common mistake. It's tempting to think the piece with the biggest starting amount wins, because it has a head start. It isn't: what wins is the biggest $|\lambda|$ , because powers grow so fast. In the animation further down, the paths start with only $0.15$ or less of the growing direction and $1.5$ or more of the shrinking one, and every one of them still ends up running along the growing direction.

Markov chains. For a matrix whose columns are probabilities, $\lambda = 1$ is always an eigenvalue, and (typically) all others are smaller. That makes sense: each column adds to 1, so nothing is created or lost, and the total can neither blow up nor die out. Every starting distribution converges to the steady-state vector: the eigenvector for 1, scaled to sum to 1.

See it

Three starting points, each stepped forward by xₖ₊₁ = Axₖ with A = [[1, 0.3], [0.15, 0.85]]. This A has eigenvalue 1.15 along (2, 1) and 0.7 along (−1, 1), so every step the (−1, 1) part shrinks by 30% while the (2, 1) part grows by 15%. Notice all three paths bend toward the line through (2, 1) and then run along it, even though each one starts out mostly in the (−1, 1) direction. By step 15 that part is down to about half a percent of where it started (0.7¹⁵ ≈ 0.005), while the (2, 1) part has grown about 8 times. The largest eigenvalue takes over.

Worked examples

Example 1

Find the steady state of $\vec x_{k+1} = \begin{bmatrix}0.9 & 0.2\\ 0.1 & 0.8\end{bmatrix}\vec x_k$ .

1
The steady state is the eigenvector for $\lambda = 1$ , so solve $(A - I)\vec v = 0$ : $-0.1v_1 + 0.2v_2 = 0$ , so $\vec v = \binom21$ .

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Find the steady state of $\begin{bmatrix}0.9 & 0.2\\ 0.1 & 0.8\end{bmatrix}$ .

Problem 2+5 XP

What is its other eigenvalue?

Problem 3+5 XP

$\vec x_k = 3(1.2)^k\vec v_1 + 2(0.5)^k\vec v_2$ . By what factor does $\vec x_k$ grow per step in the long run?

Problem 4+5 XP

If every eigenvalue has $|\lambda| < 1$ , what happens to $\vec x_k$ ?

Problem 5+5 XP

For $x_{k+1} = 2x_k$ with $x_0 = 3$ , find $x_5$ .

Problem 6+5 XP

A bike-share system has two stations. Each day $30\%$ of the bikes at station 1 end up at station 2, and $10\%$ of those at station 2 end up at station 1. With $400$ bikes in all, how many sit at each station in the long run?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

For $\vec x_{k+1} = A\vec x_k$ with $A = \begin{bmatrix}1.2 & 0.2\\ 0.1 & 1.1\end{bmatrix}$ and $\vec x_0 = \binom12$ , find the first component of $\vec x_{10}$ without multiplying ten times.

Where it's used

Population ecology (Leslie matrices), Google's PageRank, weather Markov chains and economic input–output models all predict the future through powers of a matrix.

Will the Owl Population Survive?Lin Alg · Biology

Complex Eigenvalues Inner Product, Length and Orthogonality