---
title: "Matrices and Graphs"
book: "High School Mathematics"
subject: math
language: en
chapter: 30
exercises: 8
source: https://one-course.com/books/math/2/en/chapter/30-matrices-and-graphs
---

# Chapter 30 — Matrices and Graphs

A [matrix](#def-g12-matrix-matrix) is a rectangular array of numbers, added and multiplied by rules designed so that [matrix](#def-g12-matrix-matrix) algebra represents the composition of linear transformations. Matrices solve [linear systems](https://one-course.com/books/math/2/en/chapter/7-equations-of-lines-and-linear-systems#def-g10-lines-system), drive coupled recurrent [sequences](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-sequence), 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) 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](#def-g12-matrix-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](#def-g12-matrix-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](#def-g12-matrix-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](#def-g12-matrix-product); 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](#def-g12-matrix-matrix) $A$ of size $n$ is *invertible* if there is a [matrix](#def-g12-matrix-matrix) $B$ with $AB = BA = I_n$; $B$ is then unique, written $A^{-1}$.

**Proposition 30.6 (Inverse of a 2×22\times22×2 matrix).**

Let $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ and $\det A = ad - bc$ (the *determinant*). Then $A$ is [invertible](#def-g12-matrix-inverse) 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](#def-g12-matrix-matrix) [equation](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-equation) in $n$ unknowns.

## 30.2 Matrix powers and recurrent sequences

**Definition 30.8.**

For a square [matrix](#def-g12-matrix-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](#def-g12-matrix-inverse) $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](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-sequence) $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](#def-g12-matrix-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](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-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.](https://one-course.com/images/onecourse/chapters/math-2/g12-matrix/fig-783722c7530e.svg)

*$M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ A directed [graph](#def-g12-matrix-graph) and its [adjacency matrix](#def-g12-matrix-graph) ([Exercise 30.6](#exo-g12-matrix-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](#def-g12-matrix-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 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](#def-g12-matrix-inverse), 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 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](#def-g12-matrix-inverse).

**Exercise 30.3 ★.**

Solve by [matrix](#def-g12-matrix-matrix) inversion the system $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$

**Solution of Exercise 30.3.**

The system is $AX = Y$ with $A$ as in [Exercise 30.2](#exo-g12-matrix-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}$.

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

**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](#def-g12-matrix-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](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-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](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-det) multiply: $\det(MN) = \det M \det N$, which you may check for $2\times2$ matrices.)

**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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-expand) 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](#def-g12-matrix-graph) on vertices $\{1, 2, 3\}$ has edges $1\to2$, $2\to3$, $3\to1$ and $1\to3$.

1. Write the [adjacency matrix](#def-g12-matrix-graph) $M$ and compute $M^2$ and $M^3$ .
2. How many walks of length $3$ go from $1$ to $1$ ? List them.

**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.

![](https://one-course.com/images/onecourse/chapters/math-2/g12-matrix/fig-8ee5ea63de42.svg)

1. Write $X_{n+1} = MX_n$ with $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ and identify $M$ .
2. Find the equilibrium proportions (solve $MX = X$ with $a + b = 1$ ).
3. Show that $c_n = a_n - 0.6$ satisfies $c_{n+1} = 0.5\,c_n$ , and conclude that the fleet [distribution](https://one-course.com/books/math/2/en/chapter/18-probability-and-random-variables#def-g11-prob-rv) [converges](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-limit) to the equilibrium.

**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](https://one-course.com/books/math/2/en/chapter/18-probability-and-random-variables#def-g11-prob-rv).

**Exercise 30.8 ★★★.**

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

1. Compute $P^{-1}$ , then $D = P^{-1}AP$ , and check that $D$ is diagonal.
2. Deduce a closed formula for $A^n$ and compare with [Example 30.10](#ex-g12-matrix-coupled) .

**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](#ex-g12-matrix-coupled).

## 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](#def-g12-matrix-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](#def-g12-matrix-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](#thm-g12-matrix-walks), [Method 30.9](#met-g12-matrix-powers)).

**Part I — Fluency.**

1. 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?
2. Invert $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ ( [Proposition 30.6](#prop-g12-matrix-inverse2x2) ) and use the inverse to solve $2x + y = 4$ , $5x + 3y = 7$ .
3. Let $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : compute $N^2$ , and deduce $(I + N)^n = I + nN$ for every $n$ .
4. The triangle [graph](#def-g12-matrix-graph) (three vertices, all pairs joined): write its [adjacency matrix](#def-g12-matrix-graph) $A$ , compute $A^3$ , and interpret the diagonal entries ( [Theorem 30.12](#thm-g12-matrix-walks) ).
5. 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](#def-g12-matrix-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](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#pb-g11-seq-1).

6. Compute $F^2$ , $F^3$ , $F^4$ and conjecture the general form of $F^n$ in terms of Fibonacci numbers.
7. Prove the conjecture $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}  \end{pmatrix}$ by induction.
8. Take [determinants](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-det) of both sides (the [determinant](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-det) of a product is the product of the [determinants](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-det) — 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.
9. 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$.
10. Deduce from the addition formula (induction on $k$ ) that $F_n$ [divides](https://one-course.com/books/math/2/en/chapter/29-arithmetic#def-g12-arith-divides) $F_{kn}$ , and verify on $F_3 \mid F_6$ and $F_3 \mid F_9$ .
11. To compute $F_{100}$ , one need not multiply $100$ matrices: square repeatedly ( $F^2, F^4, F^8, \dots$ ) and combine. How many [matrix](#def-g12-matrix-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](https://one-course.com/books/math/2/en/chapter/9-probability-and-sampling#def-g10-proba-distribution) $0.8$; after a rainy day, sunny with [probability](https://one-course.com/books/math/2/en/chapter/9-probability-and-sampling#def-g10-proba-distribution) $0.4$. Encode the day’s [distribution](https://one-course.com/books/math/2/en/chapter/18-probability-and-random-variables#def-g11-prob-rv) 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}.
$$

12. Check that each column of $M$ sums to $1$ , and say why any weather machine must have this property.
13. Today is sunny. Compute the forecast for tomorrow and for the day after.
14. Find the *steady state* : the [distribution](https://one-course.com/books/math/2/en/chapter/18-probability-and-random-variables#def-g11-prob-rv) $v$ with $Mv = v$ (and entries summing to $1$ ). What fraction of days is sunny in the long run?
15. 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?
16. 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](#def-g12-matrix-matrix) , find the steady state, and rank the pages.
17. 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.**

18. Two coupled quantities obey $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ , i.e. the [matrix](#def-g12-matrix-matrix) $A$ of [Exercise 30.8](#exo-g12-matrix-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$ .
19. 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?
20. Finale — the [matrix](#def-g12-matrix-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 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](#def-g12-matrix-matrix) multiplication is not commutative — $B$ swaps columns on the right, rows on the left.

**2.** [Determinant](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-det) $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](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric).

**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](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-det) 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](https://one-course.com/books/math/2/en/chapter/29-arithmetic#def-g12-arith-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](https://one-course.com/books/math/2/en/chapter/9-probability-and-sampling#def-g10-proba-distribution) [distribution](https://one-course.com/books/math/2/en/chapter/18-probability-and-random-variables#def-g11-prob-rv), 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](https://one-course.com/books/math/2/en/chapter/5-coordinate-geometry#def-g10-coordgeom-system) in which the coupled system falls apart into independent [geometric sequences](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric) — 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](#def-g12-matrix-matrix) [equation](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-equation), solved by one inverse. Combinatorics: powers of the [adjacency matrix](#def-g12-matrix-graph) 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](https://one-course.com/books/math/2/en/chapter/15-vectors-and-lines-in-the-plane#def-g11-vect-vector)) are the destinies. Linear algebra, in the university volumes, is the science of exactly this.