Repeat a linear rule $\mathbf{x}_{k+1}=A\mathbf{x}_k$ and the eigenvalues decide the future: the dominant one sets the long-run growth rate and its eigenvector the long-run shape — for animal populations, Markov chains, web search and, with calculus, continuous systems $\mathbf{x}'=A\mathbf{x}$.
A wildlife agency counts foxes and rabbits each spring. A city tracks how many commuters take the bus, the car or the metro each month. A search engine imagines a surfer clicking from page to page, over and over. In each case the state of the system is a vector, and one step later the new state is obtained from the old one by the same matrix: $\mathbf{x}_{k+1}=A\mathbf{x}_k$. The big questions are always about the long run. Will the population explode, settle down, or die out? What fraction of commuters will use the metro next year? Which web page is the most important?
Section 7.2 gave us the tool: if $A$ is diagonalisable, $A^k$ is built from the powers $\lambda_i^k$ of its eigenvalues, and after many steps the eigenvalue of largest size wins. In this section we turn that idea into predictions, find Markov steady states as eigenvectors, learn the power method that computers use to find the dominant eigenvalue of huge matrices, and finally use the same eigenvector trick for systems that change continuously in time.
A discrete dynamical system is a sequence of vectors defined by $\mathbf{x}_{k+1}=A\mathbf{x}_k$ ($k=0,1,2,\dots$), where $A$ is a fixed $n\times n$ matrix and $\mathbf{x}_0$ is the initial state. Then $\mathbf{x}_k=A^k\mathbf{x}_0$. The sequence $\mathbf{x}_0,\mathbf{x}_1,\mathbf{x}_2,\dots$ is called a trajectory.
An eigenvalue $\lambda_1$ of $A$ is dominant if $|\lambda_1|\gt|\lambda|$ for every other eigenvalue $\lambda$ of $A$.
📐 Theorem 7.11 — Eigenvector form of the solution
Suppose $A$ has $n$ linearly independent eigenvectors $\mathbf{v}_1,\dots,\mathbf{v}_n$ with eigenvalues $\lambda_1,\dots,\lambda_n$, and write $\mathbf{x}_0=c_1\mathbf{v}_1+\dots+c_n\mathbf{v}_n$ (that is, $\mathbf{c}=P^{-1}\mathbf{x}_0$). Then
$$\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2+\dots+c_n\lambda_n^k\mathbf{v}_n .$$
If $\lambda_1$ is a dominant eigenvalue and $c_1\ne0$, then for large $k$
$$\mathbf{x}_k\approx c_1\lambda_1^k\mathbf{v}_1,\qquad\text{so}\qquad\mathbf{x}_{k+1}\approx\lambda_1\mathbf{x}_k .$$
In the long run every entry is multiplied by about $\lambda_1$ each step, and $\mathbf{x}_k$ points (up to sign) along $\mathbf{v}_1$.
The reason is the factorisation $\mathbf{x}_k=\lambda_1^k\left[c_1\mathbf{v}_1+c_2\left(\tfrac{\lambda_2}{\lambda_1}\right)^k\mathbf{v}_2+\dots\right]$: every ratio $|\lambda_i/\lambda_1|$ is less than $1$, so those terms fade away.
✏️ Example 1 — Foxes and rabbits
In a nature reserve, let $F_k$ be the number of foxes and $R_k$ the number of rabbits (in hundreds) in year $k$, with
$$\begin{aligned}F_{k+1}&=0.4F_k+0.35R_k\\R_{k+1}&=-0.2F_k+1.2R_k\end{aligned}\qquad\text{so}\qquad A=\begin{bmatrix}0.4&0.35\\-0.2&1.2\end{bmatrix}.$$
(Without rabbits, $60\%$ of the foxes would die each year; without foxes, rabbits would grow by $20\%$; each fox eats about $20$ rabbits a year.) If $\mathbf{x}_0=(16,20)$, find $\mathbf{x}_k$ and describe the long-term behaviour.
Initial state Solve $c_1(1,2)+c_2(7,2)=(16,20)$: $c_1+7c_2=16$ and $c_1+c_2=10$, so $c_2=1$, $c_1=9$. Hence $$\mathbf{x}_k=9(1.1)^k\begin{bmatrix}1\\2\end{bmatrix}+(0.5)^k\begin{bmatrix}7\\2\end{bmatrix}.$$
Long run $(0.5)^k\to0$ quickly, so $\mathbf{x}_k\approx9(1.1)^k(1,2)$: both populations grow by about $10\%$ a year, in the fixed ratio of $1$ fox to every $2$ hundred rabbits. After $10$ years, $F_{10}=9(1.1)^{10}+7(0.5)^{10}\approx23.4$ foxes and $R_{10}\approx46.7$ hundred rabbits.
Check $\mathbf{x}_1=A\mathbf{x}_0=(6.4+7,\,-3.2+24)=(13.4,\,20.8)$, and the formula gives $9.9(1,2)+0.5(7,2)=(13.4,\,20.8)$ ✓.
For a $2\times2$ matrix with real eigenvalues, the picture of all trajectories — the phase portrait — has only a few possible shapes, decided by the sizes of the eigenvalues.
📐 Theorem 7.12 — The origin as attractor, repeller or saddle
Let $A$ be a $2\times2$ matrix with real eigenvalues $\lambda_1,\lambda_2$ and independent eigenvectors $\mathbf{v}_1,\mathbf{v}_2$, and consider $\mathbf{x}_{k+1}=A\mathbf{x}_k$.
If $|\lambda_1|\lt1$ and $|\lambda_2|\lt1$, every trajectory tends to $\mathbf{0}$: the origin is an attractor.
If $|\lambda_1|\gt1$ and $|\lambda_2|\gt1$, every trajectory other than $\mathbf{0}$ moves away from the origin: it is a repeller.
If $|\lambda_1|\gt1\gt|\lambda_2|$, the origin is a saddle point: trajectories starting on the line of $\mathbf{v}_2$ tend to $\mathbf{0}$, every other trajectory is eventually pushed out along the direction of $\mathbf{v}_1$.
When the eigenvalues are complex, $\lambda=a\pm bi$, the trajectories spiral: inwards if $|\lambda|=\sqrt{a^2+b^2}\lt1$, outwards if $|\lambda|\gt1$, and round closed curves if $|\lambda|=1$.
✏️ Example 2 — Classifying the origin
Classify the origin for $\mathbf{x}_{k+1}=A\mathbf{x}_k$ and describe typical trajectories: (a) $A=\begin{bmatrix}0.7&0.1\\0.2&0.6\end{bmatrix}$; (b) $A=\begin{bmatrix}1.4&0.1\\0.2&1.3\end{bmatrix}$; (c) $A=\begin{bmatrix}1&0.2\\0.4&0.8\end{bmatrix}$.
💡 Show solution▶
(a) $\lambda^2-1.3\lambda+0.4=(\lambda-0.8)(\lambda-0.5)$, eigenvectors $(1,1)$ for $0.8$ and $(1,-2)$ for $0.5$. Both eigenvalues are less than $1$: an attractor. Because $0.5^k$ dies faster than $0.8^k$, trajectories curve in towards $\mathbf{0}$ tangent to the line through $(1,1)$.
(b) $\lambda^2-2.7\lambda+1.8=(\lambda-1.5)(\lambda-1.2)$, eigenvectors $(1,1)$ for $1.5$ and $(1,-2)$ for $1.2$. Both exceed $1$: a repeller. Trajectories leave the origin and bend towards the direction $(1,1)$, which grows faster.
(c) $\lambda^2-1.8\lambda+0.72=(\lambda-1.2)(\lambda-0.6)$, eigenvectors $(1,1)$ for $1.2$ and $(1,-2)$ for $0.6$. Since $1.2\gt1\gt0.6$: a saddle. Points on the line through $(1,-2)$ slide into the origin; all others are eventually pushed out along $\pm(1,1)$ (those starting near the $(1,-2)$ line first come close to the origin).
See it All three are presets in Interactive 1. (The fox–rabbit matrix of Example 1, with eigenvalues $1.1$ and $0.5$, is also a saddle.)
Interactive 1 — Phase Portraits of $\mathbf{x}_{k+1}=A\mathbf{x}_k$
Eight trajectories start from the hollow dots; each new dot is the previous one multiplied by $A$. The dashed lines are the eigenvector lines, labelled with their eigenvalues. Watch how the sizes of $|\lambda_1|$ and $|\lambda_2|$ decide everything: points are pulled in along directions with $|\lambda|\lt1$ and pushed out along directions with $|\lambda|\gt1$.
0
eigenvalues—
sizes $|\lambda|$—
the origin is…—
growth factor of the red trajectory—
Age-structured populations
Many species are better described by age classes than by a single number. In a Leslie model, $\mathbf{x}_k$ lists the numbers of females in each age class; the first row of the matrix holds the average number of daughters born to each class (fecundities), and the entries just below the diagonal are the survival rates from one class to the next.
✏️ Example 3 — A Leslie model
A species of fish has three age classes (0–1, 1–2 and 2–3 years). Females aged 1–2 have on average $2$ daughters a year, females aged 2–3 have $0.8$; $60\%$ of the fish in each of the first two classes survive to the next year. So
$$L=\begin{bmatrix}0&2&0.8\\0.6&0&0\\0&0.6&0\end{bmatrix}.$$
Show that $\lambda=1.2$ is an eigenvalue and that it is dominant, and describe the long-term behaviour of the population.
💡 Show solution▶
Characteristic polynomial Expanding along the first column, $$\det(L-\lambda I)=-\lambda\cdot\lambda^2-0.6\left(-2\lambda-0.48\right)=-\lambda^3+1.2\lambda+0.288 .$$ At $\lambda=1.2$: $-1.728+1.44+0.288=0$ ✓.
Factorise Dividing by $(\lambda-1.2)$: $\det(L-\lambda I)=-(\lambda-1.2)\left(\lambda^2+1.2\lambda+0.24\right)$. The other roots are $\lambda=\dfrac{-1.2\pm\sqrt{0.48}}{2}\approx-0.254$ and $-0.946$. Both have absolute value less than $1.2$, so $1.2$ is dominant.
Eigenvector $L\mathbf{v}=1.2\mathbf{v}$ gives $0.6v_1=1.2v_2$ and $0.6v_2=1.2v_3$, so $v_2=2v_3$, $v_1=2v_2=4v_3$: $\mathbf{v}_1=(4,2,1)$. Check the first row: $2\cdot2+0.8\cdot1=4.8=1.2\cdot4$ ✓.
Interpret In the long run the population grows by $20\%$ a year, and the age classes settle into the stable age distribution $\tfrac17(4,2,1)$: about $57\%$ young fish, $29\%$ in the middle class and $14\%$ old fish. Because the second eigenvalue $-0.946$ is fairly close to $1.2$ in size and negative, the approach is slow and the class sizes oscillate year to year at first (see the Leslie preset of Interactive 2).
Markov Chains and Steady States
In Section 2.4 you met Markov chains: a stochastic matrix $P$ has non-negative entries and each column adds up to $1$, and a probability vector evolves by $\mathbf{x}_{k+1}=P\mathbf{x}_k$. A steady-state vector $\mathbf{q}$ is a probability vector with $P\mathbf{q}=\mathbf{q}$. In the language of this chapter: $\mathbf{q}$ is an eigenvector of $P$ for the eigenvalue $\lambda=1$, scaled so its entries add to $1$.
📐 Theorem 7.13 — Eigenvalues of a stochastic matrix
Let $P$ be an $n\times n$ stochastic matrix.
$\lambda=1$ is an eigenvalue of $P$, and every eigenvalue satisfies $|\lambda|\le1$.
If $P$ is regular (some power $P^m$ has all entries strictly positive), then $E_1$ is one-dimensional, so there is exactly one steady-state vector $\mathbf{q}$; every other eigenvalue has $|\lambda|\lt1$; and $\mathbf{x}_k\to\mathbf{q}$ for every initial probability vector $\mathbf{x}_0$.
Why $1$ is an eigenvalue. Because each column of $P$ adds to $1$, $P^{T}\mathbf{1}=\mathbf{1}$ where $\mathbf{1}=(1,1,\dots,1)$. So $1$ is an eigenvalue of $P^{T}$, and $P$ and $P^{T}$ have the same eigenvalues (Section 7.1, Exercise III.6). When $P$ is diagonalisable, Theorem 7.11 shows the rest: $\mathbf{x}_k=c_1\mathbf{q}+c_2\lambda_2^k\mathbf{v}_2+\cdots$ with $|\lambda_i|\lt1$, so all terms except the first fade. The size of the second-largest $|\lambda|$ tells you how fast the chain forgets where it started.
✏️ Example 4 — Where do the rental cars end up?
A car-rental company has branches at the airport (A), the city centre (C) and the beach resort (B). Cars rented from one branch are returned to a branch at the end of each week according to
$$P=\begin{bmatrix}0.8&0.1&0.2\\0.1&0.7&0.2\\0.1&0.2&0.6\end{bmatrix}\qquad(\text{column }j=\text{where a car from branch }j\text{ goes; order A, C, B}).$$
Find the steady-state distribution. How should a fleet of $190$ cars be distributed in the long run?
💡 Show solution▶
Set up Solve $(P-I)\mathbf{x}=\mathbf{0}$. Multiplying by $10$ to clear decimals: $$10(P-I)=\begin{bmatrix}-2&1&2\\1&-3&2\\1&2&-4\end{bmatrix}.$$
Row reduce $$\xrightarrow{R_1\leftrightarrow R_2}\begin{bmatrix}1&-3&2\\-2&1&2\\1&2&-4\end{bmatrix}\xrightarrow{R_2\to R_2+2R_1,\ R_3\to R_3-R_1}\begin{bmatrix}1&-3&2\\0&-5&6\\0&5&-6\end{bmatrix}\xrightarrow{R_3\to R_3+R_2}\begin{bmatrix}1&-3&2\\0&-5&6\\0&0&0\end{bmatrix}.$$ So $x_2=\tfrac65x_3$ and $x_1=3x_2-2x_3=\tfrac85x_3$. Taking $x_3=5$: $\mathbf{v}=(8,6,5)$.
Normalise The entries add to $19$, so $\mathbf{q}=\left(\tfrac{8}{19},\tfrac{6}{19},\tfrac{5}{19}\right)\approx(0.421,\ 0.316,\ 0.263)$. $P$ has all entries positive, so it is regular and this steady state is reached from any start.
Fleet $190\mathbf{q}=(80,60,50)$: in the long run about $80$ cars at the airport, $60$ in the city centre and $50$ at the beach. Check: $P(80,60,50)=(64+6+10,\ 8+42+10,\ 8+12+30)=(80,60,50)$ ✓.
The Power Method
For the matrices in real applications — Google's link matrix had billions of rows — nobody solves $\det(A-\lambda I)=0$. Instead we exploit Theorem 7.11 directly: multiplying by $A$ again and again automatically turns a vector towards the dominant eigenvector. To stop the numbers overflowing, we rescale after every step.
🧭 The power method (with scaling)
Choose a starting vector $\mathbf{x}_0$ whose largest entry is $1$ (for example $(1,1,\dots,1)$).
For $k=0,1,2,\dots$: compute $A\mathbf{x}_k$; let $\mu_k$ be the entry of $A\mathbf{x}_k$ with the largest absolute value; set $\mathbf{x}_{k+1}=\dfrac{1}{\mu_k}A\mathbf{x}_k$.
Stop when $\mu_k$ and $\mathbf{x}_k$ stop changing (to the accuracy you need). Then $\mu_k\approx\lambda_1$ and $\mathbf{x}_k\approx$ an eigenvector for $\lambda_1$.
📐 Theorem 7.14 — Convergence of the power method
Suppose $A$ is diagonalisable with a strictly dominant eigenvalue $\lambda_1$ ($|\lambda_1|\gt|\lambda_2|\ge\dots\ge|\lambda_n|$), and that $\mathbf{x}_0$ has a nonzero component $c_1$ along the eigenvector $\mathbf{v}_1$. Then in the power method $\mu_k\to\lambda_1$ and $\mathbf{x}_k$ converges to an eigenvector for $\lambda_1$. The error shrinks roughly by the factor $\left|\dfrac{\lambda_2}{\lambda_1}\right|$ at each step.
✏️ Example 5 — Running the power method
Apply the power method to $A=\begin{bmatrix}6&5\\1&2\end{bmatrix}$ with $\mathbf{x}_0=(0,1)$. Compare with the exact eigenvalues.
💡 Show solution▶
Iterate
$k$
$\mathbf{x}_k$
$A\mathbf{x}_k$
$\mu_k$
0
$(0,\ 1)$
$(5,\ 2)$
$5$
1
$(1,\ 0.4)$
$(8,\ 1.8)$
$8$
2
$(1,\ 0.225)$
$(7.125,\ 1.45)$
$7.125$
3
$(1,\ 0.2035)$
$(7.0175,\ 1.4070)$
$7.0175$
4
$(1,\ 0.2005)$
$(7.0025,\ 1.4010)$
$7.0025$
5
$(1,\ 0.2001)$
$(7.0004,\ 1.4001)$
$7.0004$
The estimates settle at $\mu\approx7$ with eigenvector $\approx(1,0.2)$.
Exact $\det(A-\lambda I)=\lambda^2-8\lambda+7=(\lambda-7)(\lambda-1)$, and $A-7I=\begin{bmatrix}-1&5\\1&-5\end{bmatrix}$ gives the eigenvector $(5,1)=5(1,0.2)$ ✓.
Speed $|\lambda_2/\lambda_1|=\tfrac17$, so each step cuts the error by about $7$: the errors $0.125$, $0.0175$, $0.0025$, $0.0004$ shrink by roughly that factor.
Interactive 2 — Watching the Power Method Converge
Each dot is the estimate $\mu_k$ after one more multiplication by $A$ and rescaling; the dashed line is the true dominant eigenvalue $\lambda_1$. The ratio $|\lambda_2/\lambda_1|$ predicts the speed: close to $0$ means a few steps are enough, close to $1$ means a slow, sometimes oscillating approach.
1
current $\mathbf{x}_k$ (scaled)—
estimate $\mu_k$—
true $\lambda_1$—
error $|\mu_k-\lambda_1|$—
$|\lambda_2/\lambda_1|$—
Systems of Linear Differential Equations (uses calculus)
Some systems change continuously rather than in steps: drug concentrations in the blood and in body tissue, temperatures in connected rooms, currents in an electric circuit. Then the rule is a system of differential equations $\mathbf{x}'(t)=A\mathbf{x}(t)$, meaning $x_i'(t)=a_{i1}x_1(t)+\dots+a_{in}x_n(t)$ for each $i$. For a single equation $y'=ky$ you know the solution $y=Ce^{kt}$ from Calculus II §7.3. Eigenvectors let us reduce a whole system to such single equations.
Try $\mathbf{x}(t)=e^{\lambda t}\mathbf{v}$ with a fixed vector $\mathbf{v}$. Then $\mathbf{x}'(t)=\lambda e^{\lambda t}\mathbf{v}$ while $A\mathbf{x}(t)=e^{\lambda t}A\mathbf{v}$. These are equal for all $t$ exactly when $A\mathbf{v}=\lambda\mathbf{v}$. So each eigenpair gives a solution, and since the equation is linear, sums of solutions are solutions.
📐 Theorem 7.15 — Solving $\mathbf{x}'=A\mathbf{x}$ with eigenvectors (uses calculus)
If the $n\times n$ matrix $A$ has $n$ linearly independent eigenvectors $\mathbf{v}_1,\dots,\mathbf{v}_n$ with real eigenvalues $\lambda_1,\dots,\lambda_n$, then every solution of $\mathbf{x}'=A\mathbf{x}$ has the form
$$\mathbf{x}(t)=c_1e^{\lambda_1t}\mathbf{v}_1+c_2e^{\lambda_2t}\mathbf{v}_2+\dots+c_ne^{\lambda_nt}\mathbf{v}_n,$$
and the constants are found from $\mathbf{x}(0)=c_1\mathbf{v}_1+\dots+c_n\mathbf{v}_n$. If every $\lambda_i\lt0$, all solutions tend to $\mathbf{0}$; if some $\lambda_i\gt0$ (and its $c_i\ne0$), the solution grows without bound.
⚠️ Discrete versus continuous
For steps $\mathbf{x}_{k+1}=A\mathbf{x}_k$ the borderline is $|\lambda|=1$ (because $\lambda^k$ decays when $|\lambda|\lt1$). For $\mathbf{x}'=A\mathbf{x}$ the borderline is $\lambda=0$ (because $e^{\lambda t}$ decays when $\lambda\lt0$). An eigenvalue of $0.5$ means decay in a discrete model but growth in a continuous one. Always check which kind of system you have.
✏️ Example 6 — Two rooms cooling (uses calculus)
Two adjoining rooms are heated and then the heating is switched off. Let $x_1(t)$, $x_2(t)$ be how many degrees each room is above the outside temperature, $t$ hours later. Each room loses heat to the outside at rate $1\cdot x_i$ and exchanges heat with the other room at rate equal to the temperature difference, so
$$x_1'=-x_1+(x_2-x_1)=-2x_1+x_2,\qquad x_2'=-x_2+(x_1-x_2)=x_1-2x_2 .$$
Solve with $\mathbf{x}(0)=(4,0)$ and find when room 2 is warmest.
General solution $\mathbf{x}(t)=c_1e^{-t}(1,1)+c_2e^{-3t}(1,-1)$. At $t=0$: $c_1+c_2=4$, $c_1-c_2=0$, so $c_1=c_2=2$: $$\mathbf{x}(t)=2e^{-t}\begin{bmatrix}1\\1\end{bmatrix}+2e^{-3t}\begin{bmatrix}1\\-1\end{bmatrix},\qquad x_2(t)=2e^{-t}-2e^{-3t}.$$
Check $\mathbf{x}'=-2e^{-t}(1,1)-6e^{-3t}(1,-1)$; and $A\mathbf{x}=2e^{-t}A(1,1)+2e^{-3t}A(1,-1)=2e^{-t}(-1,-1)+2e^{-3t}(-3,3)$ — the same ✓.
Maximum $x_2'(t)=-2e^{-t}+6e^{-3t}=0\iff e^{2t}=3\iff t=\tfrac12\ln3\approx0.549$ h (about $33$ minutes). Then $e^{-t}=\tfrac{1}{\sqrt3}$ and $x_2=\tfrac{2}{\sqrt3}-\tfrac{2}{3\sqrt3}=\tfrac{4}{3\sqrt3}\approx0.770$ °C above outside. Both eigenvalues are negative, so both rooms cool towards the outside temperature; the $e^{-3t}$ “difference mode” dies fastest, after which the two rooms cool together like $2e^{-t}$.
Exercises
I
Discrete dynamical systems $\mathbf{x}_{k+1}=A\mathbf{x}_k$.
1 $A=\begin{bmatrix}0.5&0.3\\0.2&0.6\end{bmatrix}$, $\mathbf{x}_0=(5,0)$. Find $\mathbf{x}_k$ in eigenvector form and describe what happens as $k\to\infty$.
2 Classify the origin if the eigenvalues are $1.2$ and $0.9$.
3 Classify the origin if the eigenvalues are $0.95$ and $0.4$.
4 Classify the origin if the eigenvalues are $2$ and $1.5$.
5 $A=\begin{bmatrix}1&0.2\\0.4&0.8\end{bmatrix}$ (Example 2(c)), $\mathbf{x}_0=(1,4)$. Find $\mathbf{x}_k$ and its long-term growth rate and direction.
6Ecology. A two-stage model of an insect has juveniles and adults with $L=\begin{bmatrix}0&1.2\\0.4&0.8\end{bmatrix}$. Find the long-term growth rate and the stable juvenile : adult ratio.
7Predator–prey. In $A=\begin{bmatrix}0.4&0.3\\-p&1.2\end{bmatrix}$ the number $p\gt0$ measures predation. Find $p$ so that the dominant eigenvalue is exactly $1$, and describe the long-term behaviour for that $p$.
8 $A=\begin{bmatrix}0.8&-0.6\\0.6&0.8\end{bmatrix}$. Find the eigenvalues and $|\lambda|$, and describe the trajectories.
9 $A=\begin{bmatrix}0.6&-0.6\\0.6&0.6\end{bmatrix}$. Find $|\lambda|$ and describe the trajectories.
💡 Show solutions▶
1 $\lambda^2-1.1\lambda+0.24=(\lambda-0.8)(\lambda-0.3)$; $E_{0.8}$: $(1,1)$; $E_{0.3}$: $0.2x_1+0.3x_2=0$, $(3,-2)$. $c_1(1,1)+c_2(3,-2)=(5,0)$ gives $c_2=1$, $c_1=2$: $$\mathbf{x}_k=2(0.8)^k\begin{bmatrix}1\\1\end{bmatrix}+(0.3)^k\begin{bmatrix}3\\-2\end{bmatrix}\to\mathbf{0}.$$ The origin is an attractor; the trajectory approaches along the $(1,1)$ direction.
2 $1.2\gt1\gt0.9$: a saddle point.
3 Both less than $1$: an attractor (slowly, since $0.95$ is close to $1$).
4 Both greater than $1$: a repeller.
5 Eigenpairs $(1.2,(1,1))$ and $(0.6,(1,-2))$. $c_1+c_2=1$, $c_1-2c_2=4$ give $c_2=-1$, $c_1=2$: $\mathbf{x}_k=2(1.2)^k(1,1)-(0.6)^k(1,-2)$. Check $k=0$: $(2-1,\,2+2)=(1,4)$ ✓. Long run: growth by $20\%$ per step, direction $(1,1)$.
6 $\lambda^2-0.8\lambda-0.48=(\lambda-1.2)(\lambda+0.4)$, so the dominant eigenvalue is $1.2$: growth of $20\%$ per generation. $L-1.2I=\begin{bmatrix}-1.2&1.2\\0.4&-0.4\end{bmatrix}$ gives the eigenvector $(1,1)$: equal numbers of juveniles and adults.
7 $\det(A-\lambda I)=\lambda^2-1.6\lambda+0.48+0.3p$. Setting $\lambda=1$: $1-1.6+0.48+0.3p=0$, so $p=0.4$. Then the product of the eigenvalues is $0.48+0.12=0.6$, so the other is $0.6$, and $1$ is dominant. $A-I=\begin{bmatrix}-0.6&0.3\\-0.4&0.2\end{bmatrix}$ gives the eigenvector $(1,2)$: the populations level off at a fixed size in the ratio $1$ predator to $2$ prey (units as in the model).
8 $\lambda^2-1.6\lambda+1=0$, $\lambda=0.8\pm0.6i$, $|\lambda|=\sqrt{0.64+0.36}=1$. $A$ is a rotation through $\theta$ with $\cos\theta=0.8$ ($\theta\approx36.9^\circ$): every trajectory goes round a circle centred at the origin for ever.
9 $\lambda=0.6\pm0.6i$, $|\lambda|=0.6\sqrt2\approx0.849\lt1$. $A$ rotates by $45^\circ$ and shrinks by $0.849$ each step: trajectories spiral into the origin.
II
Markov chains as eigenvalue problems. (Columns of $P$ add to $1$.)
1 Find the steady-state vector of $P=\begin{bmatrix}0.7&0.4\\0.3&0.6\end{bmatrix}$ and its second eigenvalue.
2 Find the steady-state vector of $P=\begin{bmatrix}0.5&0.25\\0.5&0.75\end{bmatrix}$ and its second eigenvalue.
3Transport. Each month commuters switch between bus, car and metro according to $P=\begin{bmatrix}0.6&0.2&0.1\\0.3&0.7&0.3\\0.1&0.1&0.6\end{bmatrix}$ (order bus, car, metro). Find the long-run share of each mode.
4 Explain why every stochastic matrix has $\lambda=1$ as an eigenvalue.
5 For $P$ of part 1 and $\mathbf{x}_0=(1,0)$, find $\mathbf{x}_k$ exactly and evaluate $\mathbf{x}_3$.
6 Show that $P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ is stochastic but $\mathbf{x}_k$ does not converge for $\mathbf{x}_0=(1,0)$. Which hypothesis of Theorem 7.13 fails, and which eigenvalue causes the trouble?
Check: iterate the chain and watch it settle on your steady state
step $k$—
$\mathbf{x}_k$—
steady state $\mathbf{q}$—
💡 Show solutions▶
1 $P-I=\begin{bmatrix}-0.3&0.4\\0.3&-0.4\end{bmatrix}$ gives $3x_1=4x_2$: $\mathbf{v}=(4,3)$, so $\mathbf{q}=\left(\tfrac47,\tfrac37\right)\approx(0.571,0.429)$. The trace is $1.3=1+\lambda_2$, so $\lambda_2=0.3$.
3 $10(P-I)=\begin{bmatrix}-4&2&1\\3&-3&3\\1&1&-4\end{bmatrix}$ reduces to $x_1=1.5x_3$, $x_2=2.5x_3$: $\mathbf{v}=(3,5,2)$, sum $10$. Long run: $30\%$ bus, $50\%$ car, $20\%$ metro. Check: $P(0.3,0.5,0.2)=(0.18+0.10+0.02,\ 0.09+0.35+0.06,\ 0.03+0.05+0.12)=(0.3,0.5,0.2)$ ✓. (The other eigenvalues are $0.5$ and $0.4$.)
4 Each column of $P$ adds to $1$, so $P^{T}(1,\dots,1)=(1,\dots,1)$: $1$ is an eigenvalue of $P^{T}$, and $P$, $P^{T}$ have the same characteristic polynomial.
6 Columns are non-negative and add to $1$. But $\mathbf{x}_1=(0,1)$, $\mathbf{x}_2=(1,0)$, … alternates for ever. $P$ is not regular (its powers are $P$ and $I$, which always contain zeros), and its eigenvalues are $1$ and $-1$: the eigenvalue $-1$ has $|\lambda|=1$, so the term $(-1)^k$ never dies away.
III
The power method.
1 Perform four steps of the power method (with scaling) on $A=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ from $\mathbf{x}_0=(1,0)$. What are the dominant eigenvalue and eigenvector?
2 Perform five steps on $A=\begin{bmatrix}2&1&0\\1&2&1\\0&1&2\end{bmatrix}$ from $\mathbf{x}_0=(1,1,1)$. Compare the last estimate $\mu_4$ with the exact dominant eigenvalue $2+\sqrt2$.
3 For $A=\begin{bmatrix}4&1\\2&3\end{bmatrix}$ and $\mathbf{x}_0=(1,1)$ the power method gives the exact answer after one step. Why?
4 Run the power method on $A=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ from $\mathbf{x}_0=(1,0)$. Explain what goes wrong.
5 If $|\lambda_2/\lambda_1|=0.5$, roughly how many steps reduce the error by a factor of $1000$? How many for the matrix of Example 5?
💡 Show solutions▶
1 $A\mathbf{x}_0=(2,1)$, $\mu_0=2$, $\mathbf{x}_1=(1,0.5)$; $A\mathbf{x}_1=(2.5,2)$, $\mu_1=2.5$, $\mathbf{x}_2=(1,0.8)$; $A\mathbf{x}_2=(2.8,2.6)$, $\mu_2=2.8$, $\mathbf{x}_3=(1,0.9286)$; $A\mathbf{x}_3=(2.9286,2.8571)$, $\mu_3\approx2.9286$, $\mathbf{x}_4=(1,0.9756)$. Converging to $\lambda_1=3$ with eigenvector $(1,1)$ (the other eigenvalue is $1$, ratio $\tfrac13$).
2 $\mu_0=4$, $\mathbf{x}_1=(0.75,1,0.75)$; $\mu_1=3.5$, $\mathbf{x}_2=(0.7143,1,0.7143)$; $\mu_2\approx3.4286$, $\mathbf{x}_3=(0.7083,1,0.7083)$; $\mu_3\approx3.4167$, $\mathbf{x}_4=(0.7073,1,0.7073)$; $\mu_4\approx3.4146$, $\mathbf{x}_5=(0.7071,1,0.7071)$. Exact: $2+\sqrt2\approx3.4142$ with eigenvector $\left(\tfrac{1}{\sqrt2},1,\tfrac{1}{\sqrt2}\right)$; $\mu_4$ is already within $0.0004$.
3 $A(1,1)=(5,5)=5(1,1)$: the starting vector is already an eigenvector for the dominant eigenvalue $5$ (the other eigenvalue is $2$), so it has no component along the other eigenvector.
4 $\mathbf{x}_1=(0,1)$, $\mathbf{x}_2=(1,0)$, … and $\mu_k=1$ but the vectors flip for ever. The eigenvalues are $1$ and $-1$, of equal size, so there is no strictly dominant eigenvalue and Theorem 7.14 does not apply.
5 We need $0.5^k\le0.001$, i.e. $k\ge\dfrac{\ln1000}{\ln2}\approx9.97$: about $10$ steps. For Example 5, $\left(\tfrac17\right)^k\le0.001$ needs $7^k\ge1000$: $k=4$ (since $7^3=343$, $7^4=2401$).
IV
Systems of differential equations $\mathbf{x}'=A\mathbf{x}$ (uses calculus).
4 Verify by substitution that $\mathbf{x}(t)=e^{2t}\begin{bmatrix}1\\1\end{bmatrix}$ solves $\mathbf{x}'=\begin{bmatrix}4&-2\\1&1\end{bmatrix}\mathbf{x}$, and give the general solution.
5 For parts 2, 3 and 4, say whether all solutions tend to $\mathbf{0}$, all (nonzero) solutions grow, or the origin is a saddle.
6Pharmacology. A drug moves between the blood ($x_1$, mg) and body tissue ($x_2$, mg) according to $\mathbf{x}'=\begin{bmatrix}-0.3&0.1\\0.2&-0.2\end{bmatrix}\mathbf{x}$ ($t$ in hours; illustrative rates). A dose of $30$ mg is injected into the blood at $t=0$, so $\mathbf{x}(0)=(30,0)$. Find $\mathbf{x}(t)$, the time at which the amount in the tissue is greatest, and that greatest amount.
💡 Show solutions▶
1 Diagonal: the equations are separate, $x_1'=3x_1$, $x_2'=-2x_2$, so $\mathbf{x}(t)=\left(e^{3t},\ e^{-2t}\right)$.
2 Eigenpairs $(3,(1,1))$ and $(-1,(1,-1))$. $c_1+c_2=3$, $c_1-c_2=1$: $c_1=2$, $c_2=1$. $\mathbf{x}(t)=2e^{3t}(1,1)+e^{-t}(1,-1)$.
4 $\mathbf{x}'=2e^{2t}(1,1)$ and $A\mathbf{x}=e^{2t}A(1,1)=e^{2t}(2,2)$ ✓. With the other eigenpair $(3,(2,1))$ (Section 7.2, Example 1): $\mathbf{x}(t)=c_1e^{2t}(1,1)+c_2e^{3t}(2,1)$.
5 Part 2: eigenvalues $3\gt0\gt-1$, a saddle. Part 3: $-1,-4\lt0$, all solutions tend to $\mathbf{0}$. Part 4: $2,3\gt0$, all nonzero solutions grow.
6 $\lambda^2+0.5\lambda+0.04=(\lambda+0.1)(\lambda+0.4)$; $E_{-0.1}$: $(1,2)$; $E_{-0.4}$: $(1,-1)$. $c_1+c_2=30$, $2c_1-c_2=0$: $c_1=10$, $c_2=20$. $$\mathbf{x}(t)=10e^{-0.1t}\begin{bmatrix}1\\2\end{bmatrix}+20e^{-0.4t}\begin{bmatrix}1\\-1\end{bmatrix},\qquad x_2(t)=20e^{-0.1t}-20e^{-0.4t}.$$ $x_2'(t)=-2e^{-0.1t}+8e^{-0.4t}=0\iff e^{0.3t}=4\iff t=\dfrac{\ln4}{0.3}\approx4.62$ h. Then $e^{-0.1t}=4^{-1/3}$, $e^{-0.4t}=4^{-4/3}$, and $x_2=20\cdot4^{-1/3}\left(1-\tfrac14\right)=15\cdot4^{-1/3}\approx9.45$ mg.
🔬 Research–Teaching NexusResearch-tutored · optional, about 30 minutes
Research question. How does a search engine decide which page is most important — and why is the answer an eigenvector?
Why it matters. The PageRank idea imagines a “random surfer” who follows a random link on the current page $85\%$ of the time and jumps to a random page $15\%$ of the time. The fraction of time spent on each page in the long run is the steady state of a Markov chain — an eigenvector for $\lambda=1$ — and is computed with the power method. Similar rankings are used for scientific citations, football teams and protein networks.
What to do.
Sample web of four pages: page 1 links to pages 2 and 3; page 2 links to page 3; page 3 links to page 1; page 4 links to pages 1 and 3. Build the link matrix $M$ whose column $j$ shares $1$ equally among the pages that page $j$ links to.
Form the Google matrix $G=0.85M+\tfrac{0.15}{4}J$, where $J$ is the $4\times4$ matrix of ones. Check that $G$ is stochastic and regular.
Run the power method (with entries rescaled to add to $1$) from $\mathbf{x}_0=(0.25,0.25,0.25,0.25)$ in a spreadsheet for $30$ steps. Rank the pages.
Confirm by solving $(G-I)\mathbf{q}=\mathbf{0}$. Then add a link from page 2 to page 4 and see how the ranking changes.
Tools: Spreadsheet (matrix multiply with MMULT), or Python/GeoGebra.
Hand in: A half-page note with the matrix $G$, the PageRank vector, the ranking, and one sentence explaining why page 4 ranks last.
Going further. Build the link matrix for six pages of your university's website or for the citations between a few research papers, and compute their ranks. How sensitive is the ranking to the damping factor $0.85$?
Instructor note: $\mathbf{q}\approx(0.380,\ 0.199,\ 0.384,\ 0.0375)$, so page 3 ranks first, just ahead of page 1, then page 2; page 4 has no incoming links and receives only the random-jump share $0.15/4=0.0375$. The second-largest eigenvalue of $G$ has size at most $0.85$, so the power method converges steadily.
🧪 Self-check quiz
0/5 correct
Q1. For $\mathbf{x}_{k+1}=A\mathbf{x}_k$, $A$ has eigenvalues $1.2$ and $0.5$. The origin is
Q2. A steady-state vector of a Markov matrix $P$ is an eigenvector of $P$ for the eigenvalue
Q3. The power method (when it works) approximates
Q4. If $A\mathbf{v}=-2\mathbf{v}$, then a solution of $\mathbf{x}'=A\mathbf{x}$ is
Q5. The dominant eigenvalue of a Leslie matrix for a turtle population is $0.95$. In the long run the population