---
title: "Matrices"
book: "University Mathematics — Year 1"
subject: math
language: en
chapter: 21
exercises: 12
source: https://one-course.com/books/math/3/en/chapter/21-matrices
---

# Chapter 21 — Matrices

A matrix is a [linear map](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-def) written in [coordinates](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-coordinates). This chapter [sets](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) up the dictionary — composition becomes matrix product, bijectivity becomes invertibility, [change of basis](#def-b1-matrices-changeofbasis) becomes conjugation — and the algorithmic side: [row operations](#met-b1-matrices-gauss), computation of ranks and inverses. First met in the High School volume, matrices are now grounded in the theory of Chapters [18](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#ch-b1-vspaces), [19](https://one-course.com/books/math/3/en/chapter/19-finite-dimension#ch-b1-findim) and [20](https://one-course.com/books/math/3/en/chapter/20-linear-maps#ch-b1-linmaps).

## 21.1 Matrices and linear maps

**Definition 21.1.**

$\mathcal{M}_{n,p}(K)$ is the [vector space](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-def) of $n \times p$ arrays $A
= (a_{ij})$ of scalars ($i$: row, $j$: column), of dimension $np$ ([basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free): 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#prop-b1-linmaps-basis): a [linear map](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-def) is exactly a choice of [images](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim) of the $e_j$).

**Example 21.2 (The derivative, as a matrix).**

Let $D(P) = P'$ on $\R_3[X]$. In the monomial [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) $(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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) $\bigl(1,\ X,\ \frac{X^2}2,\
\frac{X^3}6\bigr)$, each [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) vector [maps](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map), [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free)), not to the [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) alone; and a good [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-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 Mn(K)\mathcal{M}_n(K)Mn​(K)).**

Square matrices $\mathcal{M}_n(K)$ form a (non-commutative for $n
\geq 2$) [ring](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#def-b1-structures-ring), with identity $I_n$; its [group](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#def-b1-structures-group) of units is the *general linear group* $GL_n(K)$, corresponding to [bijective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) 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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#cor-b1-linmaps-samedim)).

**Proof.** [Ring](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#def-b1-structures-ring) axioms transport from $\mathcal{L}(E)$ through the isomorphism of [Definition 21.1](#def-b1-matrices-def): 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map), 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) ($x =
a(b(x))$ exhibits a [preimage](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) of every $x$), hence [bijective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) in [finite dimension](https://one-course.com/books/math/3/en/chapter/19-finite-dimension#def-b1-findim-def) ([Corollary 20.9](https://one-course.com/books/math/3/en/chapter/20-linear-maps#cor-b1-linmaps-samedim)); 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](https://one-course.com/books/math/3/en/chapter/19-finite-dimension#def-b1-findim-def) 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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-def), 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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-projection) of [Chapter 20](https://one-course.com/books/math/3/en/chapter/20-linear-maps#ch-b1-linmaps) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free): indeed $A^2 = A$, and

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

illustrating [Exercise 21.8](#exo-b1-matrices-8): for idempotents the [trace](#def-b1-matrices-transpose) *counts* the dimension of the [image](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim), whatever slanted [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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](#def-b1-matrices-transpose) — the first *numerical invariant* of an endomorphism, to be joined by the determinant in [Chapter 22](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det) (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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) are [supplementary subspaces](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-sum) of $\mathcal{M}_n(K)$ — the exact analogue of the even/odd split of functions ([Example 18.11](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#ex-b1-vspaces-evenodd)), with transposition playing the role of $x \mapsto -x$. Dimensions: a symmetric matrix is [free](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/14-differentiation#def-b1-derivative-def) data of [Chapter 25](https://one-course.com/books/math/3/en/chapter/25-functions-of-two-variables#ch-b1-multivar) (the Monge triple $r, s, t$), and the symmetric-orthogonal ones are classified in [Exercise 23.12](https://one-course.com/books/math/3/en/chapter/23-euclidean-spaces#exo-b1-euclid-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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-coordinates) of the *new* [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) vectors in the *old* [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free). It is invertible, $P^{-1} = P_{\mathcal{B}'\to\mathcal{B}}$, and [coordinates](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-coordinates), column by column). The vector of old [coordinates](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-coordinates) $X = (3, 1)^{\mathsf T}$ has new [coordinates](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) but converts *new to old* [coordinates](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free). In the [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) $\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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) identities alone already go.

**Example 21.12 (Change of basis, run in reverse).**

The [projection](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-projection) onto $F = \operatorname{Vect}(1,1)$ along $G =
\operatorname{Vect}(1,-1)$ has, in the adapted [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) $\mathcal
B' = \bigl((1,1),(1,-1)\bigr)$, the transparent matrix $A' =
\operatorname{diag}(1, 0)$. To get its [canonical-basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) matrix, run [Theorem 21.10](#thm-b1-matrices-conjugation) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free), then conjugate back — is how rotation, reflection and [projection](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-def)) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-sum) $S$ of $\ker u$ ($\dim S = r$, [Theorem 20.7](https://one-course.com/books/math/3/en/chapter/20-linear-maps#thm-b1-linmaps-ranknullity)) with [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) $(e_1, \dots, e_r)$, completed by a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) of $\ker u$ into a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) of $E$; the [images](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim) $f_i = u(e_i)$, $i \leq r$, form a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) of $\operatorname{im} u$ (the restriction is an isomorphism), completed into a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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](#def-b1-matrices-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](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det) (the [polynomial](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) $-(m+2)(m-1)^2$ of [Exercise 22.7](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#exo-b1-det-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](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#prop-b1-structures-binomial)) 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 AnA^nAn: the three routes).**

1. *Binomial route* : if $A = \lambda I + N$ with $N$ nilpotent, the binomial theorem truncates ( [Example 21.17](#ex-b1-matrices-powers) , [Exercise 21.5](#exo-b1-matrices-5) ); it applies because $\lambda I$ commutes with everything.
2. *[Polynomial](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) route* : find a [polynomial](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) 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.
3. *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](#thm-b1-matrices-conjugation) , [Example 21.11](#ex-b1-matrices-conjugationrun) ); 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](#exo-b1-matrices-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](#def-b1-matrices-transpose)*: $\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](#def-b1-matrices-transpose) reverse*: $(AB)^{\mathsf T} = B^{\mathsf
T}A^{\mathsf T}$ — forgetting the reversal is the most common error in orthogonality computations ([Chapter 23](https://one-course.com/books/math/3/en/chapter/23-euclidean-spaces#ch-b1-euclid)). 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](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det) attaches to each square matrix a single number deciding invertibility, and solves $AX = B$ systematically; [Chapter 23](https://one-course.com/books/math/3/en/chapter/23-euclidean-spaces#ch-b1-euclid) singles out the matrices preserving lengths (orthogonal matrices); and in [Chapter 25](https://one-course.com/books/math/3/en/chapter/25-functions-of-two-variables#ch-b1-multivar), the second-order behavior of a function of two variables is a symmetric $2 \times 2$ matrix. The [trace](#def-b1-matrices-transpose), introduced above almost in passing, becomes a powerful invariant: Exercises [21.6](#exo-b1-matrices-6) and [21.8](#exo-b1-matrices-8) give a first taste, and the Year 2 volume builds eigenvalue theory on it. The weekend problem develops the other workhorse: [polynomial](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) identities satisfied by a matrix, which turn the computation of $A^n$ into a two-term [linear recurrence](#pb-b1-matrices-1).

**Remark 21.21 (Perspectives inside Book 3).**

Three matrix families introduced here have appointments later in this volume. *Symmetric matrices* ([Example 21.7](#ex-b1-matrices-symsplit)) carry the second-order data of functions of two variables: the Monge test of [Chapter 25](https://one-course.com/books/math/3/en/chapter/25-functions-of-two-variables#ch-b1-multivar) is a [statement](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-statement) about the sign behavior of a symmetric $2\times2$ matrix, and its determinant $rt - s^2$ is computed by [Chapter 22](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det)’s machinery. *Orthogonal matrices* ($A^{\mathsf T}A = I$) are the isometries of [Chapter 23](https://one-course.com/books/math/3/en/chapter/23-euclidean-spaces#ch-b1-euclid), where the [transpose](#def-b1-matrices-transpose) finally acquires its geometric meaning: it is the algebraic shadow of the inner product. *Invertible matrices* meet their practical test in [Chapter 22](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det) — one number, $\det A \neq 0$ — closing the search this chapter began with row reduction. [Trace](#def-b1-matrices-transpose) 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 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 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 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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 of Exercise 21.4.**

$u(1) = 1$, $u(X) = X + 1$, $u(X^2) = X^2 + 2X + 1$: columns of [coordinates](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#prop-b1-vspaces-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 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](#def-b1-matrices-transpose).)*

**Solution of Exercise 21.6.**

[Traces](#def-b1-matrices-transpose): $\operatorname{tr}(AB - BA) = \operatorname{tr}(AB) -
\operatorname{tr}(BA) = 0$ ([Definition 21.5](#def-b1-matrices-transpose)), 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](#def-b1-matrices-transpose) 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 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](#prop-b1-matrices-ring) 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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-projection) and choose an adapted [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free); [Theorem 21.10](#thm-b1-matrices-conjugation) says the [trace](#def-b1-matrices-transpose) is basis-independent since $\operatorname{tr}(P^{-1}MP) =
\operatorname{tr} M$.)*

**Solution of Exercise 21.8.**

$A^2 = A$: the endomorphism $a$ is a [projection](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-projection) ([Theorem 20.15](https://one-course.com/books/math/3/en/chapter/20-linear-maps#thm-b1-linmaps-projchar)), $E = \operatorname{im} a \oplus
\ker a$ with $\dim\operatorname{im} a = r = \operatorname{rk} A$. In a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) adapted to this decomposition ($r$ vectors of the [image](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim), then a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) of the kernel), the matrix of $a$ is $\begin{pmatrix} I_r & 0\\ 0 & 0\end{pmatrix}$, of [trace](#def-b1-matrices-transpose) $r$. The [trace](#def-b1-matrices-transpose) is invariant under [change of basis](#def-b1-matrices-changeofbasis): $\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 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) of $A$ to $\operatorname{im} B$.)*

**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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) of $A$ restricted to $V =
\operatorname{im} B$ (dimension $\operatorname{rk} B$). Its [image](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim) 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*.

1. Prove that a matrix $A$ commutes with $D$ if and only if $A$ is diagonal. *(Compare the $(i,j)$ entries of $AD$ and $DA$.)*
2. 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 of Exercise 21.11.**

1. 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.
2. 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$.

1. 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}$ .
2. 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](#def-b1-matrices-transpose) is zero.
3. 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 of Exercise 21.12.**

1. If $\operatorname{rk} A = 1$ : the [image](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim) 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$ .
2. $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](#def-b1-matrices-transpose) is zero.
3. 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj), 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) 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](#pb-b1-matrices-1) — with the [Fibonacci numbers](#pb-b1-matrices-1) as running example.

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

1. 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)$.
2. 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](#pb-b1-matrices-1) attached to $D$.
3. 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} .$$
4. Suppose $D = (X - \lambda)^2$ . Using the [derivative](https://one-course.com/books/math/3/en/chapter/14-differentiation#def-b1-derivative-def) of the division identity, prove $a_n = n\lambda^{n-1}$ and $b_n = (1 - n)\lambda^{n}$ .
5. Show that substituting a fixed matrix $M \in  \mathcal{M}_k(K)$ into [polynomials](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) 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](#def-b1-matrices-transpose), 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](https://one-course.com/books/math/3/en/chapter/22-determinants-and-linear-systems#ch-b1-det) will name the determinant).

6. Verify by direct computation the *Cayley–Hamilton identity in dimension $2$*: $$A^2 - s\,A + p\,I_2 = 0 .$$
7. 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).$$
8. Let $A = \begin{pmatrix} 1 & 1\\ 0 & 2\end{pmatrix}$ . Compute $s$ , $p$ , the roots of $D$ , and deduce a [closed](https://one-course.com/books/math/3/en/chapter/12-topology-of-the-real-line#def-b1-topology-closed) formula for $A^n$ ; check it against a direct computation of $A^2$ .
9. 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$ .
10. Let $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ and define the [Fibonacci numbers](#pb-b1-matrices-1) 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](#pb-b1-matrices-1), structurally.** Fix $s, p \in K$ with $p \neq 0$, and let $E_D$ be the [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) of sequences with $u_{n+2} = s\,u_{n+1} - p\,u_n$ for all $n$.

11. Show that $E_D$ is a [vector space](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-def) of dimension $2$ (adapt [Exercise 19.10](https://one-course.com/books/math/3/en/chapter/19-finite-dimension#exo-b1-findim-10) ).
12. 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.
13. If $\lambda \neq \mu$ are the roots of $D$ , show that $\bigl((\lambda^n), (\mu^n)\bigr)$ is a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) of $E_D$ ; if $D = (X-\lambda)^2$ with $\lambda \neq 0$ , show that $\bigl((\lambda^n), (n\lambda^n)\bigr)$ is one.
14. 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$ .
15. 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) $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}.
$$

16. Show that $D_3(C_3) = 0$ . *(Compute the [images](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-kerim) of the canonical [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) vectors under powers of $C_3$: the [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) of $C_3$ sends $e_1 \mapsto \dots \mapsto$ a combination forced by the last row.)*
17. 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#thm-b1-poly-lagrange) ); deduce that every entry of $C_3^{\,n}$ is a fixed linear combination of $\lambda_1^n, \lambda_2^n, \lambda_3^n$ .
18. 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$ .
19. 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.
20. 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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.**

21. Prove $F_1 + F_2 + \dots + F_n = F_{n+2} - 1$ .
22. 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})$.
23. Prove that $F_n$ is the nearest integer to $\varphi^n/\sqrt5$ for every $n \geq 0$ .
24. 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$ .
25. 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-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](https://one-course.com/books/math/3/en/chapter/17-numerical-series#def-b1-series-def) ); and what the companion matrix construction adds to the picture.

**Solution of Problem 21.1.**

**1.** Euclidean division of $X^n$ by the degree-$2$ [monic](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) $D$ ([Theorem 8.3](https://one-course.com/books/math/3/en/chapter/8-polynomials#thm-b1-poly-division)): 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](#prop-b1-matrices-ring) 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](https://one-course.com/books/math/3/en/chapter/20-linear-maps#def-b1-linmaps-def) and contains the zero sequence: a [subspace](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/19-finite-dimension#exo-b1-findim-10), $E_D$ is parametrized [bijectively](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) vectors in dimension $2$: a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free). 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def).

**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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) of degree $\leq 2$ interpolating the three values $\lambda_i^n$ at the three distinct nodes $\lambda_i$: by uniqueness in [Theorem 8.23](https://one-course.com/books/math/3/en/chapter/8-polynomials#thm-b1-poly-lagrange), $R_n = \sum_i
\lambda_i^n L_i$ with $(L_i)$ the Lagrange [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) $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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) 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](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free) solutions in dimension $3$, a [basis](https://one-course.com/books/math/3/en/chapter/18-vector-spaces#def-b1-vspaces-free); 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) 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](#pb-b1-matrices-1) *is* a matrix power, with the same [polynomial](https://one-course.com/books/math/3/en/chapter/8-polynomials#def-b1-poly-def) $D$ appearing as trace-and-determinant data, so the remainder calculus solves recurrences and computes powers in one stroke.