7.3 The characteristic polynomial

In Section 7.2 we found eigenvalues by solving $𝑇 𝐯 = 𝜆 𝐯$ by hand, with a separate argument for each operator. Theorem 7.2.9 points to a systematic method: $𝜆$ is an eigenvalue of $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ exactly when $det (𝐴 - 𝜆 𝐼_{𝑛}) = 0$ . If we leave $𝜆$ unknown and call it $𝑥$ , the Leibniz formula turns $det (𝑥 𝐼_{𝑛} - 𝐴)$ into a polynomial of degree $𝑛$ in $𝑥$ , and the eigenvalues of $𝐴$ are its roots. This section makes that precise, reads the trace and the determinant of $𝐴$ off the coefficients, and shows that every monic polynomial occurs. It also settles the existence question raised by the rotation in Example 7.2.18. Over $ℂ$ every operator on a nonzero finite-dimensional space has an eigenvalue, and we prove this twice, once with the characteristic polynomial and once without determinants.

7.3.1Determinants with polynomial entries

The matrix $𝑥 𝐼_{𝑛} - 𝐴$ has entries in $𝐹 [𝑥]$ , and $𝐹 [𝑥]$ is not a field: $𝑥$ has no multiplicative inverse in $𝐹 [𝑥]$ (Corollary 7.1.7). Chapter 5 defined the determinant only for matrices with entries in a field. So before we can write $det (𝑥 𝐼_{𝑛} - 𝐴)$ , we have to say what it means and which rules it obeys.

Intuition (What the Leibniz formula needs). The Leibniz formula (Theorem 5.3.3) builds

det 𝐴

out of the entries of

𝐴

with additions, subtractions, and multiplications, and never divides. So it makes sense for entries from any commutative ring (Definition 1.1.20), and for

𝐹 [𝑥]

in particular (Proposition 7.1.3). The real question is which theorems of Chapter 5 survive. Most facts there were proved twice: once by row reduction, which divides by pivots, and once from the Leibniz formula or from the uniqueness of multilinear alternating functions, which do not divide. The second kind of proof works over a commutative ring word for word. The one statement that changes is the invertibility criterion, because in a ring a nonzero element need not be invertible.

Definition 7.3.1 (Determinant over a commutative ring). Let $𝑅$ be a commutative ring and $𝑛 \geq 1$ . We write $𝑅^{𝑛 \times 𝑛}$ for the set of $𝑛 \times 𝑛$ arrays $𝑀 = (𝑚_{𝑖 𝑗})$ with entries in $𝑅$ , and add, multiply, and transpose such arrays by the same formulas as matrices over a field. The determinant of $𝑀 \in 𝑅^{𝑛 \times 𝑛}$ is

det 𝑀 = \sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) 𝑚_{𝜎 (1) 1} 𝑚_{𝜎 (2) 2} \dots 𝑚_{𝜎 (𝑛) 𝑛} \in 𝑅,

where $sgn (𝜎) \in {1, - 1}$ is read in $𝑅$ . When $𝑅 = 𝐹$ is a field, this is the determinant of Definition 5.3.6, by Theorem 5.3.3.

For example, with $𝑅 = 𝐹 [𝑥]$ ,

det (\begin{matrix} 𝑥 - 𝑎 & - 𝑏 \\ - 𝑐 & 𝑥 - 𝑑 \end{matrix}) = (𝑥 - 𝑎) (𝑥 - 𝑑) - (- 𝑏) (- 𝑐) = 𝑥^{2} - (𝑎 + 𝑑) 𝑥 + (𝑎 𝑑 - 𝑏 𝑐) .

Proposition 7.3.2 (Determinants over a commutative ring). Let $𝑅$ and $𝑅^{'}$ be commutative rings, $𝑛 \geq 1$ , and $𝑀, 𝑁 \in 𝑅^{𝑛 \times 𝑛}$ .

(a)Multiplication in $𝑅^{𝑛 \times 𝑛}$ is associative and distributes over addition, $(𝑟 𝑀) 𝑁 =$ $𝑟 (𝑀 𝑁) =$ $𝑀 (𝑟 𝑁)$ for $𝑟 \in 𝑅$ , and the array $𝐼_{𝑛}$ with $1$ on the diagonal and $0$ elsewhere is a two-sided identity. In particular the scalar arrays $𝑟 𝐼_{𝑛}$ commute with every array.
(b) $det$ is linear in each column (with coefficients in $𝑅$ ), it vanishes when two columns are equal, and $det 𝐼_{𝑛} = 1$ . Every function $𝐷 : 𝑅^{𝑛 \times 𝑛} \to 𝑅$ with these first two properties satisfies $𝐷 (𝑀) =$ $𝐷 (𝐼_{𝑛}) det 𝑀$ .
(c) $det (𝑀 𝑁) =$ $det 𝑀 det 𝑁$ .
(d) $det 𝑀^{𝖳} = det 𝑀$ . So (b) holds for rows as well as columns.
(e)If $𝑀 = (\begin{matrix} 𝑃 & 𝑄 \\ 0 & 𝑆 \end{matrix})$ with square blocks $𝑃$ and $𝑆$ , then $det 𝑀 = det 𝑃 det 𝑆$ . In particular, if $𝑀$ is upper or lower triangular, then $det 𝑀 =$ $𝑚_{11} 𝑚_{22} \dots 𝑚_{𝑛 𝑛}$ .
(f)For $𝑛 \geq 2$ , cofactor expansion along any row or column computes $det 𝑀$ , and $𝑀 adj (𝑀) =$ $adj (𝑀) 𝑀 =$ $(det 𝑀) 𝐼_{𝑛}$ .
(g)Let $𝜑 : 𝑅 \to 𝑅^{'}$ satisfy $𝜑 (𝑎 + 𝑏) =$ $𝜑 (𝑎) +$ $𝜑 (𝑏)$ , $𝜑 (𝑎 𝑏) =$ $𝜑 (𝑎) 𝜑 (𝑏)$ , and $𝜑 (1) = 1$ for all $𝑎, 𝑏 \in 𝑅$ , and write $𝜑 (𝑀) =$ $(𝜑 (𝑚_{𝑖 𝑗}))$ . Then $det 𝜑 (𝑀) =$ $𝜑 (det 𝑀)$ .

Proof.standard

Uses. Definition 7.3.1 (Determinant over a commutative ring), Proposition 2.4.14 (Algebra of matrices), Theorem 5.3.4 (Existence and uniqueness of the determinant), Theorem 5.3.3 (The Leibniz formula), Theorem 5.4.10 (Multiplicativity), Theorem 5.4.14 (The transpose), Theorem 5.4.26 (Block-triangular matrices), Proposition 5.3.15 (Triangular matrices), Theorem 5.5.3 (Cofactor expansion), Theorem 5.5.9 (The adjugate and the inverse), Definition 1.1.20 (Commutative ring)

Techniques. Cancel terms in pairs (Technique 5.3.5), Recognize the determinant by its axioms (Technique 5.4.11)

Hint 1. For (a)–(f), go back to Chapter 5 and, for each fact, find a proof that never divides. Which proofs used row reduction, and which used only the Leibniz formula or the uniqueness of multilinear alternating functions?

Hint 2. Alternation is the delicate point: the shortcut “

𝐿 (𝐴) = - 𝐿 (𝐴)

” divides by

1 + 1

. The proof of Theorem 5.3.4 cancelled terms in pairs instead.

Hint 3. For (g), apply

𝜑

to the Leibniz sum term by term. You need

𝜑 (0) = 0

and

𝜑 (- 𝑎) = - 𝜑 (𝑎)

; derive them from additivity.

Sketch. Each of (a)–(f) has a proof in Chapter 5 that uses only the commutative ring axioms: entrywise computation for (a); the Leibniz formula, pairing

𝜎

with

𝜎 𝜏

, for (b); uniqueness for (c), since

𝐛 \mapsto det (𝑀 𝐛)

is multilinear and alternating; reindexing by

𝜎^{- 1}

for (d); the Leibniz formula for (e) and (f). For (g),

𝜑 (0) = 0

and

𝜑 (- 𝑎) = - 𝜑 (𝑎)

follow from additivity, so

𝜑

maps each Leibniz term of

𝑀

to the corresponding term of

𝜑 (𝑀)

We go through Chapter 5 and point, for each statement, to an argument that uses only the commutative ring axioms, that is, never divides and never uses $1 + 1 \neq 0$ .

(a) The entrywise proof of Proposition 2.4.14 compares the entries of both sides, each of which is a sum of products of entries, using associativity, commutativity, and distributivity in the scalars. These hold in $𝑅$ .

(b) The proof of Theorem 5.3.4 (parts 2 and 3) shows that the Leibniz formula is normalized, linear in each column, and alternating. Normalization and multilinearity are checked term by term, since each term contains exactly one entry from each column. Alternation is proved by pairing each even $𝜎$ with $𝜎 𝜏$ , where $𝜏$ swaps the two equal columns, and the two terms cancel (Technique 5.3.5). None of this divides. The last statement is Theorem 5.3.3. Its proof expands $𝐷 (𝑀)$ by multilinearity into a sum over functions $[𝑛] \to [𝑛]$ , discards the non-injective ones because $𝐷$ vanishes on arrays with two equal columns, and evaluates $𝐷$ on permuted identity columns with Theorem 5.2.31; these steps use multilinearity, alternation, and the ring axioms only.

(c) We use the second proof of Theorem 5.4.10 (Technique 5.4.11). Fix $𝑀$ and let $𝐷 (𝑁) = det (𝑀 𝑁)$ . Column $𝑗$ of $𝑀 𝑁$ is $𝑀$ times column $𝑗$ of $𝑁$ , so $𝐷$ is linear in each column of $𝑁$ by (a) and (b), and two equal columns of $𝑁$ give two equal columns of $𝑀 𝑁$ , where $det$ vanishes. By (b), $𝐷 (𝑁) =$ $𝐷 (𝐼_{𝑛}) det 𝑁 =$ $det 𝑀 det 𝑁$ .

(d) The second proof of Theorem 5.4.14 reindexes the Leibniz sum by $𝜎 \mapsto 𝜎^{- 1}$ and uses $sgn (𝜎^{- 1}) = sgn (𝜎)$ ; this is ring arithmetic.

(e) In the Leibniz formula for $(\begin{matrix} 𝑃 & 𝑄 \\ 0 & 𝑆 \end{matrix})$ , with $𝑃$ of size $𝑘 \times 𝑘$ , a term can be nonzero only if $𝜎$ maps ${1, \dots, 𝑘}$ into itself, and then the term is a product of a Leibniz term of $𝑃$ and one of $𝑆$ . This is the proof of Theorem 5.4.26 via the Leibniz formula, and the triangular case is the Leibniz proof of Proposition 5.3.15. Lower block-triangular arrays follow by (d).

(f) The second proof of Theorem 5.5.3 derives the expansion from the Leibniz formula by regrouping its terms, using the signs of cycles and the multiplicativity of $sgn$ , and gets the row version from (d). The identity $𝑀 adj (𝑀) =$ $(det 𝑀) 𝐼_{𝑛}$ is proved in Theorem 5.5.9 by expanding along a row and noting that expansion along the “wrong” row computes the determinant of an array with two equal rows, which is $0$ by (b) and (d). Neither step divides.

(g) First, $𝜑 (0) =$ $𝜑 (0 + 0) =$ $𝜑 (0) +$ $𝜑 (0)$ , so $𝜑 (0) = 0$ ; and $𝜑 (𝑎) +$ $𝜑 (- 𝑎) =$ $𝜑 (0) =$ $0$ , so $𝜑 (- 𝑎) = - 𝜑 (𝑎)$ . Hence $𝜑 (sgn (𝜎)) =$ $sgn (𝜎)$ , and since $𝜑$ respects sums and products of any finite length,

𝜑 (det 𝑀) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝜑 (sgn (𝜎)) 𝜑 (𝑚_{𝜎 (1) 1}) \dots 𝜑 (𝑚_{𝜎 (𝑛) 𝑛}) = det 𝜑 (𝑀) .

□

The most important instance of (g) is evaluation. For $𝑀 \in {𝐹 [𝑥]}^{𝑛 \times 𝑛}$ and $𝜆 \in 𝐹$ , let $𝑀 (𝜆) \in 𝐹^{𝑛 \times 𝑛}$ be the matrix obtained by evaluating every entry at $𝜆$ . Evaluation respects sums, products, and $1$ (Proposition 7.1.10), so

(det 𝑀) (𝜆) = det 𝑀 (𝜆) .

(7.3.1)

In words, it does not matter whether we first compute the determinant as a polynomial and then plug in $𝜆$ , or first plug in $𝜆$ and then compute a determinant of scalars. The same holds for substituting a polynomial $𝑟 \in 𝐹 [𝑥]$ for $𝑥$ in every entry (also Proposition 7.1.10), and for complex conjugation of the coefficients of polynomials in $ℂ [𝑥]$ (Lemma 7.1.37).

Remark 7.3.3 (What does not carry over). Over a field,

𝑀

is invertible if and only if

det 𝑀 \neq 0

(Theorem 5.4.7). Over

𝐹 [𝑥]

this fails:

det (𝑥 𝐼_{𝑛}) =

𝑥^{𝑛} \neq

𝟎

, but

𝑥 𝐼_{𝑛}

has no inverse in

{𝐹 [𝑥]}^{𝑛 \times 𝑛}

: if

(𝑥 𝐼_{𝑛}) 𝑁 = 𝐼_{𝑛}

, then

𝑥 𝑛_{11} = 1

, which is impossible by Corollary 7.1.7(c). The proof of Theorem 5.4.7 used row reduction, which divides by pivots. What survives is (f): if

det 𝑀

has an inverse in

𝑅

, then

{(det 𝑀)}^{- 1} adj (𝑀)

is an inverse of

𝑀

. The converse also holds, by (c):

𝑀 𝑁 = 𝐼_{𝑛}

gives

det 𝑀 det 𝑁 = 1

. So

𝑀

is invertible in

𝑅^{𝑛 \times 𝑛}

exactly when

det 𝑀

is invertible in

𝑅

, which for

𝑅 = 𝐹 [𝑥]

means that

det 𝑀

is a nonzero constant. We will not need this, but it explains why nothing like “

det (𝑥 𝐼_{𝑛} - 𝐴) \neq 𝟎

, so

𝑥 𝐼_{𝑛} - 𝐴

is invertible” can be used.

Aside (Rational functions). There is a second way to make sense of

det (𝑥 𝐼_{𝑛} - 𝐴)

. Fractions

𝑝 / 𝑞

of polynomials with

𝑞 \neq 𝟎

, with the usual rules for fractions, form a field

𝐹 (𝑥)

that contains

𝐹 [𝑥]

, in the same way that

ℚ

contains

ℤ

. All of Chapter 5 applies to matrices over

𝐹 (𝑥)

, and the Leibniz formula shows that a matrix with polynomial entries has a polynomial determinant. This route gives everything in Proposition 7.3.2 for

𝑅 = 𝐹 [𝑥]

at once, at the cost of constructing

𝐹 (𝑥)

. We stay with commutative rings, which we need anyway for (g).

7.3.2The characteristic polynomial

Definition 7.3.4 (Characteristic polynomial). Let $𝑛 \geq 1$ and $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . The characteristic polynomial of $𝐴$ is

𝑝_{𝐴} = det (𝑥 𝐼_{𝑛} - 𝐴) \in 𝐹 [𝑥],

the determinant (Definition 7.3.1) of the matrix $𝑥 𝐼_{𝑛} -$ $𝐴 \in$ ${𝐹 [𝑥]}^{𝑛 \times 𝑛}$ , whose diagonal entries are $𝑥 - 𝑎_{𝑖 𝑖}$ and whose off-diagonal entries are the constants $- 𝑎_{𝑖 𝑗}$ . When the polynomial is evaluated, we write $𝑝_{𝐴} (𝜆)$ for its value at $𝜆 \in 𝐹$ .

Some texts, including the lecture notes, use $det (𝐴 - 𝑥 𝐼_{𝑛})$ instead. Multiplying each of the $𝑛$ columns by $- 1$ shows $det (𝐴 - 𝑥 𝐼_{𝑛}) =$ ${(- 1)}^{𝑛} 𝑝_{𝐴}$ (Proposition 7.3.2(b)), so the two conventions differ by a sign and have the same roots. With our sign, $𝑝_{𝐴}$ is monic (Proposition 7.3.18).

Example 7.3.5 (Small cases).

(a)For $𝐴 = (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})$ , the computation after Definition 7.3.1 gives
$𝑝_{𝐴} = 𝑥^{2} - (𝑎 + 𝑑) 𝑥 + (𝑎 𝑑 - 𝑏 𝑐) = 𝑥^{2} - (tr 𝐴) 𝑥 + det 𝐴 .$
(b)For $𝐴 = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix})$ of Example 7.2.8, $𝑝_{𝐴} =$ $𝑥^{2} -$ $4 𝑥 +$ $3 =$ $(𝑥 - 1) (𝑥 - 3)$ , and its roots $1$ and $3$ are the eigenvalues found there.
(c)For the rotation $𝐴 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ of Example 7.2.18, $𝑝_{𝐴} = 𝑥^{2} + 1$ . It has no root in $ℝ$ or $𝔽_{3}$ , the roots $\pm 𝑖$ in $ℂ$ , and the roots $2, 3$ in $𝔽_{5}$ , matching the eigenvalues found there field by field.
(d)If $𝐴$ is upper triangular, so is $𝑥 𝐼_{𝑛} - 𝐴$ , with diagonal entries $𝑥 - 𝑎_{𝑖 𝑖}$ . By Proposition 7.3.2(e),
$𝑝_{𝐴} = (𝑥 - 𝑎_{11}) (𝑥 - 𝑎_{22}) \dots (𝑥 - 𝑎_{𝑛 𝑛}) .$
For instance, $𝑝_{𝐴} = {(𝑥 - 2)}^{2}$ for $𝐴 = (\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix})$ , the matrix of Example 7.2.39 in its chain basis.

Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

and

𝜆 \in 𝐹

. Then

𝜆

is an eigenvalue of

𝐴

if and only if

𝑝_{𝐴} (𝜆) = 0

Proof.routine

Uses. Theorem 7.2.9 (Eigenvalues and invertibility), Proposition 7.3.2 (Determinants over a commutative ring), Proposition 7.1.10 (Evaluation respects sums and products), Definition 7.3.4 (Characteristic polynomial)

Hint 1. Theorem 7.2.9 already says that

𝜆

is an eigenvalue if and only if

det (𝐴 - 𝜆 𝐼_{𝑛}) = 0

. How is that number related to the polynomial

𝑝_{𝐴}

Hint 2. Evaluate

𝑥 𝐼_{𝑛} - 𝐴

entry by entry at

𝜆

and use (7.3.1).

Sketch. By (7.3.1),

𝑝_{𝐴} (𝜆) =

det (𝜆 𝐼_{𝑛} - 𝐴) =

{(- 1)}^{𝑛} det (𝐴 - 𝜆 𝐼_{𝑛})

, which vanishes exactly when

𝜆

is an eigenvalue, by Theorem 7.2.9.

Evaluating every entry of

𝑥 𝐼_{𝑛} - 𝐴

𝜆

gives

𝜆 𝐼_{𝑛} - 𝐴

, so by (7.3.1),

𝑝_{𝐴} (𝜆) =

det (𝜆 𝐼_{𝑛} - 𝐴)

. Multiplying each column by

- 1

gives

det (𝜆 𝐼_{𝑛} - 𝐴) =

{(- 1)}^{𝑛} det (𝐴 - 𝜆 𝐼_{𝑛})

. So

𝑝_{𝐴} (𝜆) = 0

if and only if

det (𝐴 - 𝜆 𝐼_{𝑛}) = 0

, which by Theorem 7.2.9 holds if and only if

𝜆

is an eigenvalue of

𝐴

. □

The theorem turns the search for eigenvalues into a search for roots of one polynomial of degree $𝑛$ . It reproves Corollary 7.2.22 for matrices: a nonzero polynomial of degree $𝑛$ has at most $𝑛$ roots (Proposition 7.1.22).

Algorithm 7.3.7 (Eigenvalues by the characteristic polynomial)

Input: A matrix $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .
Output: The eigenvalues of $𝐴$ in $𝐹$ , and a basis of each eigenspace.

Compute

𝑝_{𝐴} =

det (𝑥 𝐼_{𝑛} - 𝐴)

, by cofactor expansion along a sparse row or column, or by the Leibniz formula for small

𝑛

Find the roots

𝜆_{1}, \dots, 𝜆_{𝑘}

𝑝_{𝐴}

𝐹

. These are the eigenvalues.

For each

𝜆_{𝑗}

, row reduce

𝐴 - 𝜆_{𝑗} 𝐼_{𝑛}

and read off a basis of its null space

𝐸_{𝜆_{𝑗}}

from the free columns.

The algorithm is correct by Theorem 7.3.6 and Definition 7.2.13. In step 3 the matrix $𝐴 - 𝜆_{𝑗} 𝐼_{𝑛}$ must have rank less than $𝑛$ ; if row reduction finds $𝑛$ pivots, then $𝜆_{𝑗}$ was not a root, and the arithmetic in step 1 or step 2 should be checked. The hard step is step 2: for $𝑛 \geq 5$ there is no formula in radicals for the roots in general, and in practice eigenvalues are computed by other methods. For hand computations in this book, the roots will be findable.

Example 7.3.8 (A $3 \times 3$ computation). Let $𝐴 =$ $(\begin{matrix} 4 & 0 & 1 \\ - 2 & 1 & 0 \\ - 2 & 0 & 1 \end{matrix}) \in$ $ℝ^{3 \times 3}$ . Then

𝑥 𝐼_{3} - 𝐴 = (\begin{matrix} 𝑥 - 4 & 0 & - 1 \\ 2 & 𝑥 - 1 & 0 \\ 2 & 0 & 𝑥 - 1 \end{matrix}) .

The middle column has a single nonzero entry, so expanding along it (Proposition 7.3.2(f)),

𝑝_{𝐴} = (𝑥 - 1) det (\begin{matrix} 𝑥 - 4 & - 1 \\ 2 & 𝑥 - 1 \end{matrix}) = (𝑥 - 1) ((𝑥 - 4) (𝑥 - 1) + 2) = (𝑥 - 1) (𝑥^{2} - 5 𝑥 + 6) = (𝑥 - 1) (𝑥 - 2) (𝑥 - 3) .

So the eigenvalues are $1$ , $2$ , $3$ . For $𝜆 = 2$ , row reduction gives

𝐴 - 2 𝐼_{3} = (\begin{matrix} 2 & 0 & 1 \\ - 2 & - 1 & 0 \\ - 2 & 0 & - 1 \end{matrix}) ⇝ (\begin{matrix} 1 & 0 & 1 / 2 \\ 0 & 1 & - 1 \\ 0 & 0 & 0 \end{matrix}),

so $𝐸_{2} =$ $span ((1, - 2, - 2))$ ; check: $𝐴 (1, - 2, - 2) =$ $(2, - 4, - 4)$ . In the same way, $𝐸_{1} = span ((0, 1, 0))$ and $𝐸_{3} =$ $span ((1, - 1, - 1))$ . Realize that $tr 𝐴 = 6 = 1 + 2 + 3$ and $det 𝐴 = 6 = 1 \cdot 2 \cdot 3$ ; Remark 7.3.19 explains this.

(\begin{matrix} 2 & 0 & 1 \\ - 2 & - 1 & 0 \\ - 2 & 0 & - 1 \end{matrix}) ⇝ (\begin{matrix} 1 & 0 & 1 / 2 \\ 0 & 1 & - 1 \\ 0 & 0 & 0 \end{matrix})

Row reduction of

𝐴 - 2 𝐼_{3}

from Example 7.3.8. The third column is free, so

𝐸_{2}

is a line. Use “Edit” to try

𝐴 - 𝜆 𝐼_{3}

for other values of

𝜆

: you get three pivots, and only the zero vector in the null space, unless

𝜆

1

2

, or

3

Exercise 7.3.9.routine Let

𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})

. Find

𝑝_{𝐴}

, and find the eigenvalues of

𝐴

together with an eigenvector for each, over

ℝ

, over

𝔽_{2}

, over

𝔽_{5}

, and over

𝔽_{11}

Solution.

Uses. Example 7.3.5 (Small cases), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial)

Hint 1.

𝑝_{𝐴} =

𝑥^{2} -

(tr 𝐴) 𝑥 +

det 𝐴

. Then find the roots field by field.

Hint 2. For a root

𝜆

, the first row of

𝐴 - 𝜆 𝐼_{2}

(1 - 𝜆, 1)

, so

(1, 𝜆 - 1)

is in the kernel. Since

𝜆^{2} = 𝜆 + 1

, this is

(1, 1 / 𝜆)

, or more simply the multiple

(𝜆, 1)

Sketch.

𝑝_{𝐴} = 𝑥^{2} - 𝑥 - 1

. Over

ℝ

(1 \pm \sqrt{5}) / 2

. Over

𝔽_{2}

𝑥^{2} + 𝑥 + 1

has no root. Over

𝔽_{5}

{(𝑥 - 3)}^{2}

, one eigenvalue

3

. Over

𝔽_{11}

: roots

4

and

8

. Eigenvectors

(𝜆, 1)

in each case.

By Example 7.3.5(a), $𝑝_{𝐴} = 𝑥^{2} - 𝑥 - 1$ . If $𝜆$ is a root, then $(𝐴 - 𝜆 𝐼_{2}) (𝜆, 1) =$ $(𝜆 - 𝜆^{2} + 1, 𝜆 - 𝜆) =$ $(0, 0)$ , because $𝜆^{2} = 𝜆 + 1$ . So $(𝜆, 1)$ is an eigenvector for every root $𝜆$ , and by Theorem 7.3.6 the eigenvalues are exactly the roots.

Over $ℝ$ , the roots are $(1 \pm \sqrt{5}) / 2$ , the golden ratio and its conjugate.

Over $𝔽_{2}$ , $𝑝_{𝐴} = 𝑥^{2} + 𝑥 + 1$ takes the value $1$ at both $0$ and $1$ , so $𝐴$ has no eigenvalues.

Over $𝔽_{5}$ , $𝑝_{𝐴} =$ $𝑥^{2} -$ $𝑥 -$ $1 =$ $𝑥^{2} +$ $4 𝑥 +$ $4 =$ ${(𝑥 + 2)}^{2} =$ ${(𝑥 - 3)}^{2}$ , so $3$ is the only eigenvalue, with eigenvector $(3, 1)$ . Indeed $𝐴 (3, 1) =$ $(4, 3) =$ $3 (3, 1)$ , as $9 = 4$ in $𝔽_{5}$ .

Over $𝔽_{11}$ , $𝑝_{𝐴} (4) =$ $16 -$ $4 -$ $1 =$ $11 =$ $0$ and $𝑝_{𝐴} (8) =$ $64 -$ $8 -$ $1 =$ $55 =$ $0$ , so the eigenvalues are $4$ and $8$ (there are at most two), with eigenvectors $(4, 1)$ and $(8, 1)$ . These are the two “square roots of $5$ formulas” $(1 \pm 4) / 2$ read in $𝔽_{11}$ , since $4^{2} = 5$ there.

Remark 7.3.10 (A polynomial, not a function). Over a finite field, the function

𝜆 \mapsto det (𝜆 𝐼_{𝑛} - 𝐴)

𝐹

carries less information than the polynomial

𝑝_{𝐴}

. Over

𝔽_{2}

, take

𝐴 = 0_{3 \times 3}

and

𝐵 = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})

. Then

𝑝_{𝐴} = 𝑥^{3}

, and by Proposition 7.3.2(e) and Example 7.3.5(a),

𝑝_{𝐵} =

𝑥 (𝑥^{2} + 𝑥 + 1) =

𝑥^{3} +

𝑥^{2} +

𝑥

. Both polynomials take the value

0

0

and

1

1

, so they define the same function on

𝔽_{2}

. But they differ, and so do

tr 𝐴 = 0

and

tr 𝐵 = 1

, which Proposition 7.3.18 reads off the coefficients. This is why we defined

𝑝_{𝐴}

through determinants over

𝐹 [𝑥]

, instead of as the function

𝜆 \mapsto det (𝜆 𝐼_{𝑛} - 𝐴)

7.3.3Similarity and operators

The characteristic polynomial of a matrix should depend only on the operator the matrix represents, as the trace and the determinant do (Definition 4.5.30, Definition 5.4.18).

Proposition 7.3.11 (Similar matrices have the same characteristic polynomial). If

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

are similar, then

𝑝_{𝐴} = 𝑝_{𝐵}

Proof (by multiplicativity over $𝐹 [𝑥]$ ).routine

Uses. Definition 4.5.23 (Similar matrices), Proposition 7.3.2 (Determinants over a commutative ring), Definition 7.3.4 (Characteristic polynomial)

Hint 1. Write

𝐵 = 𝑆^{- 1} 𝐴 𝑆

. Can you write

𝑥 𝐼_{𝑛} - 𝐵

as a product of three matrices with entries in

𝐹 [𝑥]

Hint 2.

𝑥 𝐼_{𝑛} =

𝑆^{- 1} (𝑥 𝐼_{𝑛}) 𝑆

. Then take determinants in

𝐹 [𝑥]

, using Proposition 7.3.2(c).

Sketch.

𝑥 𝐼_{𝑛} -

𝑆^{- 1} 𝐴 𝑆 =

𝑆^{- 1} (𝑥 𝐼_{𝑛} - 𝐴) 𝑆

{𝐹 [𝑥]}^{𝑛 \times 𝑛}

. Taking determinants with Proposition 7.3.2(c) gives

𝑝_{𝐵} =

det 𝑆^{- 1} 𝑝_{𝐴} det 𝑆 =

𝑝_{𝐴}

, since

det 𝑆^{- 1} det 𝑆 =

det 𝐼_{𝑛} =

1

Let $𝐵 = 𝑆^{- 1} 𝐴 𝑆$ with $𝑆 \in 𝐹^{𝑛 \times 𝑛}$ invertible. In ${𝐹 [𝑥]}^{𝑛 \times 𝑛}$ , by Proposition 7.3.2(a),

𝑆^{- 1} (𝑥 𝐼_{𝑛} - 𝐴) 𝑆 = 𝑥 𝑆^{- 1} 𝑆 - 𝑆^{- 1} 𝐴 𝑆 = 𝑥 𝐼_{𝑛} - 𝐵 .

Taking determinants and using Proposition 7.3.2(c) twice,

𝑝_{𝐵} = det (𝑆^{- 1}) det (𝑥 𝐼_{𝑛} - 𝐴) det (𝑆) = det (𝑆^{- 1}) det (𝑆) 𝑝_{𝐴} = det (𝑆^{- 1} 𝑆) 𝑝_{𝐴} = 𝑝_{𝐴},

where we used that $𝐹 [𝑥]$ is commutative and $det 𝐼_{𝑛} = 1$ . □

Proof (pointwise, when $𝐹$ is infinite).routine

Uses. Theorem 5.4.10 (Multiplicativity), Corollary 7.1.23 (Polynomials and their values), (7.3.1)

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. Compare the values

𝑝_{𝐴} (𝜆)

and

𝑝_{𝐵} (𝜆)

for a scalar

𝜆

. Only determinants over

𝐹

are involved.

Hint 2. Two polynomials that agree at infinitely many points are equal.

Sketch. For

𝜆 \in 𝐹

𝑝_{𝐵} (𝜆) =

det (𝑆^{- 1} (𝜆 𝐼_{𝑛} - 𝐴) 𝑆) =

𝑝_{𝐴} (𝜆)

by multiplicativity over

𝐹

. If

𝐹

is infinite, polynomials that agree at every point are equal.

Let $𝐵 = 𝑆^{- 1} 𝐴 𝑆$ and $𝜆 \in 𝐹$ . By (7.3.1) and multiplicativity over the field $𝐹$ (Theorem 5.4.10),

𝑝_{𝐵} (𝜆) = det (𝑆^{- 1} (𝜆 𝐼_{𝑛} - 𝐴) 𝑆) = det (𝑆^{- 1}) det (𝜆 𝐼_{𝑛} - 𝐴) det (𝑆) = 𝑝_{𝐴} (𝜆) .

So $𝑝_{𝐴}$ and $𝑝_{𝐵}$ agree at every point of $𝐹$ . If $𝐹$ is infinite, Corollary 7.1.23 gives $𝑝_{𝐴} = 𝑝_{𝐵}$ . □

The second proof avoids determinants over $𝐹 [𝑥]$ but only proves equality of functions, which is weaker than equality of polynomials over a finite field (Remark 7.3.10). Over an infinite field this is no loss. The idea of proving a polynomial identity by checking it at many points returns in Proposition 7.3.22.

Definition 7.3.12 (Characteristic polynomial of an operator). Let $𝑉$ be finite-dimensional with $dim 𝑉 \geq 1$ , and $𝑇 \in L (𝑉)$ . The characteristic polynomial of $𝑇$ is

𝑝_{𝑇} = 𝑝_{{[𝑇]}_{ℬ︀ ℬ︀}},

where $ℬ︀$ is any basis of $𝑉$ . Matrices of $𝑇$ in two bases are similar (Theorem 4.5.25), so by Proposition 7.3.11 this does not depend on $ℬ︀$ .

Corollary 7.3.13 (Eigenvalues of an operator). Let

𝑉

be finite-dimensional with

dim 𝑉 \geq 1

𝑇 \in L (𝑉)

, and

𝜆 \in 𝐹

. Then

𝜆

is an eigenvalue of

𝑇

if and only if

𝑝_{𝑇} (𝜆) = 0

Proof.routine

Uses. Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Definition 7.3.12 (Characteristic polynomial of an operator), Definition 2.3.1 (Matrix of a linear map), Proposition 1.6.20 (Coordinates translate questions about $𝑉$ into $𝐹^{𝑛}$ )

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Fix a basis

ℬ︀

and let

𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}

. Compare the eigenvectors of

𝑇

with those of

𝐴

Hint 2.

{[𝑇 𝐯]}_{ℬ︀} = 𝐴 {[𝐯]}_{ℬ︀}

, and the coordinate map is a linear bijection.

Sketch. With

𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}

𝑇 𝐯 = 𝜆 𝐯

if and only if

𝐴 {[𝐯]}_{ℬ︀} = 𝜆 {[𝐯]}_{ℬ︀}

, and

𝐯 \neq 𝟎

if and only if

{[𝐯]}_{ℬ︀} \neq 𝟎

. So

𝑇

and

𝐴

have the same eigenvalues, which are the roots of

𝑝_{𝐴} = 𝑝_{𝑇}

Let

ℬ︀

be a basis of

𝑉

and

𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}

, so

𝑝_{𝑇} = 𝑝_{𝐴}

. For

𝐯 \in 𝑉

{[𝑇 𝐯]}_{ℬ︀} = 𝐴 {[𝐯]}_{ℬ︀}

(Definition 2.3.1), and the coordinate map

𝐯 \mapsto {[𝐯]}_{ℬ︀}

is a linear bijection (Proposition 1.6.20). So

𝑇 𝐯 = 𝜆 𝐯

with

𝐯 \neq 𝟎

if and only if

𝐴 𝐰 = 𝜆 𝐰

with

𝐰 = {[𝐯]}_{ℬ︀} \neq 𝟎

. Hence

𝑇

and

𝐴

have the same eigenvalues, and Theorem 7.3.6 finishes the proof. □

Example 7.3.14 (Characteristic polynomials of operators).

(a)Differentiation $𝐷$ on ${𝐹 [𝑥]}_{\leq 𝑛}$ has, in the basis $1, 𝑥, \dots, 𝑥^{𝑛}$ , a strictly upper triangular matrix (it lowers degrees). So $𝑝_{𝐷} = 𝑥^{𝑛 + 1}$ by Example 7.3.5(d), and $0$ is its only eigenvalue, as found in Example 7.2.19.
(b)On the real vector space $𝑊 = span (cos, sin)$ of functions $ℝ \to ℝ$ , differentiation maps $cos \mapsto - sin$ and $sin \mapsto cos$ . Its matrix in the basis $cos, sin$ is $(\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$ , with characteristic polynomial $𝑥^{2} + 1$ . So it has no real eigenvalue: no nonzero $𝑎 cos + 𝑏 sin$ is proportional to its own derivative.
(c)The cyclic permutation $𝑍 (𝑥, 𝑦, 𝑧) =$ $(𝑧, 𝑥, 𝑦)$ of Example 7.2.36 has matrix $(\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ in the standard basis. Expanding along the first row,
$𝑝_{𝑍} = det (\begin{matrix} 𝑥 & 0 & - 1 \\ - 1 & 𝑥 & 0 \\ 0 & - 1 & 𝑥 \end{matrix}) = 𝑥 \cdot 𝑥^{2} + (- 1) \cdot {(- 1)}^{1 + 3} \cdot ((- 1) (- 1) - 𝑥 \cdot 0) = 𝑥^{3} - 1 .$

The converse of Proposition 7.3.11 is false. The matrices $𝐼_{2}$ and $(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ both have characteristic polynomial ${(𝑥 - 1)}^{2}$ , but the only matrix similar to $𝐼_{2}$ is $𝑆^{- 1} 𝐼_{2} 𝑆 = 𝐼_{2}$ itself. So the characteristic polynomial is one more similarity invariant to try (Technique 4.5.29), stronger than trace and determinant together, but not a complete one. Chapter 10 finds the complete invariant over $ℂ$ (Section 10.3).

Block-triangular matrices and invariant subspaces

Proposition 7.3.15 (Block-triangular matrices). Let

𝑀 =

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix}) \in

𝐹^{𝑛 \times 𝑛}

, where

𝐴 \in 𝐹^{𝑘 \times 𝑘}

and

𝐷 \in

𝐹^{(𝑛 - 𝑘) \times (𝑛 - 𝑘)}

with

1 \leq 𝑘 < 𝑛

. Then

𝑝_{𝑀} = 𝑝_{𝐴} 𝑝_{𝐷}

. The same holds for

(\begin{matrix} 𝐴 & 0 \\ 𝐶 & 𝐷 \end{matrix})

Proof.routine

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Definition 7.3.4 (Characteristic polynomial)

Hint 1. Write

𝑥 𝐼_{𝑛} - 𝑀

in block form. Is it still block triangular?

Hint 2. Apply Proposition 7.3.2(e) over the ring

𝐹 [𝑥]

Sketch.

𝑥 𝐼_{𝑛} -

𝑀 =

(\begin{matrix} 𝑥 𝐼_{𝑘} - 𝐴 & - 𝐵 \\ 0 & 𝑥 𝐼_{𝑛 - 𝑘} - 𝐷 \end{matrix})

is block upper triangular in

{𝐹 [𝑥]}^{𝑛 \times 𝑛}

, so its determinant is

𝑝_{𝐴} 𝑝_{𝐷}

by Proposition 7.3.2(e). The lower case is the same, or follows by transposing.

In ${𝐹 [𝑥]}^{𝑛 \times 𝑛}$ ,

𝑥 𝐼_{𝑛} - 𝑀 = (\begin{matrix} 𝑥 𝐼_{𝑘} - 𝐴 & - 𝐵 \\ 0 & 𝑥 𝐼_{𝑛 - 𝑘} - 𝐷 \end{matrix}),

which is block upper triangular with diagonal blocks $𝑥 𝐼_{𝑘} - 𝐴$ and $𝑥 𝐼_{𝑛 - 𝑘} - 𝐷$ . By Proposition 7.3.2(e), $𝑝_{𝑀} =$ $det (𝑥 𝐼_{𝑘} - 𝐴) det (𝑥 𝐼_{𝑛 - 𝑘} - 𝐷) =$ $𝑝_{𝐴} 𝑝_{𝐷}$ . For $(\begin{matrix} 𝐴 & 0 \\ 𝐶 & 𝐷 \end{matrix})$ , the matrix $𝑥 𝐼_{𝑛} - 𝑀$ is block lower triangular, and Proposition 7.3.2(e) applies again. □

Combined with the block form of an operator with an invariant subspace (Remark 7.2.5), this says that an invariant subspace splits off a factor of the characteristic polynomial.

Corollary 7.3.16 (Invariant subspaces give factors). Let

𝑉

be finite-dimensional,

𝑇 \in L (𝑉)

, and

𝑈

𝑇

-invariant subspace with

dim 𝑈 \geq 1

. Then

𝑝_{𝑇 ↾_{𝑈}}

divides

𝑝_{𝑇}

Proof.routine

Uses. Proposition 4.5.35 (Preserved subspaces give block triangular matrices), Proposition 7.3.15 (Block-triangular matrices), Theorem 4.1.16 (Extending to a basis), Definition 7.3.12 (Characteristic polynomial of an operator)

Techniques. Choose a basis adapted to a preserved subspace (Technique 4.5.36)

Hint 1. Choose a basis of

𝑉

that starts with a basis of

𝑈

. What does the matrix of

𝑇

look like?

Hint 2. Proposition 4.5.35 gives

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})

with

𝐴 = [𝑇 ↾_{𝑈}]

. Now use Proposition 7.3.15.

Sketch. If

𝑈 = 𝑉

there is nothing to prove. Otherwise extend a basis of

𝑈

to a basis

ℬ︀

𝑉

; then

{[𝑇]}_{ℬ︀ ℬ︀} =

(\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix})

with

𝐴

the matrix of

𝑇 ↾_{𝑈}

(Proposition 4.5.35), and

𝑝_{𝑇} =

𝑝_{𝐴} 𝑝_{𝐷} =

𝑝_{𝑇 ↾_{𝑈}} 𝑝_{𝐷}

If $𝑈 = 𝑉$ , then $𝑇 ↾_{𝑈} = 𝑇$ and there is nothing to prove. Otherwise let $𝑘 = dim 𝑈$ and $𝑛 = dim 𝑉$ , so $1 \leq 𝑘 < 𝑛$ . Extend a basis $𝐛_{1}, \dots, 𝐛_{𝑘}$ of $𝑈$ to a basis $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ of $𝑉$ (Theorem 4.1.16). By Proposition 4.5.35,

{[𝑇]}_{ℬ︀ ℬ︀} = (\begin{matrix} 𝐴 & 𝐵 \\ 0 & 𝐷 \end{matrix}) with 𝐴 = {[𝑇 ↾_{𝑈}]}_{{ℬ︀}_{𝑈} {ℬ︀}_{𝑈}} .

By Proposition 7.3.15, $𝑝_{𝑇} =$ $𝑝_{𝐴} 𝑝_{𝐷} =$ $𝑝_{𝑇 ↾_{𝑈}} 𝑝_{𝐷}$ . □

Exercise 7.3.17.routine Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .

(a)Show that $𝑝_{𝐴^{𝖳}} = 𝑝_{𝐴}$ .
(b)For $𝐹 = ℂ$ , let $𝐴$ be the entrywise conjugate of $𝐴$ , and $𝑓$ the polynomial whose coefficients are the conjugates of those of $𝑓 \in ℂ [𝑥]$ . Show that $𝑝_{𝐴} = 𝑝_{𝐴}$ , and deduce that the eigenvalues of $𝐴^{𝖧}$ are the conjugates of the eigenvalues of $𝐴$ .

Solution.

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Lemma 7.1.37 (Conjugating polynomials), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Definition 6.3.26 (Conjugate transpose)

Hint 1. For (a), what is

{(𝑥 𝐼_{𝑛} - 𝐴)}^{𝖳}

? Use Proposition 7.3.2(d).

Hint 2. For (b), coefficientwise conjugation

ℂ [𝑥] \to ℂ [𝑥]

respects sums, products, and

1

(Lemma 7.1.37). Apply Proposition 7.3.2(g) to it.

Sketch. (a)

{(𝑥 𝐼_{𝑛} - 𝐴)}^{𝖳} =

𝑥 𝐼_{𝑛} -

𝐴^{𝖳}

, and transposing does not change

det

. (b) Conjugating every entry of

𝑥 𝐼_{𝑛} - 𝐴

gives

𝑥 𝐼_{𝑛} - 𝐴

, so

𝑝_{𝐴} = 𝑝_{𝐴}

by Proposition 7.3.2(g). With (a),

𝑝_{𝐴^{𝖧}} = 𝑝_{𝐴}

, whose roots are the conjugates of the roots of

𝑝_{𝐴}

by Lemma 7.1.37(b).

(a) The transpose of $𝑥 𝐼_{𝑛} - 𝐴$ is $𝑥 𝐼_{𝑛} - 𝐴^{𝖳}$ , since $𝑥 𝐼_{𝑛}$ is symmetric. By Proposition 7.3.2(d), $𝑝_{𝐴^{𝖳}} =$ $det ({(𝑥 𝐼_{𝑛} - 𝐴)}^{𝖳}) =$ $det (𝑥 𝐼_{𝑛} - 𝐴) =$ $𝑝_{𝐴}$ .

(b) Let $𝜑 : ℂ [𝑥] \to ℂ [𝑥]$ , $𝜑 (𝑓) = 𝑓$ . By Lemma 7.1.37(a), $𝜑$ respects sums and products, and $𝜑 (1) = 1$ . Applying $𝜑$ to every entry of $𝑥 𝐼_{𝑛} - 𝐴$ gives $𝑥 𝐼_{𝑛} - 𝐴$ , because $𝑥 = 𝑥$ and the constant $- 𝑎_{𝑖 𝑗}$ becomes $- 𝑎_{𝑖 𝑗}$ . By Proposition 7.3.2(g), $𝑝_{𝐴} =$ $det 𝜑 (𝑥 𝐼_{𝑛} - 𝐴) =$ $𝜑 (𝑝_{𝐴}) =$ $𝑝_{𝐴}$ .

Now $𝐴^{𝖧} = 𝐴^{𝖳}$ , so by (a), $𝑝_{𝐴^{𝖧}} = 𝑝_{𝐴} = 𝑝_{𝐴}$ . By Lemma 7.1.37(b), $𝑝_{𝐴} (𝜆) = 𝑝_{𝐴} (𝜆)$ , so $𝜆$ is a root of $𝑝_{𝐴}$ if and only if $𝜆$ is a root of $𝑝_{𝐴}$ . By Theorem 7.3.6, the eigenvalues of $𝐴^{𝖧}$ are exactly the conjugates $𝜆$ of the eigenvalues $𝜆$ of $𝐴$ .

7.3.4The coefficients: trace and determinant

Proposition 7.3.18 (The first and last coefficients). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Then $𝑝_{𝐴}$ is monic of degree $𝑛$ , the coefficient of $𝑥^{𝑛 - 1}$ in $𝑝_{𝐴}$ is $- tr 𝐴$ , and its constant term is ${(- 1)}^{𝑛} det 𝐴$ . That is, for $𝑛 \geq 3$ ,

𝑝_{𝐴} = 𝑥^{𝑛} - (tr 𝐴) 𝑥^{𝑛 - 1} + 𝑐_{𝑛 - 2} 𝑥^{𝑛 - 2} + \dots + 𝑐_{1} 𝑥 + {(- 1)}^{𝑛} det 𝐴

for some $𝑐_{1}, \dots, 𝑐_{𝑛 - 2} \in 𝐹$ , while $𝑝_{𝐴} =$ $𝑥^{2} -$ $(tr 𝐴) 𝑥 +$ $det 𝐴$ for $𝑛 = 2$ and $𝑝_{𝐴} = 𝑥 - 𝑎_{11}$ for $𝑛 = 1$ .

Proof.standard

Uses. Definition 7.3.1 (Determinant over a commutative ring), Proposition 7.3.2 (Determinants over a commutative ring), Definition 2.4.26 (Trace), Proposition 7.1.4 (Degree of a product), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ )

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12)

Hint 1. Each entry of

𝑥 𝐼_{𝑛} - 𝐴

has degree at most

1

, and only the diagonal entries involve

𝑥

. In the Leibniz term of

𝜎

, which factors have degree

1

Hint 2. Only the factors

𝑥 - 𝑎_{𝑗 𝑗}

with

𝜎 (𝑗) = 𝑗

. A permutation

𝜎 \neq id

moves at least two points. What does that say about the degree of its term?

Hint 3. So

𝑥^{𝑛}

and

𝑥^{𝑛 - 1}

come only from

(𝑥 - 𝑎_{11}) \dots (𝑥 - 𝑎_{𝑛 𝑛})

. For the constant term, evaluate at

0

with (7.3.1).

Sketch. The Leibniz term of

𝜎

is a product of

𝑛

factors of degree at most

1

, of which only those with

𝜎 (𝑗) = 𝑗

have degree

1

. A permutation other than

id

fixes at most

𝑛 - 2

points, so its term has degree at most

𝑛 - 2

. Thus the coefficients of

𝑥^{𝑛}

and

𝑥^{𝑛 - 1}

are those of

\prod_{𝑗} (𝑥 - 𝑎_{𝑗 𝑗}) =

𝑥^{𝑛} -

(\sum_{𝑗} 𝑎_{𝑗 𝑗}) 𝑥^{𝑛 - 1} +

\dots

. The constant term is

𝑝_{𝐴} (0) =

det (- 𝐴) =

{(- 1)}^{𝑛} det 𝐴

Let $𝑀 = 𝑥 𝐼_{𝑛} - 𝐴$ , so $𝑚_{𝑗 𝑗} = 𝑥 - 𝑎_{𝑗 𝑗}$ and $𝑚_{𝑖 𝑗} = - 𝑎_{𝑖 𝑗}$ for $𝑖 \neq 𝑗$ . The Leibniz term of $𝜎 \in 𝑆_{𝑛}$ is

𝑡_{𝜎} = sgn (𝜎) \prod_{𝑗 = 1}^{𝑛} 𝑚_{𝜎 (𝑗) 𝑗} .

Each factor has degree at most $1$ , with degree $1$ exactly when $𝜎 (𝑗) = 𝑗$ . So $𝑡_{𝜎}$ is $𝟎$ or has degree at most the number of fixed points of $𝜎$ (Proposition 7.1.4). If $𝜎 \neq id$ , pick $𝑗$ with $𝜎 (𝑗) \neq 𝑗$ ; then $𝑖 = 𝜎 (𝑗)$ is also moved, since $𝜎 (𝑖) = 𝑖 = 𝜎 (𝑗)$ would contradict injectivity. So $𝜎$ fixes at most $𝑛 - 2$ points, and $𝑡_{𝜎}$ contributes nothing to the coefficients of $𝑥^{𝑛}$ and $𝑥^{𝑛 - 1}$ .

These two coefficients therefore come from

𝑡_{id} = (𝑥 - 𝑎_{11}) (𝑥 - 𝑎_{22}) \dots (𝑥 - 𝑎_{𝑛 𝑛}) .

Expanding by distributivity, a product of $𝑛$ factors $𝑥 - 𝑎_{𝑗 𝑗}$ is a sum over the ways to choose $𝑥$ or $- 𝑎_{𝑗 𝑗}$ from each factor. The only way to get $𝑥^{𝑛}$ is to choose $𝑥$ every time, and the ways to get $𝑥^{𝑛 - 1}$ are to choose $- 𝑎_{𝑗 𝑗}$ from exactly one factor $𝑗$ . So the coefficient of $𝑥^{𝑛}$ is $1$ and that of $𝑥^{𝑛 - 1}$ is $- (𝑎_{11} + \dots + 𝑎_{𝑛 𝑛}) =$ $- tr 𝐴$ . In particular $𝑝_{𝐴}$ is monic of degree $𝑛$ .

The constant term of a polynomial is its value at $0$ . By (7.3.1), $𝑝_{𝐴} (0) = det (- 𝐴)$ , and multiplying each of the $𝑛$ columns of $𝐴$ by $- 1$ multiplies $det$ by ${(- 1)}^{𝑛}$ (Proposition 7.3.2(b)). So the constant term is ${(- 1)}^{𝑛} det 𝐴$ . □

This is the computation in the proof of Proposition 5.3.19, done in $𝐹 [𝑥]$ instead of for each scalar $𝑡$ . The coefficients in between are sums of minors (Exercise 7.3.53).

Remark 7.3.19 (Trace and determinant from the roots). Suppose $𝑝_{𝐴}$ splits over $𝐹$ , say $𝑝_{𝐴} =$ $(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ with $𝜆_{𝑖} \in 𝐹$ . By Proposition 7.1.36, the coefficient of $𝑥^{𝑛 - 1}$ in this product is $- (𝜆_{1} + \dots + 𝜆_{𝑛})$ and its constant term is ${(- 1)}^{𝑛} 𝜆_{1} \dots 𝜆_{𝑛}$ . Comparing with Proposition 7.3.18 gives

tr 𝐴 = 𝜆_{1} + \dots + 𝜆_{𝑛}, det 𝐴 = 𝜆_{1} 𝜆_{2} \dots 𝜆_{𝑛} .

The $𝜆_{𝑖}$ are the eigenvalues of $𝐴$ (Theorem 7.3.6), each repeated as often as its multiplicity as a root of $𝑝_{𝐴}$ , its algebraic multiplicity (Definition 7.4.11). Repetitions matter: $(\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix})$ has the single eigenvalue $2$ but trace $4 = 2 + 2$ . Over $ℂ$ , $𝑝_{𝐴}$ always splits (Corollary 7.1.35), and Theorem 7.5.22 proves the same statement a second way, by triangularizing $𝐴$ .

For $2 \times 2$ matrices the trace and determinant determine $𝑝_{𝐴} =$ $𝑥^{2} -$ $(tr 𝐴) 𝑥 +$ $det 𝐴$ , and with it the eigenvalues. Over $ℝ$ , the quadratic formula says that the number of real eigenvalues is governed by the discriminant

Δ = {(tr 𝐴)}^{2} - 4 det 𝐴 :

two real eigenvalues if $Δ > 0$ , one repeated real eigenvalue if $Δ = 0$ , and a pair of conjugate nonreal eigenvalues if $Δ < 0$ (Theorem B.1.30).

Figure 7.3.1. Real

2 \times 2

matrices placed by

(tr 𝐴, det 𝐴)

, with

Δ = {(tr 𝐴)}^{2} - 4 det 𝐴

. Below the parabola

det 𝐴 = {(tr 𝐴)}^{2} / 4

there are two real eigenvalues, and above it none. The rotation

𝑅_{𝜋 / 2}

sits at

(0, 1)

, above the parabola. The matrix

(\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix})

of Example 7.2.8 sits at

(4, 3)

and the reflection

diag (1, - 1)

(0, - 1)

, both below. The shear

(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})

sits on the parabola at

(2, 1)

, as do

𝐼_{2}

and the matrix of Example 7.2.39 (at

(4, 4)

). A point on the parabola can be a multiple of

𝐼_{2}

or not: the plane cannot tell them apart.

Exercise 7.3.20.routine Let

𝐴 \in ℝ^{3 \times 3}

have

tr 𝐴 = 2

and

det 𝐴 = - 2

, and suppose

𝐴 - 𝐼_{3}

is not invertible and

𝑝_{𝐴}

splits over

ℝ

. Find

𝑝_{𝐴}

and the eigenvalues of

𝐴

Solution.

Uses. Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Remark 7.3.19 (Trace and determinant from the roots), Theorem 7.2.9 (Eigenvalues and invertibility)

Hint 1. Since

𝐴 - 𝐼_{3}

is not invertible,

1

is an eigenvalue. Write

𝑝_{𝐴} =

(𝑥 - 1) (𝑥 - 𝑟) (𝑥 - 𝑠)

Hint 2. Remark 7.3.19 gives

1 + 𝑟 + 𝑠 = 2

and

𝑟 𝑠 = - 2

Sketch.

1

is a root,

𝑟 + 𝑠 = 1

𝑟 𝑠 = - 2

, so

𝑟, 𝑠

are the roots of

𝑡^{2} -

𝑡 -

2 =

(𝑡 - 2) (𝑡 + 1)

. Hence

𝑝_{𝐴} =

(𝑥 - 1) (𝑥 - 2) (𝑥 + 1)

By Theorem 7.2.9,

1

is an eigenvalue of

𝐴

, so

𝑝_{𝐴} (1) = 0

by Theorem 7.3.6, and since

𝑝_{𝐴}

splits we can write

𝑝_{𝐴} =

(𝑥 - 1) (𝑥 - 𝑟) (𝑥 - 𝑠)

with

𝑟, 𝑠 \in ℝ

. By Remark 7.3.19,

1 + 𝑟 + 𝑠 = tr 𝐴 = 2

and

1 \cdot 𝑟 𝑠 = det 𝐴 = - 2

. So

𝑟 + 𝑠 = 1

and

𝑟 𝑠 = - 2

, which makes

𝑟

and

𝑠

the roots of

(𝑡 - 𝑟) (𝑡 - 𝑠) =

𝑡^{2} -

𝑡 -

2 =

(𝑡 - 2) (𝑡 + 1)

. Therefore

𝑝_{𝐴} =

(𝑥 - 1) (𝑥 - 2) (𝑥 + 1)

, and the eigenvalues are

1

2

- 1

. (The matrix

diag (1, 2, - 1)

shows that such an

𝐴

exists.)

Products in either order

For square matrices, $𝐴 𝐵$ and $𝐵 𝐴$ are usually different, and they need not be similar. But their characteristic polynomials always agree.

Technique 7.3.21 (Compare $𝐴 𝐵$ and $𝐵 𝐴$ ). The products $𝐴 𝐵$ and $𝐵 𝐴$ are close relatives. If $𝐴$ is invertible, they are similar: $𝐵 𝐴 = 𝐴^{- 1} (𝐴 𝐵) 𝐴$ . In general they are not necessarily similar, but they still share the characteristic polynomial (when square) and the nonzero eigenvalues (always). Three ways to transfer information between them are useful. Conjugate by $𝐴$ when $𝐴$ is invertible, and reduce the general case to it by a polynomial identity in a perturbation parameter. Or embed both products in block matrices of twice the size that are similar. Or transport eigenvectors directly: if $𝐴 𝐵 𝐯 = 𝜆 𝐯$ with $𝜆 \neq 0$ , then $𝐵 𝐯 \neq 𝟎$ and $𝐵 𝐴 (𝐵 𝐯) = 𝜆 𝐵 𝐯$ .

Reach for it whenever a question involves a product in both orders, such as $𝐴^{𝖳} 𝐴$ and $𝐴 𝐴^{𝖳}$ , or $𝐮 𝐯^{𝖳}$ and $𝐯^{𝖳} 𝐮$ . The canonical example is Proposition 7.3.22.

Used in 5 places and 1 practice exercise

Proposition 7.3.22, Exercise 7.3.40, Exercise 7.3.41, Exercise 7.7.10, Proposition 8.3.20; 1 practice exercise.

Proposition 7.3.22 (

𝐴 𝐵

and

𝐵 𝐴

). For

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

𝑝_{𝐴 𝐵} = 𝑝_{𝐵 𝐴}

. In particular

𝐴 𝐵

and

𝐵 𝐴

have the same eigenvalues.

Intuition. If

𝐴

is invertible, then

𝐵 𝐴 = 𝐴^{- 1} (𝐴 𝐵) 𝐴

is similar to

𝐴 𝐵

, and we are done by Proposition 7.3.11. If

𝐴

is not invertible,

𝐴 𝐵

and

𝐵 𝐴

need not be similar: for

𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})

and

𝐵 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

𝐴 𝐵 = 𝐵 \neq 0

while

𝐵 𝐴 = 0

. Two ideas get around this. The first replaces

𝐴

by the invertible matrices

𝐴 + 𝑡 𝐼_{𝑛}

, which differ from

𝐴

by a parameter

𝑡

that we then set to

0

; this needs the identity to be polynomial in

𝑡

, and enough values of

𝑡

to conclude. The second finds a pair of larger matrices, built from

𝐴 𝐵

and

𝐵 𝐴

, that are similar for every

𝐴

Proof (by block matrices).standard

Uses. Proposition 7.3.11 (Similar matrices have the same characteristic polynomial), Proposition 7.3.15 (Block-triangular matrices), Theorem 2.4.34 (Block multiplication), Corollary 7.1.7 (No zero divisors, cancellation, and units)

Techniques. Compare $𝐴 𝐵$ and $𝐵 𝐴$ (Technique 7.3.21), Block decomposition (Technique 2.4.35)

Hint 1. Look for a

2 𝑛 \times 2 𝑛

matrix

𝑆

with

(\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 0 \end{matrix}) 𝑆 =

𝑆 (\begin{matrix} 0 & 0 \\ 𝐵 & 𝐵 𝐴 \end{matrix})

. Try

𝑆

block upper triangular with identity blocks on the diagonal.

Hint 2.

𝑆 = (\begin{matrix} 𝐼_{𝑛} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})

works. Both block matrices are block triangular; compute their characteristic polynomials.

Hint 3. You get

𝑥^{𝑛} 𝑝_{𝐴 𝐵} =

𝑥^{𝑛} 𝑝_{𝐵 𝐴}

. Cancel

𝑥^{𝑛}

𝐹 [𝑥]

Sketch. With

𝑋 = (\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 0 \end{matrix})

𝑌 = (\begin{matrix} 0 & 0 \\ 𝐵 & 𝐵 𝐴 \end{matrix})

, and

𝑆 = (\begin{matrix} 𝐼_{𝑛} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})

, block multiplication gives

𝑋 𝑆 =

(\begin{matrix} 𝐴 𝐵 & 𝐴 𝐵 𝐴 \\ 𝐵 & 𝐵 𝐴 \end{matrix}) =

𝑆 𝑌

, and

𝑆

is invertible, so

𝑋

and

𝑌

are similar. By Proposition 7.3.15,

𝑝_{𝑋} = 𝑝_{𝐴 𝐵} 𝑥^{𝑛}

and

𝑝_{𝑌} = 𝑥^{𝑛} 𝑝_{𝐵 𝐴}

. Cancel

𝑥^{𝑛}

(Corollary 7.1.7).

Consider the $2 𝑛 \times 2 𝑛$ matrices

𝑋 = (\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 0 \end{matrix}), 𝑌 = (\begin{matrix} 0 & 0 \\ 𝐵 & 𝐵 𝐴 \end{matrix}), 𝑆 = (\begin{matrix} 𝐼_{𝑛} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix}) .

By block multiplication (Theorem 2.4.34),

𝑋 𝑆 = (\begin{matrix} 𝐴 𝐵 & 𝐴 𝐵 𝐴 \\ 𝐵 & 𝐵 𝐴 \end{matrix}) = 𝑆 𝑌 .

The matrix $𝑆$ is invertible, with inverse $(\begin{matrix} 𝐼_{𝑛} & - 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})$ (multiply out). So $𝑌 = 𝑆^{- 1} 𝑋 𝑆$ , and $𝑝_{𝑋} = 𝑝_{𝑌}$ by Proposition 7.3.11. Both matrices are block triangular, so by Proposition 7.3.15,

𝑝_{𝑋} = 𝑝_{𝐴 𝐵} 𝑝_{0_{𝑛 \times 𝑛}} = 𝑝_{𝐴 𝐵} 𝑥^{𝑛}, 𝑝_{𝑌} = 𝑝_{0_{𝑛 \times 𝑛}} 𝑝_{𝐵 𝐴} = 𝑥^{𝑛} 𝑝_{𝐵 𝐴} .

So $𝑥^{𝑛} 𝑝_{𝐴 𝐵} =$ $𝑥^{𝑛} 𝑝_{𝐵 𝐴}$ , and since $𝑥^{𝑛} \neq 𝟎$ , cancellation in $𝐹 [𝑥]$ (Corollary 7.1.7(b)) gives $𝑝_{𝐴 𝐵} = 𝑝_{𝐵 𝐴}$ . The statement about eigenvalues follows from Theorem 7.3.6. □

Proof (by perturbation, when $𝐹$ is infinite).hard

Uses. Proposition 7.3.11 (Similar matrices have the same characteristic polynomial), Proposition 5.3.19 ( $det (𝐴 + 𝑡 𝐼_{𝑛})$ as a function of $𝑡$ ), Proposition 7.3.2 (Determinants over a commutative ring), Proposition 7.1.22 (Counting roots), Corollary 7.1.23 (Polynomials and their values), Theorem 5.4.7 (Invertibility and the determinant)

Techniques. Compare $𝐴 𝐵$ and $𝐵 𝐴$ (Technique 7.3.21), Polynomial identity arguments (Technique 5.5.24), $det$ is a polynomial in the entries (Technique 5.3.18)

Hint 1. Fix

𝜆 \in 𝐹

. For a scalar

𝑠

with

𝐴 + 𝑠 𝐼_{𝑛}

invertible, compare

det (𝜆 𝐼_{𝑛} - (𝐴 + 𝑠 𝐼_{𝑛}) 𝐵)

with

det (𝜆 𝐼_{𝑛} - 𝐵 (𝐴 + 𝑠 𝐼_{𝑛}))

Hint 2. They are equal, by similarity. Now regard

𝑠

as an indeterminate

𝑡

: both sides are values of polynomials in

𝑡

, and their difference has infinitely many roots.

Hint 3. Set

𝑡 = 0

to get

𝑝_{𝐴 𝐵} (𝜆) =

𝑝_{𝐵 𝐴} (𝜆)

for every

𝜆

, and use that

𝐹

is infinite once more.

Sketch. Fix

𝜆

. In

𝐹 [𝑡]

let

𝑔 =

det (𝜆 𝐼_{𝑛} - (𝐴 + 𝑡 𝐼_{𝑛}) 𝐵) -

det (𝜆 𝐼_{𝑛} - 𝐵 (𝐴 + 𝑡 𝐼_{𝑛}))

. For each

𝑠 \in 𝐹

with

𝐴 + 𝑠 𝐼_{𝑛}

invertible,

𝑔 (𝑠) = 0

by similarity; this excludes at most

𝑛

values of

𝑠

. So

𝑔

has infinitely many roots and

𝑔 = 𝟎

. Then

𝑔 (0) =

𝑝_{𝐴 𝐵} (𝜆) -

𝑝_{𝐵 𝐴} (𝜆) =

0

for every

𝜆 \in 𝐹

, and Corollary 7.1.23 finishes.

Assume $𝐹$ is infinite, and fix $𝜆 \in 𝐹$ . Work in $𝐹 [𝑡]$ , polynomials in a new indeterminate $𝑡$ , and let

𝑔 = det (𝜆 𝐼_{𝑛} - (𝐴 + 𝑡 𝐼_{𝑛}) 𝐵) - det (𝜆 𝐼_{𝑛} - 𝐵 (𝐴 + 𝑡 𝐼_{𝑛})) \in 𝐹 [𝑡] .

For $𝑠 \in 𝐹$ , evaluating every entry at $𝑡 = 𝑠$ (Proposition 7.3.2(g)) gives

𝑔 (𝑠) = det (𝜆 𝐼_{𝑛} - (𝐴 + 𝑠 𝐼_{𝑛}) 𝐵) - det (𝜆 𝐼_{𝑛} - 𝐵 (𝐴 + 𝑠 𝐼_{𝑛})) .

If $𝐴 + 𝑠 𝐼_{𝑛}$ is invertible, then $𝐵 (𝐴 + 𝑠 𝐼_{𝑛}) =$ ${(𝐴 + 𝑠 𝐼_{𝑛})}^{- 1} ((𝐴 + 𝑠 𝐼_{𝑛}) 𝐵) (𝐴 + 𝑠 𝐼_{𝑛})$ , so the two matrices $(𝐴 + 𝑠 𝐼_{𝑛}) 𝐵$ and $𝐵 (𝐴 + 𝑠 𝐼_{𝑛})$ are similar, and their characteristic polynomials agree at $𝜆$ (Proposition 7.3.11). So $𝑔 (𝑠) = 0$ .

By Proposition 5.3.19 and Theorem 5.4.7, $𝐴 + 𝑠 𝐼_{𝑛}$ fails to be invertible only for roots $𝑠$ of a monic polynomial of degree $𝑛$ , that is, for at most $𝑛$ values of $𝑠$ (Proposition 7.1.22). Since $𝐹$ is infinite, $𝑔$ has infinitely many roots, so $𝑔 = 𝟎$ , again by Proposition 7.1.22. In particular $𝑔 (0) = 0$ , which says $𝑝_{𝐴 𝐵} (𝜆) =$ $𝑝_{𝐵 𝐴} (𝜆)$ by (7.3.1). This holds for every $𝜆 \in 𝐹$ , so $𝑝_{𝐴 𝐵} = 𝑝_{𝐵 𝐴}$ by Corollary 7.1.23. □

The first proof is shorter and works over every field. The second shows a pattern that recurs: prove an identity for invertible matrices, where it is easy, and extend it to all matrices because both sides are polynomials. Over a finite field there are too few values of $𝑡$ , and this pattern alone does not suffice.

7.3.5Companion matrices

Which polynomials occur as characteristic polynomials? Every characteristic polynomial of an $𝑛 \times 𝑛$ matrix is monic of degree $𝑛$ . Conversely, every such polynomial occurs, and the matrix realizing it already appeared twice: in Proposition 5.5.20 as a determinant computation, and after Proposition 7.2.35 as the matrix of an operator on a Krylov subspace.

Definition 7.3.23 (Companion matrix). Let $𝑝 =$ $𝑥^{𝑛} +$ $𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $\dots +$ $𝑎_{1} 𝑥 +$ $𝑎_{0} \in$ $𝐹 [𝑥]$ be monic of degree $𝑛 \geq 1$ . The companion matrix of $𝑝$ is

𝐶_{𝑝} = (\begin{matrix} 0 & 0 & \dots & 0 & - 𝑎_{0} \\ 1 & 0 & \dots & 0 & - 𝑎_{1} \\ 0 & 1 & \dots & 0 & - 𝑎_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & - 𝑎_{𝑛 - 1} \end{matrix}) \in 𝐹^{𝑛 \times 𝑛},

whose column $𝑘$ is $𝐞_{𝑘 + 1}$ for $𝑘 < 𝑛$ and whose last column is $- (𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛 - 1})$ .

For example, $𝐶_{𝑥 - 𝑐} = (𝑐)$ , the companion matrix of $𝑥^{2} + 1$ is the rotation $(\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ , and the companion matrix of $𝑥^{3} - 1$ is the matrix of the cyclic permutation $𝑍$ in Example 7.3.14. In general $𝐶_{𝑝} 𝐞_{𝑘} = 𝐞_{𝑘 + 1}$ for $𝑘 < 𝑛$ : $𝐶_{𝑝}$ shifts the standard basis forward, and the last basis vector goes to $𝐶_{𝑝} 𝐞_{𝑛} =$ $- (𝑎_{0} 𝐞_{1} + \dots + 𝑎_{𝑛 - 1} 𝐞_{𝑛})$ . Some books use the transpose $𝐶_{𝑝}^{𝖳}$ instead; it has the same characteristic polynomial (Exercise 7.3.17).

Theorem 7.3.24 (Every monic polynomial is a characteristic polynomial). Let

𝑝 \in 𝐹 [𝑥]

be monic of degree

𝑛 \geq 1

. Then

𝑝_{𝐶_{𝑝}} = 𝑝

Proof (by rerunning Proposition 5.5.20).standard

Uses. Proposition 5.5.20 (Companion matrices), Proposition 7.3.2 (Determinants over a commutative ring)

Hint 1. Proposition 5.5.20 proves

det (𝑡 𝐼_{𝑛} - 𝐶) =

𝑝 (𝑡)

for every scalar

𝑡 \in 𝐹

. Over a finite field this is weaker than an identity in

𝐹 [𝑥]

. Which tools did its first proof use?

Hint 2. It used cofactor expansion along the first row, a triangular determinant, and induction on

𝑛

. All of these are available over

𝐹 [𝑥]

by Proposition 7.3.2.

Sketch. The first proof of Proposition 5.5.20 expands

det (𝑡 𝐼_{𝑛} - 𝐶_{𝑝})

along the first row, recognizes one minor as the same kind of matrix for

𝑞 = (𝑝 - 𝑎_{0}) / 𝑥

and the other as triangular with

- 1

′s on the diagonal, and inducts. Each step is valid with

𝑡

replaced by the indeterminate

𝑥

, by Proposition 7.3.2(e) and (f). So

det (𝑥 𝐼_{𝑛} - 𝐶_{𝑝}) =

𝑥 𝑞 +

𝑎_{0} =

𝑝

𝐹 [𝑥]

The first proof of Proposition 5.5.20 computes

det (𝑡 𝐼_{𝑛} - 𝐶_{𝑝})

by induction on

𝑛

. It expands along the first row, identifies the minor at position

(1, 1)

𝑡 𝐼_{𝑛 - 1} - 𝐶_{𝑞}

for

𝑞 =

𝑎_{1} +

𝑎_{2} 𝑥 +

\dots +

𝑎_{𝑛 - 1} 𝑥^{𝑛 - 2} +

𝑥^{𝑛 - 1}

, and the minor at position

(1, 𝑛)

as an upper triangular matrix with diagonal entries

- 1

. It then concludes

det (𝑡 𝐼_{𝑛} - 𝐶_{𝑝}) =

𝑡 𝑞 (𝑡) +

𝑎_{0} =

𝑝 (𝑡)

. Every step uses only cofactor expansion, the determinant of a triangular matrix, and ring arithmetic. By Proposition 7.3.2(e) and (f) these hold in

{𝐹 [𝑥]}^{𝑛 \times 𝑛}

, so the same induction, with the indeterminate

𝑥

in place of the scalar

𝑡

, proves

det (𝑥 𝐼_{𝑛} - 𝐶_{𝑝}) =

𝑥 𝑞 +

𝑎_{0} =

𝑝

𝐹 [𝑥]

. □

Proof (by expanding along the last column).standard

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Definition 7.3.23 (Companion matrix)

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12)

Hint 1. The last column of

𝑥 𝐼_{𝑛} - 𝐶_{𝑝}

(𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛 - 2}, 𝑥 + 𝑎_{𝑛 - 1})

. Expand along it.

Hint 2. Deleting row

𝑘

and column

𝑛

leaves a block-diagonal matrix: a lower triangular block of size

𝑘 - 1

with

𝑥

on the diagonal, and an upper triangular block of size

𝑛 - 𝑘

with

- 1

on the diagonal.

Hint 3. So the minor is

𝑥^{𝑘 - 1} {(- 1)}^{𝑛 - 𝑘}

, and the sign

{(- 1)}^{𝑘 + 𝑛}

cancels the

{(- 1)}^{𝑛 - 𝑘}

Sketch. Let

𝑀 = 𝑥 𝐼_{𝑛} - 𝐶_{𝑝}

. The minor

𝑀_{\hat{𝑘 𝑛}}

is block diagonal, with a lower triangular

(𝑘 - 1) \times (𝑘 - 1)

block with diagonal

𝑥

and an upper triangular

(𝑛 - 𝑘) \times (𝑛 - 𝑘)

block with diagonal

- 1

, so

det 𝑀_{\hat{𝑘 𝑛}} =

𝑥^{𝑘 - 1} {(- 1)}^{𝑛 - 𝑘}

. Expanding along column

𝑛

det 𝑀 =

\sum_{𝑘} {(- 1)}^{𝑘 + 𝑛} 𝑚_{𝑘 𝑛} 𝑥^{𝑘 - 1} {(- 1)}^{𝑛 - 𝑘} =

\sum_{𝑘} 𝑚_{𝑘 𝑛} 𝑥^{𝑘 - 1} =

𝑎_{0} +

𝑎_{1} 𝑥 +

\dots +

𝑎_{𝑛 - 2} 𝑥^{𝑛 - 2} +

(𝑥 + 𝑎_{𝑛 - 1}) 𝑥^{𝑛 - 1} =

𝑝

For $𝑛 = 1$ , $𝐶_{𝑝} = (- 𝑎_{0})$ and $det (𝑥 𝐼_{1} - 𝐶_{𝑝}) =$ $𝑥 +$ $𝑎_{0} =$ $𝑝$ . Let $𝑛 \geq 2$ and $𝑀 = 𝑥 𝐼_{𝑛} - 𝐶_{𝑝}$ . Row $𝑘$ of $𝑀$ has $- 1$ in column $𝑘 - 1$ (if $𝑘 \geq 2$ ), $𝑥$ in column $𝑘$ (if $𝑘 \leq 𝑛 - 1$ ), and $𝑚_{𝑘 𝑛} = 𝑎_{𝑘 - 1}$ in column $𝑛$ , except that $𝑚_{𝑛 𝑛} = 𝑥 + 𝑎_{𝑛 - 1}$ ; all other entries are $0$ . Fix $𝑘$ and delete row $𝑘$ and column $𝑛$ .

Rows $1, \dots, 𝑘 - 1$ have their nonzero entries (outside column $𝑛$ ) in columns $1, \dots, 𝑘 - 1$ . They form a $(𝑘 - 1) \times (𝑘 - 1)$ lower triangular block $𝐿$ with diagonal entries $𝑥$ .
Rows $𝑘 + 1, \dots, 𝑛$ have their nonzero entries (outside column $𝑛$ ) in columns $𝑘, \dots, 𝑛 - 1$ : row $𝑖$ has $- 1$ in column $𝑖 - 1$ and $𝑥$ in column $𝑖$ (if $𝑖 \leq 𝑛 - 1$ ). They form an $(𝑛 - 𝑘) \times (𝑛 - 𝑘)$ upper triangular block $𝑈$ with diagonal entries $- 1$ .

So $𝑀_{\hat{𝑘 𝑛}} = (\begin{matrix} 𝐿 & 0 \\ 0 & 𝑈 \end{matrix})$ , and by Proposition 7.3.2(e), $det 𝑀_{\hat{𝑘 𝑛}} =$ $𝑥^{𝑘 - 1} {(- 1)}^{𝑛 - 𝑘}$ . (For $𝑘 = 1$ there is no block $𝐿$ , and for $𝑘 = 𝑛$ no block $𝑈$ ; the formula still holds.) Expanding along column $𝑛$ (Proposition 7.3.2(f)),

\begin{aligned} det 𝑀 & = \sum_{𝑘 = 1}^{𝑛} {(- 1)}^{𝑘 + 𝑛} 𝑚_{𝑘 𝑛} 𝑥^{𝑘 - 1} {(- 1)}^{𝑛 - 𝑘} = \sum_{𝑘 = 1}^{𝑛} 𝑚_{𝑘 𝑛} 𝑥^{𝑘 - 1} \\ = 𝑎_{0} + 𝑎_{1} 𝑥 + \dots + 𝑎_{𝑛 - 2} 𝑥^{𝑛 - 2} + (𝑥 + 𝑎_{𝑛 - 1}) 𝑥^{𝑛 - 1} = 𝑝, \end{aligned}

since ${(- 1)}^{𝑘 + 𝑛} {(- 1)}^{𝑛 - 𝑘} =$ ${(- 1)}^{2 𝑛} =$ $1$ . □

The first proof builds $𝑝$ from the inside out, as in Horner’s scheme. The second reads all coefficients off at once: the cofactor of the entry in row $𝑘$ of the last column is exactly $𝑥^{𝑘 - 1}$ , so the last column of $𝑥 𝐼_{𝑛} - 𝐶_{𝑝}$ is the list of coefficients of $𝑝$ and the expansion reassembles $𝑝$ .

Example 7.3.25 (Matrices with prescribed eigenvalues).

(a)The polynomial $𝑝 = 𝑥^{3} - 2$ has no root in $ℚ$ (a rational root would be an integer dividing $2$ , by the argument of Exercise 7.3.42, and none of $\pm 1, \pm 2$ works). So $𝐶_{𝑝} =$ $(\begin{matrix} 0 & 0 & 2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) \in$ $ℚ^{3 \times 3}$ has no eigenvalues in $ℚ$ , although over $ℝ$ it has the eigenvalue $\sqrt[3]{2}$ .
(b)To get a real $2 \times 2$ matrix with eigenvalues $3$ and $- 1$ that is neither diagonal nor triangular, take $𝑝 =$ $(𝑥 - 3) (𝑥 + 1) =$ $𝑥^{2} -$ $2 𝑥 -$ $3$ and $𝐶_{𝑝} = (\begin{matrix} 0 & 3 \\ 1 & 2 \end{matrix})$ .

The connection with Krylov subspaces gives the companion matrix its meaning. By Proposition 7.2.35, if $𝐯 \neq 𝟎$ and $𝐾_{𝑇} (𝐯)$ is finite-dimensional, then $𝐯,$ $𝑇 𝐯,$ $\dots,$ $𝑇^{𝑑 - 1} 𝐯$ is a basis of $𝐾_{𝑇} (𝐯)$ , and

𝑇^{𝑑} 𝐯 = - (𝑐_{0} 𝐯 + 𝑐_{1} 𝑇 𝐯 + \dots + 𝑐_{𝑑 - 1} 𝑇^{𝑑 - 1} 𝐯) .

In this basis, $𝑇 ↾_{𝐾_{𝑇} (𝐯)}$ moves each basis vector to the next and sends the last one to the vector with coordinates $- (𝑐_{0}, \dots, 𝑐_{𝑑 - 1})$ . That is the description of $𝐶_{𝑝}$ for $𝑝 =$ $𝑥^{𝑑} +$ $𝑐_{𝑑 - 1} 𝑥^{𝑑 - 1} +$ $\dots +$ $𝑐_{0}$ .

Proposition 7.3.26 (Krylov subspaces and the characteristic polynomial). Let $𝑉$ be finite-dimensional, $𝑇 \in L (𝑉)$ , and $𝐯 \in 𝑉$ with $𝐯 \neq 𝟎$ . Let $𝑑$ and the monic polynomial $𝑝$ of degree $𝑑$ be as in Proposition 7.2.35, so that $𝑝 (𝑇) 𝐯 = 𝟎$ . Then

(a)the matrix of $𝑇 ↾_{𝐾_{𝑇} (𝐯)}$ in the basis $𝐯,$ $𝑇 𝐯,$ $\dots,$ $𝑇^{𝑑 - 1} 𝐯$ is $𝐶_{𝑝}$ ;
(b) $𝑝_{𝑇 ↾_{𝐾_{𝑇} (𝐯)}} = 𝑝$ ;
(c) $𝑝$ divides $𝑝_{𝑇}$ .

Proof.routine

Uses. Proposition 7.2.35 (A basis of a Krylov subspace), Proposition 7.2.34 (The smallest invariant subspace containing a vector), Definition 2.3.1 (Matrix of a linear map), Theorem 7.3.24 (Every monic polynomial is a characteristic polynomial), Corollary 7.3.16 (Invariant subspaces give factors)

Hint 1. Compute

𝑇

on each basis vector

𝑇^{𝑖} 𝐯

and write the result in the basis.

Hint 2. For (b) use Theorem 7.3.24, and for (c) use that

𝐾_{𝑇} (𝐯)

𝑇

-invariant.

Sketch.

𝑇 (𝑇^{𝑖} 𝐯) =

𝑇^{𝑖 + 1} 𝐯

for

𝑖 < 𝑑 - 1

, and

𝑇 (𝑇^{𝑑 - 1} 𝐯) =

- \sum_{𝑖} 𝑐_{𝑖} 𝑇^{𝑖} 𝐯

, so the columns are

𝐞_{2}, \dots, 𝐞_{𝑑}

and

- (𝑐_{0}, \dots, 𝑐_{𝑑 - 1})

, which is

𝐶_{𝑝}

. Then the characteristic polynomial is

𝑝_{𝐶_{𝑝}} = 𝑝

, and

𝑝

divides

𝑝_{𝑇}

because

𝐾_{𝑇} (𝐯)

is invariant (Corollary 7.3.16).

Write

𝑝 =

𝑥^{𝑑} +

𝑐_{𝑑 - 1} 𝑥^{𝑑 - 1} +

\dots +

𝑐_{0}

and

𝐛_{𝑖 + 1} = 𝑇^{𝑖} 𝐯

for

0 \leq 𝑖 \leq 𝑑 - 1

. For

𝑖 < 𝑑 - 1

𝑇 𝐛_{𝑖 + 1} =

𝑇^{𝑖 + 1} 𝐯 =

𝐛_{𝑖 + 2}

, and

𝑇 𝐛_{𝑑} =

𝑇^{𝑑} 𝐯 =

- (𝑐_{0} 𝐛_{1} + \dots + 𝑐_{𝑑 - 1} 𝐛_{𝑑})

because

𝑝 (𝑇) 𝐯 = 𝟎

. So column

𝑘

of the matrix of

𝑇 ↾_{𝐾_{𝑇} (𝐯)}

𝐞_{𝑘 + 1}

for

𝑘 < 𝑑

, and the last column is

- (𝑐_{0}, \dots, 𝑐_{𝑑 - 1})

(Definition 2.3.1). This is

𝐶_{𝑝}

, proving (a). Then (b) follows from (a), Definition 7.3.12, and Theorem 7.3.24. Since

𝐾_{𝑇} (𝐯)

𝑇

-invariant (Proposition 7.2.34) and has dimension

𝑑 \geq 1

, (c) follows from (b) and Corollary 7.3.16. □

So every nonzero vector produces a factor of $𝑝_{𝑇}$ , namely the polynomial that records the first dependence among $𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots$ . In Example 7.2.36, the vectors $(1, 1, 1)$ , $(1, - 1, 0)$ , and $𝐞_{1}$ produced $𝑥 - 1$ , $𝑥^{2} + 𝑥 + 1$ , and $𝑥^{3} - 1$ , and each divides $𝑝_{𝑍} = 𝑥^{3} - 1$ . When $𝐾_{𝑇} (𝐯) = 𝑉$ , part (b) says $𝑝_{𝑇} = 𝑝$ (Exercise 7.3.50).

7.3.6Eigenvalues exist over $ℂ$

Example 7.2.18 showed that a real operator need not have an eigenvalue, and Example 7.2.20 that an operator on an infinite-dimensional space need not either. Neither obstruction survives over $ℂ$ in finite dimensions.

Theorem 7.3.27 (Existence of eigenvalues over

ℂ

). Let

𝑉

be a finite-dimensional complex vector space with

𝑉 \neq {𝟎}

, and let

𝑇 \in L (𝑉)

. Then

𝑇

has an eigenvalue. In particular, every

𝐴 \in ℂ^{𝑛 \times 𝑛}

with

𝑛 \geq 1

has an eigenvalue.

The two proofs below locate the eigenvalue in two different polynomials. The first uses $𝑝_{𝑇}$ , which collects all eigenvalues at once and needs determinants. The second uses the polynomial of a single Krylov sequence, which only needs linear dependence.

Proof (via the characteristic polynomial).routine

Uses. Proposition 7.3.18 (The first and last coefficients), Theorem 7.1.32 (Fundamental Theorem of Algebra), Corollary 7.3.13 (Eigenvalues of an operator)

Hint 1. What is the degree of

𝑝_{𝑇}

Hint 2. A polynomial of degree at least

1

over

ℂ

has a root (Theorem 7.1.32).

Sketch.

𝑝_{𝑇}

has degree

dim 𝑉 \geq 1

, so it has a root

𝜆 \in ℂ

by the FTA, and

𝜆

is an eigenvalue by Corollary 7.3.13.

Let

𝑛 = dim 𝑉 \geq 1

. By Proposition 7.3.18,

𝑝_{𝑇}

is monic of degree

𝑛

, in particular nonconstant. By Theorem 7.1.32 it has a root

𝜆 \in ℂ

, and

𝜆

is an eigenvalue of

𝑇

by Corollary 7.3.13. □

Intuition (A proof without determinants). Take any $𝐯 \neq 𝟎$ and look at $𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots$ . In a space of dimension $𝑛$ , the $𝑛 + 1$ vectors $𝐯, \dots, 𝑇^{𝑛} 𝐯$ are dependent, so some nonzero polynomial $𝑞$ has $𝑞 (𝑇) 𝐯 = 𝟎$ . Over $ℂ$ we can factor $𝑞 =$ $𝑐 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑚})$ , so

𝑐 (𝑇 - 𝜆_{1} id) (𝑇 - 𝜆_{2} id) \dots (𝑇 - 𝜆_{𝑚} id) 𝐯 = 𝟎

with $𝐯 \neq 𝟎$ . A composite of injective maps is injective, so some factor $𝑇 - 𝜆_{𝑗} id$ is not injective, and $𝜆_{𝑗}$ is an eigenvalue. If we use the first dependence, the polynomial $𝑝$ of Proposition 7.2.35, we can even say which vector is the eigenvector: split off one linear factor, $𝑝 = (𝑥 - 𝜆) 𝑞$ , and apply $𝑞 (𝑇)$ to $𝐯$ . The result is nonzero because $𝑞$ has smaller degree than $𝑝$ , and $𝑇 - 𝜆 id$ kills it.

Technique 7.3.28 (Krylov sequences must become dependent). In a finite-dimensional space, the sequence $𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots$ eventually becomes dependent, and the first dependence is a monic polynomial $𝑝$ with $𝑝 (𝑇) 𝐯 = 𝟎$ and no nonzero polynomial of smaller degree killing $𝐯$ (Proposition 7.2.35). This converts a question about $𝑇$ into a question about one polynomial: factor $𝑝$ , and use the factors to build vectors. If $𝑝 = 𝑓 𝑞$ with $deg 𝑓 \geq 1$ , then $𝐰 = 𝑞 (𝑇) 𝐯$ is nonzero and $𝑓 (𝑇) 𝐰 = 𝟎$ , so a factor $𝑓 = 𝑥 - 𝜆$ produces an eigenvector, and a quadratic factor produces a two-dimensional invariant subspace (Theorem 7.3.31).

Reach for it when you need an eigenvector or a small invariant subspace and want to avoid determinants, or when $𝑉$ is infinite-dimensional but some Krylov subspace is not. The canonical example is the second proof of Theorem 7.3.27.

Used in 10 places and 1 practice exercise

Theorem 7.3.27, Theorem 7.3.31, Exercise 7.3.45, Exercise 7.3.46, Exercise 7.3.51, Lemma 7.6.21, Exercise 7.6.47, Problem 7.9, Problem 7.15, Theorem 8.1.3; 1 practice exercise.

Proof (via a Krylov sequence, without determinants).standard

Uses. Proposition 7.2.35 (A basis of a Krylov subspace), Theorem 7.1.32 (Fundamental Theorem of Algebra), Theorem 7.1.20 (Factor theorem), Proposition 7.2.27 (Evaluating polynomials at an operator), Definition 7.2.6 (Eigenvalue, eigenvector)

Techniques. Krylov sequences must become dependent (Technique 7.3.28), Too many vectors force a dependence (Technique 4.1.30)

Hint 1. Fix

𝐯 \neq 𝟎

. The sequence

𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots

cannot stay independent. Use the first dependence, from Proposition 7.2.35.

Hint 2. This gives a monic

𝑝

of degree

𝑑 \geq 1

with

𝑝 (𝑇) 𝐯 = 𝟎

, and no nonzero polynomial of degree less than

𝑑

kills

𝐯

. Use the FTA to split off a linear factor

𝑥 - 𝜆

Hint 3. Write

𝑝 = (𝑥 - 𝜆) 𝑞

. Then

𝑞 (𝑇) 𝐯 \neq 𝟎

(why?) and

(𝑇 - 𝜆 id) 𝑞 (𝑇) 𝐯 =

𝑝 (𝑇) 𝐯

Sketch. Let

𝐯 \neq 𝟎

and let

𝑝

, of degree

𝑑 \geq 1

, record the first dependence among

𝐯, 𝑇 𝐯, \dots

(Proposition 7.2.35). By the FTA and the factor theorem,

𝑝 = (𝑥 - 𝜆) 𝑞

with

𝑞

monic of degree

𝑑 - 1

. Then

𝐰 = 𝑞 (𝑇) 𝐯 \neq 𝟎

by the minimality of

𝑑

, and

(𝑇 - 𝜆 id) 𝐰 =

𝑝 (𝑇) 𝐯 =

𝟎

. So

𝐰

is an eigenvector for

𝜆

Choose $𝐯 \in 𝑉$ with $𝐯 \neq 𝟎$ . Since $𝑉$ is finite-dimensional, so is $𝐾_{𝑇} (𝐯)$ , and Proposition 7.2.35 gives $𝑑 \geq 1$ and a monic polynomial $𝑝 \in ℂ [𝑥]$ of degree $𝑑$ with $𝑝 (𝑇) 𝐯 = 𝟎$ , such that no nonzero polynomial of degree less than $𝑑$ sends $𝐯$ to $𝟎$ .

As $deg 𝑝 = 𝑑 \geq 1$ , the FTA (Theorem 7.1.32) gives a root $𝜆 \in ℂ$ of $𝑝$ , and the factor theorem (Theorem 7.1.20) gives $𝑝 = (𝑥 - 𝜆) 𝑞$ for some $𝑞 \in ℂ [𝑥]$ . Comparing leading coefficients and degrees, $𝑞$ is monic of degree $𝑑 - 1$ ; in particular $𝑞 \neq 𝟎$ . Let $𝐰 = 𝑞 (𝑇) 𝐯$ . Since $𝑞$ is nonzero of degree less than $𝑑$ , $𝐰 \neq 𝟎$ . By Proposition 7.2.27(a),

(𝑇 - 𝜆 id) 𝐰 = ((𝑥 - 𝜆) 𝑞) (𝑇) 𝐯 = 𝑝 (𝑇) 𝐯 = 𝟎 .

So $𝑇 𝐰 = 𝜆 𝐰$ with $𝐰 \neq 𝟎$ , and $𝜆$ is an eigenvalue of $𝑇$ (Definition 7.2.6). □

Example 7.3.29 (Finding an eigenvector from a Krylov sequence). Let $𝐴 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) \in ℂ^{2 \times 2}$ and $𝐯 = 𝐞_{1}$ . Then $𝐴 𝐯 = 𝐞_{2}$ , which is not a multiple of $𝐞_{1}$ , and $𝐴^{2} 𝐯 = - 𝐞_{1} = - 𝐯$ . So the first dependence is $𝐴^{2} 𝐯 + 𝐯 = 𝟎$ , and $𝑝 =$ $𝑥^{2} +$ $1 =$ $(𝑥 - 𝑖) (𝑥 + 𝑖)$ . Splitting off $𝑥 - 𝑖$ leaves $𝑞 = 𝑥 + 𝑖$ , and

𝐰 = (𝐴 + 𝑖 𝐼_{2}) 𝐞_{1} = (𝑖, 1), 𝐴 𝐰 = (- 1, 𝑖) = 𝑖 (𝑖, 1) .

Splitting off $𝑥 + 𝑖$ instead gives $(𝐴 - 𝑖 𝐼_{2}) 𝐞_{1} =$ $(- 𝑖, 1)$ , an eigenvector for $- 𝑖$ . For the cyclic permutation $𝑍$ and $𝐯 = 𝐞_{1}$ , the first dependence is $𝑥^{3} -$ $1 =$ $(𝑥 - 1) (𝑥^{2} + 𝑥 + 1)$ (Example 7.2.36), and $(𝑍^{2} + 𝑍 + id) 𝐞_{1} =$ $(1, 1, 1)$ is the eigenvector for $1$ .

Intuition (Comparing the two proofs). The first proof is shorter, but it rests on determinants over $𝐹 [𝑥]$ , and it finds an eigenvalue without an eigenvector. The second proof needs only linear dependence and polynomial arithmetic. It also uses less: it never needs all of $𝑉$ , only the finite-dimensional subspace $𝐾_{𝑇} (𝐯)$ . So it shows, for instance, that an operator on an infinite-dimensional complex space has an eigenvalue as soon as some nonzero vector has a finite-dimensional Krylov subspace. On the other hand, the first proof locates every eigenvalue at once, with multiplicities, which the second does not.

Both proofs use exactly one property of $ℂ$ : every nonconstant polynomial over $ℂ$ has a root. So both prove the theorem over any field with this property, and over $ℝ$ both fail at the same step, with the rotation as the witness: its characteristic polynomial is $𝑥^{2} + 1$ , and so is the Krylov polynomial of every $𝐯 \neq 𝟎$ . Over a finite field the theorem always fails (Exercise 7.3.44).

7.3.7Real operators Beyond 21-242

Real operators and complexification are covered in LADR and LADW (5.8), but not in 21-242 lecture.

Over $ℝ$ an operator may have no eigenvalue, but it cannot avoid small invariant subspaces altogether.

Proposition 7.3.30 (Odd dimension). Let

𝑉

be a real vector space of odd dimension. Then every

𝑇 \in L (𝑉)

has an eigenvalue.

Proof.routine

Uses. Proposition 7.3.18 (The first and last coefficients), Corollary 7.1.43 (Odd degree gives a real root), Corollary 7.3.13 (Eigenvalues of an operator)

Hint. What is the degree of

𝑝_{𝑇}

, and what do you know about real polynomials of that degree?

Sketch.

𝑝_{𝑇} \in ℝ [𝑥]

has odd degree

dim 𝑉

, so it has a real root (Corollary 7.1.43), which is an eigenvalue.

By Proposition 7.3.18,

𝑝_{𝑇} \in ℝ [𝑥]

has degree

dim 𝑉

, which is odd. By Corollary 7.1.43 it has a real root

𝜆

, and

𝜆

is an eigenvalue of

𝑇

by Corollary 7.3.13. □

For example, every operator on $ℝ^{3}$ maps some line to itself; for a rotation this is its axis. In even dimension there may be no eigenvalue: the operator on $ℝ^{4}$ with matrix $(\begin{matrix} 𝑅_{𝜋 / 2} & 0 \\ 0 & 𝑅_{𝜋 / 2} \end{matrix})$ has characteristic polynomial ${(𝑥^{2} + 1)}^{2}$ by Proposition 7.3.15. It still has invariant planes, such as $span (𝐞_{1}, 𝐞_{2})$ .

Theorem 7.3.31 (Small invariant subspaces). Let

𝑉

be a finite-dimensional real vector space with

𝑉 \neq {𝟎}

, and let

𝑇 \in L (𝑉)

. Then

𝑇

has an invariant subspace of dimension

1

2

Proof (via a Krylov sequence).standard

Uses. Proposition 7.2.35 (A basis of a Krylov subspace), Theorem 7.1.39 (Factorization over $ℝ$ ), Proposition 7.2.27 (Evaluating polynomials at an operator), Proposition 7.2.4 (Invariance is checked on a spanning list), Proposition 7.2.7 (Invariant lines are spanned by eigenvectors)

Techniques. Krylov sequences must become dependent (Technique 7.3.28)

Hint 1. Imitate the second proof of Theorem 7.3.27. What replaces the FTA over

ℝ

Hint 2. By Theorem 7.1.39, the polynomial

𝑝

of the first dependence has a monic factor

𝑓

of degree

1

2

. Write

𝑝 = 𝑓 𝑞

and set

𝐰 = 𝑞 (𝑇) 𝐯

Hint 3. If

𝑓 = 𝑥^{2} + 𝑏 𝑥 + 𝑐

, then

𝑇^{2} 𝐰 =

- 𝑏 𝑇 𝐰 -

𝑐 𝐰

. Which subspace is invariant?

Sketch. Let

𝑝

record the first dependence of a Krylov sequence. Over

ℝ

𝑝

has a monic factor

𝑓

of degree

1

2

(Theorem 7.1.39); write

𝑝 = 𝑓 𝑞

. Then

𝐰 = 𝑞 (𝑇) 𝐯 \neq 𝟎

and

𝑓 (𝑇) 𝐰 = 𝟎

. If

𝑓 = 𝑥 - 𝜆

𝐰

spans an invariant line. If

𝑓 = 𝑥^{2} + 𝑏 𝑥 + 𝑐

, then

𝑇 (𝑇 𝐰) =

- 𝑏 𝑇 𝐰 -

𝑐 𝐰

, so

span (𝐰, 𝑇 𝐰)

is invariant, of dimension

1

2

Choose $𝐯 \neq 𝟎$ and let $𝑝$ , monic of degree $𝑑 \geq 1$ , be as in Proposition 7.2.35. By Theorem 7.1.39, $𝑝$ is a product of monic factors of degree $1$ and $2$ (times its leading coefficient $1$ ), so $𝑝 = 𝑓 𝑞$ with $𝑓$ monic of degree $1$ or $2$ and $𝑞$ monic of degree less than $𝑑$ . Let $𝐰 = 𝑞 (𝑇) 𝐯$ . Then $𝐰 \neq 𝟎$ by the minimality in Proposition 7.2.35, and $𝑓 (𝑇) 𝐰 =$ $𝑝 (𝑇) 𝐯 =$ $𝟎$ by Proposition 7.2.27(a).

If $𝑓 = 𝑥 - 𝜆$ , then $𝑇 𝐰 = 𝜆 𝐰$ , so $span (𝐰)$ is an invariant line (Proposition 7.2.7). If $𝑓 = 𝑥^{2} + 𝑏 𝑥 + 𝑐$ , then $𝑇^{2} 𝐰 +$ $𝑏 𝑇 𝐰 +$ $𝑐 𝐰 =$ $𝟎$ . Let $𝑈 = span (𝐰, 𝑇 𝐰)$ . Then $𝑇 𝐰 \in 𝑈$ and $𝑇 (𝑇 𝐰) =$ $- 𝑏 𝑇 𝐰 -$ $𝑐 𝐰 \in$ $𝑈$ , so $𝑈$ is $𝑇$ -invariant by Proposition 7.2.4. It has dimension $1$ or $2$ , since $𝐰 \neq 𝟎$ and it is spanned by two vectors. □

A second proof, through complex eigenvectors, follows in the next subsection.

7.3.8Complexification Beyond 21-242

To use complex eigenvalues for a real operator, we need a complex vector space for it to act on. For $ℝ^{𝑛}$ the answer is $ℂ^{𝑛}$ : a real matrix is also a complex matrix. For an abstract real vector space $𝑉$ , we build the complex space by adjoining “imaginary parts”, just as $ℂ$ is built from $ℝ$ (Definition 1.1.29).

Definition 7.3.32 (Complexification). Let $𝑉$ be a real vector space. Its complexification $𝑉_{ℂ}$ is the set $𝑉 \times 𝑉$ , whose element $(𝐮, 𝐯)$ we write $𝐮 + 𝑖 𝐯$ , with addition $(𝐮 + 𝑖 𝐯) +$ $(𝐮^{'} + 𝑖 𝐯^{'}) =$ $(𝐮 + 𝐮^{'}) +$ $𝑖 (𝐯 + 𝐯^{'})$ and scalar multiplication by $𝑎 + 𝑏 𝑖 \in ℂ$ ( $𝑎, 𝑏 \in ℝ$ ) given by

(𝑎 + 𝑏 𝑖) (𝐮 + 𝑖 𝐯) = (𝑎 𝐮 - 𝑏 𝐯) + 𝑖 (𝑏 𝐮 + 𝑎 𝐯) .

We identify $𝐮 \in 𝑉$ with $𝐮 + 𝑖 𝟎 \in 𝑉_{ℂ}$ . For $𝑇 \in L (𝑉)$ , its complexification is $𝑇_{ℂ} : 𝑉_{ℂ} \to 𝑉_{ℂ}$ , $𝑇_{ℂ} (𝐮 + 𝑖 𝐯) =$ $𝑇 𝐮 +$ $𝑖 𝑇 𝐯$ .

The formula for scalar multiplication is what we get by expanding $(𝑎 + 𝑏 𝑖) (𝐮 + 𝑖 𝐯)$ formally with $𝑖^{2} = - 1$ . For $𝑉 = ℝ^{𝑛}$ , the map $𝐮 +$ $𝑖 𝐯 \mapsto$ $𝐮 +$ $𝑖 𝐯 \in$ $ℂ^{𝑛}$ (with the right side computed coordinatewise) identifies $𝑉_{ℂ}$ with $ℂ^{𝑛}$ , and $𝑇_{ℂ}$ with the complex matrix of $𝑇$ .

Proposition 7.3.33 (Basic properties). Let $𝑉$ be a real vector space and $𝑇 \in L (𝑉)$ .

(a) $𝑉_{ℂ}$ is a complex vector space.
(b)If $𝐛_{1}, \dots, 𝐛_{𝑛}$ is a basis of $𝑉$ over $ℝ$ , it is a basis of $𝑉_{ℂ}$ over $ℂ$ . In particular ${dim}_{ℂ} 𝑉_{ℂ} = {dim}_{ℝ} 𝑉$ .
(c) $𝑇_{ℂ}$ is $ℂ$ -linear, and ${[𝑇_{ℂ}]}_{ℬ︀ ℬ︀} =$ ${[𝑇]}_{ℬ︀ ℬ︀}$ for every basis $ℬ︀$ of $𝑉$ . In particular $𝑝_{𝑇_{ℂ}} = 𝑝_{𝑇}$ when $𝑉$ is finite-dimensional and nonzero.

Proof.standard

Uses. Definition 7.3.32 (Complexification), Definition 1.2.1 (Vector space), Definition 1.6.1 (Basis), Definition 2.3.1 (Matrix of a linear map), Definition 7.3.12 (Characteristic polynomial of an operator)

Hint 1. For (a), most axioms hold coordinatewise. The interesting one is

(𝛼 𝛽) 𝐳 = 𝛼 (𝛽 𝐳)

; expand both sides with

𝛼 = 𝑎 + 𝑏 𝑖

𝛽 = 𝑐 + 𝑑 𝑖

Hint 2. For (b), write

𝐮 + 𝑖 𝐯

with

𝐮 = \sum 𝛼_{𝑘} 𝐛_{𝑘}

and

𝐯 = \sum 𝛽_{𝑘} 𝐛_{𝑘}

, and compute

\sum (𝛼_{𝑘} + 𝑖 𝛽_{𝑘}) 𝐛_{𝑘}

Hint 3. For (c), check

𝑇_{ℂ} ((𝑎 + 𝑏 𝑖) 𝐳) =

(𝑎 + 𝑏 𝑖) 𝑇_{ℂ} (𝐳)

directly, and compute

𝑇_{ℂ} 𝐛_{𝑗}

Sketch. (a) Addition is that of

𝑉 \times 𝑉

; scalar multiplication satisfies

1 𝐳 = 𝐳

, both distributive laws (by linearity of the formula in

(𝑎, 𝑏)

and in

(𝐮, 𝐯)

), and associativity, which reduces to the multiplication rule of

ℂ

. (b)

\sum (𝛼_{𝑘} + 𝑖 𝛽_{𝑘}) 𝐛_{𝑘} =

\sum 𝛼_{𝑘} 𝐛_{𝑘} +

𝑖 \sum 𝛽_{𝑘} 𝐛_{𝑘}

, so spanning and independence over

ℂ

reduce to the same statements over

ℝ

for the real and imaginary parts. (c) Expanding gives linearity;

𝑇_{ℂ} 𝐛_{𝑗} = 𝑇 𝐛_{𝑗}

has the same real coordinates.

(a) $𝑉 \times 𝑉$ is a real vector space under coordinatewise operations, so addition in $𝑉_{ℂ}$ satisfies the additive axioms. For scalar multiplication, $1 (𝐮 + 𝑖 𝐯) =$ $𝐮 +$ $𝑖 𝐯$ is the case $𝑎 = 1$ , $𝑏 = 0$ . The formula is additive in $𝑎 + 𝑏 𝑖$ and in $𝐮 + 𝑖 𝐯$ separately, which gives the two distributive laws. For associativity, let $𝛼 = 𝑎 + 𝑏 𝑖$ and $𝛽 = 𝑐 + 𝑑 𝑖$ . Then

\begin{aligned} 𝛼 (𝛽 (𝐮 + 𝑖 𝐯)) & = 𝛼 ((𝑐 𝐮 - 𝑑 𝐯) + 𝑖 (𝑑 𝐮 + 𝑐 𝐯)) \\ = (𝑎 (𝑐 𝐮 - 𝑑 𝐯) - 𝑏 (𝑑 𝐮 + 𝑐 𝐯)) + 𝑖 (𝑏 (𝑐 𝐮 - 𝑑 𝐯) + 𝑎 (𝑑 𝐮 + 𝑐 𝐯)) \\ = ((𝑎 𝑐 - 𝑏 𝑑) 𝐮 - (𝑎 𝑑 + 𝑏 𝑐) 𝐯) + 𝑖 ((𝑎 𝑑 + 𝑏 𝑐) 𝐮 + (𝑎 𝑐 - 𝑏 𝑑) 𝐯), \end{aligned}

which is $(𝛼 𝛽) (𝐮 + 𝑖 𝐯)$ since $𝛼 𝛽 =$ $(𝑎 𝑐 - 𝑏 𝑑) +$ $(𝑎 𝑑 + 𝑏 𝑐) 𝑖$ .

(b) For $𝛼_{𝑘}, 𝛽_{𝑘} \in ℝ$ , $(𝛼_{𝑘} + 𝑖 𝛽_{𝑘}) 𝐛_{𝑘} =$ $(𝛼_{𝑘} + 𝑖 𝛽_{𝑘}) (𝐛_{𝑘} + 𝑖 𝟎) =$ $𝛼_{𝑘} 𝐛_{𝑘} +$ $𝑖 𝛽_{𝑘} 𝐛_{𝑘}$ , so

\sum_{𝑘} (𝛼_{𝑘} + 𝑖 𝛽_{𝑘}) 𝐛_{𝑘} = \sum_{𝑘} 𝛼_{𝑘} 𝐛_{𝑘} + 𝑖 \sum_{𝑘} 𝛽_{𝑘} 𝐛_{𝑘} .

(7.3.2)

Every $𝐮 + 𝑖 𝐯 \in 𝑉_{ℂ}$ is of this form, by expanding $𝐮$ and $𝐯$ in the basis, so the $𝐛_{𝑘}$ span $𝑉_{ℂ}$ . If the left side of (7.3.2) is $𝟎$ , then $\sum 𝛼_{𝑘} 𝐛_{𝑘} = 𝟎$ and $\sum 𝛽_{𝑘} 𝐛_{𝑘} = 𝟎$ , so all $𝛼_{𝑘}$ and $𝛽_{𝑘}$ vanish. Hence the $𝐛_{𝑘}$ are independent over $ℂ$ .

(c) $𝑇_{ℂ}$ is additive because $𝑇$ is. For $𝑎 + 𝑏 𝑖 \in ℂ$ ,

𝑇_{ℂ} ((𝑎 + 𝑏 𝑖) (𝐮 + 𝑖 𝐯)) = 𝑇 (𝑎 𝐮 - 𝑏 𝐯) + 𝑖 𝑇 (𝑏 𝐮 + 𝑎 𝐯) = (𝑎 𝑇 𝐮 - 𝑏 𝑇 𝐯) + 𝑖 (𝑏 𝑇 𝐮 + 𝑎 𝑇 𝐯),

which is $(𝑎 + 𝑏 𝑖) (𝑇 𝐮 + 𝑖 𝑇 𝐯)$ . Finally, $𝑇_{ℂ} 𝐛_{𝑗} =$ $𝑇 𝐛_{𝑗} +$ $𝑖 𝟎 =$ $\sum_{𝑘} 𝑡_{𝑘 𝑗} 𝐛_{𝑘}$ , where ${[𝑇]}_{ℬ︀ ℬ︀} = (𝑡_{𝑘 𝑗})$ , so $𝑇_{ℂ}$ has the same matrix (Definition 2.3.1) and the same characteristic polynomial. □

Conjugation $𝐮 + 𝑖 𝐯 = 𝐮 - 𝑖 𝐯$ on $𝑉_{ℂ}$ commutes with $𝑇_{ℂ}$ , and this pairs up the eigenvectors of $𝑇_{ℂ}$ .

Proposition 7.3.34 (Eigenvalues of a complexification). Let $𝑉 \neq {𝟎}$ be a finite-dimensional real vector space and $𝑇 \in L (𝑉)$ .

(a)A real number $𝜆$ is an eigenvalue of $𝑇$ if and only if it is an eigenvalue of $𝑇_{ℂ}$ .
(b)If $𝑇_{ℂ} (𝐮 + 𝑖 𝐯) =$ $𝜆 (𝐮 + 𝑖 𝐯)$ , then $𝑇_{ℂ} (𝐮 - 𝑖 𝐯) =$ $𝜆 (𝐮 - 𝑖 𝐯)$ . So the nonreal eigenvalues of $𝑇_{ℂ}$ come in conjugate pairs.
(c)If $𝜆 = 𝑎 + 𝑏 𝑖$ with $𝑏 \neq 0$ and $𝐮 + 𝑖 𝐯$ is an eigenvector of $𝑇_{ℂ}$ for $𝜆$ , then $𝐮, 𝐯$ is linearly independent, $𝑈 = span (𝐮, 𝐯)$ is $𝑇$ -invariant, and the matrix of $𝑇 ↾_{𝑈}$ in the basis $𝐮, 𝐯$ is $(\begin{matrix} 𝑎 & 𝑏 \\ - 𝑏 & 𝑎 \end{matrix})$ .

Proof.standard

Uses. Proposition 7.3.33 (Basic properties), Corollary 7.3.13 (Eigenvalues of an operator), Proposition 7.2.4 (Invariance is checked on a spanning list), Proposition 7.2.7 (Invariant lines are spanned by eigenvectors), Proposition 1.2.35 (Zero products)

Techniques. Complexify, then take real and imaginary parts (Technique 7.3.35)

Hint 1. For (a), compare characteristic polynomials.

Hint 2. For (b) and (c), write out

𝑇_{ℂ} (𝐮 + 𝑖 𝐯) =

(𝑎 + 𝑏 𝑖) (𝐮 + 𝑖 𝐯)

and compare the parts in front of

𝑖

and outside it.

Hint 3. You should get

𝑇 𝐮 = 𝑎 𝐮 - 𝑏 𝐯

and

𝑇 𝐯 = 𝑏 𝐮 + 𝑎 𝐯

. If

𝐮, 𝐯

were dependent, they would lie on a

𝑇

-invariant line.

Sketch. (a)

𝑝_{𝑇_{ℂ}} = 𝑝_{𝑇}

. (b), (c) Comparing real and imaginary parts,

𝑇 𝐮 = 𝑎 𝐮 - 𝑏 𝐯

and

𝑇 𝐯 = 𝑏 𝐮 + 𝑎 𝐯

, which gives both the conjugate eigenvector and the invariant plane with matrix

(\begin{matrix} 𝑎 & 𝑏 \\ - 𝑏 & 𝑎 \end{matrix})

. If

𝐮, 𝐯

were dependent, they would lie on an invariant line on which

𝑇

acts by a real

𝜇

, forcing

𝜆 = 𝜇

(a) By Proposition 7.3.33(c), $𝑝_{𝑇_{ℂ}} = 𝑝_{𝑇}$ . For real $𝜆$ , both statements say $𝑝_{𝑇} (𝜆) = 0$ , by Corollary 7.3.13 applied to $𝑇$ and to $𝑇_{ℂ}$ .

(b) Let $𝜆 = 𝑎 + 𝑏 𝑖$ . The equation $𝑇 𝐮 +$ $𝑖 𝑇 𝐯 =$ $(𝑎 𝐮 - 𝑏 𝐯) +$ $𝑖 (𝑏 𝐮 + 𝑎 𝐯)$ is an equation in $𝑉 \times 𝑉$ , so

𝑇 𝐮 = 𝑎 𝐮 - 𝑏 𝐯, 𝑇 𝐯 = 𝑏 𝐮 + 𝑎 𝐯 .

(7.3.3)

Then $𝑇_{ℂ} (𝐮 - 𝑖 𝐯) =$ $(𝑎 𝐮 - 𝑏 𝐯) -$ $𝑖 (𝑏 𝐮 + 𝑎 𝐯)$ , and the definition of scalar multiplication gives the same vector for $(𝑎 - 𝑏 𝑖) (𝐮 + 𝑖 (- 𝐯))$ . Since $𝐮 + 𝑖 𝐯 \neq 𝟎$ , also $𝐮 - 𝑖 𝐯 \neq 𝟎$ , so $𝜆$ is an eigenvalue whenever $𝜆$ is.

(c) By (7.3.3) and Proposition 7.2.4, $𝑈$ is $𝑇$ -invariant, and the coordinates of $𝑇 𝐮$ and $𝑇 𝐯$ in $𝐮, 𝐯$ are $(𝑎, - 𝑏)$ and $(𝑏, 𝑎)$ , giving the matrix $(\begin{matrix} 𝑎 & 𝑏 \\ - 𝑏 & 𝑎 \end{matrix})$ , once we know that $𝐮, 𝐯$ is independent. Suppose it is not. Since $𝐮$ and $𝐯$ are not both $𝟎$ , $𝑈$ is then a line $span (𝐳)$ , and it is $𝑇$ -invariant, so $𝑇 𝐳 = 𝜇 𝐳$ for some $𝜇 \in ℝ$ (Proposition 7.2.7). Writing $𝐮 = 𝛼 𝐳$ and $𝐯 = 𝛽 𝐳$ with $𝛼, 𝛽 \in ℝ$ , we get $𝑇_{ℂ} (𝐮 + 𝑖 𝐯) =$ $𝜇 (𝐮 + 𝑖 𝐯)$ . Comparing with $𝑇_{ℂ} (𝐮 + 𝑖 𝐯) =$ $𝜆 (𝐮 + 𝑖 𝐯)$ gives $(𝜆 - 𝜇) (𝐮 + 𝑖 𝐯) =$ $𝟎$ , so $𝜆 = 𝜇 \in ℝ$ by Proposition 1.2.35, contradicting $𝑏 \neq 0$ . □

Technique 7.3.35 (Complexify, then take real and imaginary parts). To prove something about an operator $𝑇$ on a real vector space, pass to $𝑇_{ℂ}$ on $𝑉_{ℂ}$ , where the FTA is available, use a complex result (an eigenvector, later a triangular form), and then split the conclusion into real and imaginary parts. A complex eigenvector $𝐮 + 𝑖 𝐯$ for $𝑎 + 𝑏 𝑖$ becomes the pair of real equations (7.3.3), and conjugation exchanges $𝜆$ with $𝜆$ .

Reach for it when a statement about real operators is easy over $ℂ$ , and the obstruction over $ℝ$ is only that $𝑝_{𝑇}$ may have nonreal roots. The canonical example is the second proof of Theorem 7.3.31.

Used in 6 places and 2 practice exercises

Proposition 7.3.34, Theorem 7.3.31, Exercise 7.7.12, Problem 7.17, Exercise 8.2.48, Theorem 8.4.27; 2 practice exercises.

Proof of Theorem 7.3.31 (via complexification).standard

Uses. Theorem 7.3.27 (Existence of eigenvalues over $ℂ$ ), Proposition 7.3.33 (Basic properties), Proposition 7.3.34 (Eigenvalues of a complexification), Proposition 7.2.7 (Invariant lines are spanned by eigenvectors)

Techniques. Complexify, then take real and imaginary parts (Technique 7.3.35)

Hint 1.

𝑇_{ℂ}

acts on a nonzero finite-dimensional complex space. What does Theorem 7.3.27 give?

Hint 2. Split into the cases

𝜆 \in ℝ

and

𝜆 \notin ℝ

, and use Proposition 7.3.34.

Sketch.

𝑇_{ℂ}

has an eigenvalue

𝜆

. If

𝜆

is real, it is an eigenvalue of

𝑇

, and an eigenvector spans an invariant line. Otherwise an eigenvector

𝐮 + 𝑖 𝐯

gives the invariant plane

span (𝐮, 𝐯)

of Proposition 7.3.34(c).

By Proposition 7.3.33(b),

𝑉_{ℂ}

is a nonzero finite-dimensional complex vector space, so

𝑇_{ℂ}

has an eigenvalue

𝜆

by Theorem 7.3.27. If

𝜆 \in ℝ

, it is an eigenvalue of

𝑇

by Proposition 7.3.34(a), and any eigenvector spans a

𝑇

-invariant line (Proposition 7.2.7). If

𝜆 \notin ℝ

, an eigenvector

𝐮 + 𝑖 𝐯

𝑇_{ℂ}

gives the two-dimensional

𝑇

-invariant subspace

span (𝐮, 𝐯)

of Proposition 7.3.34(c). □

The Krylov proof stays inside $𝑉$ and uses the real factorization of polynomials. The complexification proof uses only the complex theorem, but has to leave $𝑉$ and come back, and it is the version that generalizes, to the block triangular form of real operators (Section 7.5) and to real normal operators in Chapter 8.

Example 7.3.36 (Decomplexification). The opposite construction forgets structure. A complex vector space is also a real vector space, by restricting scalars to $ℝ$ , and $ℂ^{𝑛}$ becomes $ℝ^{2 𝑛}$ with real basis $𝐞_{1},$ $\dots,$ $𝐞_{𝑛},$ $𝑖 𝐞_{1},$ $\dots,$ $𝑖 𝐞_{𝑛}$ . A complex matrix $𝐴 = 𝑃 + 𝑖 𝑄$ , with $𝑃, 𝑄 \in ℝ^{𝑛 \times 𝑛}$ , acts by

(𝑃 + 𝑖 𝑄) (𝐱 + 𝑖 𝐲) = (𝑃 𝐱 - 𝑄 𝐲) + 𝑖 (𝑄 𝐱 + 𝑃 𝐲) (𝐱, 𝐲 \in ℝ^{𝑛}),

so as a real linear map of $ℝ^{2 𝑛}$ its matrix is $(\begin{matrix} 𝑃 & - 𝑄 \\ 𝑄 & 𝑃 \end{matrix})$ . For $𝑛 = 1$ , multiplication by $𝑎 + 𝑏 𝑖$ on $ℂ = ℝ^{2}$ becomes $(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})$ , as in Proposition B.1.18. Conversely, decomplexifying $𝑉_{ℂ}$ gives $𝑉 \times 𝑉$ , on which $𝑇_{ℂ}$ acts as $(\begin{matrix} 𝑇 & 0 \\ 0 & 𝑇 \end{matrix})$ .

Exercises

Exercise 7.3.37.routine For each matrix, find $𝑝_{𝐴}$ , the eigenvalues, and a basis of each eigenspace.

(a) $𝐴 =$ $(\begin{matrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 2 & 2 & 1 \end{matrix}) \in$ $ℝ^{3 \times 3}$ .
(b) $𝐴 =$ $(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & - 5 & 4 \end{matrix}) \in$ $ℝ^{3 \times 3}$ .
(c) $𝐴 = (\begin{matrix} 1 & - 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 2 \end{matrix})$ , over $ℝ$ and over $ℂ$ .

Solution.

Uses. Algorithm 7.3.7 (Eigenvalues by the characteristic polynomial), Proposition 7.3.2 (Determinants over a commutative ring), Proposition 7.3.15 (Block-triangular matrices), Exercise 7.3.17, Theorem 7.3.24 (Every monic polynomial is a characteristic polynomial)

Hint 1. In (a), add the second and third rows of

𝑥 𝐼_{3} - 𝐴

to the first; a common factor appears. In (b),

𝐴

is the transpose of a companion matrix. In (c),

𝐴

is block diagonal.

Hint 2. The answers are

(𝑥 - 5) {(𝑥 + 1)}^{2}

{(𝑥 - 1)}^{2} (𝑥 - 2)

, and

(𝑥 - 2) (𝑥^{2} - 2 𝑥 + 2)

. Now row reduce

𝐴 - 𝜆 𝐼_{3}

for each root.

Sketch. (a)

𝑝_{𝐴} =

(𝑥 - 5) {(𝑥 + 1)}^{2}

𝐸_{5} = span ((1, 1, 1))

𝐸_{- 1} =

span ((1, - 1, 0), (1, 0, - 1))

. (b)

𝑝_{𝐴} =

𝑥^{3} -

4 𝑥^{2} +

5 𝑥 -

2 =

{(𝑥 - 1)}^{2} (𝑥 - 2)

𝐸_{1} = span ((1, 1, 1))

𝐸_{2} = span ((1, 2, 4))

. (c)

𝑝_{𝐴} =

(𝑥 - 2) (𝑥^{2} - 2 𝑥 + 2)

; over

ℝ

only

𝐸_{2} = span (𝐞_{3})

; over

ℂ

also

𝐸_{1 + 𝑖} =

span ((𝑖, 1, 0))

and

𝐸_{1 - 𝑖} =

span ((- 𝑖, 1, 0))

(a) In $𝑥 𝐼_{3} - 𝐴$ , add rows $2$ and $3$ to row $1$ ; this does not change the determinant (Proposition 7.3.2(b), (d)). Row $1$ becomes $(𝑥 - 5, 𝑥 - 5, 𝑥 - 5)$ , and pulling out the factor $𝑥 - 5$ and then adding $2$ times row $1$ to rows $2$ and $3$ ,

𝑝_{𝐴} = (𝑥 - 5) det (\begin{matrix} 1 & 1 & 1 \\ - 2 & 𝑥 - 1 & - 2 \\ - 2 & - 2 & 𝑥 - 1 \end{matrix}) = (𝑥 - 5) det (\begin{matrix} 1 & 1 & 1 \\ 0 & 𝑥 + 1 & 0 \\ 0 & 0 & 𝑥 + 1 \end{matrix}) = (𝑥 - 5) {(𝑥 + 1)}^{2} .

Next, $𝐴 -$ $5 𝐼_{3} =$ $(\begin{matrix} - 4 & 2 & 2 \\ 2 & - 4 & 2 \\ 2 & 2 & - 4 \end{matrix})$ has rank $2$ and kills $(1, 1, 1)$ , so $𝐸_{5} = span ((1, 1, 1))$ . Every row of $𝐴 + 𝐼_{3}$ is $(2, 2, 2)$ , so $𝐸_{- 1} =$ ${(𝑥, 𝑦, 𝑧) | 𝑥 + 𝑦 + 𝑧 = 0} =$ $span ((1, - 1, 0), (1, 0, - 1))$ . As a check, $𝐴 = 2 𝐽 - 𝐼_{3}$ with $𝐽$ the all-ones matrix, and $𝐽$ acts as $3$ on $(1, 1, 1)$ and as $0$ on the plane $𝑥 + 𝑦 + 𝑧 = 0$ .

(b) $𝐴^{𝖳} = (\begin{matrix} 0 & 0 & 2 \\ 1 & 0 & - 5 \\ 0 & 1 & 4 \end{matrix})$ is the companion matrix of $𝑝 = 𝑥^{3} - 4 𝑥^{2} + 5 𝑥 - 2$ , so $𝑝_{𝐴} = 𝑝_{𝐴^{𝖳}} = 𝑝$ by Exercise 7.3.17 and Theorem 7.3.24. (Expanding $det (𝑥 𝐼_{3} - 𝐴)$ along the first row gives the same.) Since $𝑝 (1) = 0$ , dividing gives $𝑝 =$ $(𝑥 - 1) (𝑥^{2} - 3 𝑥 + 2) =$ ${(𝑥 - 1)}^{2} (𝑥 - 2)$ . Then

𝐴 - 𝐼_{3} = (\begin{matrix} - 1 & 1 & 0 \\ 0 & - 1 & 1 \\ 2 & - 5 & 3 \end{matrix}), 𝐴 - 2 𝐼_{3} = (\begin{matrix} - 2 & 1 & 0 \\ 0 & - 2 & 1 \\ 2 & - 5 & 2 \end{matrix}) .

The first two rows of each are independent, so both have rank $2$ . The first two rows of $𝐴 - 𝐼_{3}$ force $𝑦 = 𝑥$ and $𝑧 = 𝑦$ , and $(1, 1, 1)$ satisfies the third row; so $𝐸_{1} = span ((1, 1, 1))$ . Likewise $𝐸_{2} = span ((1, 2, 4))$ . Although $1$ is a double root of $𝑝_{𝐴}$ , its eigenspace is only a line.

(c) $𝐴$ is block diagonal with blocks $(\begin{matrix} 1 & - 1 \\ 1 & 1 \end{matrix})$ and $(2)$ , so by Proposition 7.3.15 and Example 7.3.5(a), $𝑝_{𝐴} =$ $(𝑥^{2} - 2 𝑥 + 2) (𝑥 - 2)$ . Over $ℝ$ , $𝑥^{2} -$ $2 𝑥 +$ $2 =$ ${(𝑥 - 1)}^{2} +$ $1$ has no root, so the only eigenvalue is $2$ , and $𝐴 -$ $2 𝐼_{3} =$ $(\begin{matrix} - 1 & - 1 & 0 \\ 1 & - 1 & 0 \\ 0 & 0 & 0 \end{matrix})$ gives $𝐸_{2} = span (𝐞_{3})$ . Over $ℂ$ , the quadratic has roots $1 \pm 𝑖$ . For $𝜆 = 1 + 𝑖$ , the first row of $𝐴 - 𝜆 𝐼_{3}$ is $(- 𝑖, - 1, 0)$ , so $(𝑖, 1, 0)$ spans $𝐸_{1 + 𝑖}$ ; indeed $𝐴 (𝑖, 1, 0) =$ $(𝑖 - 1, 𝑖 + 1, 0) =$ $(1 + 𝑖) (𝑖, 1, 0)$ . Since $𝐴$ is real, conjugating $𝐴 𝐯 = 𝜆 𝐯$ entrywise gives $𝐴 𝐯 = 𝜆 𝐯$ , so $𝐸_{1 - 𝑖} =$ $span ((- 𝑖, 1, 0))$ , and $𝐸_{2} = span (𝐞_{3})$ as before.

Exercise 7.3.38.standard Let $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ . Prove or disprove:

(a)If $𝑝_{𝐴} = 𝑝_{𝐵}$ , then $𝐴$ and $𝐵$ are similar.
(b)If $𝑝_{𝐴} = 𝑝_{𝐵}$ , then $rank 𝐴 = rank 𝐵$ .
(c)For every $𝑐 \in 𝐹$ , $𝑝_{𝐴 + 𝑐 𝐼_{𝑛}}$ is obtained from $𝑝_{𝐴}$ by substituting $𝑥 - 𝑐$ for $𝑥$ , that is, $𝑝_{𝐴 + 𝑐 𝐼_{𝑛}} =$ $𝑝_{𝐴} (𝑥 - 𝑐)$ .
(d)If $𝑝_{𝐴} = 𝑝_{𝐵}$ and $𝑝_{𝐴}$ has $𝑛$ distinct roots in $𝐹$ , then $𝐴$ and $𝐵$ are similar.

Solution.

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Proposition 7.1.10 (Evaluation respects sums and products), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Theorem 7.2.21 (Eigenvectors for distinct eigenvalues are independent), Corollary 3.5.25 (The invertible matrix theorem), Proposition 4.5.24 (Similarity is an equivalence relation)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18), Rule out similarity with an invariant (Technique 4.5.29)

Hint 1. For (a) and (b), look at

2 \times 2

matrices with a repeated eigenvalue.

Hint 2. For (c),

𝑥 𝐼_{𝑛} -

(𝐴 + 𝑐 𝐼_{𝑛}) =

(𝑥 - 𝑐) 𝐼_{𝑛} -

𝐴

. Which map

𝐹 [𝑥] \to 𝐹 [𝑥]

turns

𝑥 𝐼_{𝑛} - 𝐴

into this matrix?

Hint 3. For (d), pick an eigenvector of

𝐴

for each root. They form a basis, in which

𝐴

becomes

diag (𝜆_{1}, \dots, 𝜆_{𝑛})

. Do the same for

𝐵

separately, in its own basis of eigenvectors.

Sketch. (a) False:

𝐼_{2}

and

(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})

. (b) False:

0

and

(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})

. (c) True: substitute

𝑥 - 𝑐

for

𝑥

entrywise and use Proposition 7.3.2(g). (d) True:

𝑛

distinct eigenvalues give a basis of eigenvectors, so

𝐴

and

𝐵

are both similar to

diag (𝜆_{1}, \dots, 𝜆_{𝑛})

(a) False. $𝐼_{2}$ and $𝑁 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ both have characteristic polynomial ${(𝑥 - 1)}^{2}$ (Example 7.3.5(d)). But $𝑆^{- 1} 𝐼_{2} 𝑆 = 𝐼_{2} \neq 𝑁$ for every invertible $𝑆$ , so they are not similar.

(b) False. $0_{2 \times 2}$ and $(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ both have characteristic polynomial $𝑥^{2}$ , but their ranks are $0$ and $1$ .

(c) True. Substituting $𝑥 - 𝑐$ for $𝑥$ respects sums, products, and $1$ (Proposition 7.1.10), and applied to every entry of $𝑥 𝐼_{𝑛} - 𝐴$ it gives $(𝑥 - 𝑐) 𝐼_{𝑛} -$ $𝐴 =$ $𝑥 𝐼_{𝑛} -$ $(𝐴 + 𝑐 𝐼_{𝑛})$ , since the constant entries are unchanged. By Proposition 7.3.2(g), $𝑝_{𝐴 + 𝑐 𝐼_{𝑛}} =$ $𝑝_{𝐴} (𝑥 - 𝑐)$ . In particular the eigenvalues of $𝐴 + 𝑐 𝐼_{𝑛}$ are the $𝜆 + 𝑐$ for the eigenvalues $𝜆$ of $𝐴$ .

(d) True. Let $𝜆_{1}, \dots, 𝜆_{𝑛}$ be the distinct roots. By Theorem 7.3.6 each $𝜆_{𝑖}$ is an eigenvalue of $𝐴$ ; choose eigenvectors $𝐯_{𝑖}$ . By Theorem 7.2.21 they are independent, so they form a basis of $𝐹^{𝑛}$ , and the matrix $𝑆$ with columns $𝐯_{𝑖}$ is invertible (Corollary 3.5.25). Column $𝑖$ of $𝐴 𝑆$ is $𝐴 𝐯_{𝑖} = 𝜆_{𝑖} 𝐯_{𝑖}$ , which is column $𝑖$ of $𝑆 𝐷$ for $𝐷 =$ $diag (𝜆_{1}, \dots, 𝜆_{𝑛})$ . So $𝑆^{- 1} 𝐴 𝑆 = 𝐷$ . The same argument for $𝐵$ gives $𝑅^{- 1} 𝐵 𝑅 = 𝐷$ . Hence $𝐴 \sim 𝐷 \sim 𝐵$ , and $𝐴 \sim 𝐵$ by Proposition 4.5.24.

Exercise 7.3.39.standard

(a)Let $𝜏 : 𝐹^{𝑛 \times 𝑛} \to$ $𝐹^{𝑛 \times 𝑛}$ be transposition, $𝜏 (𝑋) = 𝑋^{𝖳}$ . Show that
$𝑝_{𝜏} = {(𝑥 - 1)}^{𝑛 (𝑛 + 1) / 2} {(𝑥 + 1)}^{𝑛 (𝑛 - 1) / 2} .$
(b)Let $𝑊$ be the real vector space of functions $ℝ \to ℝ$ with basis $sin 𝑡,$ $cos 𝑡,$ $𝑡 sin 𝑡,$ $𝑡 cos 𝑡$ . Find the characteristic polynomial of differentiation $𝐷 : 𝑊 \to 𝑊$ , and conclude that no nonzero function in $𝑊$ satisfies $𝑓^{'} = 𝜆 𝑓$ with $𝜆 \in ℝ$ .

Solution.

Uses. Lemma 2.4.24 (Matrix units), Definition 2.3.1 (Matrix of a linear map), Proposition 7.3.15 (Block-triangular matrices), Corollary 7.3.13 (Eigenvalues of an operator)

Hint 1. For (a), order the matrix units so that

𝑈_{𝑖 𝑗}

and

𝑈_{𝑗 𝑖}

are adjacent. What does the matrix of

𝜏

look like?

Hint 2. It is block diagonal, with

𝑛

blocks

(1)

and

𝑛 (𝑛 - 1) / 2

blocks

(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})

. For (b), compute

𝐷

on each basis function; the matrix is block upper triangular.

Sketch. (a)

𝜏 (𝑈_{𝑖 𝑖}) = 𝑈_{𝑖 𝑖}

and

𝜏

swaps

𝑈_{𝑖 𝑗}

and

𝑈_{𝑗 𝑖}

; so

𝑝_{𝜏} =

{(𝑥 - 1)}^{𝑛} {(𝑥^{2} - 1)}^{𝑛 (𝑛 - 1) / 2}

. (b) The matrix is

(\begin{matrix} 𝑅 & 𝐼_{2} \\ 0 & 𝑅 \end{matrix})

with

𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})

, so

𝑝_{𝐷} = {(𝑥^{2} + 1)}^{2}

, which has no real root.

(a) By Lemma 2.4.24, the matrix units $𝑈_{𝑖 𝑗}$ form a basis of $𝐹^{𝑛 \times 𝑛}$ . Order it as $𝑈_{11}, \dots, 𝑈_{𝑛 𝑛}$ , followed by the pairs $𝑈_{𝑖 𝑗}, 𝑈_{𝑗 𝑖}$ for $𝑖 < 𝑗$ . Since $𝜏 (𝑈_{𝑖 𝑖}) = 𝑈_{𝑖 𝑖}$ , $𝜏 (𝑈_{𝑖 𝑗}) = 𝑈_{𝑗 𝑖}$ , and $𝜏 (𝑈_{𝑗 𝑖}) = 𝑈_{𝑖 𝑗}$ , the matrix of $𝜏$ is block diagonal with $𝑛$ blocks $(1)$ and $𝑛 (𝑛 - 1) / 2$ blocks $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ , whose characteristic polynomial is $𝑥^{2} -$ $1 =$ $(𝑥 - 1) (𝑥 + 1)$ . Applying Proposition 7.3.15 once for each block,

𝑝_{𝜏} = {(𝑥 - 1)}^{𝑛} {(𝑥^{2} - 1)}^{𝑛 (𝑛 - 1) / 2} = {(𝑥 - 1)}^{𝑛 + 𝑛 (𝑛 - 1) / 2} {(𝑥 + 1)}^{𝑛 (𝑛 - 1) / 2},

and $𝑛 +$ $𝑛 (𝑛 - 1) / 2 =$ $𝑛 (𝑛 + 1) / 2$ . This fits Example 7.2.17: $𝜏^{2} = id$ , the symmetric matrices form $𝐸_{1}$ , of dimension $𝑛 (𝑛 + 1) / 2$ , and the antisymmetric ones form $𝐸_{- 1}$ . When $1 + 1 = 0$ in $𝐹$ , the formula reads $𝑝_{𝜏} = {(𝑥 - 1)}^{𝑛^{2}}$ .

(b) Let $𝐛_{1} = sin 𝑡$ , $𝐛_{2} = cos 𝑡$ , $𝐛_{3} = 𝑡 sin 𝑡$ , $𝐛_{4} = 𝑡 cos 𝑡$ . Then

𝐷 𝐛_{1} = 𝐛_{2}, 𝐷 𝐛_{2} = - 𝐛_{1}, 𝐷 𝐛_{3} = 𝐛_{1} + 𝐛_{4}, 𝐷 𝐛_{4} = 𝐛_{2} - 𝐛_{3},

so $𝐷$ maps $𝑊$ to $𝑊$ , and its matrix (Definition 2.3.1) is

[𝐷] = (\begin{matrix} 0 & - 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & - 1 \\ 0 & 0 & 1 & 0 \end{matrix}) .

This is block upper triangular with both diagonal blocks equal to $(\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ , so $𝑝_{𝐷} = {(𝑥^{2} + 1)}^{2}$ by Proposition 7.3.15. It has no real root, so $𝐷$ has no real eigenvalue (Corollary 7.3.13): no nonzero $𝑓 \in 𝑊$ satisfies $𝑓^{'} = 𝜆 𝑓$ with $𝜆 \in ℝ$ . The upper left block reflects the invariant plane $span (sin 𝑡, cos 𝑡)$ .

Exercise 7.3.40.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ , where $𝑚, 𝑛 \geq 1$ .

(a)Show that $𝑥^{𝑛} 𝑝_{𝐴 𝐵} =$ $𝑥^{𝑚} 𝑝_{𝐵 𝐴}$ .
(b)Deduce that $𝐴 𝐵$ and $𝐵 𝐴$ have the same nonzero eigenvalues.
(c)Prove (b) again without characteristic polynomials: if $𝐴 𝐵 𝐯 = 𝜆 𝐯$ with $𝐯 \neq 𝟎$ and $𝜆 \neq 0$ , show that $𝐵 𝐯$ is an eigenvector of $𝐵 𝐴$ .
(d)Give an example in which $0$ is an eigenvalue of $𝐵 𝐴$ but not of $𝐴 𝐵$ .

Solution.

Uses. Proposition 7.3.22 ( $𝐴 𝐵$ and $𝐵 𝐴$ ), Proposition 7.3.11 (Similar matrices have the same characteristic polynomial), Proposition 7.3.15 (Block-triangular matrices), Theorem 2.4.34 (Block multiplication), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial)

Techniques. Compare $𝐴 𝐵$ and $𝐵 𝐴$ (Technique 7.3.21)

Hint 1. Imitate the first proof of Proposition 7.3.22 with

𝑆 = (\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})

. The zero blocks now have different sizes.

Hint 2. For (b), evaluate the identity of (a) at

𝜆 \neq 0

Hint 3. For (c), why is

𝐵 𝐯 \neq 𝟎

? Apply

𝐴

to it.

Sketch. (a)

𝑋 =

(\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 0_{𝑛 \times 𝑛} \end{matrix})

and

𝑌 =

(\begin{matrix} 0_{𝑚 \times 𝑚} & 0 \\ 𝐵 & 𝐵 𝐴 \end{matrix})

satisfy

𝑋 𝑆 = 𝑆 𝑌

with

𝑆 = (\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})

, and

𝑝_{𝑋} = 𝑝_{𝐴 𝐵} 𝑥^{𝑛}

𝑝_{𝑌} = 𝑥^{𝑚} 𝑝_{𝐵 𝐴}

. (b) For

𝜆 \neq 0

𝜆^{𝑛} 𝑝_{𝐴 𝐵} (𝜆) =

𝜆^{𝑚} 𝑝_{𝐵 𝐴} (𝜆)

. (c)

𝐴 (𝐵 𝐯) = 𝜆 𝐯 \neq 𝟎

, and

𝐵 𝐴 (𝐵 𝐯) =

𝐵 (𝜆 𝐯)

. (d)

𝐴 = (1, 0)

𝐵 = {(1, 0)}^{𝖳}

(a) Let $𝑆 = (\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})$ , which is invertible with inverse $(\begin{matrix} 𝐼_{𝑚} & - 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})$ , and let

𝑋 = (\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 0_{𝑛 \times 𝑛} \end{matrix}), 𝑌 = (\begin{matrix} 0_{𝑚 \times 𝑚} & 0 \\ 𝐵 & 𝐵 𝐴 \end{matrix}) .

By block multiplication (Theorem 2.4.34), $𝑋 𝑆 =$ $(\begin{matrix} 𝐴 𝐵 & 𝐴 𝐵 𝐴 \\ 𝐵 & 𝐵 𝐴 \end{matrix}) =$ $𝑆 𝑌$ . So $𝑋$ and $𝑌$ are similar and $𝑝_{𝑋} = 𝑝_{𝑌}$ (Proposition 7.3.11). Both are block lower triangular, so by Proposition 7.3.15, $𝑝_{𝑋} =$ $𝑝_{𝐴 𝐵} 𝑝_{0_{𝑛 \times 𝑛}} =$ $𝑝_{𝐴 𝐵} 𝑥^{𝑛}$ and $𝑝_{𝑌} = 𝑥^{𝑚} 𝑝_{𝐵 𝐴}$ .

(b) Let $𝜆 \neq 0$ . Evaluating (a) at $𝜆$ gives $𝜆^{𝑛} 𝑝_{𝐴 𝐵} (𝜆) =$ $𝜆^{𝑚} 𝑝_{𝐵 𝐴} (𝜆)$ , and $𝜆^{𝑛}, 𝜆^{𝑚} \neq 0$ . So $𝑝_{𝐴 𝐵} (𝜆) = 0$ if and only if $𝑝_{𝐵 𝐴} (𝜆) = 0$ , and Theorem 7.3.6 finishes.

(c) Suppose $𝐴 𝐵 𝐯 = 𝜆 𝐯$ with $𝐯 \neq 𝟎$ and $𝜆 \neq 0$ . Then $𝐴 (𝐵 𝐯) = 𝜆 𝐯 \neq 𝟎$ , so $𝐵 𝐯 \neq 𝟎$ , and $(𝐵 𝐴) (𝐵 𝐯) =$ $𝐵 (𝐴 𝐵 𝐯) =$ $𝜆 𝐵 𝐯$ . So every nonzero eigenvalue of $𝐴 𝐵$ is one of $𝐵 𝐴$ , and exchanging the roles of $𝐴$ and $𝐵$ gives the converse.

(d) Let $𝐴 = (\begin{matrix} 1 & 0 \end{matrix}) \in 𝐹^{1 \times 2}$ and $𝐵 = (\begin{matrix} 1 \\ 0 \end{matrix}) \in 𝐹^{2 \times 1}$ . Then $𝐴 𝐵 = (1)$ has the single eigenvalue $1$ , while $𝐵 𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ also has the eigenvalue $0$ . Consistently with (a), $𝑥^{2} (𝑥 - 1) =$ $𝑥 \cdot$ $𝑥 (𝑥 - 1)$ .

Exercise 7.3.41.standard Let $𝑛 \geq 2$ and $𝐮, 𝐯 \in 𝐹^{𝑛}$ .

(a)Show that $𝑝_{𝐮 𝐯^{𝖳}} =$ $𝑥^{𝑛 - 1} (𝑥 - 𝐯^{𝖳} 𝐮)$ .
(b)Let $𝐽 \in 𝐹^{𝑛 \times 𝑛}$ be the matrix whose entries are all $1$ . Find $𝑝_{𝐽}$ and the eigenvalues of $𝐽$ over $ℚ$ , and over $𝔽_{𝑝}$ for a prime $𝑝$ dividing $𝑛$ .

Solution.

Uses. Exercise 7.3.40, Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 4.5.35 (Preserved subspaces give block triangular matrices), Proposition 4.5.27 (Similarity invariants), Theorem 4.2.11 (Rank–nullity), Example 7.3.5 (Small cases)

Techniques. Compare $𝐴 𝐵$ and $𝐵 𝐴$ (Technique 7.3.21), Choose a basis adapted to a preserved subspace (Technique 4.5.36)

Hint 1. Write

𝐮 𝐯^{𝖳}

as a product of an

𝑛 \times 1

and a

1 \times 𝑛

matrix, and use Exercise 7.3.40.

Hint 2. Alternatively, if

𝐯 \neq 𝟎

, the hyperplane

{𝐰 | 𝐯^{𝖳} 𝐰 = 0}

lies in the kernel. Choose a basis starting with a basis of it; the matrix becomes triangular. Its last diagonal entry is the trace.

Sketch. (a) With

𝐴 = 𝐮 \in 𝐹^{𝑛 \times 1}

and

𝐵 = 𝐯^{𝖳} \in 𝐹^{1 \times 𝑛}

, Exercise 7.3.40 gives

𝑥 𝑝_{𝐮 𝐯^{𝖳}} =

𝑥^{𝑛} 𝑝_{𝐯^{𝖳} 𝐮} =

𝑥^{𝑛} (𝑥 - 𝐯^{𝖳} 𝐮)

; cancel

𝑥

. (b)

𝐽 = 𝟏 𝟏^{𝖳}

and

𝟏^{𝖳} 𝟏 = 𝑛

, so

𝑝_{𝐽} =

𝑥^{𝑛 - 1} (𝑥 - 𝑛)

: eigenvalues

0, 𝑛

over

ℚ

, and only

0

over

𝔽_{𝑝}

when

𝑝 ∣ 𝑛

(a) First proof. Let $𝐴 = 𝐮 \in 𝐹^{𝑛 \times 1}$ and $𝐵 = 𝐯^{𝖳} \in 𝐹^{1 \times 𝑛}$ , so $𝐴 𝐵 = 𝐮 𝐯^{𝖳}$ and $𝐵 𝐴 = (𝐯^{𝖳} 𝐮)$ is $1 \times 1$ , with $𝑝_{𝐵 𝐴} = 𝑥 - 𝐯^{𝖳} 𝐮$ . By Exercise 7.3.40, $𝑥 𝑝_{𝐮 𝐯^{𝖳}} =$ $𝑥^{𝑛} (𝑥 - 𝐯^{𝖳} 𝐮)$ . Cancelling $𝑥$ in $𝐹 [𝑥]$ (Corollary 7.1.7) gives the claim.

Second proof. Let $𝑀 = 𝐮 𝐯^{𝖳}$ . If $𝐯 = 𝟎$ , then $𝑀 = 0$ and $𝑝_{𝑀} = 𝑥^{𝑛}$ , as claimed. Otherwise $𝐻 =$ ${𝐰 \in 𝐹^{𝑛} | 𝐯^{𝖳} 𝐰 = 0}$ is the kernel of a nonzero linear map $𝐹^{𝑛} \to 𝐹$ , so $dim 𝐻 = 𝑛 - 1$ (Theorem 4.2.11), and $𝑀 𝐰 =$ $𝐮 (𝐯^{𝖳} 𝐰) =$ $𝟎$ for $𝐰 \in 𝐻$ . Extend a basis $𝐰_{1}, \dots, 𝐰_{𝑛 - 1}$ of $𝐻$ to a basis $ℬ︀$ of $𝐹^{𝑛}$ . The first $𝑛 - 1$ columns of ${[𝑇_{𝑀}]}_{ℬ︀ ℬ︀}$ are $𝟎$ , so this matrix is upper triangular with diagonal entries $0, \dots, 0, 𝑐$ , and $𝑝_{𝑀} =$ $𝑥^{𝑛 - 1} (𝑥 - 𝑐)$ by Example 7.3.5(d). Since the trace is a similarity invariant (Proposition 4.5.27), $𝑐 =$ $tr 𝑀 =$ $\sum_{𝑖} 𝑢_{𝑖} 𝑣_{𝑖} =$ $𝐯^{𝖳} 𝐮$ .

(b) $𝐽 = 𝟏 𝟏^{𝖳}$ with $𝟏 = (1, \dots, 1)$ , and $𝟏^{𝖳} 𝟏 = 𝑛$ . By (a), $𝑝_{𝐽} =$ $𝑥^{𝑛 - 1} (𝑥 - 𝑛)$ . Over $ℚ$ the eigenvalues are $0$ and $𝑛$ . Over $𝔽_{𝑝}$ with $𝑝 ∣ 𝑛$ , we have $𝑛 = 0$ , so $𝑝_{𝐽} = 𝑥^{𝑛}$ and $0$ is the only eigenvalue; indeed $𝐽 𝟏 = 𝑛 𝟏 = 𝟎$ there.

Exercise 7.3.42.standard Let $𝐴 \in ℚ^{𝑛 \times 𝑛}$ have integer entries.

(a)Show that all coefficients of $𝑝_{𝐴}$ are integers.
(b)Show that every rational eigenvalue of $𝐴$ is an integer that divides $det 𝐴$ .
(c)Show that $(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$ has no rational eigenvalue.

Solution.

Uses. Definition 7.3.1 (Determinant over a commutative ring), Definition 7.1.1 (Product of polynomials), Proposition 7.3.18 (The first and last coefficients), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial)

Hint 1. For (a), every entry of

𝑥 𝐼_{𝑛} - 𝐴

is a polynomial with integer coefficients. What happens to such polynomials under sums and products?

Hint 2. For (b), write the eigenvalue as

𝑎 / 𝑏

in lowest terms with

𝑏 \geq 1

, substitute into

𝑝_{𝐴}

, and multiply by

𝑏^{𝑛}

. Which terms are divisible by

𝑏

Sketch. (a) The Leibniz formula is a signed sum of products of polynomials with integer coefficients. (b) If

𝑝_{𝐴} (𝑎 / 𝑏) = 0

with

gcd (𝑎, 𝑏) = 1

, then

𝑎^{𝑛} =

- 𝑏 (𝑐_{𝑛 - 1} 𝑎^{𝑛 - 1} + \dots + 𝑐_{0} 𝑏^{𝑛 - 1})

, so every prime factor of

𝑏

divides

𝑎

; hence

𝑏 = 1

. Then

𝑎

divides the constant term

{(- 1)}^{𝑛} det 𝐴

. (c)

𝑝_{𝐴} = 𝑥^{2} - 5 𝑥 - 2

has no root among

\pm 1, \pm 2

(a) Every entry of $𝑥 𝐼_{𝑛} - 𝐴$ is $𝑥 - 𝑎_{𝑖 𝑖}$ or $- 𝑎_{𝑖 𝑗}$ , a polynomial with integer coefficients. By the formula for the product (Definition 7.1.1), sums and products of polynomials with integer coefficients have integer coefficients. So every Leibniz term, and hence $𝑝_{𝐴}$ , has integer coefficients.

(b) Write $𝑝_{𝐴} =$ $𝑥^{𝑛} +$ $𝑐_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $\dots +$ $𝑐_{0}$ with $𝑐_{𝑖} \in ℤ$ , and suppose $𝑝_{𝐴} (𝑎 / 𝑏) = 0$ with $𝑎, 𝑏 \in ℤ$ , $𝑏 \geq 1$ , and $gcd (𝑎, 𝑏) = 1$ . Multiplying by $𝑏^{𝑛}$ ,

𝑎^{𝑛} = - 𝑏 (𝑐_{𝑛 - 1} 𝑎^{𝑛 - 1} + 𝑐_{𝑛 - 2} 𝑎^{𝑛 - 2} 𝑏 + \dots + 𝑐_{0} 𝑏^{𝑛 - 1}) .

If $𝑏 > 1$ , a prime $𝑞$ dividing $𝑏$ divides $𝑎^{𝑛}$ , hence divides $𝑎$ , contradicting $gcd (𝑎, 𝑏) = 1$ . So $𝑏 = 1$ and the eigenvalue $𝑎$ is an integer. Then $0 =$ $𝑎^{𝑛} +$ $𝑐_{𝑛 - 1} 𝑎^{𝑛 - 1} +$ $\dots +$ $𝑐_{1} 𝑎 +$ $𝑐_{0}$ gives $𝑐_{0} =$ $- 𝑎 (𝑎^{𝑛 - 1} + 𝑐_{𝑛 - 1} 𝑎^{𝑛 - 2} + \dots + 𝑐_{1})$ , so $𝑎$ divides $𝑐_{0} = {(- 1)}^{𝑛} det 𝐴$ (Proposition 7.3.18), and therefore divides $det 𝐴$ .

(c) Here $𝑝_{𝐴} = 𝑥^{2} - 5 𝑥 - 2$ and $det 𝐴 = - 2$ . By (b), a rational eigenvalue would be one of $\pm 1, \pm 2$ , but $𝑝_{𝐴} (1) = - 6$ , $𝑝_{𝐴} (- 1) = 4$ , $𝑝_{𝐴} (2) = - 8$ , and $𝑝_{𝐴} (- 2) = 12$ . So there is none, and the eigenvalues $(5 \pm \sqrt{33}) / 2$ are irrational.

Exercise 7.3.43.standard Let $𝐴 \in ℝ^{𝑛 \times 𝑛}$ satisfy $𝐴^{2} = - 𝐼_{𝑛}$ .

(a)Show that $𝑛$ is even, using determinants.
(b)Give a second proof using $𝑝_{𝐴}$ and the eigenvalues of $𝐴$ regarded as a complex matrix.
(c)Show that, conversely, $𝐴^{2} = - 𝐼_{𝑛}$ has a solution in $ℝ^{𝑛 \times 𝑛}$ for every even $𝑛$ , and in $ℂ^{𝑛 \times 𝑛}$ for every $𝑛$ .

Solution.

Uses. Theorem 5.4.10 (Multiplicativity), Proposition 7.2.28 (Polynomials act on eigenvectors by their values), Corollary 7.1.35 (Factorization over $ℂ$ ), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Proposition 7.1.38 (Conjugate roots)

Hint 1. For (a), take determinants of both sides. What sign does a real square have?

Hint 2. For (b), an eigenvalue

𝜆

𝐴

over

ℂ

satisfies

𝜆^{2} = - 1

. Then

𝑝_{𝐴} =

{(𝑥 - 𝑖)}^{𝑎} {(𝑥 + 𝑖)}^{𝑏}

. Use that

𝑝_{𝐴}

has real coefficients.

Sketch. (a)

{(det 𝐴)}^{2} =

det (- 𝐼_{𝑛}) =

{(- 1)}^{𝑛}

, and a nonzero real square is positive, so

{(- 1)}^{𝑛} = 1

. (b) All complex eigenvalues are

\pm 𝑖

, so

𝑝_{𝐴} =

{(𝑥 - 𝑖)}^{𝑎} {(𝑥 + 𝑖)}^{𝑏}

with

𝑎 + 𝑏 = 𝑛

; real coefficients force

𝑎 = 𝑏

(Proposition 7.1.38). (c) Block-diagonal rotations by

𝜋 / 2

over

ℝ

;

𝑖 𝐼_{𝑛}

over

ℂ

(a) By Theorem 5.4.10, ${(det 𝐴)}^{2} =$ $det (𝐴^{2}) =$ $det (- 𝐼_{𝑛}) =$ ${(- 1)}^{𝑛}$ . Since $det 𝐴 \in ℝ$ and ${(det 𝐴)}^{2} = {(- 1)}^{𝑛} \neq 0$ , we get ${(- 1)}^{𝑛} = {(det 𝐴)}^{2} > 0$ , so $𝑛$ is even.

(b) Regard $𝐴$ as a complex matrix. If $𝐴 𝐯 = 𝜆 𝐯$ with $𝐯 \neq 𝟎$ , then $- 𝐯 = 𝐴^{2} 𝐯 = 𝜆^{2} 𝐯$ (Proposition 7.2.28), so $𝜆^{2} = - 1$ and $𝜆 = \pm 𝑖$ . By Corollary 7.1.35, $𝑝_{𝐴}$ is a product of $𝑛$ factors $𝑥 - 𝜆_{𝑘}$ , and each $𝜆_{𝑘}$ is a root, hence an eigenvalue (Theorem 7.3.6), hence $\pm 𝑖$ . So $𝑝_{𝐴} =$ ${(𝑥 - 𝑖)}^{𝑎} {(𝑥 + 𝑖)}^{𝑏}$ with $𝑎 + 𝑏 = 𝑛$ . The entries of $𝐴$ are real, so $𝑝_{𝐴} \in ℝ [𝑥]$ , and by Proposition 7.1.38 the roots $𝑖$ and $- 𝑖 = 𝑖$ have the same multiplicity: $𝑎 = 𝑏$ . Hence $𝑛 = 2 𝑎$ is even.

(c) Over $ℂ$ , ${(𝑖 𝐼_{𝑛})}^{2} = - 𝐼_{𝑛}$ . Over $ℝ$ with $𝑛 = 2 𝑚$ , the block-diagonal matrix with $𝑚$ blocks $𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ works, since $𝑅^{2} = - 𝐼_{2}$ .

Exercise 7.3.44.standard Let $𝐹$ be a finite field with elements $𝑐_{1}, \dots, 𝑐_{𝑞}$ .

(a)Show that $𝑝 =$ $(𝑥 - 𝑐_{1}) (𝑥 - 𝑐_{2}) \dots (𝑥 - 𝑐_{𝑞}) +$ $1$ has no root in $𝐹$ .
(b)Deduce that some operator on $𝐹^{𝑞}$ has no eigenvalue. So Theorem 7.3.27 fails over every finite field.
(c)Write down this operator for $𝐹 = 𝔽_{2}$ and check directly that it has no eigenvalue.

Solution.

Uses. Theorem 7.3.24 (Every monic polynomial is a characteristic polynomial), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Definition 7.3.23 (Companion matrix)

Hint 1. Evaluate

𝑝

at each

𝑐_{𝑗}

Hint 2. Every monic polynomial is a characteristic polynomial (Theorem 7.3.24).

Sketch. (a)

𝑝 (𝑐_{𝑗}) = 0 + 1 = 1

. (b)

𝐶_{𝑝} \in 𝐹^{𝑞 \times 𝑞}

has

𝑝_{𝐶_{𝑝}} = 𝑝

, which has no root. (c) Over

𝔽_{2}

𝑝 =

𝑥 (𝑥 - 1) +

1 =

𝑥^{2} +

𝑥 +

1

and

𝐶_{𝑝} = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})

; neither

𝐶_{𝑝}

nor

𝐶_{𝑝} - 𝐼_{2}

is singular.

(a) For each $𝑗$ , the product $(𝑐_{𝑗} - 𝑐_{1}) \dots (𝑐_{𝑗} - 𝑐_{𝑞})$ contains the factor $𝑐_{𝑗} - 𝑐_{𝑗} = 0$ , so $𝑝 (𝑐_{𝑗}) = 0 + 1 = 1 \neq 0$ .

(b) $𝑝$ is monic of degree $𝑞$ , so by Theorem 7.3.24 the companion matrix $𝐶_{𝑝} \in 𝐹^{𝑞 \times 𝑞}$ has $𝑝_{𝐶_{𝑝}} = 𝑝$ . By (a) and Theorem 7.3.6, $𝐶_{𝑝}$ has no eigenvalue in $𝐹$ .

(c) Over $𝔽_{2}$ , $𝑝 =$ $𝑥 (𝑥 - 1) +$ $1 =$ $𝑥^{2} -$ $𝑥 +$ $1 =$ $𝑥^{2} +$ $𝑥 +$ $1$ , and $𝐶_{𝑝} =$ $(\begin{matrix} 0 & - 1 \\ 1 & - 1 \end{matrix}) =$ $(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ . Its determinant is $- 1 = 1 \neq 0$ , so $0$ is not an eigenvalue, and $𝐶_{𝑝} - 𝐼_{2} = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ has determinant $- 1 = 1 \neq 0$ , so $1$ is not one either.

Exercise 7.3.45.standard Let $𝑝 =$ $𝑥^{𝑛} +$ $𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $\dots +$ $𝑎_{0} \in$ $𝐹 [𝑥]$ with $𝑛 \geq 2$ , and let $𝐶 = 𝐶_{𝑝}$ .

(a)Show that $rank (𝐶 - 𝜆 𝐼_{𝑛}) \geq$ $𝑛 -$ $1$ for every $𝜆 \in 𝐹$ . So every eigenspace of $𝐶$ is a line.
(b)Let $𝜆$ be a root of $𝑝$ and write $𝑝 = (𝑥 - 𝜆) 𝑞$ with $𝑞 =$ $𝑥^{𝑛 - 1} +$ $𝑏_{𝑛 - 2} 𝑥^{𝑛 - 2} +$ $\dots +$ $𝑏_{0}$ . Show that $(𝑏_{0}, 𝑏_{1}, \dots, 𝑏_{𝑛 - 2}, 1)$ is an eigenvector of $𝐶$ for $𝜆$ .
(c)Show that $𝐹^{𝑛}$ has a basis of eigenvectors of $𝐶$ if and only if $𝑝$ has $𝑛$ distinct roots in $𝐹$ .

Solution.

Uses. Definition 7.3.23 (Companion matrix), Theorem 4.2.11 (Rank–nullity), Remark 7.1.11 (Polynomials in a matrix), Theorem 7.3.24 (Every monic polynomial is a characteristic polynomial), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Theorem 7.2.21 (Eigenvectors for distinct eigenvalues are independent), Proposition 7.1.22 (Counting roots)

Techniques. Krylov sequences must become dependent (Technique 7.3.28)

Hint 1. For (a), look at the first

𝑛 - 1

columns of

𝐶 - 𝜆 𝐼_{𝑛}

Hint 2. For (b),

𝐶^{𝑗} 𝐞_{1} = 𝐞_{𝑗 + 1}

for

𝑗 \leq 𝑛 - 1

. Compute

𝑞 (𝐶) 𝐞_{1}

and

𝑝 (𝐶) 𝐞_{1}

Hint 3. For (c), a basis of eigenvectors has at most one vector in each eigenspace, by (a).

Sketch. (a) Columns

𝑘 < 𝑛

𝐶 - 𝜆 𝐼_{𝑛}

are

𝐞_{𝑘 + 1} - 𝜆 𝐞_{𝑘}

, which are independent (look at the last coordinate first). (b)

𝑞 (𝐶) 𝐞_{1}

is the given vector, and

(𝐶 - 𝜆 𝐼_{𝑛}) 𝑞 (𝐶) 𝐞_{1} =

𝑝 (𝐶) 𝐞_{1} =

𝐶 𝐞_{𝑛} +

\sum 𝑎_{𝑗} 𝐞_{𝑗 + 1} =

𝟎

. (c) Distinct roots give independent eigenvectors; conversely a basis of eigenvectors needs

𝑛

different eigenvalues, all roots of

𝑝

(a) For $𝑘 \leq 𝑛 - 1$ , column $𝑘$ of $𝐶 - 𝜆 𝐼_{𝑛}$ is $𝐞_{𝑘 + 1} - 𝜆 𝐞_{𝑘}$ . Suppose $\sum_{𝑘 = 1}^{𝑛 - 1} 𝑐_{𝑘} (𝐞_{𝑘 + 1} - 𝜆 𝐞_{𝑘}) =$ $𝟎$ . The coordinate at $𝐞_{𝑛}$ is $𝑐_{𝑛 - 1}$ , so $𝑐_{𝑛 - 1} = 0$ . If $𝑐_{𝑘 + 1} = \dots = 𝑐_{𝑛 - 1} = 0$ , the coordinate at $𝐞_{𝑘 + 1}$ is $𝑐_{𝑘} -$ $𝜆 𝑐_{𝑘 + 1} =$ $𝑐_{𝑘}$ , so $𝑐_{𝑘} = 0$ . Hence these $𝑛 - 1$ columns are independent, $rank (𝐶 - 𝜆 𝐼_{𝑛}) \geq$ $𝑛 -$ $1$ , and $dim 𝐸_{𝜆} =$ $𝑛 -$ $rank (𝐶 - 𝜆 𝐼_{𝑛}) \leq$ $1$ by Theorem 4.2.11.

(b) Since $𝐶 𝐞_{𝑘} = 𝐞_{𝑘 + 1}$ for $𝑘 < 𝑛$ , we have $𝐶^{𝑗} 𝐞_{1} = 𝐞_{𝑗 + 1}$ for $0 \leq 𝑗 \leq 𝑛 - 1$ . So

𝐰 = 𝑞 (𝐶) 𝐞_{1} = 𝑏_{0} 𝐞_{1} + 𝑏_{1} 𝐞_{2} + \dots + 𝑏_{𝑛 - 2} 𝐞_{𝑛 - 1} + 𝐞_{𝑛} = (𝑏_{0}, \dots, 𝑏_{𝑛 - 2}, 1),

which is nonzero. Also $𝐶^{𝑛} 𝐞_{1} =$ $𝐶 𝐞_{𝑛} =$ $- \sum_{𝑗 = 0}^{𝑛 - 1} 𝑎_{𝑗} 𝐞_{𝑗 + 1}$ , so $𝑝 (𝐶) 𝐞_{1} =$ $𝐶^{𝑛} 𝐞_{1} +$ $\sum_{𝑗} 𝑎_{𝑗} 𝐞_{𝑗 + 1} =$ $𝟎$ . By Remark 7.1.11, $(𝐶 - 𝜆 𝐼_{𝑛}) 𝐰 =$ $((𝑥 - 𝜆) 𝑞) (𝐶) 𝐞_{1} =$ $𝑝 (𝐶) 𝐞_{1} =$ $𝟎$ .

(c) By Theorem 7.3.24 and Theorem 7.3.6, the eigenvalues of $𝐶$ are the roots of $𝑝$ in $𝐹$ . If there are $𝑛$ distinct ones, eigenvectors for them are independent (Theorem 7.2.21), hence a basis of $𝐹^{𝑛}$ . Conversely, suppose $𝐯_{1}, \dots, 𝐯_{𝑛}$ is a basis of eigenvectors. Two of them with the same eigenvalue would be two independent vectors in one eigenspace, which is a line by (a). So their eigenvalues are $𝑛$ distinct roots of $𝑝$ , and $𝑝$ has at least, hence exactly, $𝑛$ distinct roots (Proposition 7.1.22). In the language of Section 7.4, $𝐶_{𝑝}$ is diagonalizable over $𝐹$ exactly when $𝑝$ splits with distinct roots.

Exercise 7.3.46.standard Let $𝐴 =$ $(\begin{matrix} 1 & - 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 2 \end{matrix}) \in$ $ℂ^{3 \times 3}$ .

(a)For $𝐯 = 𝐞_{1} + 𝐞_{3}$ , compute $𝐯,$ $𝐴 𝐯,$ $𝐴^{2} 𝐯,$ $𝐴^{3} 𝐯$ , and find the polynomial $𝑝$ of Proposition 7.2.35.
(b)Factor $𝑝$ over $ℂ$ , and use the second proof of Theorem 7.3.27 to produce an eigenvector for each root.
(c)Repeat (a) for $𝐯 = 𝐞_{1}$ . Which eigenvalue does this Krylov sequence miss, and why is that consistent with Proposition 7.3.26?

Solution.

Uses. Proposition 7.2.35 (A basis of a Krylov subspace), Theorem 7.3.27 (Existence of eigenvalues over $ℂ$ ), Proposition 7.3.26 (Krylov subspaces and the characteristic polynomial), Remark 7.1.11 (Polynomials in a matrix)

Techniques. Krylov sequences must become dependent (Technique 7.3.28)

Hint 1.

𝐯, 𝐴 𝐯, 𝐴^{2} 𝐯

turn out to be independent. Solve

𝐴^{3} 𝐯 =

𝛼 𝐯 +

𝛽 𝐴 𝐯 +

𝛾 𝐴^{2} 𝐯

Hint 2.

𝑝 = 𝑥^{3} - 4 𝑥^{2} + 6 𝑥 - 4

has the root

2

. For a root

𝜆

, apply

𝑞 = 𝑝 / (𝑥 - 𝜆)

𝐴

𝐯

Sketch. (a)

𝐯 = (1, 0, 1)

𝐴 𝐯 = (1, 1, 2)

𝐴^{2} 𝐯 = (0, 2, 4)

𝐴^{3} 𝐯 =

(- 2, 2, 8) =

4 𝐯 -

6 𝐴 𝐯 +

4 𝐴^{2} 𝐯

, so

𝑝 = 𝑥^{3} - 4 𝑥^{2} + 6 𝑥 - 4

. (b)

𝑝 =

(𝑥 - 2) (𝑥 - 1 - 𝑖) (𝑥 - 1 + 𝑖)

, with eigenvectors

(0, 0, 2)

(- 1 - 𝑖, - 1 + 𝑖, 0)

, and

(- 1 + 𝑖, - 1 - 𝑖, 0)

. (c)

𝐴^{2} 𝐞_{1} =

2 𝐴 𝐞_{1} -

2 𝐞_{1}

, so

𝑝 = 𝑥^{2} - 2 𝑥 + 2

, which misses

2

; it is a proper divisor of

𝑝_{𝐴}

(a) We get $𝐯 = (1, 0, 1)$ , $𝐴 𝐯 = (1, 1, 2)$ , $𝐴^{2} 𝐯 = (0, 2, 4)$ , and $𝐴^{3} 𝐯 = (- 2, 2, 8)$ . The first three are independent: the matrix with these columns has determinant $1 \cdot$ $(4 - 4) -$ $1 \cdot$ $(0 - 2) +$ $0 =$ $2 \neq$ $0$ . Solving $𝐴^{3} 𝐯 =$ $𝛼 𝐯 +$ $𝛽 𝐴 𝐯 +$ $𝛾 𝐴^{2} 𝐯$ coordinatewise gives $𝛼 + 𝛽 = - 2$ , $𝛽 + 2 𝛾 = 2$ , $𝛼 + 2 𝛽 + 4 𝛾 = 8$ , so $𝛾 = 4$ , $𝛽 = - 6$ , $𝛼 = 4$ . Hence $𝑑 = 3$ and $𝑝 = 𝑥^{3} - 4 𝑥^{2} + 6 𝑥 - 4$ .

(b) $𝑝 (2) = 0$ , and dividing, $𝑝 =$ $(𝑥 - 2) (𝑥^{2} - 2 𝑥 + 2) =$ $(𝑥 - 2) (𝑥 - (1 + 𝑖)) (𝑥 - (1 - 𝑖))$ . For each root $𝜆$ let $𝑞 = 𝑝 / (𝑥 - 𝜆)$ ; then $𝑞 (𝐴) 𝐯$ is an eigenvector for $𝜆$ .

$𝜆 = 2$ : $𝑞 = 𝑥^{2} - 2 𝑥 + 2$ , and $𝑞 (𝐴) 𝐯 =$ $(0, 2, 4) -$ $2 (1, 1, 2) +$ $2 (1, 0, 1) =$ $(0, 0, 2)$ .
$𝜆 = 1 + 𝑖$ : $𝑞 =$ $(𝑥 - 2) (𝑥 - 1 + 𝑖) =$ $𝑥^{2} -$ $(3 - 𝑖) 𝑥 +$ $(2 - 2 𝑖)$ , and
$𝑞 (𝐴) 𝐯 = (0, 2, 4) - (3 - 𝑖) (1, 1, 2) + (2 - 2 𝑖) (1, 0, 1) = (- 1 - 𝑖, - 1 + 𝑖, 0) = (- 1 + 𝑖) (𝑖, 1, 0) .$
$𝜆 = 1 - 𝑖$ : conjugating the previous computation, since $𝐴$ and $𝐯$ are real, gives $(- 1 + 𝑖, - 1 - 𝑖, 0) =$ $(- 1 - 𝑖) (- 𝑖, 1, 0)$ .

Check: $𝐴 (0, 0, 1) =$ $2 (0, 0, 1)$ and $𝐴 (𝑖, 1, 0) =$ $(𝑖 - 1, 𝑖 + 1, 0) =$ $(1 + 𝑖) (𝑖, 1, 0)$ .

(c) For $𝐯 = 𝐞_{1}$ : $𝐴 𝐞_{1} = (1, 1, 0)$ , which is not a multiple of $𝐞_{1}$ , and $𝐴^{2} 𝐞_{1} =$ $(0, 2, 0) =$ $2 𝐴 𝐞_{1} -$ $2 𝐞_{1}$ . So $𝑑 = 2$ and $𝑝 = 𝑥^{2} - 2 𝑥 + 2$ , which produces the eigenvectors $(𝐴 - (1 - 𝑖) 𝐼_{3}) 𝐞_{1} =$ $(𝑖, 1, 0)$ and $(𝐴 - (1 + 𝑖) 𝐼_{3}) 𝐞_{1} =$ $(- 𝑖, 1, 0)$ but misses the eigenvalue $2$ . This is consistent with Proposition 7.3.26: $𝑝$ divides $𝑝_{𝐴} =$ $(𝑥 - 2) (𝑥^{2} - 2 𝑥 + 2)$ , but need not equal it, because $𝐾_{𝐴} (𝐞_{1}) =$ $span (𝐞_{1}, 𝐞_{2})$ is a proper invariant subspace.

Exercise 7.3.47.standard Find the error in the following argument.

Claim. For every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , $𝑝_{𝐴} (𝐴) = 0$ .

“Proof.” By definition, $𝑝_{𝐴} (𝑥) =$ $det (𝑥 𝐼_{𝑛} - 𝐴)$ . Substituting $𝑥 = 𝐴$ gives $𝑝_{𝐴} (𝐴) =$ $det (𝐴 𝐼_{𝑛} - 𝐴) =$ $det (𝐴 - 𝐴) =$ $det 0 =$ $0$ .

Solution.

Uses. Definition 7.3.4 (Characteristic polynomial), Proposition 7.3.2 (Determinants over a commutative ring), Remark 7.1.11 (Polynomials in a matrix)

Hint 1. What kind of object is each side?

𝑝_{𝐴} (𝐴)

is a matrix. What is

det (\dots)

Hint 2. Proposition 7.3.2(g) lets us substitute

𝐴

for

𝑥

in every entry of

𝑥 𝐼_{𝑛} - 𝐴

. What does that array look like? Is it the matrix

𝐴 - 𝐴

Hint 3. Apply the same reasoning to the single entry

𝑥 - 𝑎_{11}

𝑥 𝐼_{𝑛} - 𝐴

, instead of to its determinant.

Sketch. The two sides have different types:

𝑝_{𝐴} (𝐴)

is a matrix and a determinant is a scalar. Substituting

𝐴

for

𝑥

entrywise turns

𝑥 𝐼_{𝑛} - 𝐴

into an

𝑛 \times 𝑛

array of matrices, with

𝐴 - 𝑎_{𝑖 𝑖} 𝐼_{𝑛}

on the diagonal and

- 𝑎_{𝑖 𝑗} 𝐼_{𝑛}

elsewhere, not into

𝐴 - 𝐴 = 0

. The same move would show

𝐴 = 𝑎_{11} 𝐼_{𝑛}

for every

𝐴

. The claim is true (Cayley–Hamilton) but needs a real proof.

The claim is true; it is the Cayley–Hamilton theorem (Theorem 7.6.20), and Exercise 7.3.51 proves it. The argument is not a proof.

First, the types do not match: $𝑝_{𝐴} (𝐴) =$ $𝐴^{𝑛} +$ $𝑐_{𝑛 - 1} 𝐴^{𝑛 - 1} +$ $\dots +$ $𝑐_{0} 𝐼_{𝑛}$ is an $𝑛 \times 𝑛$ matrix, while a determinant is a scalar.

Second, the substitution is done wrongly. The identity $𝑝_{𝐴} =$ $det (𝑥 𝐼_{𝑛} - 𝐴)$ holds in $𝐹 [𝑥]$ , and Proposition 7.3.2(g) does allow us to apply a map like “substitute $𝐴$ for $𝑥$ ” to it, but entry by entry. The map $𝑞 \mapsto 𝑞 (𝐴)$ takes values in the commutative ring of polynomials in $𝐴$ (Remark 7.1.11), and applied to the entries of $𝑥 𝐼_{𝑛} - 𝐴$ it gives the $𝑛 \times 𝑛$ array whose $(𝑖, 𝑖)$ entry is the matrix $𝐴 - 𝑎_{𝑖 𝑖} 𝐼_{𝑛}$ and whose $(𝑖, 𝑗)$ entry is the matrix $- 𝑎_{𝑖 𝑗} 𝐼_{𝑛}$ . The determinant of that array, computed in this ring, is indeed $𝑝_{𝐴} (𝐴)$ . But the array is not the zero matrix “ $𝐴 𝐼_{𝑛} - 𝐴$ ”: the scalar entries $𝑎_{𝑖 𝑗}$ became the matrices $𝑎_{𝑖 𝑗} 𝐼_{𝑛}$ , not the scalars $𝑎_{𝑖 𝑗}$ . For $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , the array is $(\begin{matrix} 𝐴 & - 𝐼_{2} \\ 0 & 𝐴 \end{matrix})$ , whose determinant in this ring is $𝐴^{2} = 0$ , although no entry is $0$ .

Third, the argument proves too much. Apply the same move to the polynomial $𝑓 = 𝑥 - 𝑎_{11}$ , the $(1, 1)$ entry of $𝑥 𝐼_{𝑛} - 𝐴$ : “substituting $𝑥 = 𝐴$ ” gives $𝑓 (𝐴) =$ ${(𝐴 𝐼_{𝑛} - 𝐴)}_{11} =$ $0$ , that is, $𝐴 = 𝑎_{11} 𝐼_{𝑛}$ for every $𝐴$ , which is false.

Exercise 7.3.48.hard Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐴^{𝑘} = 0$ for some $𝑘 \geq 1$ .

(a)Show that in ${𝐹 [𝑥]}^{𝑛 \times 𝑛}$ ,
$(𝑥 𝐼_{𝑛} - 𝐴) (𝑥^{𝑘 - 1} 𝐼_{𝑛} + 𝑥^{𝑘 - 2} 𝐴 + \dots + 𝑥 𝐴^{𝑘 - 2} + 𝐴^{𝑘 - 1}) = 𝑥^{𝑘} 𝐼_{𝑛} .$
(b)Deduce that $𝑝_{𝐴} = 𝑥^{𝑛}$ . In particular $tr 𝐴 = 0$ , and $0$ is the only eigenvalue of $𝐴$ .
(c)For $𝐹 = ℂ$ , give a shorter proof of (b) using eigenvalues. Why does it not work over every field?

Solution.

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Theorem 7.1.20 (Factor theorem), Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 7.3.18 (The first and last coefficients), Proposition 7.2.28 (Polynomials act on eigenvectors by their values), Corollary 7.1.35 (Factorization over $ℂ$ )

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. For (a), multiply out; the sum telescopes.

Hint 2. For (b), take determinants:

𝑝_{𝐴} 𝑔 = 𝑥^{𝑘 𝑛}

for some

𝑔 \in 𝐹 [𝑥]

. So

𝑝_{𝐴}

divides a power of

𝑥

Hint 3. Write

𝑝_{𝐴} = 𝑥^{𝑚} ℎ

with

ℎ (0) \neq 0

. Show that

ℎ

divides

1

, by evaluating at

0

and cancelling

𝑥

repeatedly.

Sketch. (a) Telescoping:

\sum_{𝑗} 𝑥^{𝑘 - 𝑗} 𝐴^{𝑗} -

\sum_{𝑗} 𝑥^{𝑘 - 1 - 𝑗} 𝐴^{𝑗 + 1} =

𝑥^{𝑘} 𝐼_{𝑛} -

𝐴^{𝑘}

. (b) Taking determinants,

𝑝_{𝐴} \cdot 𝑔 = 𝑥^{𝑘 𝑛}

. Write

𝑝_{𝐴} = 𝑥^{𝑚} ℎ

with

ℎ (0) \neq 0

; cancelling

𝑥^{𝑚}

gives

ℎ 𝑔 = 𝑥^{𝑘 𝑛 - 𝑚}

, and evaluating at

0

repeatedly shows that

𝑔

absorbs every factor

𝑥

, so

ℎ 𝑔^{'} = 1

and

ℎ

is a constant, hence

1

. So

𝑝_{𝐴} = 𝑥^{𝑛}

. (c) Over

ℂ

, every eigenvalue satisfies

𝜆^{𝑘} = 0

, and

𝑝_{𝐴}

splits.

(a) Let $𝑁 =$ $\sum_{𝑗 = 0}^{𝑘 - 1} 𝑥^{𝑘 - 1 - 𝑗} 𝐴^{𝑗}$ . By Proposition 7.3.2(a), and since the scalar matrices $𝑥^{𝑚} 𝐼_{𝑛}$ commute with every matrix,

(𝑥 𝐼_{𝑛} - 𝐴) 𝑁 = \sum_{𝑗 = 0}^{𝑘 - 1} 𝑥^{𝑘 - 𝑗} 𝐴^{𝑗} - \sum_{𝑗 = 0}^{𝑘 - 1} 𝑥^{𝑘 - 1 - 𝑗} 𝐴^{𝑗 + 1} = \sum_{𝑗 = 0}^{𝑘 - 1} 𝑥^{𝑘 - 𝑗} 𝐴^{𝑗} - \sum_{𝑗 = 1}^{𝑘} 𝑥^{𝑘 - 𝑗} 𝐴^{𝑗} = 𝑥^{𝑘} 𝐼_{𝑛} - 𝐴^{𝑘},

which is $𝑥^{𝑘} 𝐼_{𝑛}$ because $𝐴^{𝑘} = 0$ .

(b) Let $𝑔 = det 𝑁 \in 𝐹 [𝑥]$ . Taking determinants in (a) with Proposition 7.3.2(c) and (e), $𝑝_{𝐴} 𝑔 =$ $det (𝑥^{𝑘} 𝐼_{𝑛}) =$ $𝑥^{𝑘 𝑛}$ . Since $𝑝_{𝐴} \neq 𝟎$ , write $𝑝_{𝐴} = 𝑥^{𝑚} ℎ$ with $𝑚 \geq 0$ as large as possible, so that $𝑥$ does not divide $ℎ$ , that is, $ℎ (0) \neq 0$ (Theorem 7.1.20). Comparing degrees in $𝑥^{𝑚} ℎ 𝑔 = 𝑥^{𝑘 𝑛}$ gives $𝑚 \leq 𝑘 𝑛$ , and cancelling $𝑥^{𝑚}$ (Corollary 7.1.7(b)) gives $ℎ 𝑔 = 𝑥^{𝑘 𝑛 - 𝑚}$ .

We show by induction on $𝑟 = 𝑘 𝑛 - 𝑚$ that an equation $ℎ 𝑔 = 𝑥^{𝑟}$ forces $ℎ$ to be a nonzero constant. If $𝑟 = 0$ , then $ℎ 𝑔 = 1$ , so $ℎ$ is invertible in $𝐹 [𝑥]$ , hence a nonzero constant (Corollary 7.1.7(c)). If $𝑟 \geq 1$ , evaluating at $0$ gives $ℎ (0) 𝑔 (0) = 0$ , so $𝑔 (0) = 0$ and $𝑔 = 𝑥 𝑔_{1}$ (Theorem 7.1.20). Then $𝑥 (ℎ 𝑔_{1}) =$ $𝑥 \cdot$ $𝑥^{𝑟 - 1}$ , and cancelling $𝑥$ gives $ℎ 𝑔_{1} = 𝑥^{𝑟 - 1}$ , to which the induction hypothesis applies.

So $ℎ$ is a constant, and $ℎ = 1$ because $𝑝_{𝐴}$ is monic. Thus $𝑝_{𝐴} = 𝑥^{𝑚}$ , and $𝑚 = deg 𝑝_{𝐴} = 𝑛$ (Proposition 7.3.18). The coefficient of $𝑥^{𝑛 - 1}$ is $0 = - tr 𝐴$ , and $0$ is the only root.

(c) Over $ℂ$ : if $𝐴 𝐯 = 𝜆 𝐯$ with $𝐯 \neq 𝟎$ , then $𝟎 = 𝐴^{𝑘} 𝐯 = 𝜆^{𝑘} 𝐯$ (Proposition 7.2.28), so $𝜆 = 0$ . By Corollary 7.1.35, $𝑝_{𝐴}$ is a product of factors $𝑥 - 𝜆_{𝑗}$ whose roots $𝜆_{𝑗}$ are eigenvalues, hence $0$ ; so $𝑝_{𝐴} = 𝑥^{𝑛}$ . Over a general field this argument only shows that $0$ is the only root of $𝑝_{𝐴}$ in $𝐹$ ; it cannot rule out an irreducible factor of degree at least $2$ , because $𝑝_{𝐴}$ need not split. The proof of (b) never needs $𝑝_{𝐴}$ to split.

Exercise 7.3.49.hard Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . For $𝑓 \in 𝐹 [𝑥]$ , write $𝑓 (𝑥^{2})$ and $𝑓 (- 𝑥)$ for the polynomials obtained by substituting $𝑥^{2}$ and $- 𝑥$ for $𝑥$ (Definition 7.1.9).

(a)Show that $𝑝_{𝐴^{2}} (𝑥^{2}) =$ ${(- 1)}^{𝑛} 𝑝_{𝐴} (𝑥) 𝑝_{𝐴} (- 𝑥)$ .
(b)Suppose $𝑝_{𝐴} =$ $(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ . Show that $𝑝_{𝐴^{2}} =$ $(𝑥 - 𝜆_{1}^{2}) \dots (𝑥 - 𝜆_{𝑛}^{2})$ .
(c)Deduce that if $𝐴 \in ℝ^{𝑛 \times 𝑛}$ , $𝑝_{𝐴}$ splits over $ℝ$ , and $tr (𝐴^{2}) = 0$ , then $𝑝_{𝐴} = 𝑥^{𝑛}$ .

Solution.

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Proposition 7.1.10 (Evaluation respects sums and products), Remark 7.3.19 (Trace and determinant from the roots)

Techniques. Polynomial identity arguments (Technique 5.5.24)

Hint 1. Factor

𝑥^{2} 𝐼_{𝑛} - 𝐴^{2}

{𝐹 [𝑥]}^{𝑛 \times 𝑛}

Hint 2.

det (𝑥^{2} 𝐼_{𝑛} - 𝐴^{2})

𝑝_{𝐴^{2}}

with

𝑥^{2}

substituted, by Proposition 7.3.2(g). Similarly, what is

det (𝑥 𝐼_{𝑛} + 𝐴)

in terms of

𝑝_{𝐴}

Hint 3. For (b),

(𝑥 - 𝜆) (𝑥 + 𝜆) =

𝑥^{2} -

𝜆^{2}

. A polynomial

𝑟

is determined by

𝑟 (𝑥^{2})

Sketch. (a)

𝑥^{2} 𝐼_{𝑛} -

𝐴^{2} =

(𝑥 𝐼_{𝑛} - 𝐴) (𝑥 𝐼_{𝑛} + 𝐴)

. Substituting

𝑥^{2}

into

𝑥 𝐼_{𝑛} - 𝐴^{2}

gives

𝑥^{2} 𝐼_{𝑛} - 𝐴^{2}

, so its determinant is

𝑝_{𝐴^{2}} (𝑥^{2})

; and

det (𝑥 𝐼_{𝑛} + 𝐴) =

{(- 1)}^{𝑛} det (- 𝑥 𝐼_{𝑛} - 𝐴) =

{(- 1)}^{𝑛} 𝑝_{𝐴} (- 𝑥)

. (b)

{(- 1)}^{𝑛} 𝑝_{𝐴} (- 𝑥) =

\prod (𝑥 + 𝜆_{𝑖})

, so the right side is

\prod (𝑥^{2} - 𝜆_{𝑖}^{2}) =

𝑞 (𝑥^{2})

with

𝑞 = \prod (𝑥 - 𝜆_{𝑖}^{2})

; compare coefficients. (c)

tr (𝐴^{2}) = \sum 𝜆_{𝑖}^{2} = 0

with real

𝜆_{𝑖}

(a) In ${𝐹 [𝑥]}^{𝑛 \times 𝑛}$ , $(𝑥 𝐼_{𝑛} - 𝐴) (𝑥 𝐼_{𝑛} + 𝐴) =$ $𝑥^{2} 𝐼_{𝑛} +$ $𝑥 𝐴 -$ $𝑥 𝐴 -$ $𝐴^{2} =$ $𝑥^{2} 𝐼_{𝑛} -$ $𝐴^{2}$ . Substituting $𝑥^{2}$ for $𝑥$ respects sums, products, and $1$ (Proposition 7.1.10), and applied to every entry of $𝑥 𝐼_{𝑛} - 𝐴^{2}$ it gives $𝑥^{2} 𝐼_{𝑛} - 𝐴^{2}$ ; so by Proposition 7.3.2(g), $det (𝑥^{2} 𝐼_{𝑛} - 𝐴^{2}) =$ $𝑝_{𝐴^{2}} (𝑥^{2})$ . In the same way, substituting $- 𝑥$ into $𝑥 𝐼_{𝑛} - 𝐴$ gives $- 𝑥 𝐼_{𝑛} - 𝐴$ , so $det (- 𝑥 𝐼_{𝑛} - 𝐴) =$ $𝑝_{𝐴} (- 𝑥)$ , and $det (𝑥 𝐼_{𝑛} + 𝐴) =$ ${(- 1)}^{𝑛} det (- 𝑥 𝐼_{𝑛} - 𝐴) =$ ${(- 1)}^{𝑛} 𝑝_{𝐴} (- 𝑥)$ by multilinearity. Taking determinants of the factorization (Proposition 7.3.2(c)) gives $𝑝_{𝐴^{2}} (𝑥^{2}) =$ $𝑝_{𝐴} (𝑥) \cdot$ ${(- 1)}^{𝑛} 𝑝_{𝐴} (- 𝑥)$ .

(b) Substituting $- 𝑥$ into the factorization gives $𝑝_{𝐴} (- 𝑥) =$ $\prod_{𝑖} (- 𝑥 - 𝜆_{𝑖}) =$ ${(- 1)}^{𝑛} \prod_{𝑖} (𝑥 + 𝜆_{𝑖})$ . So by (a),

𝑝_{𝐴^{2}} (𝑥^{2}) = \prod_{𝑖} (𝑥 - 𝜆_{𝑖}) (𝑥 + 𝜆_{𝑖}) = \prod_{𝑖} (𝑥^{2} - 𝜆_{𝑖}^{2}) = 𝑞 (𝑥^{2}), 𝑞 = \prod_{𝑖} (𝑥 - 𝜆_{𝑖}^{2}) .

For any $𝑟 = \sum_{𝑘} 𝑟_{𝑘} 𝑥^{𝑘}$ , the coefficient of $𝑥^{2 𝑘}$ in $𝑟 (𝑥^{2}) =$ $\sum_{𝑘} 𝑟_{𝑘} 𝑥^{2 𝑘}$ is $𝑟_{𝑘}$ . So $𝑟 (𝑥^{2}) = 𝑠 (𝑥^{2})$ implies $𝑟 = 𝑠$ , and $𝑝_{𝐴^{2}} = 𝑞$ .

(c) Let $𝑝_{𝐴} = \prod (𝑥 - 𝜆_{𝑖})$ with $𝜆_{𝑖} \in ℝ$ . By (b) and Remark 7.3.19 applied to $𝐴^{2}$ , $tr (𝐴^{2}) =$ $𝜆_{1}^{2} +$ $\dots +$ $𝜆_{𝑛}^{2}$ . If this is $0$ , then every $𝜆_{𝑖} = 0$ , since a sum of squares of reals vanishes only when each term does. So $𝑝_{𝐴} = 𝑥^{𝑛}$ .

Exercise 7.3.50.hard Let $dim 𝑉 = 𝑛 \geq 1$ and $𝑇 \in L (𝑉)$ . A vector $𝐯$ is a cyclic vector for $𝑇$ if $𝐾_{𝑇} (𝐯) = 𝑉$ .

(a)Show that if $𝑇$ has a cyclic vector, then the matrix of $𝑇$ in some basis is $𝐶_{𝑝_{𝑇}}$ .
(b)Suppose $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ both have cyclic vectors (for $𝑇_{𝐴}$ and $𝑇_{𝐵}$ ). Show that $𝐴$ and $𝐵$ are similar if and only if $𝑝_{𝐴} = 𝑝_{𝐵}$ .
(c)Show that $𝐼_{2}$ has no cyclic vector, and that $𝐶_{𝑝}$ and $𝐶_{𝑝}^{𝖳}$ are similar for every monic $𝑝$ .

Solution.

Uses. Proposition 7.2.35 (A basis of a Krylov subspace), Proposition 7.3.26 (Krylov subspaces and the characteristic polynomial), Theorem 4.5.25 (Similar matrices are one operator in two bases), Proposition 4.5.24 (Similarity is an equivalence relation), Proposition 7.3.11 (Similar matrices have the same characteristic polynomial), Exercise 7.3.17

Hint 1. For (a), if

𝐾_{𝑇} (𝐯) = 𝑉

, what is

𝑑

in Proposition 7.2.35? Then use Proposition 7.3.26.

Hint 2. For (b), both matrices are similar to the same companion matrix.

Hint 3. For (c),

𝐶_{𝑝}

has the cyclic vector

𝐞_{1}

. For

𝐶_{𝑝}^{𝖳}

, try

𝐞_{𝑛}

and show that

{(𝐶_{𝑝}^{𝖳})}^{𝑗} 𝐞_{𝑛}

𝐞_{𝑛 - 𝑗}

plus a combination of

𝐞_{𝑛 - 𝑗 + 1}, \dots, 𝐞_{𝑛}

Sketch. (a)

𝑑 = 𝑛

, and in the basis

𝐯, \dots, 𝑇^{𝑛 - 1} 𝐯

the matrix is

𝐶_{𝑝}

with

𝑝 = 𝑝_{𝑇}

(Proposition 7.3.26). (b) Both are similar to

𝐶_{𝑓}

for

𝑓 = 𝑝_{𝐴} = 𝑝_{𝐵}

; the converse is Proposition 7.3.11. (c)

dim 𝐾 (𝐯) \leq 1

for

𝐼_{2}

𝐶_{𝑝}

is cyclic with

𝐞_{1}

𝐶_{𝑝}^{𝖳}

with

𝐞_{𝑛}

(triangular argument), and

𝑝_{𝐶_{𝑝}} = 𝑝_{𝐶_{𝑝}^{𝖳}}

(a) Let $𝐯$ be cyclic, so $𝐯 \neq 𝟎$ (as $𝑉 \neq {𝟎}$ ). In Proposition 7.2.35, $𝑑 = dim 𝐾_{𝑇} (𝐯) = 𝑛$ , so $𝐯,$ $𝑇 𝐯,$ $\dots,$ $𝑇^{𝑛 - 1} 𝐯$ is a basis of $𝑉$ , and by Proposition 7.3.26 the matrix of $𝑇$ in it is $𝐶_{𝑝}$ , with $𝑝_{𝑇} = 𝑝$ . So the matrix is $𝐶_{𝑝_{𝑇}}$ .

(b) If $𝐴 \sim 𝐵$ , then $𝑝_{𝐴} = 𝑝_{𝐵}$ by Proposition 7.3.11. Conversely, let $𝑓 = 𝑝_{𝐴} = 𝑝_{𝐵}$ . By (a), $𝑇_{𝐴}$ has matrix $𝐶_{𝑓}$ in some basis, so $𝐴 \sim 𝐶_{𝑓}$ by Theorem 4.5.25, and likewise $𝐵 \sim 𝐶_{𝑓}$ . By Proposition 4.5.24, $𝐴 \sim 𝐵$ .

(c) For every $𝐯 \in 𝐹^{2}$ , $𝐾_{𝐼_{2}} (𝐯) =$ $span (𝐯)$ has dimension at most $1$ , so $𝐼_{2}$ has no cyclic vector. (Indeed $𝐼_{2}$ and $(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ have the same characteristic polynomial and are not similar, so (b) needs the hypothesis.)

Now let $𝐶 = 𝐶_{𝑝}$ . Since $𝐶^{𝑗} 𝐞_{1} = 𝐞_{𝑗 + 1}$ for $𝑗 < 𝑛$ , $𝐞_{1}$ is cyclic for $𝐶$ . For $𝐶^{𝖳}$ : column $𝑗$ of $𝐶^{𝖳}$ is row $𝑗$ of $𝐶$ , which is $- 𝑎_{0} 𝐞_{𝑛}^{𝖳}$ for $𝑗 = 1$ and $𝐞_{𝑗 - 1}^{𝖳} -$ $𝑎_{𝑗 - 1} 𝐞_{𝑛}^{𝖳}$ for $𝑗 \geq 2$ . So $𝐶^{𝖳} 𝐞_{𝑗} =$ $𝐞_{𝑗 - 1} -$ $𝑎_{𝑗 - 1} 𝐞_{𝑛}$ for $𝑗 \geq 2$ . By induction on $𝑗$ , ${(𝐶^{𝖳})}^{𝑗} 𝐞_{𝑛} =$ $𝐞_{𝑛 - 𝑗} +$ $𝐫_{𝑗}$ with $𝐫_{𝑗} \in$ $span (𝐞_{𝑛 - 𝑗 + 1}, \dots, 𝐞_{𝑛})$ for $0 \leq 𝑗 \leq 𝑛 - 1$ (with $𝐫_{0} = 𝟎$ ): applying $𝐶^{𝖳}$ lowers each index by one and adds a multiple of $𝐞_{𝑛}$ . So ${(𝐶^{𝖳})}^{𝑗} 𝐞_{𝑛}$ has coordinate $1$ at $𝐞_{𝑛 - 𝑗}$ and coordinate $0$ at $𝐞_{1}, \dots, 𝐞_{𝑛 - 𝑗 - 1}$ . Hence the matrix with columns ${(𝐶^{𝖳})}^{𝑛 - 1} 𝐞_{𝑛},$ $\dots,$ $𝐶^{𝖳} 𝐞_{𝑛},$ $𝐞_{𝑛}$ is lower triangular with $1$ ′s on the diagonal, so these vectors are independent (Proposition 5.3.15, Theorem 5.4.7), and $𝐞_{𝑛}$ is cyclic for $𝐶^{𝖳}$ . Since $𝑝_{𝐶^{𝖳}} = 𝑝_{𝐶}$ (Exercise 7.3.17), (b) shows $𝐶 \sim 𝐶^{𝖳}$ .

Exercise 7.3.51.hardBeyond 21-242 Let $𝑉$ be finite-dimensional with $dim 𝑉 \geq 1$ , and $𝑇 \in L (𝑉)$ .

(a)Use Proposition 7.3.26 to show that $𝑝_{𝑇} (𝑇) = 0$ . This is the Cayley–Hamilton theorem (Theorem 7.6.20).
(b)Deduce that every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ satisfies a monic polynomial of degree $𝑛$ , improving the degree $𝑛^{2}$ of Proposition 4.1.31.

Solution.

Uses. Proposition 7.3.26 (Krylov subspaces and the characteristic polynomial), Proposition 7.2.27 (Evaluating polynomials at an operator), Proposition 4.1.31 (Every square matrix satisfies a polynomial)

Techniques. Krylov sequences must become dependent (Technique 7.3.28)

Hint 1. It is enough to show

𝑝_{𝑇} (𝑇) 𝐯 = 𝟎

for each

𝐯

. Fix

𝐯 \neq 𝟎

and its Krylov polynomial

𝑝

Hint 2.

𝑝

divides

𝑝_{𝑇}

, so

𝑝_{𝑇} = 𝑔 𝑝

. Evaluate at

𝑇

and apply to

𝐯

Sketch. For

𝐯 \neq 𝟎

with Krylov polynomial

𝑝

𝑝_{𝑇} = 𝑔 𝑝

by Proposition 7.3.26(c), so

𝑝_{𝑇} (𝑇) 𝐯 =

𝑔 (𝑇) 𝑝 (𝑇) 𝐯 =

𝟎

. For matrices, apply this to

𝑇_{𝐴}

and use

[𝑞 (𝑇)] = 𝑞 ([𝑇])

(a) Let $𝐯 \in 𝑉$ . If $𝐯 = 𝟎$ , then $𝑝_{𝑇} (𝑇) 𝐯 = 𝟎$ . Otherwise let $𝑝$ be the polynomial of Proposition 7.2.35 for $𝐯$ , so $𝑝 (𝑇) 𝐯 = 𝟎$ . By Proposition 7.3.26(c), $𝑝_{𝑇} = 𝑔 𝑝$ for some $𝑔 \in 𝐹 [𝑥]$ , and by Proposition 7.2.27(a),

𝑝_{𝑇} (𝑇) 𝐯 = 𝑔 (𝑇) (𝑝 (𝑇) 𝐯) = 𝑔 (𝑇) 𝟎 = 𝟎 .

So $𝑝_{𝑇} (𝑇)$ sends every vector to $𝟎$ , that is, $𝑝_{𝑇} (𝑇) = 0$ .

(b) Apply (a) to $𝑇_{𝐴}$ on $𝐹^{𝑛}$ . Its matrix in the standard basis is $𝐴$ , so $𝑝_{𝑇_{𝐴}} = 𝑝_{𝐴}$ , and by Proposition 7.2.27(c), $𝑝_{𝐴} (𝐴)$ is the matrix of $𝑝_{𝐴} (𝑇_{𝐴}) = 0$ . So $𝑝_{𝐴} (𝐴) = 0$ , and $𝑝_{𝐴}$ is monic of degree $𝑛$ .

Exercise 7.3.52.hard Let $𝑞$ be a prime and $𝑓 =$ $𝑥^{2} -$ $𝑡 𝑥 +$ $𝑑 \in$ $𝔽_{𝑞} [𝑥]$ .

(a)Show that the number of matrices $𝐴 \in 𝔽_{𝑞}^{2 \times 2}$ with $𝑝_{𝐴} = 𝑓$ is $𝑞^{2} + 𝑞$ if $𝑓$ has two distinct roots in $𝔽_{𝑞}$ , $𝑞^{2}$ if it has one repeated root, and $𝑞^{2} - 𝑞$ if it has no root.
(b)Deduce that exactly ${(𝑞^{2} - 𝑞)}^{2} / 2$ matrices in $𝔽_{𝑞}^{2 \times 2}$ have no eigenvalue in $𝔽_{𝑞}$ , and check that the counts in (a) add up to $𝑞^{4}$ .

Solution.

Uses. Example 7.3.5 (Small cases), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Proposition 7.1.22 (Counting roots)

Techniques. Double counting (Technique 4.1.36)

Hint 1. Write

𝐴 = (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑒 \end{matrix})

. The conditions are

𝑎 + 𝑒 = 𝑡

and

𝑎 𝑒 - 𝑏 𝑐 = 𝑑

. Choose

𝑎

first.

Hint 2. Then

𝑒 = 𝑡 - 𝑎

and

𝑏 𝑐 =

𝑎 (𝑡 - 𝑎) -

𝑑 =

- 𝑓 (𝑎)

. How many pairs

(𝑏, 𝑐)

have a given product

𝑚

? Distinguish

𝑚 = 0

and

𝑚 \neq 0

Hint 3. If

𝑓

has

𝑟

roots in

𝔽_{𝑞}

, the total is

𝑟 (2 𝑞 - 1) +

(𝑞 - 𝑟) (𝑞 - 1) =

𝑞 (𝑞 - 1) +

𝑟 𝑞

Sketch. For each

𝑎

𝑒 = 𝑡 - 𝑎

is forced and

𝑏 𝑐 = - 𝑓 (𝑎)

; there are

2 𝑞 - 1

pairs

(𝑏, 𝑐)

𝑓 (𝑎) = 0

and

𝑞 - 1

otherwise. So the count is

𝑞 (𝑞 - 1) + 𝑟 𝑞

, where

𝑟 \in {0, 1, 2}

is the number of roots. There are

(𝑞^{2} - 𝑞) / 2

monic quadratics without roots, each realized by

𝑞^{2} - 𝑞

matrices.

(a) Write $𝐴 = (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑒 \end{matrix})$ . By Example 7.3.5(a), $𝑝_{𝐴} = 𝑓$ if and only if $𝑎 + 𝑒 = 𝑡$ and $𝑎 𝑒 - 𝑏 𝑐 = 𝑑$ . Choose $𝑎 \in 𝔽_{𝑞}$ arbitrarily ( $𝑞$ ways). Then $𝑒 = 𝑡 - 𝑎$ is determined, and the second condition becomes

𝑏 𝑐 = 𝑎 (𝑡 - 𝑎) - 𝑑 = - (𝑎^{2} - 𝑡 𝑎 + 𝑑) = - 𝑓 (𝑎) .

The number of pairs $(𝑏, 𝑐)$ with $𝑏 𝑐 = 𝑚$ is $𝑞 - 1$ if $𝑚 \neq 0$ (any $𝑏 \neq 0$ , and then $𝑐 = 𝑚 / 𝑏$ ), and $2 𝑞 - 1$ if $𝑚 = 0$ ( $𝑏 = 0$ with $𝑐$ arbitrary, or $𝑏 \neq 0$ with $𝑐 = 0$ ). So if $𝑓$ has $𝑟$ roots in $𝔽_{𝑞}$ , the number of matrices is

𝑟 (2 𝑞 - 1) + (𝑞 - 𝑟) (𝑞 - 1) = 𝑞 (𝑞 - 1) + 𝑟 𝑞,

which is $𝑞^{2} + 𝑞$ , $𝑞^{2}$ , $𝑞^{2} - 𝑞$ for $𝑟 = 2, 1, 0$ .

(b) By Theorem 7.3.6, $𝐴$ has no eigenvalue exactly when $𝑝_{𝐴}$ has no root. There are $𝑞^{2}$ monic quadratics $𝑥^{2} - 𝑡 𝑥 + 𝑑$ . Those with two distinct roots are the products $(𝑥 - 𝛼) (𝑥 - 𝛽)$ with $𝛼 \neq 𝛽$ , and there are $(\binom{𝑞}{2}) = (𝑞^{2} - 𝑞) / 2$ of them; those with a repeated root are the ${(𝑥 - 𝛼)}^{2}$ , and there are $𝑞$ of them (a monic quadratic is determined by its roots, by Proposition 7.1.22 and the factor theorem). So $𝑞^{2} -$ $(𝑞^{2} - 𝑞) / 2 -$ $𝑞 =$ $(𝑞^{2} - 𝑞) / 2$ have no root. Each is realized by $𝑞^{2} - 𝑞$ matrices, which gives ${(𝑞^{2} - 𝑞)}^{2} / 2$ matrices without eigenvalues. The total is

\frac{𝑞^{2} - 𝑞}{2} (𝑞^{2} + 𝑞) + 𝑞 \cdot 𝑞^{2} + \frac{𝑞^{2} - 𝑞}{2} (𝑞^{2} - 𝑞) = \frac{𝑞^{2} - 𝑞}{2} \cdot 2 𝑞^{2} + 𝑞^{3} = 𝑞^{4} - 𝑞^{3} + 𝑞^{3} = 𝑞^{4},

as it should be. For $𝑞 = 2$ the two matrices without eigenvalues are $(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ and $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ .

Exercise 7.3.53.hardBeyond 21-242 For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and $𝑆 \subseteq {1, \dots, 𝑛}$ , let $𝐴_{𝑆}$ be the principal submatrix of $𝐴$ with rows and columns in $𝑆$ , and let $𝑒_{𝑘} (𝐴) =$ $\sum_{| 𝑆 | = 𝑘} det 𝐴_{𝑆}$ for $1 \leq 𝑘 \leq 𝑛$ , and $𝑒_{0} (𝐴) = 1$ . Show that

𝑝_{𝐴} = \sum_{𝑘 = 0}^{𝑛} {(- 1)}^{𝑘} 𝑒_{𝑘} (𝐴) 𝑥^{𝑛 - 𝑘},

and check that this agrees with Proposition 7.3.18. For $𝑛 = 3$ , write out the coefficient of $𝑥$ .

Solution.

Uses. Proposition 7.3.2 (Determinants over a commutative ring), Proposition 7.3.18 (The first and last coefficients)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Column

𝑗

𝑥 𝐼_{𝑛} - 𝐴

𝑥 𝐞_{𝑗} - 𝐚_{𝑗}

, a sum of two vectors. Expand

det

by multilinearity in all columns at once.

Hint 2. You get

2^{𝑛}

terms indexed by the set

𝑆

of columns where

- 𝐚_{𝑗}

was chosen. In the term for

𝑆

, the columns

𝑥 𝐞_{𝑗}

with

𝑗 \notin 𝑆

have a single nonzero entry. Expand along them.

Sketch. Multilinearity gives

𝑝_{𝐴} = \sum_{𝑆} det 𝑀_{𝑆}

, where column

𝑗

𝑀_{𝑆}

- 𝐚_{𝑗}

for

𝑗 \in 𝑆

and

𝑥 𝐞_{𝑗}

otherwise. Expanding along the columns

𝑥 𝐞_{𝑗}

𝑗 \notin 𝑆

, each contributes a factor

𝑥

and deletes row and column

𝑗

, leaving

- 𝐴_{𝑆}

. So

det 𝑀_{𝑆} =

𝑥^{𝑛 - | 𝑆 |} {(- 1)}^{| 𝑆 |} det 𝐴_{𝑆}

Column $𝑗$ of $𝑥 𝐼_{𝑛} - 𝐴$ is $𝑥 𝐞_{𝑗} - 𝐚_{𝑗}$ , where $𝐚_{𝑗}$ is column $𝑗$ of $𝐴$ . Expanding by linearity in each of the $𝑛$ columns (Proposition 7.3.2(b), Technique 5.1.7),

𝑝_{𝐴} = \sum_{𝑆 \subseteq {1, \dots, 𝑛}} det 𝑀_{𝑆},

where column $𝑗$ of $𝑀_{𝑆}$ is $- 𝐚_{𝑗}$ for $𝑗 \in 𝑆$ and $𝑥 𝐞_{𝑗}$ for $𝑗 \notin 𝑆$ .

We claim that $det 𝑀_{𝑆} =$ $𝑥^{𝑛 - | 𝑆 |} det (- 𝐴_{𝑆})$ (where $det (- 𝐴_{\emptyset}) = 1$ ), by induction on $𝑛 - | 𝑆 |$ . If $𝑆 = {1, \dots, 𝑛}$ , then $𝑀_{𝑆} = - 𝐴$ . If $𝑛 = 1$ and $𝑆 = \emptyset$ , then $𝑀_{𝑆} = (𝑥)$ and the claim holds. Otherwise $𝑛 \geq 2$ ; pick $𝑗 \notin 𝑆$ . Column $𝑗$ of $𝑀_{𝑆}$ is $𝑥 𝐞_{𝑗}$ , with the single nonzero entry $𝑥$ in position $(𝑗, 𝑗)$ , so cofactor expansion along it (Proposition 7.3.2(f)) gives $det 𝑀_{𝑆} =$ $𝑥 {(- 1)}^{𝑗 + 𝑗} det 𝑀^{'}$ , where $𝑀^{'}$ is $𝑀_{𝑆}$ with row $𝑗$ and column $𝑗$ deleted. In $𝑀^{'}$ , each remaining column $𝑥 𝐞_{𝑗^{'}}$ still has its single entry $𝑥$ on the diagonal, and each column $- 𝐚_{𝑗^{'}}$ has lost its $𝑗$ -th entry. So $𝑀^{'}$ is the matrix of the same form for the $(𝑛 - 1) \times (𝑛 - 1)$ matrix obtained from $𝐴$ by deleting row and column $𝑗$ , with the same set $𝑆$ , and the induction hypothesis applies. Since $det (- 𝐴_{𝑆}) =$ ${(- 1)}^{| 𝑆 |} det 𝐴_{𝑆}$ by multilinearity,

𝑝_{𝐴} = \sum_{𝑆} {(- 1)}^{| 𝑆 |} 𝑥^{𝑛 - | 𝑆 |} det 𝐴_{𝑆} = \sum_{𝑘 = 0}^{𝑛} {(- 1)}^{𝑘} 𝑒_{𝑘} (𝐴) 𝑥^{𝑛 - 𝑘} .

For $𝑘 = 1$ , the principal $1 \times 1$ minors are the diagonal entries, so $𝑒_{1} (𝐴) = tr 𝐴$ ; for $𝑘 = 𝑛$ , $𝑒_{𝑛} (𝐴) = det 𝐴$ . This matches Proposition 7.3.18. For $𝑛 = 3$ , the coefficient of $𝑥$ is

𝑒_{2} (𝐴) = (𝑎_{11} 𝑎_{22} - 𝑎_{12} 𝑎_{21}) + (𝑎_{11} 𝑎_{33} - 𝑎_{13} 𝑎_{31}) + (𝑎_{22} 𝑎_{33} - 𝑎_{23} 𝑎_{32}) .

Exercise 7.3.54.standardBeyond 21-242 Let $𝑉$ be a finite-dimensional real vector space, and let $𝑇 \in L (𝑉)$ have no eigenvalue.

(a)Show that every $𝑇$ -invariant subspace of $𝑉$ has even dimension.
(b)Give such a $𝑇$ on $ℝ^{4}$ , and find three different $𝑇$ -invariant planes.

Solution.

Uses. Proposition 7.3.30 (Odd dimension), Definition 7.2.1 (Invariant subspace), Proposition 7.3.15 (Block-triangular matrices), Proposition 7.2.4 (Invariance is checked on a spanning list)

Hint 1. If

𝑈

is invariant of odd dimension, then

𝑇 ↾_{𝑈}

is an operator on an odd-dimensional real space.

Hint 2. For (b), try two copies of the rotation

𝑅_{𝜋 / 2}

. Look for planes spanned by

𝐰

and

𝑇 𝐰

Sketch. (a) An invariant

𝑈

of odd dimension gives an eigenvector of

𝑇 ↾_{𝑈}

(Proposition 7.3.30), which is an eigenvector of

𝑇

. (b)

𝑇 = (\begin{matrix} 𝑅 & 0 \\ 0 & 𝑅 \end{matrix})

with

𝑅 = 𝑅_{𝜋 / 2}

has

𝑝_{𝑇} = {(𝑥^{2} + 1)}^{2}

; for any

𝐰 \neq 𝟎

span (𝐰, 𝑇 𝐰)

is invariant since

𝑇^{2} = - id

(a) Let $𝑈$ be $𝑇$ -invariant. If $dim 𝑈 = 0$ it is even. If $dim 𝑈$ is odd, then $𝑇 ↾_{𝑈} \in L (𝑈)$ has an eigenvalue by Proposition 7.3.30: there are $𝐮 \in 𝑈$ , $𝐮 \neq 𝟎$ , and $𝜆 \in ℝ$ with $𝑇 𝐮 = 𝜆 𝐮$ . Then $𝜆$ is an eigenvalue of $𝑇$ , a contradiction.

(b) Let $𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ and $𝑇 = (\begin{matrix} 𝑅 & 0 \\ 0 & 𝑅 \end{matrix})$ on $ℝ^{4}$ . By Proposition 7.3.15, $𝑝_{𝑇} = {(𝑥^{2} + 1)}^{2}$ , which has no real root, so $𝑇$ has no eigenvalue. Since $𝑅^{2} = - 𝐼_{2}$ , $𝑇^{2} = - 𝐼_{4}$ . So for every $𝐰 \neq 𝟎$ , $𝑇 (𝑇 𝐰) = - 𝐰$ , and $span (𝐰, 𝑇 𝐰)$ is $𝑇$ -invariant (Proposition 7.2.4); it is a plane by (a). Three different ones: $𝐰 = 𝐞_{1}$ gives $span (𝐞_{1}, 𝐞_{2})$ ; $𝐰 = 𝐞_{3}$ gives $span (𝐞_{3}, 𝐞_{4})$ ; and $𝐰 = 𝐞_{1} + 𝐞_{3}$ gives $span (𝐞_{1} + 𝐞_{3}, 𝐞_{2} + 𝐞_{4})$ , which contains neither $𝐞_{1}$ nor $𝐞_{3}$ .

Exercise 7.3.55.challenge Let $𝐴, 𝐵 \in ℂ^{𝑛 \times 𝑛}$ satisfy $𝐴 𝐵 - 𝐵 𝐴 = 𝐴$ .

(a)Show that $𝐴^{𝑘} 𝐵 -$ $𝐵 𝐴^{𝑘} =$ $𝑘 𝐴^{𝑘}$ for every $𝑘 \geq 1$ .
(b)Show that $𝐴^{𝑘} = 0$ for some $𝑘$ .
(c)Deduce that $𝑝_{𝐴} = 𝑥^{𝑛}$ .

Solution.

Uses. Corollary 7.2.22 (At most $dim 𝑉$ eigenvalues), Exercise 7.3.48, Definition 7.2.6 (Eigenvalue, eigenvector)

Techniques. Study a linear map on a space of matrices (Technique 4.2.29)

Hint 1. For (a), induct on

𝑘

: write

𝐴^{𝑘 + 1} 𝐵 -

𝐵 𝐴^{𝑘 + 1} =

𝐴 (𝐴^{𝑘} 𝐵 - 𝐵 𝐴^{𝑘}) +

(𝐴 𝐵 - 𝐵 𝐴) 𝐴^{𝑘}

Hint 2. For (b), consider the linear map

𝐿 (𝑋) = 𝑋 𝐵 - 𝐵 𝑋

ℂ^{𝑛 \times 𝑛}

. What does (a) say about

𝐿 (𝐴^{𝑘})

Hint 3. An operator on an

𝑛^{2}

-dimensional space has at most

𝑛^{2}

eigenvalues, but

1, 2, 3, \dots

are infinitely many.

Sketch. (a)

𝐴^{𝑘 + 1} 𝐵 -

𝐵 𝐴^{𝑘 + 1} =

𝐴 (𝐴^{𝑘} 𝐵 - 𝐵 𝐴^{𝑘}) +

(𝐴 𝐵 - 𝐵 𝐴) 𝐴^{𝑘} =

𝑘 𝐴^{𝑘 + 1} +

𝐴^{𝑘 + 1}

. (b) With

𝐿 (𝑋) = 𝑋 𝐵 - 𝐵 𝑋

𝐿 (𝐴^{𝑘}) = 𝑘 𝐴^{𝑘}

, so if

𝐴^{𝑘} \neq 0

then

𝑘

is an eigenvalue of

𝐿

𝐿

has at most

𝑛^{2}

eigenvalues, so

𝐴^{𝑘} = 0

for some

𝑘 \leq 𝑛^{2} + 1

. (c) Exercise 7.3.48.

(a) For $𝑘 = 1$ this is the hypothesis. If it holds for $𝑘$ , then

𝐴^{𝑘 + 1} 𝐵 - 𝐵 𝐴^{𝑘 + 1} = 𝐴 (𝐴^{𝑘} 𝐵 - 𝐵 𝐴^{𝑘}) + (𝐴 𝐵 - 𝐵 𝐴) 𝐴^{𝑘} = 𝐴 (𝑘 𝐴^{𝑘}) + 𝐴 \cdot 𝐴^{𝑘} = (𝑘 + 1) 𝐴^{𝑘 + 1},

where the first equality holds because the terms $- 𝐴 𝐵 𝐴^{𝑘}$ and $+ 𝐴 𝐵 𝐴^{𝑘}$ cancel.

(b) Let $𝐿 : ℂ^{𝑛 \times 𝑛} \to ℂ^{𝑛 \times 𝑛}$ , $𝐿 (𝑋) = 𝑋 𝐵 - 𝐵 𝑋$ . It is linear, and (a) says $𝐿 (𝐴^{𝑘}) = 𝑘 𝐴^{𝑘}$ . If $𝐴^{𝑘} \neq 0$ , then $𝑘$ is an eigenvalue of $𝐿$ (Definition 7.2.6). By Corollary 7.2.22, $𝐿$ has at most $𝑛^{2}$ eigenvalues, and $1, 2, \dots, 𝑛^{2} + 1$ are $𝑛^{2} + 1$ distinct complex numbers. So $𝐴^{𝑘} = 0$ for some $𝑘 \leq 𝑛^{2} + 1$ .

(c) By (b) and Exercise 7.3.48, $𝑝_{𝐴} = 𝑥^{𝑛}$ . The proof used that the integers $1, 2, 3, \dots$ are distinct in $ℂ$ ; over $𝔽_{𝑝}$ the scalars $𝑘$ repeat, and (b) breaks down.

More practice

The practice bank has 25 exercises on this section’s topics.