Lesson 4: Applications -- Markov Chains, Matrix Powers, and Dynamical Systems
Estimated time: 45-55 minutes
Learning Objectives
- Use A^n = PD^nP^{-1} to compute matrix powers efficiently
- Define stochastic (Markov) matrices and steady-state vectors
- Apply eigenvalues to analyze discrete dynamical systems x_{k+1} = Ax_k
- Determine long-term behavior based on eigenvalue magnitudes
Computing Matrix Powers via Diagonalization
If A = PDP^{-1}, then A^2 = PDP^{-1}PDP^{-1} = PD^2P^{-1}. In general:
Matrix Power Formula: A^n = PD^nP^{-1}, where D^n = diag(lambda_1^n, lambda_2^n, ..., lambda_k^n).
Worked Example 1: Computing A^{10}
A = [1 2; 0 3]. From Lesson 3: P = [1 1; 0 1], D = [1 0; 0 3], P^{-1} = [1 -1; 0 1].
A^{10} = P * [1^{10} 0; 0 3^{10}] * P^{-1} = [1 1; 0 1][1 0; 0 59049][1 -1; 0 1].
= [1 59049; 0 59049][1 -1; 0 1] = [1, 59048; 0, 59049].
Without diagonalization, this would require multiplying the matrix 10 times!
Markov Chains
Stochastic Matrix: A square matrix where every column sums to 1 and all entries are nonneg. Each column represents transition probabilities from one state.
Markov Chain: x_{k+1} = A * x_k, where A is stochastic and x_k is a probability vector (entries sum to 1).
Worked Example 2: Weather Model
A city's weather transitions: if sunny today, 70% chance sunny tomorrow, 30% rainy. If rainy, 40% sunny tomorrow, 60% rainy.
Transition matrix: A = [0.7 0.4; 0.3 0.6]. Columns sum to 1.
If today is sunny, x_0 = (1, 0)^T.
Tomorrow: x_1 = Ax_0 = (0.7, 0.3)^T.
Day after: x_2 = Ax_1 = (0.49 + 0.12, 0.21 + 0.18) = (0.61, 0.39)^T.
Steady-State Vectors
Steady-State Vector: A probability vector q such that Aq = q. This means q is an eigenvector of A with eigenvalue lambda = 1.
For a regular stochastic matrix (some power A^k has all positive entries), a unique steady-state exists, and the system converges to it regardless of the initial state.
Worked Example 3: Finding the Steady State
A = [0.7 0.4; 0.3 0.6]. Solve (A - I)q = 0:
[-0.3 0.4; 0.3 -0.4] → [0.3 -0.4; 0 0]. So 0.3*q1 = 0.4*q2, meaning q1 = (4/3)*q2.
Normalize: q1 + q2 = 1. (4/3)*q2 + q2 = (7/3)*q2 = 1. q2 = 3/7, q1 = 4/7.
Steady state: q = (4/7, 3/7) approximately (0.571, 0.429).
Long-term: about 57.1% of days will be sunny regardless of today's weather.
Discrete Dynamical Systems
A discrete dynamical system has the form x_{k+1} = Ax_k with initial condition x_0. The solution is x_k = A^k * x_0.
Using Diagonalization: Write x_0 = c1*v1 + c2*v2 + ... + cn*vn (eigenvector decomposition). Then:
x_k = c1 * lambda_1^k * v1 + c2 * lambda_2^k * v2 + ... + cn * lambda_n^k * vn.
Worked Example 4: Population Dynamics
Two competing species with dynamics x_{k+1} = Ax_k where A = [0.5 0.3; 0.5 0.7].
Eigenvalues: lambda^2 - 1.2*lambda + 0.2 = 0. lambda = 1 and lambda = 0.2.
For lambda = 1: v1 = (3, 5)^T (after normalizing). For lambda = 0.2: v2 = (1, -1)^T.
As k grows, 0.2^k → 0. So x_k → c1 * v1. The system converges to the eigenvector for lambda = 1.
The dominant eigenvalue (largest |lambda|) determines long-term behavior.
Long-Term Behavior and Stability
Stability Criteria: For x_{k+1} = Ax_k:
- If all |lambda_i| < 1: system converges to 0 (stable, decaying)
- If any |lambda_i| > 1: system diverges (unbounded growth)
- If the largest |lambda_i| = 1: system has a stable nonzero limit
Worked Example 5: Fibonacci Connection
The Fibonacci recurrence f_{n+2} = f_{n+1} + f_n can be written as a matrix system:
[f_{n+1}; f_{n+2}] = [0 1; 1 1] * [f_n; f_{n+1}].
The eigenvalues of [0 1; 1 1] are phi = (1+sqrt(5))/2 (the golden ratio, about 1.618) and (1-sqrt(5))/2 (about -0.618).
The dominant eigenvalue phi explains why the ratio f_{n+1}/f_n converges to the golden ratio!
Check Your Understanding
1. If D = [2 0; 0 -1], what is D^5?
2. A stochastic matrix always has lambda = 1 as an eigenvalue. True or False?
3. A system x_{k+1} = Ax_k has eigenvalues 0.5 and -0.3. What happens as k goes to infinity?
4. Find the steady-state vector for A = [0.6 0.2; 0.4 0.8].
Key Takeaways
- A^n = PD^nP^{-1} makes computing large matrix powers efficient
- Markov chains: stochastic matrices model state transitions; columns sum to 1
- Steady state: eigenvector for lambda = 1, normalized to sum to 1
- Dynamical systems: the dominant eigenvalue controls long-term behavior
- |lambda| < 1 means decay; |lambda| > 1 means growth; |lambda| = 1 means persistence