Chapter 25 Exercises — Diagonalization

DataField.Dev

Chapter 25 Exercises — Diagonalization

Work the tiers in order; each builds the muscle the next one assumes. ⭐ conceptual · ⭐⭐ hand computation · ⭐⭐⭐ proof (math-major) or coding · ⭐⭐⭐⭐ application. Problems marked [numpy] want code; [proof] want a rigorous argument. Throughout, "diagonalize $A$" means produce $P$, $D$, and $P^{-1}$ with $A = PDP^{-1}$, eigenvectors in the columns of $P$ and matching eigenvalues on the diagonal of $D$.

⭐ Tier 1 — Conceptual (understand the idea)

1. In one sentence each, say what $P$ and $D$ are in the factorization $A = PDP^{-1}$, and what coordinate-system story the whole factorization tells.

2. True or false, with a reason: every $n \times n$ matrix can be diagonalized.

3. State the precise condition for an $n \times n$ matrix to be diagonalizable. Then state a sufficient condition that is quicker to check.

4. A $3 \times 3$ matrix has eigenvalues $2, 2, 5$. Can you conclude it is diagonalizable? Can you conclude it is not? Explain what extra information would settle it.

5. Why is the factorization $A = PDP^{-1}$ exactly the similarity relation of Chapter 16 applied to a special basis? Name the basis.

6. Reading $A = PDP^{-1}$ right to left as three transformations, describe in words what each of $P^{-1}$, $D$, and $P$ does to a vector.

7. A matrix is called defective. What does that mean, in terms of eigenvectors, and what goes wrong when you try to build $P$?

8. Without computing, explain why a diagonal matrix is its own diagonalization (what are $P$ and $D$?).

⭐⭐ Tier 2 — Hand computation (pencil, then check with numpy)

9. Diagonalize $A = \begin{bmatrix}3 & 0 \\ 1 & 2\end{bmatrix}$. (Find eigenvalues, eigenvectors, $P$, $D$, $P^{-1}$, and confirm $PDP^{-1} = A$ by hand.)

10. Diagonalize $A = \begin{bmatrix}4 & 1 \\ 2 & 3\end{bmatrix}$ (the worked example of §25.2.2), then use $A^k = PD^kP^{-1}$ to compute $A^3$ by hand. [numpy] Check against np.linalg.matrix_power(A, 3).

11. For $A = \begin{bmatrix}2 & 1 \\ 1 & 2\end{bmatrix}$, use the diagonalization $P = \begin{bmatrix}1&-1\\1&1\end{bmatrix}$, $D = \begin{bmatrix}3&0\\0&1\end{bmatrix}$ to compute $A^4$ by hand via $PD^4P^{-1}$.

12. Show that the shear $A = \begin{bmatrix}2 & 1 \\ 0 & 2\end{bmatrix}$ is not diagonalizable: find its only eigenvalue, compute the dimension of its eigenspace, and compare algebraic and geometric multiplicity.

13. Diagonalize $A = \begin{bmatrix}1 & 4 \\ 1 & 1\end{bmatrix}$. (Eigenvalues are integers.)

14. The matrix $A = \begin{bmatrix}5 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 3\end{bmatrix}$ has a repeated eigenvalue $5$. Is it diagonalizable? Give $P$ and $D$. (Hint: it is already nearly done.)

15. Compute $A^{10}\mathbf{x}_0$ for $A = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$ and $\mathbf{x}_0 = \begin{bmatrix}1\\1\end{bmatrix}$ by recognizing it as a Fibonacci state, and state which Fibonacci numbers appear.

16. A column-stochastic matrix $P_{\text{trans}} = \begin{bmatrix}0.8 & 0.3 \\ 0.2 & 0.7\end{bmatrix}$ has eigenvalues $1$ and $0.5$. Find its steady-state vector (the $\lambda = 1$ eigenvector, normalized to sum $1$) by hand.

17. Use Binet's formula $F_n = (\varphi^n - \psi^n)/\sqrt5$ with $\varphi = \frac{1+\sqrt5}{2}$, $\psi = \frac{1-\sqrt5}{2}$ to compute $F_8$, and confirm it equals $21$.

⭐⭐⭐ Tier 3 — Proof (math-major) and coding

18. [proof] Prove that if $A = PDP^{-1}$ then $A^k = PD^kP^{-1}$ for every positive integer $k$. (Induction, or the telescoping argument of §25.4.)

19. [proof] Prove that eigenvectors corresponding to distinct eigenvalues are linearly independent. (The minimal-dependence argument of §25.3.1.)

20. [proof] Show that if $A$ is diagonalizable with $A = PDP^{-1}$, then $\det(A) = \prod_i \lambda_i$ (product of eigenvalues) and $\operatorname{tr}(A) = \sum_i \lambda_i$ (sum of eigenvalues). (Use that determinant and trace are similarity invariants — Chapter 16.)

21. [proof] Suppose $A = PDP^{-1}$ is invertible. Show $A^{-1} = PD^{-1}P^{-1}$ and that $A^{-1}$ has eigenvalues $1/\lambda_i$ with the same eigenvectors. Why does this require all $\lambda_i \neq 0$?

22. [numpy] Write diagonalize(A) that returns (P, D) with A == P @ D @ np.linalg.inv(P), using np.linalg.eig. Test it on $\begin{bmatrix}4&1\\2&3\end{bmatrix}$ and confirm the reconstruction with np.allclose. Then have it detect the defective $\begin{bmatrix}2&1\\0&2\end{bmatrix}$ by checking whether the returned P is invertible (e.g. abs(np.linalg.det(P)) > 1e-9) and raising/printing a warning if not.

23. [numpy] Write matrix_power_via_diag(A, k) using your diagonalize, raising the diagonal to the k-th power. Verify it matches np.linalg.matrix_power(A, k) for $k = 1, 2, 5, 20$ on $\begin{bmatrix}2&1\\1&2\end{bmatrix}$, and confirm the runtime does not grow with k.

24. [proof] Prove that two diagonalizable matrices $A$ and $B$ commute ($AB = BA$) if and only if they are simultaneously diagonalizable (one $P$ diagonalizes both). [Prove at least the easy direction: simultaneously diagonalizable $\Rightarrow$ commute.]

⭐⭐⭐⭐ Tier 4 — Application (put it to work)

25. [numpy] Population model. A two-stage insect population (juveniles $j$, adults $a$) evolves yearly by $\begin{bmatrix}j\\a\end{bmatrix}_{n+1} = \begin{bmatrix}0 & 4 \\ 0.5 & 0.5\end{bmatrix}\begin{bmatrix}j\\a\end{bmatrix}_n$ (adults make $4$ juveniles each; half of juveniles survive to adulthood, half of adults survive). Diagonalize the matrix, find the dominant eigenvalue (the long-run annual growth rate) and its eigenvector (the stable juvenile:adult ratio). Does the population grow or shrink? Project $20$ years from $\begin{bmatrix}100\\100\end{bmatrix}$ and confirm the ratio approaches the dominant eigenvector.

26. [numpy] Recurrence to closed form. The recurrence $T(n) = 3T(n-1) - 2T(n-2)$ with $T(0) = 0, T(1) = 1$ arises in algorithm analysis. Write its companion matrix $C = \begin{bmatrix}3 & -2 \\ 1 & 0\end{bmatrix}$, diagonalize it (eigenvalues are integers), and use the eigenvalues to argue that $T(n) = 2^n - 1$. Confirm by computing $T(0), \dots, T(8)$ both from the recurrence and from the closed form.

27. [numpy] Long-run market share. Three streaming services compete; each month customers switch according to a column-stochastic transition matrix you design (columns summing to $1$, e.g. each service retains $80\%$ and loses $10\%$ to each rival). Diagonalize it, extract the $\lambda = 1$ steady-state market shares, and find the second-largest eigenvalue — the mixing rate that controls how fast the market settles. Roughly how many months until the shares are within $1\%$ of steady state?

Hints and selected answers

#9: eigenvalues $3, 2$; eigenvectors $(1,1)$ for $\lambda=3$ and $(0,1)$ for $\lambda=2$; $P = \begin{bmatrix}1&0\\1&1\end{bmatrix}$.
#10: $A^3 = \begin{bmatrix}86 & 39 \\ 78 & 47\end{bmatrix}$.
#11: $A^4 = \begin{bmatrix}41 & 40 \\ 40 & 41\end{bmatrix}$ (since $3^4 = 81$, and entries are $(81\pm1)/2$).
#13: eigenvalues $3, -1$; eigenvectors $(2,1)$ and $(2,-1)$.
#15: $A^{10}\mathbf{x}_0 = (F_{12}, F_{11}) = (144, 89)$.
#16: steady state $(0.6, 0.4)$.
#26: companion eigenvalues are $2$ and $1$; the general solution is $T(n) = c_1 2^n + c_2 \cdot 1^n$, and $T(0)=0, T(1)=1$ give $c_1 = 1, c_2 = -1$, hence $T(n) = 2^n - 1$.