University Mathematics — Year 1 · Bachelor Year 1

21Matrices

A matrix is a linear map written in coordinates. This chapter sets up the dictionary — composition becomes matrix product, bijectivity becomes invertibility, change of basis becomes conjugation — and the algorithmic side: row operations, computation of ranks and inverses. First met in the High School volume, matrices are now grounded in the theory of Chapters 18, 19 and 20.

21.1 Matrices and linear maps

Definition 21.1

$\mathcal{M}_{n,p}(K)$ is the vector space of $n \times p$ arrays $A = (a_{ij})$ of scalars ( $i$ : row, $j$ : column), of dimension $np$ (basis: the matrices $E_{ij}$ with a single $1$ ). Given bases $\mathcal{B} = (e_1, \dots, e_p)$ of $E$ and $\mathcal{C}$ of $F$ ( $\dim F = n$ ), the matrix of $u \in \mathcal{L}(E, F)$ is the array whose $j$ -th column lists the coordinates of $u(e_j)$ in $\mathcal{C}$ :

\operatorname{Mat}_{\mathcal{B},\mathcal{C}}(u) = (a_{ij}), \qquad u(e_j) = \sum_{i=1}^{n} a_{ij}\, f_i .

The map $u \mapsto \operatorname{Mat}_{\mathcal{B},\mathcal{C}}(u)$ is an isomorphism from $\mathcal{L}(E, F)$ onto $\mathcal{M}_{n,p}(K)$ (Proposition 20.2: a linear map is exactly a choice of images of the $e_j$ ).

Example 21.2 (The derivative, as a matrix)

Let $D(P) = P'$ on $\R_3[X]$ . In the monomial basis $(1, X, X^2, X^3)$ : $D(1) = 0$ , $D(X) = 1$ , $D(X^2) = 2X$ , $D(X^3) = 3X^2$ , so

\operatorname{Mat}(D) = \begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 3\\ 0 & 0 & 0 & 0 \end{pmatrix}.

In the divided basis $\bigl(1,\ X,\ \frac{X^2}2,\ \frac{X^3}6\bigr)$ , each basis vector maps to the previous one ( $D\bigl(\frac{X^k}{k!}\bigr) = \frac{X^{k-1}}{(k-1)!}$ ), and the matrix becomes the pure shift: ones on the superdiagonal, zeros elsewhere. Two morals: the matrix belongs to the pair (map, basis), not to the map alone; and a good basis makes structure visible at a glance — the shift form shows instantly that $D^4 = 0$ on $\R_3[X]$ , each power of the matrix pushing its diagonal of ones one step further out.

Definition 21.3 (Product)

For $A \in \mathcal{M}_{n,p}$ and $B \in \mathcal{M}_{p,q}$ :

(AB)_{ik} = \sum_{j=1}^{p} a_{ij}\, b_{jk} \qquad (1 \leq i \leq n,\ 1 \leq k \leq q).

This is precisely the matrix of the composition: $\operatorname{Mat}(v \circ u) = \operatorname{Mat}(v)\, \operatorname{Mat}(u)$ (bases matching in the middle). Similarly, if $X$ is the column of coordinates of $x$ , the column of $u(x)$ is $AX$ .

Proof of the composition formula.

v(u(e_k)) = v\Bigl(\sum_j b_{jk} f_j\Bigr) = \sum_j b_{jk}\, v(f_j) = \sum_j b_{jk} \sum_i a_{ij}\, g_i = \sum_i \Bigl(\sum_j a_{ij} b_{jk}\Bigr) g_i . \qedhere

∎

Proposition 21.4 (The algebra $\mathcal{M}_n(K)$ )

Square matrices $\mathcal{M}_n(K)$ form a (non-commutative for $n \geq 2$ ) ring, with identity $I_n$ ; its group of units is the general linear group $GL_n(K)$ , corresponding to bijective endomorphisms. For $A, B \in \mathcal{M}_n(K)$ :

AB = I_n \implies A \in GL_n(K) \text{ and } B = A^{-1}

(one-sided inverses are two-sided, by Corollary 20.9).

Proof. Ring axioms transport from $\mathcal{L}(E)$ through the isomorphism of Definition 21.1: it converts composition into product and sum into sum, so associativity, distributivity and the role of $I_n$ are inherited from the corresponding facts about maps, with no entrywise verification. Non-commutativity: $E_{12}E_{21} = E_{11} \neq E_{22} = E_{21}E_{12}$ . If $AB = I_n$ : the endomorphism $a$ of $A$ satisfies $a \circ b = \mathrm{id}$ , so $a$ is surjective ( $x = a(b(x))$ exhibits a preimage of every $x$ ), hence bijective in finite dimension (Corollary 20.9); composing $a \circ b = \mathrm{id}$ with $a^{-1}$ on the left gives $b = a^{-1}$ , and then $b\circ a = \mathrm{id}$ too: the one-sided inverse was two-sided all along — a strictly finite-dimensional favor. ∎

Definition 21.5 (Transpose; trace)

The transpose of $A = (a_{ij}) \in \mathcal{M}_{n,p}$ is $A^{\mathsf T} = (a_{ji}) \in \mathcal{M}_{p,n}$ ; it satisfies $(AB)^{\mathsf T} = B^{\mathsf T} A^{\mathsf T}$ and $(A^{\mathsf T})^{\mathsf T} = A$ . The trace of a square matrix is $\operatorname{tr} A = \sum_i a_{ii}$ ; it is linear, and

\operatorname{tr}(AB) = \operatorname{tr}(BA) \qquad (A \in \mathcal{M}_{n,p},\ B \in \mathcal{M}_{p,n}).

Proof of the trace identity. $\operatorname{tr}(AB) = \sum_i \sum_j a_{ij} b_{ji}$ and $\operatorname{tr}(BA) = \sum_j \sum_i b_{ji} a_{ij}$ : the same double sum. ∎

Example 21.6 (The trace at work)

The projection of Chapter 20 onto $\operatorname{Vect}(1,1)$ along $\operatorname{Vect}(0,1)$ , $p(x, y) = (x, x)$ , has matrix $A = \begin{pmatrix} 1 & 0\\ 1 & 0\end{pmatrix}$ in the canonical basis: indeed $A^2 = A$ , and

\operatorname{tr} A = 1 = \operatorname{rk} A ,

illustrating Exercise 21.8: for idempotents the trace counts the dimension of the image, whatever slanted basis the matrix is written in. The invariance mechanism is the identity $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ :

\operatorname{tr}\bigl(P^{-1}(AP)\bigr) = \operatorname{tr}\bigl((AP)P^{-1}\bigr) = \operatorname{tr} A ,

so all matrices similar to $A$ share its trace — the first numerical invariant of an endomorphism, to be joined by the determinant in Chapter 22 (the pair $(s, p)$ of the weekend problem below).

Example 21.7 (Symmetric plus antisymmetric)

Call $A$ symmetric when $A^{\mathsf T} = A$ , antisymmetric when $A^{\mathsf T} = -A$ . Every square matrix splits uniquely as one plus the other:

A = \underbrace{\frac{A + A^{\mathsf T}}{2}}_{\text{symmetric}} + \underbrace{\frac{A - A^{\mathsf T}}{2}}_{\text{antisymmetric}},

and a matrix that is both is zero ( $A = -A$ ): the two sets are supplementary subspaces of $\mathcal{M}_n(K)$ — the exact analogue of the even/odd split of functions (Example 18.11), with transposition playing the role of $x \mapsto -x$ . Dimensions: a symmetric matrix is free on and above the diagonal, an antisymmetric one strictly above (zero diagonal):

\frac{n(n+1)}{2} + \frac{n(n-1)}{2} = n^2 ,

and the count balancing is Grassmann’s confirmation of directness. For $n = 2$ : $\begin{pmatrix} 1 & 5\\ 1 & 2\end{pmatrix} = \begin{pmatrix} 1 & 3\\ 3 & 2\end{pmatrix} + \begin{pmatrix} 0 & 2\\ -2 & 0\end{pmatrix}$ . Symmetric matrices return as the second-derivative data of Chapter 25 (the Monge triple $r, s, t$ ), and the symmetric-orthogonal ones are classified in Exercise 23.12.

21.2 Change of basis

Definition 21.8

Let $\mathcal{B}, \mathcal{B}'$ be bases of $E$ . The change of basis matrix $P = P_{\mathcal{B}\to\mathcal{B}'}$ has for columns the coordinates of the new basis vectors in the old basis. It is invertible, $P^{-1} = P_{\mathcal{B}'\to\mathcal{B}}$ , and coordinates transform by $X = PX'$ (old $=$ $P\,\cdot$ new).

Example 21.9 (Reading the change-of-basis matrix)

In $\R^2$ , from the canonical $\mathcal B$ to $\mathcal B' = \bigl((1,1), (1,-1)\bigr)$ :

P = P_{\mathcal B\to\mathcal B'} = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}

(new vectors written in old coordinates, column by column). The vector of old coordinates $X = (3, 1)^{\mathsf T}$ has new coordinates $X' = P^{-1}X = \frac12(3 + 1,\ 3 - 1)^{\mathsf T} = (2, 1)^{\mathsf T}$ : indeed $2(1,1) + 1(1,-1) = (3,1)$ . Mind the direction — the matrix $P$ is built from the new basis but converts new to old coordinates ( $X = PX'$ ); passing from old to new costs the inverse. Writing the sanity check $2(1,1) + (1,-1) = (3,1)$ after every conversion catches the inverted- $P$ error, which is the most common mistake of the chapter.

Theorem 21.10 (Change of basis for a map)

Let $u \in \mathcal{L}(E)$ with matrix $A$ in $\mathcal{B}$ and $A'$ in $\mathcal{B}'$ , and $P = P_{\mathcal{B}\to\mathcal{B}'}$ . Then

A' = P^{-1} A\, P .

Two matrices related this way are similar. (For $u \colon E \to F$ with two pairs of bases, the formula is $A' = Q^{-1} A P$ — equivalent matrices.)

Proof. For any $x$ : $X = PX'$ and the image satisfies $Y = AX$ , $Y = PY'$ . So $PY' = APX'$ , i.e. $Y' = (P^{-1}AP)X'$ for all $X'$ : the matrix of $u$ in the new basis is $P^{-1}AP$ (take for $X'$ the canonical columns). ∎

Example 21.11 (A good basis makes a map transparent)

Let $u(x, y) = (y, x)$ (swap), with matrix $A = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ in the canonical basis. In the basis $\mathcal B' = \bigl((1,1), (1,-1)\bigr)$ :

P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}, \qquad P^{-1} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}, \qquad P^{-1} A P = \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}.

No matrix product was really needed: $u$ fixes $(1,1)$ and reverses $(1,-1)$ , so in $\mathcal B'$ its matrix must be $\operatorname{diag}(1, -1)$ — the swap is the reflection across the line $y = x$ . Finding, for a given endomorphism, a basis in which its matrix becomes diagonal is the central problem of the Year 2 volume (reduction theory); the weekend problem below shows how far polynomial identities alone already go.

Example 21.12 (Change of basis, run in reverse)

The projection onto $F = \operatorname{Vect}(1,1)$ along $G = \operatorname{Vect}(1,-1)$ has, in the adapted basis $\mathcal B' = \bigl((1,1),(1,-1)\bigr)$ , the transparent matrix $A' = \operatorname{diag}(1, 0)$ . To get its canonical-basis matrix, run Theorem 21.10 backwards, $A = P A' P^{-1}$ :

P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}, \quad P^{-1} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}, \quad A = P\begin{pmatrix} 1 & 0\\ 0 & 0\end{pmatrix}P^{-1} = \frac12\begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}.

Check: $A^2 = A$ (idempotent), $\operatorname{tr} A = 1 = \operatorname{rk} A$ , and $A\binom{1}{1} = \binom11$ , $A\binom{1}{-1} = 0$ , as prescribed. This reverse direction — design the matrix in the good basis, then conjugate back — is how rotation, reflection and projection matrices are actually produced in practice.

Theorem 21.13 (Rank normal form)

The rank of a matrix (the rank of its columns, equivalently of the associated linear map) is the only invariant of equivalence: every $A \in \mathcal{M}_{n,p}$ of rank $r$ is equivalent to

J_r = \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix},

and $\operatorname{rk}(A^{\mathsf T}) = \operatorname{rk}(A)$ : row rank equals column rank.

Proof. Let $u \colon E \to F$ have rank $r$ . Choose a supplementary $S$ of $\ker u$ ( $\dim S = r$ , Theorem 20.7) with basis $(e_1, \dots, e_r)$ , completed by a basis of $\ker u$ into a basis of $E$ ; the images $f_i = u(e_i)$ , $i \leq r$ , form a basis of $\operatorname{im} u$ (the restriction is an isomorphism), completed into a basis of $F$ . In these bases the matrix of $u$ is exactly $J_r$ . So $A = Q J_r P^{-1}$ for invertible $P, Q$ .

Transposing: $A^{\mathsf T} = (P^{-1})^{\mathsf T} J_r^{\mathsf T} Q^{\mathsf T}$ with $J_r^{\mathsf T}$ of the same form (rank $r$ ) and the outer factors invertible (transpose of invertible is invertible, from $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ applied to $AA^{-1} = I$ ): $\operatorname{rk} A^{\mathsf T} = r$ . ∎

21.3 Row operations

Method 21.14 (Gaussian elimination on matrices)

The three elementary row operations — swap two rows, multiply a row by $\lambda \neq 0$ , add a multiple of a row to another — do not change the rank (each is left multiplication by an invertible matrix). Algorithm: create a pivot (leftmost nonzero entry), clear its column below, move to the next row and column; the number of pivots of the resulting echelon form is the rank.

Inverse computation: run the algorithm on the block $(A \mid I_n)$ until the left block becomes $I_n$ (possible iff $A$ is invertible); the right block is then $A^{-1}$ — indeed the product of the elementary matrices used equals $A^{-1}$ .

Example 21.15

$A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ : reduce $(A \mid I_2)$ :

\begin{pmatrix} 1 & 2 & 1 & 0\\ 3 & 4 & 0 & 1 \end{pmatrix} \to \begin{pmatrix} 1 & 2 & 1 & 0\\ 0 & -2 & -3 & 1 \end{pmatrix} \to \begin{pmatrix} 1 & 0 & -2 & 1\\ 0 & 1 & \tfrac32 & -\tfrac12 \end{pmatrix},

(operations: $L_2 \leftarrow L_2 - 3L_1$ ; then $L_1 \leftarrow L_1 + L_2$ , $L_2 \leftarrow -\frac12 L_2$ ). So $A^{-1} = \begin{pmatrix} -2 & 1 \\ \tfrac32 & -\tfrac12\end{pmatrix}$ . Check: $AA^{-1} = I_2$ .

Example 21.16 (Rank with a parameter, by rows alone)

For $m \in \R$ , the rank of $M_m = \begin{pmatrix} 1 & 1 & m\\ 1 & m & 1\\ m & 1 & 1\end{pmatrix}$ . Reduce: $L_2 \leftarrow L_2 - L_1$ and $L_3 \leftarrow L_3 - mL_1$ give the rows

(1,\ 1,\ m), \qquad (0,\ m - 1,\ 1 - m), \qquad (0,\ 1 - m,\ 1 - m^2).

Case $m = 1$ : the last two rows vanish — one pivot, $\operatorname{rk} M_1 = 1$ (all three original rows were equal). Case $m \neq 1$ : scale $L_2$ by $\frac1{m-1}$ and $L_3$ by $\frac1{1-m}$ to get $(0, 1, -1)$ and $(0, 1, 1 + m)$ , then $L_3 \leftarrow L_3 - L_2 = (0, 0, m + 2)$ . If $m = -2$ : two pivots, rank $2$ ; otherwise three pivots, rank $3$ . Summary:

\operatorname{rk} M_m = \begin{cases} 1 & m = 1,\\ 2 & m = -2,\\ 3 & \text{otherwise}. \end{cases}

The same thresholds will drop out of one determinant computation in Chapter 22 (the polynomial $-(m+2)(m-1)^2$ of Exercise 22.7) — but note what elimination gives that the determinant does not: the value of the rank in the degenerate cases, not just the fact that it dropped.

Example 21.17 (Computing powers)

$A = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix} = I + N$ with $N = E_{12}$ , $N^2 = 0$ . Since $I$ and $N$ commute, the binomial theorem (Proposition 7.20) truncates:

A^k = I + kN = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \qquad (k \in \N, \text{ and } k \in \Z \text{ using } A^{-1} = I - N).

Method 21.18 (Computing $A^n$ : the three routes)

Binomial route: if $A = \lambda I + N$ with $N$ nilpotent, the binomial theorem truncates (Example 21.17, Exercise 21.5); it applies because $\lambda I$ commutes with everything.
Polynomial route: find a polynomial identity satisfied by $A$ (in dimension $2$ , always $A^2 = sA - pI$ ) and reduce $X^n$ modulo it; the weekend problem below builds this route completely.
Similarity route: find an invertible $P$ with $P^{-1}AP = D$ simple (diagonal, or shift), compute $D^n$ , and undo: $A^n = P D^n P^{-1}$ (Theorem 21.10, Example 21.11); the systematic search for such $P$ is Year 2’s reduction theory.

Whatever the route, check the result on $n = 0, 1, 2$ : three cheap tests that catch nearly every slip.

Remark 21.19 (Common pitfalls: the price of non-commutativity)

Every identity of scalar algebra whose proof reorders factors dies in $\mathcal{M}_n(K)$ , $n \geq 2$ . Squares: $(A + B)^2 = A^2 + AB + BA + B^2$ , and the middle collapses to $2AB$ only if $AB = BA$ (Exercise 21.1). Powers of products: $(AB)^k$ is $ABAB\cdots$ , not $A^kB^k$ . Zero divisors: $E_{12}E_{12} = 0$ with $E_{12} \neq 0$ ; consequently no cancellation: $AB = AC$ implies $B = C$ only when $A$ is invertible (multiply by $A^{-1}$ — on the correct side). Traces: $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ always, but $\operatorname{tr}(AB) \neq \operatorname{tr}A\operatorname{tr}B$ in general (take $A = B = I_2$ : $2 \neq 4$ ), and $\operatorname{tr}(ABC) = \operatorname{tr}(BCA)$ (cyclic) while $\operatorname{tr}(ACB)$ may differ. Transposes reverse: $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ — forgetting the reversal is the most common error in orthogonality computations (Chapter 23). When in doubt, test any claimed identity on $E_{12}$ and $E_{21}$ : the smallest non-commuting pair refutes most false formulas in one line.

Remark 21.20 (Where the dictionary goes)

The matrix dictionary is used on every remaining page of this volume: Chapter 22 attaches to each square matrix a single number deciding invertibility, and solves $AX = B$ systematically; Chapter 23 singles out the matrices preserving lengths (orthogonal matrices); and in Chapter 25, the second-order behavior of a function of two variables is a symmetric $2 \times 2$ matrix. The trace, introduced above almost in passing, becomes a powerful invariant: Exercises 21.6 and 21.8 give a first taste, and the Year 2 volume builds eigenvalue theory on it. The weekend problem develops the other workhorse: polynomial identities satisfied by a matrix, which turn the computation of $A^n$ into a two-term linear recurrence.

Remark 21.21 (Perspectives inside Book 3)

Three matrix families introduced here have appointments later in this volume. Symmetric matrices (Example 21.7) carry the second-order data of functions of two variables: the Monge test of Chapter 25 is a statement about the sign behavior of a symmetric $2\times2$ matrix, and its determinant $rt - s^2$ is computed by Chapter 22’s machinery. Orthogonal matrices ( $A^{\mathsf T}A = I$ ) are the isometries of Chapter 23, where the transpose finally acquires its geometric meaning: it is the algebraic shadow of the inner product. Invertible matrices meet their practical test in Chapter 22 — one number, $\det A \neq 0$ — closing the search this chapter began with row reduction. Trace and determinant then travel as the invariant pair $(s, p)$ of the weekend problem, all the way to the eigenvalue theory of Year 2.

21.4 Exercises

Exercise 21.1 ★

Let $A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}$ . Compute $AB$ , $BA$ , $A^2 - B^2$ and $(A+B)(A-B)$ ; explain why the last two differ.

Solution

Solution of Exercise 21.1.

AB = \begin{pmatrix} 2 & 1\\ 1 & 0\end{pmatrix}, \quad BA = \begin{pmatrix} 0 & 1\\ 1 & 2\end{pmatrix}, \quad A^2 - B^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix} - I = \begin{pmatrix} 0 & 4\\ 0 & 0\end{pmatrix},

(A+B)(A-B) = A^2 - AB + BA - B^2 = \begin{pmatrix} 0 & 4\\ 0 & 0\end{pmatrix} + \begin{pmatrix} -2 & 0\\ 0 & 2 \end{pmatrix} = \begin{pmatrix} -2 & 4\\ 0 & 2\end{pmatrix}.

They differ by $BA - AB \neq 0$ : the identity $(a+b)(a-b) = a^2 - b^2$ requires commutativity, which fails here.

Exercise 21.2 ★

Compute the rank of

M = \begin{pmatrix} 1 & 2 & 3\\ 2 & 4 & 6\\ 1 & 1 & 1 \end{pmatrix}, \qquad N = \begin{pmatrix} 1 & 1 & 0 & 2\\ 0 & 1 & 1 & 1\\ 1 & 2 & 1 & 3 \end{pmatrix}.

Solution

Solution of Exercise 21.2.

$M$ : $L_2 \leftarrow L_2 - 2L_1$ kills the second row; $L_3 \leftarrow L_3 - L_1$ gives $(0, -1, -2)$ . Two pivots: $\operatorname{rk} M = 2$ .

$N$ : $L_3 \leftarrow L_3 - L_1$ gives $(0,1,1,1) = L_2$ ; then $L_3 \leftarrow L_3 - L_2 = 0$ . Two pivots: $\operatorname{rk} N = 2$ .

Exercise 21.3 ★

Invert, by row reduction, $A = \begin{pmatrix} 1 & 0 & 1\\ 2 & 1 & 1\\ 1 & 1 & 1 \end{pmatrix}$ , and check on one product.

Solution

Solution of Exercise 21.3.

Reducing $(A \mid I_3)$ : $L_2 \leftarrow L_2 - 2L_1$ , $L_3 \leftarrow L_3 - L_1$ :

\begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & -1 & -2 & 1 & 0\\ 0 & 1 & 0 & -1 & 0 & 1 \end{pmatrix} \xrightarrow{L_3 \leftarrow L_3 - L_2} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & -1 & -2 & 1 & 0\\ 0 & 0 & 1 & 1 & -1 & 1 \end{pmatrix},

then $L_1 \leftarrow L_1 - L_3$ , $L_2 \leftarrow L_2 + L_3$ :

A^{-1} = \begin{pmatrix} 0 & 1 & -1\\ -1 & 0 & 1\\ 1 & -1 & 1 \end{pmatrix}.

Check: first row of $A$ times first column of $A^{-1}$ : $1 \cdot 0 + 0\cdot(-1) + 1\cdot 1 = 1$ ; times second column: $1 - 0 - 1 = 0$ ; times third: $-1 + 0 + 1 = 0$ .

Exercise 21.4 ★

Write the matrix, in the canonical basis of $\R_2[X]$ , of the endomorphism $u(P) = P(X + 1)$ . Explain, without computation, why it is invertible, and give the matrix of $u^{-1}$ .

Solution

Solution of Exercise 21.4.

$u(1) = 1$ , $u(X) = X + 1$ , $u(X^2) = X^2 + 2X + 1$ : columns of coordinates in $(1, X, X^2)$ give

M = \begin{pmatrix} 1 & 1 & 1\\ 0 & 1 & 2\\ 0 & 0 & 1 \end{pmatrix}.

$u$ is invertible because it has the obvious inverse $P \mapsto P(X - 1)$ (composition of substitutions). Its matrix is obtained the same way from $u^{-1}(X^k) = (X-1)^k$ :

M^{-1} = \begin{pmatrix} 1 & -1 & 1\\ 0 & 1 & -2\\ 0 & 0 & 1 \end{pmatrix}.

Exercise 21.5 ★★

Let $A = \begin{pmatrix} 2 & 1 \\ 0 & 2\end{pmatrix}$ . Write $A = 2I + N$ , compute $N^2$ , and deduce $A^k$ for all $k \in \N$ by the binomial theorem.

Solution

Solution of Exercise 21.5.

$N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ , $N^2 = 0$ . Since $2I$ and $N$ commute, the binomial expansion truncates after two terms:

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 $k = 2$ : $A^2 = \begin{pmatrix}4 & 4\\ 0 & 4\end{pmatrix}$ , correct by direct product.)

Exercise 21.6 ★★

Prove that there are no matrices $A, B \in \mathcal{M}_n(K)$ (with $K = \R$ or $\C$ ) such that $AB - BA = I_n$ . (Take traces.)

Solution

Solution of Exercise 21.6.

Traces: $\operatorname{tr}(AB - BA) = \operatorname{tr}(AB) - \operatorname{tr}(BA) = 0$ (Definition 21.5), while $\operatorname{tr}(I_n) = n \neq 0$ in $\R$ or $\C$ . No solution. (On infinite-dimensional spaces the identity is realizable — differentiation and multiplication by $x$ satisfy it — precisely because no trace exists there.)

Exercise 21.7 ★★

A matrix $A$ is nilpotent when $A^m = 0$ for some $m$ . Prove that $I - A$ is then invertible, with

(I - A)^{-1} = I + A + A^2 + \dots + A^{m-1} .

Application: invert $\begin{pmatrix} 1 & 2 & 3\\ 0 & 1 & 2\\ 0 & 0 & 1\end{pmatrix}$ .

Solution

Solution of Exercise 21.7.

Telescoping product, all powers of $A$ commuting:

(I - A)(I + A + \dots + A^{m-1}) = I - A^m = I ,

and Proposition 21.4 upgrades the one-sided inverse. For the application: the given matrix is $I + N$ with

N = \begin{pmatrix} 0 & 2 & 3\\ 0 & 0 & 2\\ 0&0&0 \end{pmatrix}, \quad N^2 = \begin{pmatrix} 0&0&4\\ 0&0&0\\ 0&0&0\end{pmatrix}, \quad N^3 = 0 ,

so, replacing $A$ by $-N$ in the formula:

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

Exercise 21.8 ★★

Let $A \in \mathcal{M}_n(\R)$ satisfy $A^2 = A$ (idempotent). Prove that $\operatorname{tr} A = \operatorname{rk} A$ . (Interpret $A$ as a projection and choose an adapted basis; Theorem 21.10 says the trace is basis-independent since $\operatorname{tr}(P^{-1}MP) = \operatorname{tr} M$ .)

Solution

Solution of Exercise 21.8.

$A^2 = A$ : the endomorphism $a$ is a projection (Theorem 20.15), $E = \operatorname{im} a \oplus \ker a$ with $\dim\operatorname{im} a = r = \operatorname{rk} A$ . In a basis adapted to this decomposition ( $r$ vectors of the image, then a basis of the kernel), the matrix of $a$ is $\begin{pmatrix} I_r & 0\\ 0 & 0\end{pmatrix}$ , of trace $r$ . The trace is invariant under change of basis: $\operatorname{tr}(P^{-1}MP) = \operatorname{tr}(MPP^{-1}) = \operatorname{tr} M$ by the cyclic identity. Hence $\operatorname{tr} A = r = \operatorname{rk} A$ .

Exercise 21.9 ★★★

Let $J \in \mathcal{M}_n(\R)$ be the all-ones matrix. Compute $J^2$ , and deduce, for $a, b \in \R$ , the condition of invertibility of $M = aI + bJ$ together with $M^{-1}$ (look for an inverse of the same form $\alpha I + \beta J$ ).

Solution

Solution of Exercise 21.9.

$J^2 = nJ$ (each entry of $J^2$ sums $n$ ones). Seek $M^{-1} = \alpha I + \beta J$ :

(aI + bJ)(\alpha I + \beta J) = a\alpha\, I + (a\beta + b\alpha + nb\beta)\, J .

This equals $I$ iff $a\alpha = 1$ and $a\beta + b\alpha + nb\beta = 0$ , i.e. $\alpha = \frac1a$ and $\beta(a + nb) = -\frac ba$ . If $a \neq 0$ and $a + nb \neq 0$ :

M^{-1} = \frac 1a I - \frac{b}{a(a + nb)}\, J .

Conversely, if $a = 0$ : $M = bJ$ has rank $\leq 1 < n$ (for $n \geq 2$ ): not invertible ( $n = 1$ is the scalar case). If $a + nb = 0$ : the vector $v = (1, \dots, 1)^{\mathsf T}$ satisfies $Mv = (a + nb)v = 0$ with $v \neq 0$ : not invertible. So $M \in GL_n \iff a \neq 0$ and $a + nb \neq 0$ .

Exercise 21.10 ★★★

(Rank inequalities) For $A, B \in \mathcal{M}_n(K)$ , prove

\operatorname{rk}(A + B) \leq \operatorname{rk} A + \operatorname{rk} B, \qquad \operatorname{rk}(AB) \geq \operatorname{rk} A + \operatorname{rk} B - n .

(For the second — Sylvester’s inequality — apply rank–nullity to the restriction of the map of $A$ to $\operatorname{im} B$ .)

Solution

Solution of Exercise 21.10.

Sum: $\operatorname{im}(A + B) \subseteq \operatorname{im} A + \operatorname{im} B$ (each $(A+B)x = Ax + Bx$ ), and Grassmann bounds the dimension of a sum by the sum of dimensions.

Sylvester: let $a$ be the map of $A$ restricted to $V = \operatorname{im} B$ (dimension $\operatorname{rk} B$ ). Its image is $\operatorname{im}(AB)$ ( $a(Bx) = ABx$ ), and rank–nullity in $V$ :

\operatorname{rk} B = \dim\ker(a_{|V}) + \operatorname{rk}(AB) .

Now $\ker(a_{|V}) \subseteq \ker A$ , of dimension $n - \operatorname{rk} A$ : so

\operatorname{rk}(AB) \geq \operatorname{rk} B - (n - \operatorname{rk} A) = \operatorname{rk} A + \operatorname{rk} B - n . \qedhere

Exercise 21.11 ★★

Let $D = \operatorname{diag}(d_1, \dots, d_n)$ with the $d_i$ pairwise distinct.

Prove that a matrix $A$ commutes with $D$ if and only if $A$ is diagonal. (Compare the $(i,j)$ entries of $AD$ and $DA$ .)
Deduce the center of $\mathcal{M}_n(K)$ : the matrices commuting with every matrix are exactly the scalar matrices $\lambda I_n$ . (Test against $D$ , then against the matrices $E_{ij}$ .)

Solution

Solution of Exercise 21.11.

Entrywise, $(AD)_{ij} = a_{ij}\,d_j$ and $(DA)_{ij} = d_i\,a_{ij}$ . So $AD = DA$ iff $a_{ij}(d_j - d_i) = 0$ for all $i, j$ ; when $i \neq j$ the factor $d_j - d_i$ is nonzero, forcing $a_{ij} = 0$ : $A$ is diagonal. Conversely diagonal matrices commute with each other.
If $A$ commutes with every matrix, it commutes with $\operatorname{diag}(1, 2, \dots, n)$ , so $A = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ by (1). Then $A E_{ij} = \lambda_i E_{ij}$ (only row $i$ of $E_{ij}$ survives) while $E_{ij} A = \lambda_j E_{ij}$ : commuting with $E_{ij}$ forces $\lambda_i = \lambda_j$ . Hence $A = \lambda I_n$ ; and scalar matrices do commute with everything. The center of $\mathcal{M}_n(K)$ is $K\,I_n$ .

Exercise 21.12 ★★★

(Rank-one matrices) Let $A \in \mathcal{M}_n(K)$ , $A \neq 0$ .

Prove that $\operatorname{rk} A = 1$ if and only if $A = CL$ for a nonzero column $C \in \mathcal{M}_{n,1}$ and a nonzero row $L \in \mathcal{M}_{1,n}$ .
For such an $A$ , prove $A^2 = (\operatorname{tr} A)\,A$ ; deduce that a rank-one matrix is nilpotent if and only if its trace is zero.
If $\operatorname{tr} A \neq -1$ , prove that $I_n + A$ is invertible with

$(I_n + A)^{-1} = I_n - \frac{1}{1 + \operatorname{tr} A}\,A ,$

and that $I_n + A$ is not invertible when $\operatorname{tr} A = -1$ . (Find a vector killed by $I_n + A$ .)

Solution

Solution of Exercise 21.12.

If $\operatorname{rk} A = 1$ : the image of $A$ is a line $\operatorname{Vect}(C)$ , $C \neq 0$ , so the $j$ -th column of $A$ is $\ell_j\,C$ for scalars $\ell_j$ (not all zero), i.e. $A = C L$ with $L = (\ell_1, \dots, \ell_n) \neq 0$ . Conversely if $A = CL \neq 0$ , all columns are multiples of $C$ : rank $1$ .
$A^2 = C\,(L C)\,L$ , and $LC$ is the scalar $\sum_i \ell_i c_i = \operatorname{tr}(CL) = \operatorname{tr} A$ . So $A^2 = (\operatorname{tr} A)\,A$ , hence by induction $A^m = (\operatorname{tr} A)^{m-1} A$ . If $\operatorname{tr} A \neq 0$ , no power vanishes; if $\operatorname{tr} A = 0$ , then $A^2 = 0$ : a rank-one matrix is nilpotent iff its trace is zero.
With $t = \operatorname{tr} A \neq -1$ :

$(I_n + A)\Bigl(I_n - \frac{A}{1 + t}\Bigr) = I_n + A - \frac{A + A^2}{1 + t} = I_n + A - \frac{(1 + t)A}{1 + t} = I_n ,$

using $A^2 = tA$ . If $t = -1$ : $(I_n + A)A = A + A^2 = A - A = 0$ with $A \neq 0$ , so $I_n + A$ kills every (nonzero) column of $A$ : not injective, not invertible.

21.5 Problem: powers of a matrix by polynomial division

Problem 21.1

Computing $A^{100}$ entry by entry is hopeless; computing it through a polynomial identity satisfied by $A$ is three lines. This problem builds the method from scratch: euclidean division of $X^n$ , the identity $A^2 - sA + pI = 0$ verified by every $2 \times 2$ matrix (the Cayley–Hamilton theorem in dimension $2$ ), and the dictionary between matrix powers and linear recurrences — with the Fibonacci numbers as running example.

Part I — The remainder calculus. Fix $s, p \in K$ and $D = X^2 - sX + p$ .

Justify that for each $n \in \N$ there are unique $Q_n \in K[X]$ and $(a_n, b_n) \in K^2$ with

$X^n = Q_n\,D + a_n X + b_n ,$

and compute $(a_0, b_0)$ and $(a_1, b_1)$ .
Multiplying by $X$ and dividing again, establish the recurrences

$a_{n+1} = s\,a_n + b_n, \qquad b_{n+1} = -p\,a_n ,$

and deduce $a_{n+2} = s\,a_{n+1} - p\,a_n$ : the coefficient sequence obeys the linear recurrence attached to $D$ .
Suppose $D$ has two distinct roots $\lambda \neq \mu$ . Evaluating the division identity, prove

$a_n = \frac{\lambda^n - \mu^n}{\lambda - \mu}, \qquad b_n = \frac{\lambda\mu^n - \mu\lambda^n}{\lambda - \mu} .$
Suppose $D = (X - \lambda)^2$ . Using the derivative of the division identity, prove $a_n = n\lambda^{n-1}$ and $b_n = (1 - n)\lambda^{n}$ .
Show that substituting a fixed matrix $M \in \mathcal{M}_k(K)$ into polynomials respects sums and products: $(PQ)(M) = P(M)\,Q(M)$ . Deduce that if $D(M) = 0$ , then

$M^n = a_n\,M + b_n\,I \qquad (n \in \N).$

Part II — Dimension 2: trace, determinant number, Cayley–Hamilton. For $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ set $s = a + d = \operatorname{tr} A$ and $p = ad - bc$ (the number that Chapter 22 will name the determinant).

Verify by direct computation the Cayley–Hamilton identity in dimension $2$ :

$A^2 - s\,A + p\,I_2 = 0 .$
Prove by direct expansion that $p$ is multiplicative: with obvious notation, $p(AB) = p(A)\,p(B)$ . Then show: $A$ is invertible if and only if $p \neq 0$ , in which case

$A^{-1} = \frac1p\,\bigl(s\,I_2 - A\bigr).$
Let $A = \begin{pmatrix} 1 & 1\\ 0 & 2\end{pmatrix}$ . Compute $s$ , $p$ , the roots of $D$ , and deduce a closed formula for $A^n$ ; check it against a direct computation of $A^2$ .
Let $A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ . Show that $D$ has a double root and compute $A^n$ ; check at $n = 2$ .
Let $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ and define the Fibonacci numbers by $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ . Prove

$F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix} \quad (n \geq 1),$

deduce Binet’s formula $F_n = \dfrac{\varphi^n - \psi^n}{\sqrt5}$ where $\varphi = \frac{1 + \sqrt5}2$ , $\psi = \frac{1 - \sqrt5}2$ , and, using question 7, Cassini’s identity $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ .

Part III — Linear recurrences, structurally. Fix $s, p \in K$ with $p \neq 0$ , and let $E_D$ be the set of sequences with $u_{n+2} = s\,u_{n+1} - p\,u_n$ for all $n$ .

Show that $E_D$ is a vector space of dimension $2$ (adapt Exercise 19.10).
Show that the sequence $(a_n)$ of Part I is the element of $E_D$ with initial values $0, 1$ , and that every $u \in E_D$ satisfies

$u_n = u_1\,a_n + u_0\,b_n \qquad (n \in \N),$

with $(b_n)$ as in Part I: the division remainders solve all recurrences at once.
If $\lambda \neq \mu$ are the roots of $D$ , show that $\bigl((\lambda^n), (\mu^n)\bigr)$ is a basis of $E_D$ ; if $D = (X-\lambda)^2$ with $\lambda \neq 0$ , show that $\bigl((\lambda^n), (n\lambda^n)\bigr)$ is one.
Solve completely: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ ; check the answer on $u_2$ and $u_3$ .
Let $C = \begin{pmatrix} 0 & 1\\ -p & s\end{pmatrix}$ (the companion matrix of $D$ ). Show that

$\begin{pmatrix} u_{n}\\ u_{n+1}\end{pmatrix} = C^n \begin{pmatrix} u_0\\ u_1\end{pmatrix} \quad (u \in E_D),$

and that $\operatorname{tr} C = s$ and $p(C) = p$ : the recurrence and the matrix carry the same polynomial $D$ .

Part IV — Degree three. Let $D_3 = X^3 - \alpha X^2 - \beta X - \gamma$ and

C_3 = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ \gamma & \beta & \alpha \end{pmatrix}.

Show that $D_3(C_3) = 0$ . (Compute the images of the canonical basis vectors under powers of $C_3$ : the map of $C_3$ sends $e_1 \mapsto \dots \mapsto$ a combination forced by the last row.)
Show that if $D_3$ has three distinct roots $\lambda_1, \lambda_2, \lambda_3$ , the remainder $R_n$ of $X^n$ divided by $D_3$ is the Lagrange interpolant of the values $\lambda_i^n$ at the nodes $\lambda_i$ (Theorem 8.23); deduce that every entry of $C_3^{\,n}$ is a fixed linear combination of $\lambda_1^n, \lambda_2^n, \lambda_3^n$ .
Solve: $u_{n+3} = 2u_{n+2} + u_{n+1} - 2u_n$ with $u_0 = 0$ , $u_1 = 1$ , $u_2 = 1$ . (Factor $D_3 = (X - 1)(X + 1)(X - 2)$ .) Check on $u_3$ .
Compute the remainder of $X^n$ modulo $(X - \lambda)^3$ (Taylor expansion of $X^n$ at $\lambda$ ), and deduce a formula for $(\lambda I + N)^n$ when $N^3 = 0$ and $N$ commutes with everything in sight; check it against the binomial theorem.
Show that for $D_3$ with distinct roots, the general solution of the order- $3$ recurrence is $u_n = c_1 \lambda_1^n + c_2\lambda_2^n + c_3\lambda_3^n$ : prove that the three geometric sequences form a basis of the solution space. (For freeness, evaluate a null combination at $n = 0, 1, 2$ and recognize an interpolation system at the distinct nodes $\lambda_i$ .)

Part V — Fibonacci dividends, and synthesis.

Prove $F_1 + F_2 + \dots + F_n = F_{n+2} - 1$ .
From $F^{m+n} = F^m F^n$ , derive the addition formula

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

and deduce $F_{2n} = F_n(F_{n+1} + F_{n-1})$ .
Prove that $F_n$ is the nearest integer to $\varphi^n/\sqrt5$ for every $n \geq 0$ .
Let $t_n = \operatorname{tr}(F^n) = F_{n+1} + F_{n-1}$ (the Lucas numbers $L_n$ ). Show $t_{n+2} = t_{n+1} + t_n$ , $t_1 = 1$ , $t_2 = 3$ , that $L_n = \varphi^n + \psi^n$ , and recover $F_{2n} = F_n L_n$ .
Synthesis, in four sentences: why the powers of a $2 \times 2$ matrix live in the plane $\operatorname{Vect}(I, A)$ of $\mathcal{M}_2(K)$ (which dimension argument guarantees a quadratic identity, and which explicit identity Part II produced); how euclidean division converts exponentiation into a two-term recurrence; which statement of this problem is the $n = 2$ case of a theorem valid in all dimensions (name it, and say where it is proved in this series); and what the companion matrix construction adds to the picture.

Solution

Solution of Problem 21.1.

1. Euclidean division of $X^n$ by the degree- $2$ monic $D$ (Theorem 8.3): quotient and remainder exist and are unique, and the remainder has degree $\leq 1$ : $X^n = Q_n D + a_n X + b_n$ . For $n = 0$ : $Q_0 = 0$ , $(a_0, b_0) = (0, 1)$ ; for $n = 1$ : $(a_1, b_1) = (1, 0)$ .

2. Multiply by $X$ and reduce $X^2 = D + sX - p$ :

X^{n+1} = X Q_n D + a_n X^2 + b_n X = (X Q_n + a_n)\,D + (s\,a_n + b_n)\,X - p\,a_n .

The last expression has remainder shape (degree $\leq 1$ ), so by uniqueness $a_{n+1} = s a_n + b_n$ and $b_{n+1} = -p a_n$ . Substituting $b_{n+1} = -pa_n$ into $a_{n+2} = s a_{n+1} + b_{n+1}$ gives $a_{n+2} = s\,a_{n+1} - p\,a_n$ .

3. Evaluate $X^n = Q_n D + a_n X + b_n$ at the roots: $\lambda^n = a_n\lambda + b_n$ and $\mu^n = a_n\mu + b_n$ . Subtracting and dividing by $\lambda - \mu \neq 0$ :

a_n = \frac{\lambda^n - \mu^n}{\lambda - \mu}, \qquad b_n = \lambda^n - a_n\lambda = \frac{\lambda\mu^n - \mu\lambda^n}{\lambda - \mu} .

4. At the double root: $\lambda^n = a_n\lambda + b_n$ . Differentiating the identity, $nX^{n-1} = Q_n'\,(X - \lambda)^2 + 2Q_n\,(X - \lambda) + a_n$ , and evaluating at $\lambda$ : $a_n = n\lambda^{n-1}$ ; then $b_n = \lambda^n - n\lambda^{n} = (1 - n)\lambda^{n}$ .

5. For $P = \sum_i p_i X^i$ and $Q = \sum_j q_j X^j$ ,

P(M)\,Q(M) = \sum_{i,j} p_i q_j M^{i+j} = (PQ)(M),

because powers of the single matrix $M$ commute with each other (sums are clear by linearity). If $D(M) = 0$ , substituting $M$ into $X^n = Q_n D + a_n X + b_n$ gives $M^n = Q_n(M)\,D(M) + a_n M + b_n I = a_n M + b_n I$ .

6. Direct products:

A^2 = \begin{pmatrix} a^2 + bc & b(a + d)\\ c(a + d) & d^2 + bc \end{pmatrix}, \qquad s A = \begin{pmatrix} a(a+d) & b(a+d)\\ c(a+d) & d(a+d) \end{pmatrix},

so $A^2 - sA$ has zero off-diagonal entries and diagonal entries $a^2 + bc - a^2 - ad = bc - ad = -p$ : $A^2 - sA + pI_2 = 0$ .

7. With $A' = \begin{pmatrix} a' & b'\\ c' & d'\end{pmatrix}$ , expanding $p(AA') = (aa' + bc')(cb' + dd') - (ab' + bd')(ca' + dc')$ : the terms $aa'cb'$ and $ab'ca'$ cancel, the terms $bc'dd'$ and $bd'dc'$ cancel, and what remains is

aa'dd' - bca'd' + bcb'c' - adb'c' = (ad - bc)(a'd' - b'c') = p(A)\,p(A').

If $p \neq 0$ , Cayley–Hamilton gives $A\,\bigl(\tfrac1p(sI_2 - A)\bigr) = \tfrac1p(sA - A^2) = I_2$ , whence the inverse (and Proposition 21.4 makes it two-sided). If $p = 0$ and $A$ were invertible, multiplicativity gives $1 = p(I_2) = p(A)\,p(A^{-1}) = 0$ : impossible. So $A \in GL_2 \iff p \neq 0$ .

8. $s = 3$ , $p = 2$ , $D = X^2 - 3X + 2 = (X - 1)(X - 2)$ : $\lambda = 2$ , $\mu = 1$ , so $a_n = 2^n - 1$ and $b_n = 2 - 2^n$ (question 3). Hence

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

Check: $A^2 = \begin{pmatrix} 1 & 3\\ 0 & 4\end{pmatrix}$ both by the formula and by squaring directly.

9. $s = 4$ , $p = 3\cdot1 - 1\cdot(-1) = 4$ : $D = X^2 - 4X + 4 = (X - 2)^2$ , double root $\lambda = 2$ . Question 4: $a_n = n\,2^{n-1}$ , $b_n = (1 - n)2^n$ , so

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

At $n = 2$ : $2\begin{pmatrix} 4 & 2\\ -2 & 0\end{pmatrix} = \begin{pmatrix} 8 & 4\\ -4 & 0 \end{pmatrix}$ , which is $A^2$ computed directly.

10. Induction: $F^1 = \begin{pmatrix} F_2 & F_1\\ F_1 & F_0\end{pmatrix}$ , and

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

Here $s = 1$ , $p = -1$ , $D = X^2 - X - 1$ with roots $\varphi, \psi$ ( $\varphi - \psi = \sqrt5$ , $\varphi\psi = -1$ ). The sequence $(F_n)$ has $F_0 = 0 = a_0$ , $F_1 = 1 = a_1$ and obeys the same recurrence as $(a_n)$ : $F_n = a_n = (\varphi^n - \psi^n)/\sqrt5$ , Binet’s formula. Cassini: applying question 7’s multiplicativity to $F^n$ ,

F_{n+1}F_{n-1} - F_n^2 = p(F^n) = p(F)^n = (-1)^n .

11. The condition is linear and contains the zero sequence: a subspace. By induction $u_0, u_1$ determine $u$ linearly, and every pair of initial values is realized by exactly one solution: as in Exercise 19.10, $E_D$ is parametrized bijectively and linearly by $(u_0, u_1) \in K^2$ : $\dim E_D = 2$ .

12. $(a_n)$ obeys the recurrence (question 2) with $a_0 = 0$ , $a_1 = 1$ . So does $(b_n)$ : $b_{n+2} = -p\,a_{n+1} = -p(s a_n + b_n) = s\,b_{n+1} - p\,b_n$ (using $b_{n+1} = -pa_n$ twice), with $b_0 = 1$ , $b_1 = 0$ . The combination $v_n = u_1 a_n + u_0 b_n$ is then a solution with $v_0 = u_0$ , $v_1 = u_1$ ; two solutions with the same initial values coincide (induction), so $u_n = u_1 a_n + u_0 b_n$ for all $n$ .

13. $(\lambda^n)$ is a solution iff $\lambda^{n+2} = s\lambda^{n+1} - p\lambda^n$ for all $n$ , i.e. $D(\lambda) = 0$ (after dividing by $\lambda^n \neq 0$ ; note $\lambda, \mu \neq 0$ since $p = \lambda\mu \neq 0$ ). Freeness of $\bigl((\lambda^n), (\mu^n)\bigr)$ : a relation at $n = 0, 1$ gives $c + c' = 0$ , $c\lambda + c'\mu = 0$ , so $c(\lambda - \mu) = 0$ : $c = c' = 0$ . Two free vectors in dimension $2$ : a basis. Double root: $\bigl((n\lambda^n)\bigr)$ is a solution since, with $s = 2\lambda$ , $p = \lambda^2$ :

s(n+1)\lambda^{n+1} - p\,n\lambda^n = \lambda^{n+2}\bigl(2(n+1) - n\bigr) = (n+2)\lambda^{n+2} ;

freeness at $n = 0, 1$ : $c = 0$ , then $c'\lambda = 0$ with $\lambda \neq 0$ .

14. $D = X^2 - X - 6 = (X - 3)(X + 2)$ . General solution $u_n = A\,3^n + B(-2)^n$ ; the initial conditions give $A + B = 1$ and $3A - 2B = 8$ , so $A = 2$ , $B = -1$ :

u_n = 2\cdot 3^n - (-2)^n .

Check: $u_2 = 18 - 4 = 14 = u_1 + 6u_0$ ; $u_3 = 54 + 8 = 62 = u_2 + 6u_1 = 14 + 48$ .

15. $C\begin{pmatrix} u_n\\ u_{n+1}\end{pmatrix} = \begin{pmatrix} u_{n+1}\\ -p\,u_n + s\,u_{n+1}\end{pmatrix} = \begin{pmatrix} u_{n+1}\\ u_{n+2}\end{pmatrix}$ , and induction gives the formula with $C^n$ . Moreover $\operatorname{tr} C = 0 + s = s$ and $p(C) = 0\cdot s - 1\cdot(-p) = p$ : the companion matrix has exactly $D$ as its Cayley–Hamilton polynomial.

16. For any solution $u$ of $u_{n+3} = \alpha u_{n+2} + \beta u_{n+1} + \gamma u_n$ , the state vectors $v_n = (u_n, u_{n+1}, u_{n+2})^{\mathsf T}$ satisfy $C_3 v_n = v_{n+1}$ (the first two rows shift, the last row applies the recurrence). Hence

D_3(C_3)\,v_0 = v_3 - \alpha v_2 - \beta v_1 - \gamma v_0 ,

whose three components are $u_{k+3} - \alpha u_{k+2} - \beta u_{k+1} - \gamma u_k = 0$ ( $k = 0, 1, 2$ ). As the initial state $v_0 = (u_0, u_1, u_2)^{\mathsf T}$ ranges over all of $K^3$ (initial values are free), the matrix $D_3(C_3)$ kills every vector: $D_3(C_3) = 0$ .

17. Write $X^n = Q\,D_3 + R_n$ with $\deg R_n \leq 2$ and evaluate at each root: $\lambda_i^n = R_n(\lambda_i)$ . So $R_n$ is a polynomial of degree $\leq 2$ interpolating the three values $\lambda_i^n$ at the three distinct nodes $\lambda_i$ : by uniqueness in Theorem 8.23, $R_n = \sum_i \lambda_i^n L_i$ with $(L_i)$ the Lagrange basis of the nodes. Substituting $C_3$ (questions 5 and 16):

C_3^{\,n} = R_n(C_3) = \sum_{i=1}^{3} \lambda_i^n\,L_i(C_3),

with the three matrices $L_i(C_3)$ independent of $n$ : every entry of $C_3^{\,n}$ is a fixed combination of $\lambda_1^n, \lambda_2^n, \lambda_3^n$ .

18. $D_3 = X^3 - 2X^2 - X + 2 = (X-1)(X+1)(X-2)$ . General solution $u_n = A + B(-1)^n + C\,2^n$ . Initial conditions: $A + B + C = 0$ , $A - B + 2C = 1$ , $A + B + 4C = 1$ . Subtracting the first from the third: $3C = 1$ , $C = \frac13$ ; then $A + B = -\frac13$ and $A - B = \frac13$ : $A = 0$ , $B = -\frac13$ . Hence

u_n = \frac{2^n - (-1)^n}{3}

(the Jacobsthal numbers). Check: $u_3 = \frac{8 + 1}{3} = 3 = 2u_2 + u_1 - 2u_0 = 2 + 1 - 0$ .

19. Taylor expansion of the polynomial $X^n$ at $\lambda$ :

X^n = \sum_{k=0}^{n} \binom nk \lambda^{n-k}(X - \lambda)^k ,

and all terms with $k \geq 3$ are divisible by $(X - \lambda)^3$ : the remainder is

R_n = \lambda^n + n\lambda^{n-1}(X - \lambda) + \binom n2\lambda^{n-2}(X - \lambda)^2 .

For $M = \lambda I + N$ with $N^3 = 0$ : $(M - \lambda I)^3 = N^3 = 0$ , so question 5 gives

M^n = \lambda^n I + n\lambda^{n-1} N + \binom n2 \lambda^{n-2} N^2 ,

which is exactly the binomial expansion of $(\lambda I + N)^n$ truncated at $N^2$ — the two methods agree.

20. The solution space has dimension $3$ (same parametrization by $(u_0, u_1, u_2)$ as in question 11), and each $(\lambda_i^n)$ is a solution. Freeness: suppose $c_1\lambda_1^n + c_2\lambda_2^n + c_3\lambda_3^n = 0$ for $n = 0, 1, 2$ . Fix $i$ and let $L_i = \sum_{k \leq 2} p_k X^k$ be the Lagrange polynomial of the nodes with $L_i(\lambda_j) = \delta_{ij}$ . Then

0 = \sum_{k=0}^{2} p_k\Bigl(\sum_j c_j\lambda_j^k\Bigr) = \sum_j c_j\,L_i(\lambda_j) = c_i .

So all $c_i = 0$ : three free solutions in dimension $3$ , a basis; the general solution is $c_1\lambda_1^n + c_2\lambda_2^n + c_3\lambda_3^n$ .

21. From $F_k = F_{k+2} - F_{k+1}$ , the sum telescopes:

\sum_{k=1}^{n} F_k = \sum_{k=1}^{n}\bigl(F_{k+2} - F_{k+1}\bigr) = F_{n+2} - F_2 = F_{n+2} - 1 .

22. Take the $(1,2)$ entry of $F^{m+n} = F^m F^n$ : the left side is $F_{m+n}$ ; the right side is (row $1$ of $F^m$ ) times (column $2$ of $F^n$ ), i.e. $F_{m+1}F_n + F_m F_{n-1}$ . With $m = n$ :

F_{2n} = F_{n+1}F_n + F_nF_{n-1} = F_n\,(F_{n+1} + F_{n-1}).

23. By Binet, $F_n - \dfrac{\varphi^n}{\sqrt5} = -\dfrac{\psi^n}{\sqrt5}$ , and $\abs\psi = \frac{\sqrt5 - 1}2 < 1$ , so

\Bigl|F_n - \frac{\varphi^n}{\sqrt5}\Bigr| \leq \frac{1}{\sqrt5} < \frac12 \qquad (n \geq 0):

$F_n$ is the nearest integer to $\varphi^n/\sqrt5$ .

24. $t_n = F_{n+1} + F_{n-1}$ is a combination of shifted Fibonacci sequences, hence satisfies the same recurrence: $t_{n+2} = t_{n+1} + t_n$ ; and $t_1 = F_2 + F_0 = 1$ , $t_2 = F_3 + F_1 = 3$ : these are the Lucas numbers $L_n$ . The sequence $\varphi^n + \psi^n$ is a solution with the same first two values ( $\varphi + \psi = 1$ , $\varphi^2 + \psi^2 = ( \varphi + \psi)^2 - 2\varphi\psi = 3$ ), so $L_n = \varphi^n + \psi^n$ . Finally

F_n L_n = \frac{(\varphi^n - \psi^n)(\varphi^n + \psi^n)}{\sqrt5} = \frac{\varphi^{2n} - \psi^{2n}}{\sqrt5} = F_{2n},

recovering question 22.

25. (i) The five matrices $I, A, A^2, A^3, A^4$ live in the $4$ -dimensional $\mathcal{M}_2(K)$ , so some nonzero polynomial of degree $\leq 4$ kills $A$ ; Part II sharpened this to the explicit quadratic $A^2 = sA - pI$ , which locks all powers into the plane $\operatorname{Vect}(I, A)$ . (ii) Euclidean division reduces $X^n$ modulo that quadratic, and the remainder’s two coefficients obey the two-term recurrence $a_{n+2} = s\,a_{n+1} - p\,a_n$ : exponentiation has become iteration. (iii) Question 6 is the $n = 2$ case of the Cayley–Hamilton theorem, valid in every dimension and proved in the Year 2 volume. (iv) The companion matrix closes the loop: every linear recurrence is a matrix power, with the same polynomial $D$ appearing as trace-and-determinant data, so the remainder calculus solves recurrences and computes powers in one stroke.