7.10 The Characteristic Polynomial

For a square matrix $\mathbf{A}$ over $F$ and a scalar $c \in F$ , when is $c\mathbf{I} - \mathbf{A}$ invertible? The question matters: $c\mathbf{I} - \mathbf{A}$ fails to be invertible exactly when $\mathbf{A}\mathbf{v} = c\mathbf{v}$ for some non-zero vector $\mathbf{v}$ , the situation Chapter 9 is built around. The determinant answers the question for each single $c$ . This section lets $c$ vary. Replacing the number $c$ by a variable $x$ turns $\det(c\mathbf{I} - \mathbf{A})$ into a polynomial, the characteristic polynomial, and the scalars we are looking for become its roots. The price is that $x\mathbf{I} - \mathbf{A}$ is a matrix of polynomials, not of field elements, so we must check which determinant facts survive there. The remarks at the ends of §4, §5 and §6 did exactly that bookkeeping, and here we cash them in.

7.10.1. From a number to a variable

Take $\mathbf{A} = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \in M_2(\mathbb{Q})$ . For each $c \in \mathbb{Q}$ , $\det(c\mathbf{I} - \mathbf{A}) = \det\begin{pmatrix} c - 1 & -2 \\ -3 & c - 4 \end{pmatrix} = (c - 1)(c - 4) - 6 = c^2 - 5c - 2 .$ The same expression $c^2 - 5c - 2$ appears whatever $c$ is. It is the value at $c$ of one polynomial, and that polynomial deserves a name. To define it directly, without first choosing $c$ , we put the variable $x$ into the matrix and take the determinant of $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x - 1 & -2 \\ -3 & x - 4 \end{pmatrix},$ a matrix whose entries lie in $F[x]$ .

Is that allowed? $F[x]$ is not a field, but it is a commutative ring in the sense of the remark in §4: all the field axioms hold except the existence of inverses (Theorem 0.8.1). The Leibniz formula of Definition 7.4.1 uses only sums, differences and products of entries, so it defines $\det \mathbf{M} \in F[x]$ for every $\mathbf{M} \in M_n(F[x])$ .

The characteristic polynomial of $\mathbf{A}$ is the determinant of $x\mathbf{I} - \mathbf{A}$ , computed with polynomial entries.

Definition 7.10.1 (Characteristic Polynomial)

Let $n \ge 1$ and $\mathbf{A} = (a_{ij}) \in M_n(F)$ . The characteristic polynomial of $\mathbf{A}$ is $p_{\mathbf{A}}(x) \mathrel{:=} \det(x\mathbf{I}_n - \mathbf{A}) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{j=1}^{n} \big(x\,\delta_{\sigma(j)j} - a_{\sigma(j)j}\big) \ \in F[x],$ where $\delta_{ij} = 1$ if $i = j$ and $0$ otherwise, so that $x\delta_{ij} - a_{ij}$ is the $(i, j)$ -entry of $x\mathbf{I}_n - \mathbf{A}$ . The determinant is the Leibniz sum of Definition 7.4.1, computed in the commutative ring $F[x]$ .

In words: subtract $\mathbf{A}$ from $x$ times the identity, so that $x$ appears only on the diagonal; then take the determinant exactly as for a matrix of numbers, multiplying and adding polynomials instead of scalars. The result is one polynomial, not a number.

Well-definedness. Each term of the Leibniz sum is a product of $n$ polynomials, and the sum is finite, so $p_{\mathbf{A}}$ is a polynomial. It depends only on $\mathbf{A}$ .

How to compute it. By the remarks in §4, §5 and §6, the following results were proved without dividing, and so hold for matrices over $F[x]$ : Theorem 7.4.5 and Theorem 7.4.6 (§4), Theorem 7.5.4 by its first proof (§5), Theorem 7.6.1 (§6), and Theorem 7.8.4 (§8). So we may expand $\det(x\mathbf{I} - \mathbf{A})$ along any row or column, and read it off from triangular or block triangular shape. What we may not do is row reduce $x\mathbf{I} - \mathbf{A}$ by dividing by a polynomial entry, as the warning below explains.

Examples.

$1 \times 1$ . For $\mathbf{A} = (a)$ , $p_{\mathbf{A}}(x) = x - a$ .
$2 \times 2$ . For $\mathbf{A} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ , $\begin{aligned} p_{\mathbf{A}}(x) &= (x - a)(x - d) - bc = x^2 - (a + d)x + (ad - bc) \\ &= x^2 - (\operatorname{tr} \mathbf{A})\,x + \det \mathbf{A} . \end{aligned}$ For $\mathbf{A} = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ this is $x^2 - 5x - 2$ , as above.
Triangular. If $\mathbf{A}$ is upper or lower triangular, so is $x\mathbf{I} - \mathbf{A}$ , with diagonal entries $x - a_{ii}$ . By Theorem 7.4.6 over $F[x]$ , $p_{\mathbf{A}}(x) = (x - a_{11})(x - a_{22})\cdots(x - a_{nn})$ .
Degenerate cases. The zero matrix has $p_{0}(x) = x^n$ , and the identity has $p_{\mathbf{I}_n}(x) = (x - 1)^n$ ; both are triangular. These two polynomials are different, although both matrices are as simple as possible, which already shows that $p_{\mathbf{A}}$ records something about $\mathbf{A}$ .

Example (A

3 \times 3

Characteristic Polynomial)

Find $p_{\mathbf{A}}$ for $\mathbf{A} = \begin{pmatrix} 2 & 0 & 1 \\ 1 & 3 & 1 \\ 1 & 0 & 2 \end{pmatrix} \in M_3(\mathbb{Q})$ .

Solution. We have $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x - 2 & 0 & -1 \\ -1 & x - 3 & -1 \\ -1 & 0 & x - 2 \end{pmatrix}.$ Column $2$ has a single non-zero entry, $x - 3$ in position $(2, 2)$ . Expanding along it (Theorem 7.6.1 over $F[x]$ ), $\begin{aligned} p_{\mathbf{A}}(x) &= (x - 3)\,(-1)^{2+2}\det\begin{pmatrix} x - 2 & -1 \\ -1 & x - 2 \end{pmatrix} \\ &= (x - 3)\big((x - 2)^2 - 1\big) = (x - 1)(x - 3)^2 . \end{aligned}$ Multiplied out, $p_{\mathbf{A}}(x) = x^3 - 7x^2 + 15x - 9$ . Compare with $\operatorname{tr} \mathbf{A} = 2 + 3 + 2 = 7$ and $\det \mathbf{A} = 9$ (expand $\mathbf{A}$ along column $2$ : $3(4 - 1) = 9$ ).

A companion-type example. Let $\mathbf{A} = \begin{pmatrix} 0 & 0 & 6 \\ 1 & 0 & -11 \\ 0 & 1 & 6 \end{pmatrix}$ , with ones just below the diagonal, a last column $(6, -11, 6)$ , and zeros elsewhere. Expanding $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x & 0 & -6 \\ -1 & x & 11 \\ 0 & -1 & x - 6 \end{pmatrix}$ along the first row (Theorem 7.6.1 over $F[x]$ ), $\begin{aligned} p_{\mathbf{A}}(x) &= x\det\begin{pmatrix} x & 11 \\ -1 & x - 6 \end{pmatrix} + (-6)\det\begin{pmatrix} -1 & x \\ 0 & -1 \end{pmatrix} \\ &= x(x^2 - 6x + 11) - 6 = x^3 - 6x^2 + 11x - 6 , \end{aligned}$ which factors as $(x - 1)(x - 2)(x - 3)$ . The last column of $\mathbf{A}$ lists the coefficients $-6, 11, -6$ of $1, x, x^2$ in $p_{\mathbf{A}}$ , with their signs changed. This is no accident: Exercise (C1: Companion matrices) shows that the same pattern works in every size.

Non-example by minimal change. Swap the order of subtraction: $\det(\mathbf{A} - x\mathbf{I})$ . Each of the $n$ columns of $\mathbf{A} - x\mathbf{I}$ is $-1$ times the corresponding column of $x\mathbf{I} - \mathbf{A}$ , so by multilinearity $\det(\mathbf{A} - x\mathbf{I}) = (-1)^n p_{\mathbf{A}}(x)$ . For $\mathbf{A} = (a)$ this is $a - x$ , whose leading coefficient is $-1$ . What still works: the roots are the same. What fails: the result is not monic when $n$ is odd.

Why this definition. Some books use $\det(\mathbf{A} - x\mathbf{I})$ . We use $x\mathbf{I} - \mathbf{A}$ so that the characteristic polynomial is always monic (Theorem 7.10.2 below), which makes statements like “ $p_{\mathbf{A}} = (x - 1)(x - 3)^2$ ” true without sign bookkeeping. The name comes from the fact that the roots of this polynomial are the “characteristic values” of $\mathbf{A}$ , which Chapter 9 calls eigenvalues.

Warning. Do not row reduce $x\mathbf{I} - \mathbf{A}$ by dividing by polynomials. Over a field, a matrix with non-zero determinant is invertible (Theorem 7.5.2), but that proof runs through elimination, which divides by pivots, and it fails over $F[x]$ . For $\mathbf{A} = (0) \in M_1(F)$ , the matrix $x\mathbf{I} - \mathbf{A} = (x)$ has determinant $x \ne 0$ , yet it has no inverse in $M_1(F[x])$ : if $x\,q(x) = 1$ for a polynomial $q$ , then $q \ne 0$ , and $1 + \deg q = \deg 1 = 0$ by Theorem 0.8.3, which is impossible since $\deg q \ge 0$ . Likewise, “divide row $1$ of $x\mathbf{I} - \mathbf{A}$ by $x - 1$ ” produces entries that are not polynomials and that make no sense at $x = 1$ . Compute $p_{\mathbf{A}}$ by expansion, by triangular or block shape, or by the Leibniz formula.

Before looking at the coefficients, we record the fact that makes $p_{\mathbf{A}}$ useful: evaluating it at a scalar $c$ gives the same result as putting $c$ in place of $x$ before taking the determinant.

Lemma 7.10.1 (Evaluating the Characteristic Polynomial)

Let $\mathbf{A} \in M_n(F)$ and $c \in F$ . Then $p_{\mathbf{A}}(c) = \det(c\mathbf{I}_n - \mathbf{A})$ .

Proof. By Theorem 0.8.5, evaluation at $c$ turns sums of polynomials into sums and products into products, and sends a constant $a$ to $a$ . Applying it to the Leibniz sum in Definition 7.10.1 term by term, $p_{\mathbf{A}}(c) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma)\prod_{j=1}^{n}\big(c\,\delta_{\sigma(j)j} - a_{\sigma(j)j}\big),$ and $c\,\delta_{ij} - a_{ij}$ is the $(i, j)$ -entry of $c\mathbf{I}_n - \mathbf{A}$ . By Definition 7.4.1, the right side is $\det(c\mathbf{I}_n - \mathbf{A})$ .

7.10.2. The shape of the characteristic polynomial

The $2 \times 2$ example suggests a pattern: the leading coefficient is $1$ , the next coefficient is minus the trace, and the constant term is the determinant up to sign. The same holds in every size.

Theorem 7.10.2 (Coefficients of the Characteristic Polynomial)

Let $n \ge 1$ and $\mathbf{A} \in M_n(F)$ . Then $p_{\mathbf{A}}$ is monic of degree $n$ , and $p_{\mathbf{A}}(x) = x^n - (\operatorname{tr} \mathbf{A})\,x^{n-1} + \dots + (-1)^n\det \mathbf{A},$ that is, the coefficient of $x^{n-1}$ is $-\operatorname{tr} \mathbf{A}$ and the constant term is $(-1)^n\det \mathbf{A}$ . (For $n = 1$ these two statements concern the same coefficient, and both say it is $-a_{11}$ .)

Idea. Look at the Leibniz sum term by term and count powers of $x$ . A factor $x\delta_{\sigma(j)j} - a_{\sigma(j)j}$ contains $x$ only if $\sigma(j) = j$ . A permutation other than the identity moves at least two indices, so its term has degree at most $n - 2$ and cannot affect the top two coefficients. The identity contributes $\prod_j(x - a_{jj})$ , whose top two coefficients are $1$ and $-\sum_j a_{jj}$ . For the constant term, set $x = 0$ .

Proof. Write $m_{ij} = x\delta_{ij} - a_{ij}$ for the entries of $x\mathbf{I} - \mathbf{A}$ . By Definition 7.10.1, $p_{\mathbf{A}} = \sum_{\sigma} t_\sigma$ with $t_\sigma = \operatorname{sgn}(\sigma)\prod_{j} m_{\sigma(j)j}$ .

Terms with $\sigma \ne \operatorname{id}$ . If $\sigma(j) \ne j$ for some $j$ , then $\sigma(\sigma(j)) \ne \sigma(j)$ , because $\sigma$ is injective. So $\sigma$ moves at least two indices, and at most $n - 2$ indices are fixed. For a moved index $j$ , $m_{\sigma(j)j} = -a_{\sigma(j)j}$ has degree at most $0$ ; for a fixed index it has degree at most $1$ . By Theorem 0.8.3, $\deg t_\sigma \le n - 2$ .

The term $\sigma = \operatorname{id}$ . We show by induction on $k \ge 1$ that $\prod_{j=1}^{k}(x - a_{jj}) = x^k - s_kx^{k-1} + r_k$ with $s_k = a_{11} + \dots + a_{kk}$ and $\deg r_k \le k - 2$ . For $k = 1$ , take $r_1 = 0$ . If it holds for $k$ , then with $a = a_{k+1,k+1}$ , $(x^k - s_kx^{k-1} + r_k)(x - a) = x^{k+1} - (s_k + a)x^k + \big(s_kax^{k-1} + r_kx - ar_k\big),$ and the bracket has degree at most $k - 1$ by Theorem 0.8.2 and Theorem 0.8.3. This completes the induction. Since $\operatorname{sgn}(\operatorname{id}) = 1$ , $t_{\operatorname{id}} = x^n - (\operatorname{tr} \mathbf{A})\,x^{n-1} + r_n$ with $\deg r_n \le n - 2$ .

Adding, $p_{\mathbf{A}} = x^n - (\operatorname{tr} \mathbf{A})\,x^{n-1} + \big(r_n + \sum_{\sigma \ne \operatorname{id}} t_\sigma\big)$ , and the bracket has degree at most $n - 2$ by Theorem 0.8.2. Hence $p_{\mathbf{A}}$ is monic of degree $n$ , with coefficient $-\operatorname{tr} \mathbf{A}$ at $x^{n-1}$ (Definition 0.9.12).

Constant term. The constant term of a polynomial is its value at $0$ (Definition 0.8.6). By Lemma 7.10.1 with $c = 0$ , $p_{\mathbf{A}}(0) = \det(-\mathbf{A})$ . The matrix $-\mathbf{A}$ is obtained from $\mathbf{A}$ by multiplying each of its $n$ columns by $-1$ , so $\det(-\mathbf{A}) = (-1)^n\det \mathbf{A}$ by Theorem 7.5.1 (d). This proves the theorem.

So the characteristic polynomial packages two invariants we already know, the trace and the determinant, and adds $n - 2$ more coefficients in between. For $n = 2$ nothing is in between, which is why $p_{\mathbf{A}}(x) = x^2 - (\operatorname{tr} \mathbf{A})x + \det \mathbf{A}$ for every $2 \times 2$ matrix.

Quick check. Without expanding any determinant, find the coefficient of $x^2$ and the constant term of $p_{\mathbf{A}}$ for $\mathbf{A} = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$ , given that $\det \mathbf{A} = 2$ .

Solution. By Theorem 7.10.2, the coefficient of $x^2$ is $-\operatorname{tr} \mathbf{A} = 0$ , and the constant term is $(-1)^3\det \mathbf{A} = -2$ . (In full, $p_{\mathbf{A}}(x) = x^3 - 3x - 2 = (x - 2)(x + 1)^2$ .)

7.10.3. Similar matrices, same polynomial

Similar matrices describe the same operator in different bases (Theorem 4.2.4), so everything intrinsic to the operator should agree for them. The trace and determinant do (Theorem 4.2.5, Corollary 7.5.7). The characteristic polynomial, which contains both, does too, and the proof is the proof for the determinant, run over $F[x]$ .

Theorem 7.10.3 (Similar Matrices Have the Same Characteristic Polynomial)

If $\mathbf{A}, \mathbf{B} \in M_n(F)$ are similar, then $p_{\mathbf{A}} = p_{\mathbf{B}}$ .

Proof. Let $\mathbf{B} = \mathbf{P}^{-1}\mathbf{A}\mathbf{P}$ with $\mathbf{P} \in M_n(F)$ invertible. Regard $\mathbf{P}$ , $\mathbf{P}^{-1}$ , $\mathbf{A}$ and $\mathbf{I}$ as matrices over $F[x]$ whose entries happen to be constants. The laws of matrix arithmetic in Theorem 0.9.4 are proved from the ring axioms alone, so they hold in $M_n(F[x])$ . Hence $\mathbf{P}^{-1}(x\mathbf{I} - \mathbf{A})\mathbf{P} = x\,\mathbf{P}^{-1}\mathbf{P} - \mathbf{P}^{-1}\mathbf{A}\mathbf{P} = x\mathbf{I} - \mathbf{B} .$ By Theorem 7.5.4, valid over $F[x]$ by the remark in §5, $\begin{aligned} p_{\mathbf{B}} &= \det\big(\mathbf{P}^{-1}(x\mathbf{I} - \mathbf{A})\mathbf{P}\big) = \det(\mathbf{P}^{-1})\,\det(x\mathbf{I} - \mathbf{A})\,\det \mathbf{P} \\ &= \det(\mathbf{P}^{-1})\det(\mathbf{P})\; p_{\mathbf{A}} , \end{aligned}$ using commutativity of $F[x]$ in the last step. Finally $\det(\mathbf{P}^{-1})\det \mathbf{P} = \det(\mathbf{P}^{-1}\mathbf{P}) = \det \mathbf{I} = 1$ by Theorem 7.5.4 over $F$ . Hence $p_{\mathbf{B}} = p_{\mathbf{A}}$ .

This is exactly the case singled out in the remark in §5: the proof of Corollary 7.5.7 survives over $F[x]$ because $\mathbf{P}$ is invertible already over $F$ . The theorem lets us attach a characteristic polynomial to an operator.

Definition 7.10.2 (Characteristic Polynomial of an Operator)

Let $V$ be a vector space over $F$ with $\dim V = n \ge 1$ , and let $T \in \mathcal{L}(V)$ . The characteristic polynomial of $T$ is $p_T(x) \mathrel{:=} p_{[T]_{\mathcal{B}}^{\mathcal{B}}}(x) = \det\big(x\mathbf{I}_n - [T]_{\mathcal{B}}^{\mathcal{B}}\big),$ where $\mathcal{B}$ is any basis of $V$ .

This does not depend on $\mathcal{B}$ : for bases $\mathcal{B}$ and $\mathcal{C}$ , the matrices $[T]_{\mathcal{B}}^{\mathcal{B}}$ and $[T]_{\mathcal{C}}^{\mathcal{C}}$ are similar by Theorem 4.2.4 (a), so they have the same characteristic polynomial by Theorem 7.10.3. By Theorem 7.10.2, $p_T$ is monic of degree $\dim V$ , with coefficient $-\operatorname{tr} T$ at $x^{n-1}$ and constant term $(-1)^n\det T$ (Definition 4.5.2, Definition 7.5.1).

Example (Characteristic Polynomials of Two Operators)

On $V = \mathbb{R}[x]_{\le 2}$ , find the characteristic polynomials of differentiation $D(q) = q'$ and of the shift $S(q)(x) = q(x + 1)$ .

Solution. Use the basis $\mathcal{B} = (1, x, x^2)$ . Since $D(1) = 0$ , $D(x) = 1$ , $D(x^2) = 2x$ , and $S(1) = 1$ , $S(x) = 1 + x$ , $S(x^2) = 1 + 2x + x^2$ , $[D]_{\mathcal{B}}^{\mathcal{B}} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{pmatrix}, \qquad [S]_{\mathcal{B}}^{\mathcal{B}} = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}.$ Both are upper triangular, so $p_D(t) = t^3$ and $p_S(t) = (t - 1)^3$ . (We name the variable $t$ here, since $x$ is already the variable of the polynomials in $V$ .) As a check, $\operatorname{tr} S = 3$ and $\det S = 1$ , matching the coefficient $-3$ of $t^2$ and the constant term $(-1)^3 \cdot 1$ .

Warning. Equal characteristic polynomials do not make matrices similar. The converse of Theorem 7.10.3 is false. Recall the pair from the warning in Chapter 4, §02: $\mathbf{I}_2$ and $\mathbf{J} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ both have characteristic polynomial $(x - 1)^2$ , since both are triangular with diagonal $1, 1$ . But $\mathbf{I}_2$ is similar only to itself, so $\mathbf{J} \not\sim \mathbf{I}_2$ . In particular the characteristic polynomial does not determine the matrix, not even up to similarity. Deciding similarity needs finer invariants; Chapter 10 finds a complete set.

7.10.4. Roots and singular matrices

We can now answer the opening question. The determinant tests invertibility of $c\mathbf{I} - \mathbf{A}$ for one $c$ at a time; the characteristic polynomial tests all $c$ at once, and the answer is a finite set.

Theorem 7.10.4 (Roots of the Characteristic Polynomial)

Let $\mathbf{A} \in M_n(F)$ with $n \ge 1$ , and let $c \in F$ .

(a) The following are equivalent: (i) $p_{\mathbf{A}}(c) = 0$ ; (ii) $c\mathbf{I} - \mathbf{A}$ is not invertible; (iii) there is a non-zero $\mathbf{v} \in F^n$ with $\mathbf{A}\mathbf{v} = c\mathbf{v}$ .
(b) There are at most $n$ scalars $c \in F$ with these properties.

Proof.

(a) By Lemma 7.10.1, $p_{\mathbf{A}}(c) = \det(c\mathbf{I} - \mathbf{A})$ , which is a determinant of a matrix over the field $F$ . By Theorem 7.5.2, it is zero if and only if $c\mathbf{I} - \mathbf{A}$ is not invertible; this is (i) $\Leftrightarrow$ (ii). By Theorem 3.4.4, $c\mathbf{I} - \mathbf{A}$ is not invertible if and only if $(c\mathbf{I} - \mathbf{A})\mathbf{v} = \mathbf{0}$ for some $\mathbf{v} \ne \mathbf{0}$ , and $(c\mathbf{I} - \mathbf{A})\mathbf{v} = c\mathbf{v} - \mathbf{A}\mathbf{v}$ by Theorem 0.9.4; this is (ii) $\Leftrightarrow$ (iii).
(b) By Theorem 7.10.2, $p_{\mathbf{A}}$ is monic of degree $n$ , in particular non-zero. By Corollary 6.1.4, it has at most $n$ distinct roots in $F$ , and by (a) these are exactly the scalars in question.

Notice where the evaluation happens: first substitute $c$ , getting a matrix over the field $F$ , then use the invertibility test, which is valid over fields. That order is what the warning about $F[x]$ above requires.

The same holds for an operator $T$ on $V$ with $\dim V = n \ge 1$ : $p_T(c) = 0$ if and only if $c\,\operatorname{id}_V - T$ is not invertible, by (a) applied to $[T]_{\mathcal{B}}^{\mathcal{B}}$ together with Theorem 4.1.5 (b), since $[c\,\operatorname{id}_V - T]_{\mathcal{B}}^{\mathcal{B}} = c\mathbf{I} - [T]_{\mathcal{B}}^{\mathcal{B}}$ .

The scalars $c$ of this theorem are the eigenvalues of $\mathbf{A}$ , and the vectors $\mathbf{v}$ in (iii) its eigenvectors. They are the subject of Chapter 9, which starts from this theorem.

Examples.

For $\mathbf{A}$ in Example (A $3 \times 3$ Characteristic Polynomial), $p_{\mathbf{A}} = (x - 1)(x - 3)^2$ , so $c\mathbf{I} - \mathbf{A}$ is singular exactly for $c = 1$ and $c = 3$ . For instance $3\mathbf{I} - \mathbf{A} = \begin{pmatrix} 1 & 0 & -1 \\ -1 & 0 & -1 \\ -1 & 0 & 1 \end{pmatrix}$ has a zero column, and $\mathbf{v} = \mathbf{e}_2$ satisfies $\mathbf{A}\mathbf{e}_2 = 3\mathbf{e}_2$ .
The rotation $\mathbf{R} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ has $p_{\mathbf{R}} = x^2 + 1$ . Over $\mathbb{R}$ this has no root, so $c\mathbf{I} - \mathbf{R}$ is invertible for every real $c$ : no non-zero real vector is merely stretched by a quarter-turn. Over $\mathbb{C}$ , the roots $\pm i$ appear, and for example $\mathbf{R}(1, -i) = (i, 1) = i\,(1, -i)$ . The field matters.

Quick check. For which $c \in \mathbb{Q}$ is $c\mathbf{I} - \mathbf{A}$ invertible, where $\mathbf{A} = \begin{pmatrix} 5 & -2 \\ 3 & 0 \end{pmatrix}$ ?

Solution. $p_{\mathbf{A}}(x) = x^2 - (\operatorname{tr} \mathbf{A})x + \det \mathbf{A} = x^2 - 5x + 6 = (x - 2)(x - 3)$ . By Theorem 7.10.4, $c\mathbf{I} - \mathbf{A}$ is invertible exactly for $c \ne 2, 3$ .

7.10.5. A tempting false proof

Here is a statement that is true, and important: every square matrix satisfies its own characteristic polynomial, $p_{\mathbf{A}}(\mathbf{A}) = 0$ . This is the Cayley–Hamilton Theorem, proved in Chapter 9. Here $p_{\mathbf{A}}(\mathbf{A})$ means substituting the matrix $\mathbf{A}$ into the polynomial $p_{\mathbf{A}}$ , replacing each $x^k$ by $\mathbf{A}^k$ and the constant term $a_0$ by $a_0\mathbf{I}$ (Definition 0.9.14). For a $2 \times 2$ matrix it says $\mathbf{A}^2 - (\operatorname{tr} \mathbf{A})\mathbf{A} + (\det \mathbf{A})\mathbf{I} = 0$ , which you can check by multiplying out.

A one-line “proof” suggests itself, and it is wrong.

Warning. The fake proof of Cayley–Hamilton. “Since $p_{\mathbf{A}}(x) = \det(x\mathbf{I} - \mathbf{A})$ , put $x = \mathbf{A}$ : $p_{\mathbf{A}}(\mathbf{A}) = \det(\mathbf{A}\mathbf{I} - \mathbf{A}) = \det(0) = 0$ .” This is invalid for two reasons. First, the two sides are different kinds of object: $p_{\mathbf{A}}(\mathbf{A})$ is an $n \times n$ matrix, while $\det(\cdots)$ is a scalar, so “ $= 0$ ” compares a matrix with a number. Second, Lemma 7.10.1 lets us substitute only a scalar $c \in F$ into the entries of $x\mathbf{I} - \mathbf{A}$ . Substituting a matrix for $x$ inside the entries would produce a matrix whose entries are matrices, and “ $\mathbf{A}\mathbf{I} - \mathbf{A}$ ” silently treats the $x$ in the entry $x - a_{11}$ as if the entry became $\mathbf{A} - a_{11}$ , which is not what substitution into a polynomial means.

The same “argument” proves false statements, which shows it is not a proof. Replace $\det$ by $\operatorname{tr}$ : let $q(x) = \operatorname{tr}(x\mathbf{I} - \mathbf{A}) = nx - \operatorname{tr} \mathbf{A}$ . The fake reasoning gives “ $q(\mathbf{A}) = \operatorname{tr}(\mathbf{A}\mathbf{I} - \mathbf{A}) = \operatorname{tr} 0 = 0$ ”. But for $\mathbf{A} = \operatorname{diag}(1, 0)$ , $q(x) = 2x - 1$ and $q(\mathbf{A}) = 2\mathbf{A} - \mathbf{I} = \operatorname{diag}(1, -1) \ne 0$ .

7.10.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the characteristic polynomial of $\mathbf{A} \in M_n(F)$ , and say in which ring its determinant is computed.
(b) State the degree, leading coefficient, coefficient of $x^{n-1}$ and constant term of $p_{\mathbf{A}}$ .
(c) True or false: $\det(\mathbf{A} - x\mathbf{I}) = p_{\mathbf{A}}(x)$ for every $\mathbf{A} \in M_3(F)$ . Justify your answer.
(d) True or false: if $p_{\mathbf{A}} = p_{\mathbf{B}}$ , then $\mathbf{A} \sim \mathbf{B}$ . Justify your answer.
(e) What does $p_{\mathbf{A}}(c) = 0$ say about the matrix $c\mathbf{I} - \mathbf{A}$ ? About vectors?
(f) Explain in one sentence why “ $p_{\mathbf{A}}(\mathbf{A}) = \det(\mathbf{A}\mathbf{I} - \mathbf{A}) = 0$ ” is not a proof.

Solution.

(a) $p_{\mathbf{A}}(x) = \det(x\mathbf{I}_n - \mathbf{A})$ , the Leibniz sum computed in the commutative ring $F[x]$ (Definition 7.10.1).
(b) Degree $n$ , leading coefficient $1$ , coefficient $-\operatorname{tr} \mathbf{A}$ at $x^{n-1}$ , constant term $(-1)^n\det \mathbf{A}$ (Theorem 7.10.2).
(c) False. $\det(\mathbf{A} - x\mathbf{I}) = (-1)^3p_{\mathbf{A}}(x) = -p_{\mathbf{A}}(x)$ , since each of the three columns changes sign. For $\mathbf{A} = 0$ , $\det(-x\mathbf{I}_3) = -x^3 \ne x^3 = p_{\mathbf{A}}(x)$ .
(d) False. $\mathbf{I}_2$ and $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ both have $p = (x - 1)^2$ but are not similar.
(e) $c\mathbf{I} - \mathbf{A}$ is not invertible; equivalently there is a non-zero $\mathbf{v}$ with $\mathbf{A}\mathbf{v} = c\mathbf{v}$ (Theorem 7.10.4).
(f) $p_{\mathbf{A}}(\mathbf{A})$ is a matrix obtained by substituting $\mathbf{A}$ into a polynomial, while $\det(\mathbf{A}\mathbf{I} - \mathbf{A})$ is a scalar, and substitution into the entries of $x\mathbf{I} - \mathbf{A}$ is only justified for scalars (Lemma 7.10.1).

B. Practice

Exercise (B1: Computing characteristic polynomials)

Find the characteristic polynomial of each matrix over $\mathbb{Q}$ , factor it as far as possible over $\mathbb{Q}$ , and check the trace and determinant against Theorem 7.10.2. $\mathbf{A} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 2 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 1 & -1 \end{pmatrix}.$ Hence list the $c \in \mathbb{Q}$ for which $c\mathbf{I} - \mathbf{A}$ , respectively $c\mathbf{I} - \mathbf{B}$ , is not invertible.

Solution. For $\mathbf{A}$ . Expanding $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x - 1 & -1 & 0 \\ 0 & x - 1 & -1 \\ -1 & 0 & x - 1 \end{pmatrix}$ along the first row (Theorem 7.6.1 over $F[x]$ ), $\begin{aligned} p_{\mathbf{A}}(x) &= (x - 1)\big((x - 1)^2 - 0\big) - (-1)\big(0 - 1\big) + 0 \\ &= (x - 1)^3 - 1 = x^3 - 3x^2 + 3x - 2 . \end{aligned}$ Check: $-\operatorname{tr} \mathbf{A} = -3$ ; $\det \mathbf{A} = 1\cdot(1 - 0) - 1\cdot(0 - 1) + 0 = 2$ , and $(-1)^3 \cdot 2 = -2$ . Since $p_{\mathbf{A}}(2) = 1 - 1 = 0$ , divide by $x - 2$ : $p_{\mathbf{A}} = (x - 2)(x^2 - x + 1)$ . The quadratic has discriminant $1 - 4 = -3 < 0$ , so no rational (indeed no real) root. By Theorem 7.10.4, $c\mathbf{I} - \mathbf{A}$ is singular only for $c = 2$ .

For $\mathbf{B}$ . $x\mathbf{I} - \mathbf{B}$ is block upper triangular with diagonal blocks $x\mathbf{I} - \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$ and $x\mathbf{I} - \begin{pmatrix} 1 & 3 \\ 1 & -1 \end{pmatrix}$ . By Theorem 7.8.4 over $F[x]$ and the $2 \times 2$ formula, $p_{\mathbf{B}}(x) = (x - 2)^2\,\big(x^2 - 0\cdot x + (-1 - 3)\big) = (x - 2)^2(x^2 - 4) = (x - 2)^3(x + 2) .$ Multiplied out, $p_{\mathbf{B}} = x^4 - 4x^3 + 16x - 16$ . Check: $-\operatorname{tr} \mathbf{B} = -(2 + 2 + 1 - 1) = -4$ ; $\det \mathbf{B} = 4 \cdot (-4) = -16$ by Theorem 7.8.4, and $(-1)^4(-16) = -16$ . So $c\mathbf{I} - \mathbf{B}$ is singular exactly for $c = 2$ and $c = -2$ .

Exercise (B2: Transpose)

Prove that $p_{\mathbf{A}^{\top}} = p_{\mathbf{A}}$ for every $\mathbf{A} \in M_n(F)$ . Hence show that $c\mathbf{I} - \mathbf{A}$ is invertible if and only if $c\mathbf{I} - \mathbf{A}^{\top}$ is.

Solution. By Theorem 0.9.5, $(x\mathbf{I} - \mathbf{A})^{\top} = x\mathbf{I}^{\top} - \mathbf{A}^{\top} = x\mathbf{I} - \mathbf{A}^{\top}$ ; these rules are proved entrywise from the ring axioms, so they hold over $F[x]$ . By Theorem 7.4.5, which holds over $F[x]$ by the remark in §4, $p_{\mathbf{A}^{\top}} = \det(x\mathbf{I} - \mathbf{A}^{\top}) = \det\big((x\mathbf{I} - \mathbf{A})^{\top}\big) = \det(x\mathbf{I} - \mathbf{A}) = p_{\mathbf{A}} .$ By Theorem 7.10.4, $c\mathbf{I} - \mathbf{A}$ is not invertible exactly when $p_{\mathbf{A}}(c) = 0$ , which is exactly when $p_{\mathbf{A}^{\top}}(c) = 0$ , that is, when $c\mathbf{I} - \mathbf{A}^{\top}$ is not invertible.

Exercise (B3:

\mathbf{A}\mathbf{B}

and

\mathbf{B}\mathbf{A}

)

Let $\mathbf{A}, \mathbf{B} \in M_n(F)$ with $\mathbf{A}$ invertible.

(a) Show that $\mathbf{B}\mathbf{A} = \mathbf{A}^{-1}(\mathbf{A}\mathbf{B})\mathbf{A}$ , and deduce $p_{\mathbf{A}\mathbf{B}} = p_{\mathbf{B}\mathbf{A}}$ .
(b) Deduce that $\operatorname{tr}(\mathbf{A}\mathbf{B}) = \operatorname{tr}(\mathbf{B}\mathbf{A})$ and $\det(\mathbf{A}\mathbf{B}) = \det(\mathbf{B}\mathbf{A})$ in this case.
(c) Check (a) for $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ , $\mathbf{B} = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ , and note that $\mathbf{A}\mathbf{B} \ne \mathbf{B}\mathbf{A}$ .

(Chapter 9 removes the hypothesis that $\mathbf{A}$ is invertible.)

Solution.

(a) By associativity, $\mathbf{A}^{-1}(\mathbf{A}\mathbf{B})\mathbf{A} = (\mathbf{A}^{-1}\mathbf{A})(\mathbf{B}\mathbf{A}) = \mathbf{B}\mathbf{A}$ . So $\mathbf{B}\mathbf{A} \sim \mathbf{A}\mathbf{B}$ (Definition 4.2.2, with $\mathbf{P} = \mathbf{A}$ ), and $p_{\mathbf{A}\mathbf{B}} = p_{\mathbf{B}\mathbf{A}}$ by Theorem 7.10.3.
(b) By Theorem 7.10.2, the coefficient of $x^{n-1}$ is $-\operatorname{tr}(\mathbf{A}\mathbf{B})$ in $p_{\mathbf{A}\mathbf{B}}$ and $-\operatorname{tr}(\mathbf{B}\mathbf{A})$ in $p_{\mathbf{B}\mathbf{A}}$ ; the constant terms are $(-1)^n\det(\mathbf{A}\mathbf{B})$ and $(-1)^n\det(\mathbf{B}\mathbf{A})$ . Equal polynomials have equal coefficients.
(c) $\mathbf{A}\mathbf{B} = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$ and $\mathbf{B}\mathbf{A} = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$ , so $\mathbf{A}\mathbf{B} \ne \mathbf{B}\mathbf{A}$ . Both have trace $1$ and determinant $0$ , so both characteristic polynomials are $x^2 - x = x(x - 1)$ .

C. Going deeper

Exercise (C1: Companion matrices)

Let $n \ge 2$ and $p(x) = x^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 \in F[x]$ . The companion matrix of $p$ is the matrix $\mathbf{C}(p) \in M_n(F)$ with $1$ in each position $(i + 1, i)$ just below the diagonal, last column $(-a_0, -a_1, \dots, -a_{n-1})$ , and $0$ elsewhere: $\mathbf{C}(p) = \begin{pmatrix} 0 & 0 & \cdots & 0 & -a_0 \\ 1 & 0 & \cdots & 0 & -a_1 \\ 0 & 1 & \cdots & 0 & -a_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & -a_{n-1} \end{pmatrix}.$ (The matrix $\mathbf{C}$ of Exercise (B2: An annihilating polynomial by elimination) is $\mathbf{C}(x^3 - 2x^2 + x - 2)$ .)

(a) Let $\mathbf{M} = x\mathbf{I} - \mathbf{C}(p)$ . For each $i$ , show that deleting row $i$ and column $n$ of $\mathbf{M}$ leaves a block diagonal matrix whose blocks are an $(i - 1) \times (i - 1)$ lower triangular matrix with diagonal $x, \dots, x$ and an $(n - i) \times (n - i)$ upper triangular matrix with diagonal $-1, \dots, -1$ (either block may be absent when $i = 1$ or $i = n$ ). Deduce that the cofactor $C_{in}$ of $\mathbf{M}$ equals $x^{i-1}$ .
(b) Deduce, by expanding along the last column, that $p_{\mathbf{C}(p)} = p$ .
(c) Verify (b) for $p = x^4 + x^3 - 2x + 3$ by writing $\mathbf{C}(p)$ and checking the coefficients predicted by Theorem 7.10.2.
(d) Deduce that every monic polynomial of degree $n \ge 1$ over $F$ is the characteristic polynomial of some $n \times n$ matrix over $F$ .

Solution.

(a) The entries of $\mathbf{M}$ are: $x$ at $(j, j)$ for $j < n$ ; $-1$ at $(j + 1, j)$ ; $a_{j-1}$ at $(j, n)$ for $j < n$ ; $x + a_{n-1}$ at $(n, n)$ ; $0$ elsewhere. Delete row $i$ and column $n$ . In the remaining matrix, rows $1, \dots, i - 1$ have non-zero entries only in columns $j - 1$ and $j$ for row $j$ , all at most $i - 1$ ; and rows $i + 1, \dots, n$ have non-zero entries only in columns $j - 1$ and $j \le n - 1$ , all at least $i$ . So the matrix is block diagonal with blocks on rows and columns $\{1, \dots, i-1\}$ and on rows $\{i + 1, \dots, n\}$ , columns $\{i, \dots, n - 1\}$ . The first block has $x$ on its diagonal and $-1$ just below it, so it is lower triangular. In the second block, row $j$ of $\mathbf{M}$ (for $j > i$ ) has $-1$ in column $j - 1$ , which is the diagonal position of the block, and $x$ in column $j$ , one step to the right; so it is upper triangular with diagonal $-1, \dots, -1$ . By Theorem 7.8.4 and Theorem 7.4.6 over $F[x]$ (both division-free), the minor is $M_{in} = x^{i-1}(-1)^{n-i}$ , where an absent block contributes the factor $1$ (for $i = 1$ or $i = n$ the matrix is a single triangular block). Hence $C_{in} = (-1)^{i+n}(-1)^{n-i}x^{i-1} = (-1)^{2n}x^{i-1} = x^{i-1}$ .
(b) By Theorem 7.6.1 along column $n$ , valid over $F[x]$ , $\begin{aligned} p_{\mathbf{C}(p)} &= \det \mathbf{M} = \sum_{i=1}^{n-1} a_{i-1}\,x^{i-1} + (x + a_{n-1})\,x^{n-1} \\ &= a_0 + a_1x + \dots + a_{n-1}x^{n-1} + x^n = p . \end{aligned}$
(c) Here $a_3 = 1$ , $a_2 = 0$ , $a_1 = -2$ , $a_0 = 3$ , so $\mathbf{C}(p) = \begin{pmatrix} 0 & 0 & 0 & -3 \\ 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{pmatrix}.$ Its trace is $-1$ , so Theorem 7.10.2 predicts the coefficient $1 = a_3$ at $x^3$ , as in $p$ . Its determinant, expanding along the first row, whose only non-zero entry is $-3$ in position $(1, 4)$ , is $(-3)(-1)^{1+4}\det \mathbf{I}_3 = 3$ , since deleting row $1$ and column $4$ leaves $\mathbf{I}_3$ . So the predicted constant term is $(-1)^4 \cdot 3 = 3 = a_0$ .
(d) For $n \ge 2$ , take $\mathbf{C}(p)$ and use (b). For $n = 1$ , $p = x + a_0$ is $p_{(-a_0)}$ .

Exercise (C2: Nilpotent

2 \times 2

matrices)

Let $\mathbf{A} \in M_2(F)$ satisfy $\mathbf{A}^k = 0$ for some $k \ge 1$ .

(a) Show that the constant term of $p_{\mathbf{A}}$ is $0$ .
(b) By multiplying out, verify that $\mathbf{A}^2 - (\operatorname{tr} \mathbf{A})\mathbf{A} + (\det \mathbf{A})\mathbf{I} = 0$ for every $\mathbf{A} \in M_2(F)$ .
(c) Deduce that $\operatorname{tr} \mathbf{A} = 0$ , and hence $p_{\mathbf{A}} = x^2$ and $\mathbf{A}^2 = 0$ .
(d) Give an example showing that $\mathbf{A}^2 = 0$ does not force $\mathbf{A} = 0$ .

Solution.

(a) By Theorem 7.5.4, $(\det \mathbf{A})^k = \det(\mathbf{A}^k) = \det 0 = 0$ , so $\det \mathbf{A} = 0$ because a field has no zero divisors (Theorem 0.7.1). The constant term is $(-1)^2\det \mathbf{A} = 0$ by Theorem 7.10.2.
(b) Let $\mathbf{A} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ . Then $\mathbf{A}^2 = \begin{pmatrix} a^2 + bc & ab + bd \\ ca + dc & bc + d^2 \end{pmatrix}$ and $(a + d)\mathbf{A} = \begin{pmatrix} a^2 + ad & ab + bd \\ ac + dc & ad + d^2 \end{pmatrix}$ . The difference is $\begin{pmatrix} bc - ad & 0 \\ 0 & bc - ad \end{pmatrix} = -(\det \mathbf{A})\mathbf{I}$ , as claimed.
(c) By (a) and (b), $\mathbf{A}^2 = (\operatorname{tr} \mathbf{A})\mathbf{A}$ . By induction, $\mathbf{A}^m = (\operatorname{tr} \mathbf{A})^{m-1}\mathbf{A}$ for all $m \ge 1$ : if it holds for $m$ , then $\mathbf{A}^{m+1} = (\operatorname{tr} \mathbf{A})^{m-1}\mathbf{A}^2 = (\operatorname{tr} \mathbf{A})^m\mathbf{A}$ . If $\mathbf{A} = 0$ , then $\operatorname{tr} \mathbf{A} = 0$ . If $\mathbf{A} \ne 0$ , then $0 = \mathbf{A}^k = (\operatorname{tr} \mathbf{A})^{k-1}\mathbf{A}$ forces $(\operatorname{tr} \mathbf{A})^{k-1} = 0$ , since a non-zero matrix times a scalar is zero only if the scalar is zero; here $k \ge 2$ , because $k = 1$ would give $\mathbf{A} = 0$ . Hence $\operatorname{tr} \mathbf{A} = 0$ by Theorem 0.7.1 (f), applied repeatedly. So $p_{\mathbf{A}} = x^2 - 0\cdot x + 0 = x^2$ , and $\mathbf{A}^2 = (\operatorname{tr} \mathbf{A})\mathbf{A} = 0$ .
(d) $\mathbf{A} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ has $\mathbf{A}^2 = 0$ and $\mathbf{A} \ne 0$ .

Exercise (C3: Odd size over the reals)

Let $n$ be odd and $\mathbf{A} \in M_n(\mathbb{R})$ .

(a) Prove that there is $c \in \mathbb{R}$ and a non-zero $\mathbf{v} \in \mathbb{R}^n$ with $\mathbf{A}\mathbf{v} = c\mathbf{v}$ .
(b) Show by an example that (a) fails for $n = 2$ .
(c) Show that (a) holds for every $\mathbf{A} \in M_n(\mathbb{C})$ and every $n \ge 1$ .

Solution.

(a) By Theorem 7.10.2, $p_{\mathbf{A}} \in \mathbb{R}[x]$ has odd degree $n$ . By Corollary 6.5.9, it has a real root $c$ . By Theorem 7.10.4, there is a non-zero $\mathbf{v} \in \mathbb{R}^n$ with $\mathbf{A}\mathbf{v} = c\mathbf{v}$ .
(b) The rotation $\mathbf{R} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ has $p_{\mathbf{R}} = x^2 + 1$ , with no real root; by Theorem 7.10.4 no real $c$ and non-zero real $\mathbf{v}$ satisfy $\mathbf{R}\mathbf{v} = c\mathbf{v}$ .
(c) $p_{\mathbf{A}} \in \mathbb{C}[x]$ has degree $n \ge 1$ , so it has a root $c \in \mathbb{C}$ by Theorem 6.5.1. Apply Theorem 7.10.4 over $F = \mathbb{C}$ .