High School Mathematics · Grades 10–12

30Matrices and Graphs

A matrix is a rectangular array of numbers, added and multiplied by rules designed so that matrix algebra represents the composition of linear transformations. Matrices solve linear systems, drive coupled recurrent sequences, and count walks in networks — the mathematics behind search engines and shortest-path algorithms.

30.1 Matrix algebra

Definition 30.1 (Matrix)

An $m \times n$ matrix is a table of real numbers with $m$ rows and $n$ columns: $A = (a_{ij})$ , where $a_{ij}$ is the entry in row $i$ , column $j$ . Two matrices of the same size are added entry by entry, and $\lambda A = (\lambda a_{ij})$ .

Definition 30.2 (Matrix product)

Let $A$ be $m \times n$ and $B$ be $n \times p$ . The product $AB$ is the $m \times p$ matrix whose $(i,j)$ entry is

(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}

(the “row $i$ of $A$ times column $j$ of $B$ ” rule).

Example 30.3

$\begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} 2 & 3\\ 4 & 7\end{pmatrix}$ , while $\begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 4\\ 4 & 6\end{pmatrix}$ : matrix multiplication is not commutative.

Proposition 30.4 (Rules of matrix algebra)

Whenever the sizes make the products meaningful:

(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A+B)C = AC + BC,

and the identity matrix $I_n$ (ones on the diagonal, zeros elsewhere) satisfies $I_m A = A I_n = A$ for $A$ of size $m \times n$ .

Proof. All are entry-by-entry verifications from Definition 30.2; associativity, the only nontrivial one, amounts to exchanging two finite sums: $\bigl((AB)C\bigr)_{ij} = \sum_l \left(\sum_k a_{ik}b_{kl}\right) c_{lj} = \sum_k a_{ik} \left(\sum_l b_{kl} c_{lj}\right) = \bigl(A(BC)\bigr)_{ij}$ . ∎

Definition 30.5 (Inverse)

A square matrix $A$ of size $n$ is invertible if there is a matrix $B$ with $AB = BA = I_n$ ; $B$ is then unique, written $A^{-1}$ .

Proposition 30.6 (Inverse of a $2\times2$ matrix)

Let $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ and $\det A = ad - bc$ (the determinant). Then $A$ is invertible if and only if $\det A \neq 0$ , in which case

A^{-1} = \frac{1}{ad - bc}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}.

Proof. A computation gives $A \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} = \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} A = (ad - bc) I_2$ ; if $ad - bc \neq 0$ , divide. Conversely, if $ad - bc = 0$ , the columns of $A$ are proportional, and so are the columns of $AB$ for any $B$ ; but the columns of $I_2$ are not proportional, so no $B$ can satisfy $AB = I_2$ . ∎

Method 30.7 (Linear systems)

The system $\begin{cases} ax + by = e\\ cx + dy = f \end{cases}$ is the matrix equation $AX = Y$ with $X = \begin{pmatrix} x \\ y\end{pmatrix}$ , $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ . If $\det A \neq 0$ , its unique solution is $X = A^{-1}Y$ . The same formalism handles $n$ equations in $n$ unknowns.

30.2 Matrix powers and recurrent sequences

Definition 30.8

For a square matrix $A$ and $k \in \N$ , $A^k = A \times \dots \times A$ ( $k$ factors), with $A^0 = I$ .

Method 30.9 (Diagonal-plus-nilpotent and diagonalizable cases)

Two standard ways to compute $A^k$ :

If $A = \lambda I + N$ where $N^2 = 0$ , the binomial theorem (valid here since $I$ and $N$ commute) collapses to two terms: $A^k = \lambda^k I + k \lambda^{k-1} N$ .
If one finds an invertible $P$ with $A = PDP^{-1}$ and $D$ diagonal, then $A^k = P D^k P^{-1}$ , and $D^k$ is computed entry by entry. (Finding such a $P$ systematically is the theory of diagonalization, developed at university; at this level $P$ is given.)

Example 30.10 (Coupled sequences)

Let $u_{n+1} = 3u_n + v_n$ and $v_{n+1} = u_n + 3v_n$ . Setting $X_n = \begin{pmatrix} u_n\\ v_n \end{pmatrix}$ and $A = \begin{pmatrix} 3 & 1\\ 1 & 3\end{pmatrix}$ , we get $X_{n+1} = AX_n$ , so $X_n = A^n X_0$ . The auxiliary sequences $s_n = u_n + v_n$ and $d_n = u_n - v_n$ satisfy $s_{n+1} = 4s_n$ and $d_{n+1} = 2d_n$ , so $s_n = 4^n s_0$ , $d_n = 2^n d_0$ and

u_n = \frac{4^n(u_0+v_0) + 2^n(u_0-v_0)}{2}, \qquad v_n = \frac{4^n(u_0+v_0) - 2^n(u_0-v_0)}{2}.

(Behind the scenes: $(1,1)$ and $(1,-1)$ are eigenvector directions of $A$ .)

30.3 Graphs and walks

Definition 30.11 (Graph, adjacency matrix)

A graph consists of vertices $1, 2, \dots, n$ and edges joining certain pairs of vertices (ordered pairs for a directed graph). Its adjacency matrix is the $n \times n$ matrix $M$ with $m_{ij} = 1$ if there is an edge from $i$ to $j$ , and $0$ otherwise. A walk of length $k$ from $i$ to $j$ is a sequence of $k$ consecutive edges leading from $i$ to $j$ .

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix A directed graph and its adjacency matrix (): m_ij = 1 exactly when there is an edge from i to j. — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ A directed graph and its adjacency matrix (Exercise 30.6): $m_{ij} = 1$ exactly when there is an edge from $i$ to $j$ .

Theorem 30.12 (Counting walks)

The number of walks of length $k$ from vertex $i$ to vertex $j$ is the $(i,j)$ entry of $M^k$ .

Proof. Induction on $k$ . For $k = 1$ this is the definition of $M$ . Assume the claim for $k$ . A walk of length $k+1$ from $i$ to $j$ is a walk of length $k$ from $i$ to some vertex $l$ , followed by an edge from $l$ to $j$ ; by the addition and multiplication principles, their number is

\sum_{l=1}^{n} \bigl(M^k\bigr)_{il}\, m_{lj} = \bigl(M^{k+1}\bigr)_{ij}. \qedhere

∎

Example 30.13

For the triangle graph ( $3$ vertices, all pairs joined), $M = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}$ and $M^2 = \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2\end{pmatrix}$ : from each vertex there are $2$ walks of length $2$ back to itself (via either neighbor) and $1$ to each other vertex.

30.4 Exercises

Exercise 30.1 ★

Let $A = \begin{pmatrix} 1 & 2\\ 0 & 1 \end{pmatrix}$ and $B = \begin{pmatrix} 2 & 0\\ 1 & 1 \end{pmatrix}$ . Compute $A + B$ , $AB$ , $BA$ and $A^2$ .

Solution

Solution of Exercise 30.1.

A + B = \begin{pmatrix} 3 & 2\\ 1 & 2\end{pmatrix}, \quad AB = \begin{pmatrix} 4 & 2\\ 1 & 1\end{pmatrix}, \quad BA = \begin{pmatrix} 2 & 4\\ 1 & 3\end{pmatrix}, \quad A^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix}.

Note $AB \neq BA$ .

Exercise 30.2 ★

Determine whether the following matrices are invertible, and compute the inverses when they exist:

A = \begin{pmatrix} 2 & 5\\ 1 & 3\end{pmatrix}, \qquad B = \begin{pmatrix} 3 & 6\\ 2 & 4\end{pmatrix}.

Solution

Solution of Exercise 30.2.

$\det A = 6 - 5 = 1 \neq 0$ : $A^{-1} = \begin{pmatrix} 3 & -5\\ -1 & 2 \end{pmatrix}$ . $\det B = 12 - 12 = 0$ : $B$ is not invertible.

Exercise 30.3 ★

Solve by matrix inversion the system $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$

Solution

Solution of Exercise 30.3.

The system is $AX = Y$ with $A$ as in Exercise 30.2 and $Y = \begin{pmatrix} 1\\ 2\end{pmatrix}$ :

X = A^{-1}Y = \begin{pmatrix} 3 & -5\\ -1 & 2\end{pmatrix} \begin{pmatrix} 1\\ 2\end{pmatrix} = \begin{pmatrix} -7\\ 3\end{pmatrix}: \qquad x = -7,\ y = 3 .

Exercise 30.4 ★★

Let $A = \begin{pmatrix} 2 & 1\\ 0 & 2\end{pmatrix} = 2I + N$ with $N = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$ .

Check that $N^2 = 0$ and that $I$ and $N$ commute.
Deduce $A^k$ for all $k \in \N$ and verify the formula for $k=2$ by direct computation.

Solution

Solution of Exercise 30.4.

1. $N^2 = \begin{pmatrix} 0&1\\0&0\end{pmatrix} \begin{pmatrix} 0&1\\0&0\end{pmatrix} = 0$ , and $I$ commutes with every matrix.

2. Since the two terms commute, the binomial theorem applies and all terms containing $N^2$ vanish:

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N = \begin{pmatrix} 2^k & k\,2^{k-1}\\ 0 & 2^k \end{pmatrix}.

Check for $k = 2$ : $A^2 = \begin{pmatrix} 2&1\\0&2\end{pmatrix}^2 = \begin{pmatrix} 4&4\\0&4\end{pmatrix}$ , and the formula gives $2^2 = 4$ , $2 \times 2 = 4$ . ✓

Exercise 30.5 ★★

Let $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ and $F_n$ the Fibonacci sequence ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ ). Show by induction that for $n \geq 1$ ,

A^n = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix},

and deduce the identity $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ . (Hint: determinants multiply: $\det(MN) = \det M \det N$ , which you may check for $2\times2$ matrices.)

Solution

Solution of Exercise 30.5.

Induction. For $n = 1$ : $A^1 = \begin{pmatrix} 0&1\\1&1\end{pmatrix} = \begin{pmatrix} F_0 & F_1\\ F_1 & F_2\end{pmatrix}$ . Assume the formula for $n$ ; then

A^{n+1} = A^n A = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} F_n & F_{n-1} + F_n\\ F_{n+1} & F_n + F_{n+1}\end{pmatrix} = \begin{pmatrix} F_n & F_{n+1}\\ F_{n+1} & F_{n+2}\end{pmatrix}.

Identity. For $2\times2$ matrices, expanding shows $\det(MN) = \det M \det N$ ; hence $\det(A^n) = (\det A)^n = (-1)^n$ , and $\det A^n = F_{n-1}F_{n+1} - F_n^2$ . (This is Cassini’s identity.)

Exercise 30.6 ★★

A directed graph on vertices $\{1, 2, 3\}$ has edges $1\to2$ , $2\to3$ , $3\to1$ and $1\to3$ .

Write the adjacency matrix $M$ and compute $M^2$ and $M^3$ .
How many walks of length $3$ go from $1$ to $1$ ? List them.

Solution

Solution of Exercise 30.6.

1. Ordering vertices $1, 2, 3$ :

M = \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0\end{pmatrix}, \quad M^2 = \begin{pmatrix} 1&0&1\\ 1&0&0\\ 0&1&1\end{pmatrix}, \quad M^3 = \begin{pmatrix} 1&1&1\\ 1&0&1\\ 1&0&1 \end{pmatrix}.

2. $\bigl(M^3\bigr)_{11} = 1$ : exactly one closed walk of length $3$ at vertex $1$ , namely $1 \to 2 \to 3 \to 1$ . (The walk $1 \to 3 \to 1$ has length $2$ only, and $1 \to 3$ then $3\to1$ then $1\to3$ ends at $3$ .)

Exercise 30.7 ★★

A car-sharing company moves vehicles between two cities $A$ and $B$ . Each week, $80\%$ of the cars in $A$ stay in $A$ and $20\%$ move to $B$ ; $30\%$ of the cars in $B$ move to $A$ and $70\%$ stay. Let $a_n, b_n$ be the proportions of the fleet in each city.

Write $X_{n+1} = MX_n$ with $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ and identify $M$ .
Find the equilibrium proportions (solve $MX = X$ with $a + b = 1$ ).
Show that $c_n = a_n - 0.6$ satisfies $c_{n+1} = 0.5\,c_n$ , and conclude that the fleet distribution converges to the equilibrium.

Solution

Solution of Exercise 30.7.

1. $a_{n+1} = 0.8a_n + 0.3b_n$ , $b_{n+1} = 0.2a_n + 0.7b_n$ : $M = \begin{pmatrix} 0.8 & 0.3\\ 0.2 & 0.7\end{pmatrix}$ .

2. $MX = X$ gives $0.8a + 0.3b = a$ , i.e. $0.3b = 0.2a$ , so $b = \frac23 a$ ; with $a + b = 1$ : $a = 0.6$ , $b = 0.4$ .

3. Using $b_n = 1 - a_n$ : $a_{n+1} = 0.8a_n + 0.3(1 - a_n) = 0.5a_n + 0.3$ , so

c_{n+1} = a_{n+1} - 0.6 = 0.5a_n + 0.3 - 0.6 = 0.5(a_n - 0.6) = 0.5\,c_n .

Hence $c_n = 0.5^n c_0 \to 0$ : $a_n \to 0.6$ and $b_n \to 0.4$ , whatever the initial distribution.

Exercise 30.8 ★★★

Let $A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}$ , $P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}$ .

Compute $P^{-1}$ , then $D = P^{-1}AP$ , and check that $D$ is diagonal.
Deduce a closed formula for $A^n$ and compare with Example 30.10.

Solution

Solution of Exercise 30.8.

1. $\det P = -2$ , so $P^{-1} = -\frac12\begin{pmatrix} -1 & -1\\ -1 & 1\end{pmatrix} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ . Then

AP = \begin{pmatrix} 4 & 2\\ 4 & -2 \end{pmatrix}, \qquad D = P^{-1}AP = \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} \begin{pmatrix} 4&2\\4&-2\end{pmatrix} = \begin{pmatrix} 4 & 0\\ 0 & 2\end{pmatrix}.

2. From $A = PDP^{-1}$ , an immediate induction gives $A^n = PD^nP^{-1}$ with $D^n = \begin{pmatrix} 4^n & 0\\ 0 & 2^n\end{pmatrix}$ , so

A^n = P D^n P^{-1} = \begin{pmatrix} 4^n & 2^n\\ 4^n & -2^n\end{pmatrix}\cdot \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} = \frac12\begin{pmatrix} 4^n + 2^n & 4^n - 2^n\\ 4^n - 2^n & 4^n + 2^n\end{pmatrix}.

Applying $A^n$ to $X_0 = \begin{pmatrix} u_0\\v_0\end{pmatrix}$ reproduces exactly the formulas of Example 30.10.

30.5 Problem: The matrix that knows Fibonacci (and the weather)

Problem 30.1

Weekend problem — one $2 \times 2$ matrix carries all of Fibonacci, a Markov matrix forecasts the long-run weather, and an eigenvector is worth a billion dollars

A matrix is a machine that eats a state and returns the next one — and its powers therefore hold entire futures. This problem opens with the astonishing matrix whose powers list the Fibonacci numbers (and prove their identities in one line each), then runs the weather as a Markov chain to its steady state, and closes with the eigenvector on which a search engine was built (Theorem 30.12, Method 30.9).

Part I — Fluency.

With $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ and $B = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ : compute $AB$ and $BA$ . Verdict on commutativity?
Invert $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ (Proposition 30.6) and use the inverse to solve $2x + y = 4$ , $5x + 3y = 7$ .
Let $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : compute $N^2$ , and deduce $(I + N)^n = I + nN$ for every $n$ .
The triangle graph (three vertices, all pairs joined): write its adjacency matrix $A$ , compute $A^3$ , and interpret the diagonal entries (Theorem 30.12).
For $D = \begin{pmatrix} 2 & 0\\ 0 & \frac12 \end{pmatrix}$ : give $D^n$ and its behavior as $n \to \infty$ .

Part II — The Fibonacci matrix. Let $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ and let $F_1 = F_2 = 1, F_3 = 2, \dots$ be the Fibonacci numbers of Problem 13.1.

Compute $F^2$ , $F^3$ , $F^4$ and conjecture the general form of $F^n$ in terms of Fibonacci numbers.
Prove the conjecture $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$ by induction.
Take determinants of both sides (the determinant of a product is the product of the determinants — check it on $2 \times 2$ matrices if you have never seen it): deduce Cassini’s identity $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ — the vanishing-square engine, proved in one line.
From $F^{m+n} = F^m F^n$ , read off the top-right entries and derive the addition formula

$F_{m+n} = F_{m+1} F_n + F_m F_{n-1} .$

Check it for $m = n = 3$ .
Deduce from the addition formula (induction on $k$ ) that $F_n$ divides $F_{kn}$ , and verify on $F_3 \mid F_6$ and $F_3 \mid F_9$ .
To compute $F_{100}$ , one need not multiply $100$ matrices: square repeatedly ( $F^2, F^4, F^8, \dots$ ) and combine. How many matrix multiplications suffice, and which ancient multiplication trick from the Middle School volume is this, promoted to matrices?

Part III — The weather machine. In a certain city: after a sunny day, the next is sunny with probability $0.8$ ; after a rainy day, sunny with probability $0.4$ . Encode the day’s distribution as a column $\binom{p_{\text{sun}}}{p_{\text{rain}}}$ and the evolution by

M = \begin{pmatrix} 0.8 & 0.4\\ 0.2 & 0.6 \end{pmatrix}.

Check that each column of $M$ sums to $1$ , and say why any weather machine must have this property.
Today is sunny. Compute the forecast for tomorrow and for the day after.
Find the steady state: the distribution $v$ with $Mv = v$ (and entries summing to $1$ ). What fraction of days is sunny in the long run?
Start from a rainy day, $\binom01$ , and apply $M$ four times, tracking the distance to the steady state at each step. By what factor does the gap shrink per step — and what kind of convergence is this?
PageRank in miniature: three pages, with links $A \to B$ , $A \to C$ , $B \to C$ , $C \to A$ . A random surfer follows an outgoing link uniformly at random. Write the transition matrix, find the steady state, and rank the pages.
Interpret the ranking: why does $C$ score as high as $A$ despite receiving links from fewer pages — what does the steady state actually measure? (Real PageRank adds a damping factor for dead ends and jumps; the eigenvector idea is exactly this one.)

Part IV — Diagonal dividends.

Two coupled quantities obey $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ , i.e. the matrix $A$ of Exercise 30.8. Using that exercise’s diagonalization ( $D = \operatorname{diag}(4, 2)$ ), give the closed formula for $u_n$ when $u_0 = 1$ , $v_0 = 0$ , and check it against direct computation for $n = 1, 2, 3$ .
In one or two sentences: what does diagonalization do to a coupled system — and in what sense is the Markov steady state of question 14 an eigenvector story too?
Finale — the matrix’s three faces this weekend: bookkeeping (systems and inverses), combinatorics (walks and links counted by powers), and evolution (Fibonacci, weather, the web — futures read off eigen-directions). One sentence each, plus the forward pointer: the university volumes’ linear algebra makes every one of these faces a theory.

Solution

Solution of Problem 30.1.

1. $AB = \begin{pmatrix} 2 & 1\\ 4 & 3\end{pmatrix}$ and $BA = \begin{pmatrix} 3 & 4\\ 1 & 2\end{pmatrix}$ : matrix multiplication is not commutative — $B$ swaps columns on the right, rows on the left.

2. Determinant $6 - 5 = 1$ : inverse $\begin{pmatrix} 3 & -1\\ -5 & 2\end{pmatrix}$ . Applying it to $\binom{4}{7}$ : $x = 12 - 7 = 5$ , $y = -20 + 14 = -6$ .

3. $N^2 = 0$ . Then $(I + N)^n = I + nN$ by induction: $(I + nN)(I + N) = I + (n+1)N + nN^2 = I + (n+1)N$ .

4. $A = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}$ , and $A^3$ has diagonal entries $2$ : from each vertex, exactly two closed walks of length $3$ (the triangle walked clockwise or counterclockwise) — the counting theorem in action.

5. $D^n = \begin{pmatrix} 2^n & 0\\ 0 & 2^{-n} \end{pmatrix}$ : one direction explodes, the other dies — diagonal fates are independent geometric sequences.

6. $F^2 = \begin{pmatrix} 2 & 1\\ 1 & 1\end{pmatrix}$ , $F^3 = \begin{pmatrix} 3 & 2\\ 2 & 1\end{pmatrix}$ , $F^4 = \begin{pmatrix} 5 & 3\\ 3 & 2\end{pmatrix}$ : Fibonacci everywhere; conjecture as stated.

7. If $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix}$ , then

F^{n+1} = F^n F = \begin{pmatrix} F_{n+1} + F_n & F_{n+1}\\ F_n + F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_n \end{pmatrix} :

heredity; the base case $n = 1$ is $F$ itself, using the convention $F_0 = 0$ (which extends the recurrence backwards).

8. $\det F = -1$ , so $\det(F^n) = (\det F)^n = (-1)^n$ ; and directly $\det(F^n) = F_{n+1}F_{n-1} - F_n^2$ : Cassini, one line. (The product rule for $2 \times 2$ determinants is a pleasant five-minute expansion.)

9. Top-right of $F^m F^n$ : $F_{m+1}F_n + F_m F_{n-1}$ ; top-right of $F^{m+n}$ : $F_{m+n}$ . For $m = n = 3$ : $F_4 F_3 + F_3 F_2 = 3 \times 2 + 2 \times 1 = 8 = F_6$ .

10. For $k = 1$ : trivial. If $F_n \mid F_{kn}$ , the addition formula with $m = kn$ : $F_{(k+1)n} = F_{kn+1}F_n + F_{kn}F_{n-1}$ : both terms are multiples of $F_n$ . So $F_n \mid F_{kn}$ for all $k$ : check $F_3 = 2$ divides $F_6 = 8$ and $F_9 = 34$ .

11. $F^{100} = F^{64} F^{32} F^4$ : seven squarings ( $F^2, F^4, \dots, F^{64}$ ) plus two combinations — nine multiplications instead of ninety-nine. It is the doubling-table trick of the Egyptian scribes, lifted from numbers to matrices: write $100$ in binary, multiply the doublings you need.

12. $0.8 + 0.2 = 1$ and $0.4 + 0.6 = 1$ : tomorrow must be some weather — each column is a complete probability distribution, so probabilities are conserved.

13. Tomorrow: $\binom{0.8}{0.2}$ . Day after: $M\binom{0.8}{0.2} = \binom{0.72}{0.28}$ .

14. $Mv = v$ with $v = \binom{s}{r}$ , $s + r = 1$ : $0.8s + 0.4r = s$ gives $0.4r = 0.2s$ , $s = 2r$ : $v = \binom{2/3}{1/3}$ . In the long run, two days in three are sunny — whatever today looks like.

15. From $\binom01$ : sunny components $0.4$ , $0.56$ , $0.624$ , $0.6496$ ; gaps to $\frac23$ : $0.267$ , $0.107$ , $0.043$ , $0.017$ — each step multiplies the gap by exactly $0.4$ (the machine’s second eigenvalue): geometric convergence to the steady state.

16. Columns (from $A$ , $B$ , $C$ ): $P = \begin{pmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0\end{pmatrix}$ . Steady state: $v_A = v_C$ , $v_B = \frac{v_A}{2}$ , $v_C = \frac{v_A}{2} + v_B$ ; summing to $1$ : $v = \left(\frac25, \frac15, \frac25\right)$ . Ranking: $A$ and $C$ tie for first, $B$ last.

17. $C$ receives all of $B$ ’s traffic and half of $A$ ’s, and it funnels everything back to $A$ : the steady state measures where the surfer spends time, not how many links point in — one link from a popular page outweighs several from deserted ones. That recursive weighting is precisely Google’s founding idea; damping handles spider traps and dead ends.

18. $A^n = P D^n P^{-1}$ gives $u_n = \frac{4^n + 2^n}{2}$ (and $v_n = \frac{4^n - 2^n}{2}$ ). Check: $u_1 = 3$ , $u_2 = 10$ , $u_3 = 36$ ; directly: $(1,0) \to (3,1) \to (10,6) \to (36, 28)$ : matching.

19. Diagonalization changes to coordinates in which the coupled system falls apart into independent geometric sequences — each eigenvalue runs its own race. The Markov steady state is the eigenvector of eigenvalue $1$ , and the convergence rate of question 15 is the next eigenvalue: the weather machine was an eigen-story all along.

20. Bookkeeping: a system is one matrix equation, solved by one inverse. Combinatorics: powers of the adjacency matrix count walks, links, connections. Evolution: powers of the machine carry states to their destinies, and the eigen-directions (Fibonacci’s golden direction, the weather’s steady state, the web’s ranking vector) are the destinies. Linear algebra, in the university volumes, is the science of exactly this.