Linear Algebra

Matrix powers, dynamical systems and steady states

A matrix carries this year’s state of a system to next year’s. Where is the system after fifty years, and does it settle down, die out or blow up?

You need

DiagonalizationLinear Algebra

Where you are 5 in Eigenvalues and eigenvectors

Linear algebra6

Eigenvalues and eigenvectors5

The characteristic equation and finding eigenvalues Complex eigenvalues and rotation-scaling matrices Finding an eigenvector Diagonalization

Matrix powers, dynamical systems and steady states

Why this exists

Two mountain lakes are joined by a stream. Each year Joost, who studies the trout, finds that 75\% of the trout in the upper lake stay there and 25\% swim down, while 80\% of those in the lower lake stay and 20\% swim up. Writing u_k and \ell_k for the counts after k years,

\begin{bmatrix} u_{k+1} \\ \ell_{k+1} \end{bmatrix} = \begin{bmatrix} 0.75 & 0.2 \\ 0.25 & 0.8 \end{bmatrix}\begin{bmatrix} u_k \\ \ell_k \end{bmatrix}.

Next year is one matrix product away, and year fifty is fifty products away: \mathbf{x}_{50} = A^{50}\mathbf{x}_0. Multiplying fifty times answers one question for one start, and says nothing about why the counts behave as they do. Diagonalization made A^k easy to write. This lesson reads the long run straight off the eigenvalues: which part of the state survives, where it settles, and how fast.

Definition

A discrete dynamical system is a rule \mathbf{x}_{k+1} = A\mathbf{x}_k with A an n \times n matrix. The vector \mathbf{x}_k is the state at step k, and the sequence \mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots is the trajectory from \mathbf{x}_0. Since each step multiplies by A, \mathbf{x}_k = A^k\mathbf{x}_0.

A fixed point is a state with A\mathbf{x} = \mathbf{x}: the vector \mathbf{0}, or an eigenvector for \lambda = 1. An eigenvalue \lambda_1 is dominant when |\lambda_1| > |\lambda_i| for every other eigenvalue \lambda_i.

A square matrix is column-stochastic (a Markov matrix) when its entries are all \ge 0 and each column adds to 1. Column j then splits whatever is in place j among the places, with nothing lost or created. A steady-state vector of such a matrix is a vector \mathbf{q} with A\mathbf{q} = \mathbf{q}, entries \ge 0 and adding to 1: a split of the total, as fractions, that the matrix leaves unchanged.

Intuition

In the standard axes, A mixes the coordinates and every step looks like a fresh tangle. In a basis of eigenvectors \mathbf{v}_1, \dots, \mathbf{v}_n nothing mixes. Write \mathbf{x}_0 = c_1\mathbf{v}_1 + \dots + c_n\mathbf{v}_n, the coordinates of the start. Each step multiplies the coordinate along \mathbf{v}_i by \lambda_i, so after k steps it is c_i\lambda_i^k. Powers of a number larger than 1 in size grow, powers of a smaller one die away, and the largest power wins: after many steps the state points along the eigenvector of the dominant eigenvalue.

For the trout, the eigenvalues are 1 and 0.55. The part along the \lambda = 1 eigenvector never changes; that is the steady state. The rest is multiplied by 0.55 each year and fades. Seen in the plane of counts, the state slides along the line of fixed total toward the steady state, closing 45\% of the remaining gap every year.

Figure 1The trout counts from \mathbf{x}_0 = (2700, 900). Every state stays on the line of total 3600; the steady state \mathbf{q} lies where that line meets the eigenvector line for \lambda = 1, and the gap to it shrinks by the factor 0.55 each year, along the direction (1, -1).

Results

Eigenvector expansion. If \mathbf{v}_1, \dots, \mathbf{v}_n is a basis of eigenvectors of A with eigenvalues \lambda_1, \dots, \lambda_n, and \mathbf{x}_0 = c_1\mathbf{v}_1 + \dots + c_n\mathbf{v}_n, 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.

The dominant eigenvalue decides the long run. If in addition \lambda_1 is dominant and c_1 \neq 0, then \mathbf{x}_k / \lambda_1^k \to c_1\mathbf{v}_1. For large k, \mathbf{x}_k \approx c_1\lambda_1^k\mathbf{v}_1: the ratios between the entries approach those of \mathbf{v}_1, and each step multiplies the state by about \lambda_1.

Markov matrices. Let A be column-stochastic.

The total is kept: the entries of A\mathbf{x} add to the same number as the entries of \mathbf{x}.
1 is an eigenvalue of A.
(Stated without proof, part of the Perron-Frobenius theorem.) If every entry of A is positive, every other eigenvalue has |\lambda| < 1, there is exactly one steady-state vector \mathbf{q}, its entries are positive, and every trajectory whose entries add to T approaches T\mathbf{q}.

Two places. Every 2 \times 2 column-stochastic matrix is A = \begin{bmatrix} 1 - a & b \\ a & 1 - b \end{bmatrix} with 0 \le a, b \le 1. Its eigenvalues are 1, with eigenvector (b, a), and \lambda_2 = 1 - a - b, with eigenvector (1, -1). When 0 < a + b < 2, the steady state is \displaystyle \mathbf{q} = \frac{1}{a + b}(b, a), and a start with total T gives

\mathbf{x}_k = T\mathbf{q} + c\,\lambda_2^k\begin{bmatrix} 1 \\ -1 \end{bmatrix},

where c is the first entry of \mathbf{x}_0 - T\mathbf{q}. The gap to the steady state is multiplied by \lambda_2 every step.

Classification of the origin. Let A be 2 \times 2 with real eigenvalues \lambda_1, \lambda_2 and independent eigenvectors \mathbf{v}_1, \mathbf{v}_2, neither eigenvalue of size 1. If the origin is an attractor, every trajectory tends to \mathbf{0}. If it is a repeller, every trajectory except \mathbf{x}_0 = \mathbf{0} grows without bound. If it is a saddle with |\lambda_1| > 1 > |\lambda_2|, the trajectory tends to \mathbf{0} exactly when \mathbf{x}_0 lies on the line through \mathbf{v}_2; every other trajectory grows without bound, closer and closer in direction to the line through \mathbf{v}_1. For complex eigenvalues a \pm bi the trajectories spiral, inward when |\lambda| < 1 and outward when |\lambda| > 1 (Complex eigenvalues and rotation-scaling matrices).

Why it is true

Eigenvector expansion. A\mathbf{v}_i = \lambda_i\mathbf{v}_i gives A^k\mathbf{v}_i = \lambda_i^k\mathbf{v}_i, by applying A k times. Since A^k is linear, A^k\mathbf{x}_0 = \sum c_iA^k\mathbf{v}_i = \sum c_i\lambda_i^k\mathbf{v}_i. This is A^k = PD^kP^{-1} from Diagonalization read column by column: P^{-1}\mathbf{x}_0 is the coordinate vector (c_1, \dots, c_n), D^k scales it, and P turns it back into a vector.

Dominant eigenvalue. Divide by \lambda_1^k, which is not 0 because |\lambda_1| is larger than some other size:

\frac{\mathbf{x}_k}{\lambda_1^k} = c_1\mathbf{v}_1 + \sum_{i \ge 2} c_i\left(\frac{\lambda_i}{\lambda_1}\right)^k\mathbf{v}_i.

Each ratio \lambda_i / \lambda_1 has size below 1, so its powers tend to 0, and only c_1\mathbf{v}_1 is left.

The total is kept. The sum of the entries of a vector \mathbf{y} is \mathbf{1}^{T}\mathbf{y}. The columns of A add to 1, which says \mathbf{1}^{T}A = \mathbf{1}^{T}. So \mathbf{1}^{T}(A\mathbf{x}) = (\mathbf{1}^{T}A)\mathbf{x} = \mathbf{1}^{T}\mathbf{x}.

1 is an eigenvalue. Transposing \mathbf{1}^{T}A = \mathbf{1}^{T} gives A^{T}\mathbf{1} = \mathbf{1}, so 1 is an eigenvalue of A^{T} (the transpose). A matrix and its transpose have the same characteristic polynomial, because A^{T} - \lambda I = (A - \lambda I)^{T} and a transpose has the same determinant (Properties of determinants: row operations, products, transposes). So \det(A - I) = \det(A^{T} - I) = 0, and 1 is an eigenvalue of A. The eigenvector of A is usually not \mathbf{1}; it has to be found by solving (A - I)\mathbf{x} = \mathbf{0}.

Two places. The columns of A add to 1, so A has the form shown. Multiplying out, A(b, a) = (b - ab + ab,\ ab + a - ab), which is (b, a), and A(1, -1) = (1 - a - b,\ a - 1 + b), which is (1 - a - b)(1, -1). When 0 < a + b < 2 the two eigenvalues differ, the eigenvectors are independent, and \mathbf{q} = (b, a)/(a + b) has entries adding to 1. Write \mathbf{x}_0 = T\mathbf{q} + c(1, -1): the entries of (1, -1) add to 0, so the total T of \mathbf{x}_0 fixes the multiple of \mathbf{q}. The expansion then gives \mathbf{x}_k = T\mathbf{q} + c\lambda_2^k(1, -1). With positive entries 0 < a, b < 1, so |\lambda_2| < 1 and the gap dies out, which is the Perron-Frobenius statement proved for two places.

Classification. By the expansion, \mathbf{x}_k = c_1\lambda_1^k\mathbf{v}_1 + c_2\lambda_2^k\mathbf{v}_2. Both coordinates tend to 0 when both sizes are below 1. When both are above 1 and (c_1, c_2) \neq (0, 0), a nonzero coordinate grows without bound, and since \mathbf{v}_1, \mathbf{v}_2 are independent, so does \mathbf{x}_k. In the saddle case the \mathbf{v}_2 coordinate always dies, and the \mathbf{v}_1 coordinate grows unless c_1 = 0; when it grows, \lambda_1 is dominant and the previous result gives the direction.

Worked examples

Example 1

Day 1: The trout’s steady state

Find the eigenvalues and eigenvectors of Joost’s matrix P = \begin{bmatrix} 0.75 & 0.2 \\ 0.25 & 0.8 \end{bmatrix}, and the steady split of 3600 trout.

Solution

P is column-stochastic, so 1 is an eigenvalue. The trace is 1.55 and the determinant is 0.6 - 0.05 = 0.55, so the The characteristic equation and finding eigenvalues is \lambda^2 - 1.55\lambda + 0.55 = 0, which factors as (\lambda - 1)(\lambda - 0.55) = 0. The product of the roots is the determinant, so once 1 is known the other is 0.55.

For \lambda = 1, P - I = \begin{bmatrix} -0.25 & 0.2 \\ 0.25 & -0.2 \end{bmatrix}. Its first row says 0.25u = 0.2\ell, so \ell = 1.25u, and \mathbf{v}_1 = (4, 5) (Finding an eigenvector). For \lambda = 0.55, P - 0.55I = \begin{bmatrix} 0.2 & 0.2 \\ 0.25 & 0.25 \end{bmatrix}, so u = -\ell and \mathbf{v}_2 = (1, -1).

Scaling \mathbf{v}_1 so its entries add to 1 gives \mathbf{q} = \left(\tfrac49, \tfrac59\right). For 3600 trout the steady state is 3600\mathbf{q} = (1600, 2000). Check: 0.75 \cdot 1600 + 0.2 \cdot 2000 = 1200 + 400 = 1600. Each year 400 trout swim down and 400 swim up, so the counts stand still though the fish keep moving.

Example 2

Day 1: Closing the gap

In one spring there are \mathbf{x}_0 = (2700, 900) trout. Find \mathbf{x}_k for every k, check \mathbf{x}_1, and find the first year in which the upper count is within 10 of its steady value.

Solution

Write \mathbf{x}_0 = c_1(4, 5) + c_2(1, -1). The entries of (1, -1) add to 0, so adding the entries gives 9c_1 = 3600 and c_1 = 400, the steady state (1600, 2000) once more. The first entry then gives c_2 = 2700 - 1600 = 1100. By the expansion,

\mathbf{x}_k = \begin{bmatrix} 1600 \\ 2000 \end{bmatrix} + 1100(0.55)^k\begin{bmatrix} 1 \\ -1 \end{bmatrix}.

For k = 1: 1100 \cdot 0.55 = 605, so \mathbf{x}_1 = (2205, 1395). Directly, P\mathbf{x}_0 = (2025 + 180,\ 675 + 720) = (2205, 1395). The model gives fractional trout from the second year on; the counts are read to the nearest fish.

The upper count is off by 1100(0.55)^k. Since 0.55^7 \approx 0.01522 and 0.55^8 \approx 0.00837, the gap is about 16.7 after seven years and 9.2 after eight, so the first such year is k = 8. The second eigenvalue is the rate: every year the gap is 55\% of what it was, whatever the start.

Example 3

Day 1: Young and adult trout

Sanne follows the trout of the upper lake in two stages, young fish j_k and adults a_k. Each year every adult produces on average 1.5 young that survive the year, 40\% of the young become adults (in this simplified model the rest die within the year), and 70\% of the adults survive:

\begin{bmatrix} j_{k+1} \\ a_{k+1} \end{bmatrix} = \begin{bmatrix} 0 & 1.5 \\ 0.4 & 0.7 \end{bmatrix}\begin{bmatrix} j_k \\ a_k \end{bmatrix}.

She stocks 340 adults and no young. Describe the population after many years, and estimate \mathbf{x}_{10}.

Solution

This matrix is not column-stochastic: fish are born and die. The trace is 0.7 and the determinant is -0.6, so \lambda^2 - 0.7\lambda - 0.6 = (\lambda - 1.2)(\lambda + 0.5) = 0. For \lambda = 1.2 the first row of A - 1.2I is (-1.2, 1.5), so 1.2j = 1.5a and \mathbf{v}_1 = (5, 4). For \lambda = -0.5 it is (0.5, 1.5), so j = -3a and \mathbf{v}_2 = (3, -1).

Solve c_1(5, 4) + c_2(3, -1) = (0, 340): the second entry gives c_2 = 4c_1 - 340, and the first then gives 17c_1 = 1020, so c_1 = 60 and c_2 = -100. Hence

\mathbf{x}_k = 60(1.2)^k\begin{bmatrix} 5 \\ 4 \end{bmatrix} - 100(-0.5)^k\begin{bmatrix} 3 \\ -1 \end{bmatrix}.

At k = 1 this is (360, 288) + (150, -50) = (510, 238), matching A\mathbf{x}_0 = (1.5 \cdot 340,\ 0.7 \cdot 340).

The eigenvalue 1.2 is dominant. The second term changes sign every year, which is the population overshooting and correcting, but its size halves each time. For large k, \mathbf{x}_k \approx 60(1.2)^k(5, 4): the population grows by about 20\% a year, with young and adults in the ratio 5 : 4. At k = 10, 60(1.2)^{10} \approx 371.50, and the second term is only -\tfrac{100}{1024}(3, -1), so \mathbf{x}_{10} \approx (1857.2, 1486.1).

Example 4

Day 2: Building a saddle

Liesbeth wants a matrix A that multiplies the direction (1, 1) by 1.2 and the direction (-1, 1) by 0.5. Find A, find the trajectory from \mathbf{x}_0 = (3, -1), and describe the trajectories.

Solution

Put the eigenvectors in P = \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}, with P^{-1} = \tfrac12\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}, and the eigenvalues in D = \operatorname{diag}(1.2, 0.5). Then

\begin{aligned} A = PDP^{-1} &= \frac12\begin{bmatrix} 1.2 & -0.5 \\ 1.2 & 0.5 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} \\ &= \begin{bmatrix} 0.85 & 0.35 \\ 0.35 & 0.85 \end{bmatrix}. \end{aligned}

Check: A(1, 1) = (1.2, 1.2) and A(-1, 1) = (-0.5, 0.5).

For \mathbf{x}_0 = (3, -1), solve c_1 - c_2 = 3 and c_1 + c_2 = -1: c_1 = 1, c_2 = -2. So

\mathbf{x}_k = (1.2)^k\begin{bmatrix} 1 \\ 1 \end{bmatrix} - 2(0.5)^k\begin{bmatrix} -1 \\ 1 \end{bmatrix},

giving \mathbf{x}_1 = (2.2, 0.2) and \mathbf{x}_2 = (1.94, 0.94). Since 1.2 > 1 > 0.5, the origin is a saddle. The trajectory first moves toward the origin, while the shrinking part dominates, then turns and runs out along the line y = x. Only the starts on the line y = -x, where c_1 = 0, go to \mathbf{0}.

Figure 2Trajectories of A = \begin{bmatrix} 0.85 & 0.35 \\ 0.35 & 0.85 \end{bmatrix}. The part along (-1, 1) halves each step and the part along (1, 1) grows by 20\%, so every trajectory not on the line y = -x is pulled in, then pushed out along y = x. The origin is a saddle.

Example 5

Day 2: Three origins

Classify the origin for \mathbf{x}_{k+1} = A\mathbf{x}_k when (a) A = \begin{bmatrix} 0.5 & 0.2 \\ 0.1 & 0.6 \end{bmatrix}, (b) A = \begin{bmatrix} 2.5 & 0.5 \\ 1 & 2 \end{bmatrix}, (c) A = \begin{bmatrix} 0.7 & 1.2 \\ 1 & 0 \end{bmatrix}.

Solution

For a 2 \times 2 matrix, \lambda^2 - (\operatorname{tr} A)\lambda + \det A = 0.

(a) Trace 1.1, determinant 0.30 - 0.02 = 0.28: (\lambda - 0.7)(\lambda - 0.4) = 0. Both sizes are below 1, so the origin is an attractor; every trajectory dies out, and in the end it approaches \mathbf{0} along the eigenvector for 0.7.

(b) Trace 4.5, determinant 5 - 0.5 = 4.5: (\lambda - 3)(\lambda - 1.5) = 0. Both are above 1: a repeller.

(c) Trace 0.7, determinant -1.2: (\lambda - 1.5)(\lambda + 0.8) = 0. The sizes are 1.5 and 0.8: a saddle. A negative determinant means two real eigenvalues of opposite sign, and here the product of their sizes is 1.2, so they cannot both be below 1.

Example 6

Day 2: The flood year

After a spring flood widens the stream, each year 70\% of the upper trout swim down and 60\% of the lower trout swim up. The lakes start the year at the old steady state (1600, 2000). Describe what happens.

Solution

Here a = 0.7 and b = 0.6, so A = \begin{bmatrix} 0.3 & 0.6 \\ 0.7 & 0.4 \end{bmatrix}, \lambda_2 = 1 - 1.3 = -0.3, and \mathbf{q} = \tfrac{1}{1.3}(0.6, 0.7) = \left(\tfrac{6}{13}, \tfrac{7}{13}\right). The total is still 3600, so the new steady state is \left(\tfrac{21600}{13}, \tfrac{25200}{13}\right) \approx (1661.5, 1938.5).

The gap in the upper lake is c = 1600 - \tfrac{21600}{13} = -\tfrac{800}{13} \approx -61.5, so

\begin{aligned} \mathbf{x}_k &= \frac{1}{13}\begin{bmatrix} 21600 \\ 25200 \end{bmatrix} \\ &\quad - \frac{800}{13}(-0.3)^k\begin{bmatrix} 1 \\ -1 \end{bmatrix}. \end{aligned}

Check at k = 1: \tfrac{21600 + 240}{13} = 1680, and A\mathbf{x}_0 = (480 + 1200,\ 1120 + 800) = (1680, 1920). The negative eigenvalue makes the counts overshoot: the upper lake goes from 61.5 below its steady value to 18.5 above, then 5.5 below, and so on, settling much faster than before because 0.3 < 0.55.

Boundaries

The expansion needs a basis of eigenvectors. For \begin{bmatrix} 0.5 & 1 \\ 0 & 0.5 \end{bmatrix} there is only one eigenvector line, and A^k has the entry k(0.5)^{k-1}, which is not a combination of powers \lambda^k.
The dominant-eigenvalue statement needs c_1 \neq 0 and a strict inequality. If two eigenvalues share the largest size, as 1 and -1 do, no single direction wins.
The Perron-Frobenius statement needs positive entries. If the lakes are not connected, A = I and every split is a steady state. If every trout switches lakes every year, A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, the eigenvalues are 1 and -1, and the counts swap forever without settling.
The classification leaves out eigenvalues of size exactly 1. With \lambda = 1, as for every Markov matrix, a whole line of states is fixed, and the origin is neither attractor, repeller nor saddle.
A linear model is only a model: it gives fractional trout, and a real lake cannot hold a population that grows by 20\% a year forever.

Where this goes next

The same reading of the long run from eigenvalues runs through the rest of the subject: the spiral cases are in Complex eigenvalues and rotation-scaling matrices, and the change of basis behind every result here is Diagonalization. Markov matrices with many places model anything that moves among states while its total is kept, and for large ones the steady state is found by solving (A - I)\mathbf{q} = \mathbf{0}, not by computing powers. Systems that change continuously, \mathbf{x}'(t) = A\mathbf{x}(t), behave the same way with e^{\lambda t} in place of \lambda^k, so the dividing line moves from |\lambda| = 1 to the sign of \lambda.

Exercises

Day 1: eigenvector expansions, dominance and steady states

A matrix A has eigenvectors (1, 3) for \lambda = 2 and (1, -1) for \lambda = \tfrac12. For \mathbf{x}_0 = (3, 1), write \mathbf{x}_k, find \mathbf{x}_3, and give the long-run direction.
Find the eigenvalues and the steady-state vector of \begin{bmatrix} 0.6 & 0.1 \\ 0.4 & 0.9 \end{bmatrix}.
Find the eigenvalues and the steady-state vector of \begin{bmatrix} 0.9 & 0.3 \\ 0.1 & 0.7 \end{bmatrix}.
All 3600 of Joost’s trout start in the lower lake. Find \mathbf{x}_k, \mathbf{x}_1 and \mathbf{x}_2.
A stage model has A = \begin{bmatrix} 0 & 1.1 \\ 0.6 & 0.5 \end{bmatrix}. Find its eigenvalues and eigenvectors, the long-run growth rate, and the long-run ratio of young to adults.
For the matrix in Exercise 2 and \mathbf{x}_0 = (1, 0), find \mathbf{x}_k and the first k for which the first entry is within 0.01 of its steady value.
Find the eigenvalues and the steady-state vector of \begin{bmatrix} 0.5 & 0.25 & 0 \\ 0.5 & 0.5 & 0.5 \\ 0 & 0.25 & 0.5 \end{bmatrix}. By what factor does the distance to the steady state shrink each step, in the long run?
Find the 2 \times 2 column-stochastic matrix with steady state \left(\tfrac13, \tfrac23\right) and second eigenvalue 0.4.

Day 2: classifying the origin and the rate of approach

Classify the origin: (a) \begin{bmatrix} 0.6 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}; (b) \begin{bmatrix} 1.2 & 0.4 \\ 0.4 & 1.2 \end{bmatrix}; (c) \begin{bmatrix} 3 & 1 \\ 2 & 4 \end{bmatrix}; (d) \begin{bmatrix} 0.3 & -0.4 \\ 0.4 & 0.3 \end{bmatrix}.
Find the matrix with eigenvector (1, 0) for \lambda = 2 and eigenvector (1, 2) for \lambda = 0.5, and classify the origin.
For the matrix in Exercise 10 and \mathbf{x}_0 = (1, 4), find \mathbf{x}_k and \mathbf{x}_3. Which starting vectors give trajectories that tend to \mathbf{0}?
For which real t is the origin an attractor, a saddle, or a repeller for \begin{bmatrix} t & 0.5 \\ 0.5 & t \end{bmatrix}?
In a dry year, 90\% of the upper trout swim down and 60\% of the lower trout swim up. Find the matrix, \lambda_2 and the steady state, and describe the upper fraction from a start with every trout in the upper lake.
Sanne keeps 25\% of the upper trout swimming down each year. What fraction of the lower trout must swim up for the gap to the steady state to shrink to a tenth each year? Give the steady state.

Reasoning

Prove that if A is column-stochastic, the entries of A\mathbf{x} add to the same number as those of \mathbf{x}.
Prove that the product of two n \times n column-stochastic matrices is column-stochastic.
Let A be column-stochastic and A\mathbf{v} = \lambda\mathbf{v} with \lambda \neq 1. Prove that the entries of \mathbf{v} add to 0. Why is this the reason (1, -1) appears for every two-place matrix?
Explain why, when the origin is an attractor, the only fixed point is \mathbf{0}.
Refute with a counterexample: “if every entry of a 2 \times 2 matrix lies strictly between 0 and 1, every trajectory tends to \mathbf{0}.”
For a saddle with |\lambda_1| > 1 > |\lambda_2|, explain why a start with c_1 \neq 0 but very small still ends up far from the origin, and how the figure for the saddle example shows it.

Answers

\mathbf{x}_k = 2^k(1, 3) + 2\left(\tfrac12\right)^k(1, -1), \mathbf{x}_3 = (8.25, 23.75), direction (1, 3). From c_1 + c_2 = 3 and 3c_1 - c_2 = 1, c_1 = 1 and c_2 = 2; 2 is dominant, and the state roughly doubles each step.
1 and 0.5; \mathbf{q} = \left(\tfrac15, \tfrac45\right). Here a = 0.4, b = 0.1, so \lambda_2 = 1 - 0.5 and \mathbf{q} = \tfrac{1}{0.5}(0.1, 0.4).
1 and 0.6; \mathbf{q} = \left(\tfrac34, \tfrac14\right). Here a = 0.1, b = 0.3, \lambda_2 = 1 - 0.4, and \mathbf{q} = \tfrac{1}{0.4}(0.3, 0.1).
\mathbf{x}_k = (1600, 2000) - 1600(0.55)^k(1, -1), \mathbf{x}_1 = (720, 2880), \mathbf{x}_2 = (1116, 2484). The gap in the upper lake starts at 0 - 1600; 1600 \cdot 0.55 = 880 and 1600 \cdot 0.3025 = 484.
1.1 with (1, 1), and -0.6 with (11, -6); growth about 10\% a year; ratio 1 : 1. Trace 0.5, determinant -0.66, so (\lambda - 1.1)(\lambda + 0.6) = 0. For -0.6 the first row of A + 0.6I is (0.6, 1.1).
\mathbf{x}_k = \left(\tfrac15, \tfrac45\right) + \tfrac45(0.5)^k(1, -1); k = 7. The gap is 0.8(0.5)^k: 0.0125 at k = 6 and 0.00625 at k = 7.
1, 0.5 and 0; \mathbf{q} = \left(\tfrac14, \tfrac12, \tfrac14\right); by 0.5. (A - I)\mathbf{q} = \mathbf{0} gives q_2 = 2q_1 and q_2 = 2q_3. The trace is 1.5 and \det A = 0, so the other two eigenvalues are 0 and 0.5; after one step the \lambda = 0 part is gone.
\begin{bmatrix} 0.6 & 0.2 \\ 0.4 & 0.8 \end{bmatrix}. Need \tfrac{b}{a + b} = \tfrac13 and 1 - a - b = 0.4, so a + b = 0.6, b = 0.2, a = 0.4.
(a) Attractor: 0.9 and 0.4. (b) Saddle: 1.6 and 0.8. (c) Repeller: 5 and 2. (d) Spiral attractor: 0.3 \pm 0.4i with |\lambda| = 0.5. In (a) trace 1.3, determinant 0.36; in (c) trace 7, determinant 10.
\begin{bmatrix} 2 & -0.75 \\ 0 & 0.5 \end{bmatrix}, a saddle. With P = \begin{bmatrix} 1 & 1 \\ 0 & 2 \end{bmatrix}, PD = \begin{bmatrix} 2 & 0.5 \\ 0 & 1 \end{bmatrix} and P^{-1} = \tfrac12\begin{bmatrix} 2 & -1 \\ 0 & 1 \end{bmatrix}. Check: A(1, 2) = (0.5, 1).
\mathbf{x}_k = -2^k(1, 0) + 2(0.5)^k(1, 2), \mathbf{x}_3 = (-7.75, 0.5); the multiples of (1, 2). From c_1 + c_2 = 1, 2c_2 = 4: c_2 = 2, c_1 = -1.
Eigenvalues t + 0.5 (along (1, 1)) and t - 0.5 (along (1, -1)). Attractor for -0.5 < t < 0.5; saddle for 0.5 < t < 1.5 and for -1.5 < t < -0.5; repeller for t > 1.5 and t < -1.5. At t = \pm 0.5 and t = \pm 1.5 an eigenvalue has size 1 and the classification does not apply.
\begin{bmatrix} 0.1 & 0.6 \\ 0.9 & 0.4 \end{bmatrix}, \lambda_2 = -0.5, \mathbf{q} = \left(\tfrac25, \tfrac35\right). As fractions, \mathbf{x}_k = \mathbf{q} + \tfrac35(-0.5)^k(1, -1): the upper fraction goes 1, 0.1, 0.55, 0.325, and so on, alternately above and below \tfrac25, with the gap halving each year.
65\%; \mathbf{q} = \left(\tfrac{13}{18}, \tfrac{5}{18}\right). Need 1 - 0.25 - b = 0.1, so b = 0.65, and \mathbf{q} = \tfrac{1}{0.9}(0.65, 0.25).
The sum of the entries is \mathbf{1}^{T}A\mathbf{x}, and \mathbf{1}^{T}A = \mathbf{1}^{T} because the columns add to 1.
Column j of AB is A\mathbf{b}_j. Its entries are sums of products of nonnegative numbers, so nonnegative, and by Exercise 15 they add to the sum of the entries of \mathbf{b}_j, which is 1.
Let s = \mathbf{1}^{T}\mathbf{v}. Then \lambda s = \mathbf{1}^{T}A\mathbf{v} = \mathbf{1}^{T}\mathbf{v} = s, so (\lambda - 1)s = 0 and s = 0. In two places, the vectors whose entries add to 0 are exactly the multiples of (1, -1).
Every eigenvalue has size below 1, so 1 is not an eigenvalue and A - I is invertible; A\mathbf{x} = \mathbf{x} means (A - I)\mathbf{x} = \mathbf{0}, so \mathbf{x} = \mathbf{0}.
\begin{bmatrix} 0.6 & 0.6 \\ 0.6 & 0.6 \end{bmatrix} has eigenvalues 1.2 and 0, with (1, 1) for 1.2; the trajectory from (1, 1) is (1.2^k, 1.2^k), which grows without bound.
The \mathbf{v}_1 coordinate is c_1\lambda_1^k, and |\lambda_1|^k grows without bound, so even a tiny |c_1| is eventually multiplied past any size. In the figure the five chains start nearer the line y = -x than the line y = x, so their (1, 1) coordinates are the smaller ones; they sweep in toward the origin while the other coordinate halves, then the growing coordinate takes over and carries them out along y = x.