7.5 Upper-triangular form and Schur's theorem

Not every operator can be diagonalized, even over $ℂ$ . The shift $𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ has the single eigenvalue $0$ and $ker 𝑁 = span (𝐞_{1})$ , so $ℂ^{2}$ has no basis of eigenvectors of $𝑁$ (Section 7.4). But $𝑁$ is already upper triangular, and an upper-triangular matrix shows most of what a diagonal one does: its eigenvalues, its determinant, and its trace can all be read off the diagonal. This section shows that over $ℂ$ every operator has an upper-triangular matrix (Theorem 7.5.13), and that on an inner product space the basis can be taken orthonormal (Schur’s theorem, Theorem 7.5.18). The cost of settling for triangular is the entries above the diagonal; in exchange, the result holds for every operator.

Throughout, $𝑉$ is a finite-dimensional vector space over a field $𝐹$ with $dim 𝑉 = 𝑛 \geq 1$ , and $𝑇 \in L (𝑉)$ . We abbreviate ${[𝑇]}_{ℬ︀ ℬ︀}$ to ${[𝑇]}_{ℬ︀}$ .

7.5.1Upper-triangular matrices and invariant flags

Recall (Definition 3.3.31) that $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is upper triangular if $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ . For the matrix of an operator this condition has a clean meaning. Column $𝑗$ of ${[𝑇]}_{ℬ︀}$ holds the coordinates of $𝑇 𝐛_{𝑗}$ , so the zeros below the diagonal in column $𝑗$ say exactly that $𝑇 𝐛_{𝑗}$ is a combination of $𝐛_{1}, \dots, 𝐛_{𝑗}$ alone: each basis vector is sent into the span of itself and the vectors before it.

Definition 7.5.1 (Triangularizable). Let

ℬ︀

be a basis of

𝑉

. The operator

𝑇

is upper triangular with respect to $ℬ︀$ if

{[𝑇]}_{ℬ︀}

is upper triangular, and

𝑇

is triangularizable if it is upper triangular with respect to some basis of

𝑉

. A matrix

𝐴 \in 𝐹^{𝑛 \times 𝑛}

is triangularizable if it is similar to an upper-triangular matrix, that is (Theorem 4.5.25), if

𝑇_{𝐴}

is triangularizable.

Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces). Let $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ be a basis of $𝑉$ , and let $𝑉_{𝑗} =$ $span (𝐛_{1}, \dots, 𝐛_{𝑗})$ for $0 \leq 𝑗 \leq 𝑛$ , so that $𝑉_{0} = {𝟎}$ . The following are equivalent.

(I) ${[𝑇]}_{ℬ︀}$ is upper triangular.
(II) $𝑇 𝐛_{𝑗} \in 𝑉_{𝑗}$ for each $𝑗 = 1, \dots, 𝑛$ .
(III) $𝑉_{𝑗}$ is $𝑇$ -invariant for each $𝑗 = 1, \dots, 𝑛$ .

Proof.routine

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 1.6.14 (Coordinates), Proposition 7.2.4 (Invariance is checked on a spanning list), Definition 7.2.1 (Invariant subspace)

Techniques. Proving TFAE (Technique 2.7.1), Check it on a basis (Technique 2.2.7)

Hint 1. Column

𝑗

{[𝑇]}_{ℬ︀}

{[𝑇 𝐛_{𝑗}]}_{ℬ︀}

. When does a vector lie in

𝑉_{𝑗}

, in terms of its coordinates?

Hint 2. For (II)

\Rightarrow

(III),

𝑉_{𝑗}

is spanned by

𝐛_{1}, \dots, 𝐛_{𝑗}

, and

𝑇 𝐛_{𝑖} \in 𝑉_{𝑖} \subseteq 𝑉_{𝑗}

for

𝑖 \leq 𝑗

. Use Proposition 7.2.4.

Sketch. A vector lies in

𝑉_{𝑗}

exactly when its coordinates after position

𝑗

vanish, so (I)

\Leftrightarrow

(II) column by column. Since

𝑉_{𝑖} \subseteq 𝑉_{𝑗}

for

𝑖 \leq 𝑗

, (II) gives

𝑇 𝐛_{𝑖} \in 𝑉_{𝑗}

for all

𝑖 \leq 𝑗

, and invariance follows from Proposition 7.2.4. Conversely,

𝐛_{𝑗} \in 𝑉_{𝑗}

, so invariance of

𝑉_{𝑗}

gives (II).

We prove (I) $\Leftrightarrow$ (II) and (II) $\Leftrightarrow$ (III).

(I) $\Leftrightarrow$ (II). A vector of $𝑉$ lies in $𝑉_{𝑗}$ if and only if its $ℬ︀$ -coordinates in positions $𝑗 + 1, \dots, 𝑛$ are $0$ , by uniqueness of coordinates (Definition 1.6.14). Column $𝑗$ of ${[𝑇]}_{ℬ︀}$ is ${[𝑇 𝐛_{𝑗}]}_{ℬ︀}$ (Definition 2.3.1), so $𝑇 𝐛_{𝑗} \in 𝑉_{𝑗}$ if and only if column $𝑗$ has zeros in rows $𝑗 + 1, \dots, 𝑛$ . These conditions for $𝑗 = 1, \dots, 𝑛$ together say that $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ .

(II) $\Rightarrow$ (III). Fix $𝑗$ . For $𝑖 \leq 𝑗$ we have $𝑇 𝐛_{𝑖} \in 𝑉_{𝑖} \subseteq 𝑉_{𝑗}$ . So $𝑇$ maps each vector of the spanning list $𝐛_{1}, \dots, 𝐛_{𝑗}$ of $𝑉_{𝑗}$ into $𝑉_{𝑗}$ , and $𝑉_{𝑗}$ is $𝑇$ -invariant by Proposition 7.2.4.

(III) $\Rightarrow$ (II). $𝐛_{𝑗} \in 𝑉_{𝑗}$ , and $𝑉_{𝑗}$ is $𝑇$ -invariant, so $𝑇 𝐛_{𝑗} \in 𝑉_{𝑗}$ . □

The subspaces $𝑉_{0} ⊊ 𝑉_{1} ⊊ \dots ⊊ 𝑉_{𝑛}$ in the proposition are nested and grow by one dimension at a time. Such chains deserve a name.

Definition 7.5.3 (Flag). A flag in

𝑉

is a list of subspaces

𝑉_{0} \subseteq 𝑉_{1} \subseteq \dots \subseteq 𝑉_{𝑛}

with

dim 𝑉_{𝑗} = 𝑗

for each

𝑗

(so

𝑉_{0} = {𝟎}

and

𝑉_{𝑛} = 𝑉

). The flag of a basis

𝐛_{1}, \dots, 𝐛_{𝑛}

is given by

𝑉_{𝑗} =

span (𝐛_{1}, \dots, 𝐛_{𝑗})

. A flag is $𝑇$ -invariant if every

𝑉_{𝑗}

𝑇

-invariant.

Every flag is the flag of some basis: choose $𝐛_{𝑗} \in 𝑉_{𝑗}$ with $𝐛_{𝑗} \notin 𝑉_{𝑗 - 1}$ for each $𝑗$ . By induction on $𝑗$ , the list $𝐛_{1}, \dots, 𝐛_{𝑗}$ is linearly independent (Proposition 1.5.14) and lies in $𝑉_{𝑗}$ , so it is a basis of $𝑉_{𝑗}$ (Theorem 4.1.10). In $ℝ^{3}$ , a flag is a line through $𝟎$ lying in a plane through $𝟎$ . So Proposition 7.5.2 says that $𝑇$ is triangularizable if and only if $𝑉$ has a $𝑇$ -invariant flag, and that then every basis of that flag triangularizes $𝑇$ . Only the flag matters, not the particular vectors. In particular, the first vector $𝐛_{1}$ of a triangularizing basis spans an invariant line, so it is an eigenvector of $𝑇$ , with eigenvalue the $(1, 1)$ entry (Proposition 7.2.7). A triangularizable operator has at least one eigenvalue.

Technique 7.5.4 (Build a flag of invariant subspaces). To find a basis in which $𝑇$ is upper triangular, look for nested invariant subspaces of every dimension instead of for matrix entries (Proposition 7.5.2). The flag can be built from the bottom (first an eigenvector, then a vector sent into the span of it and itself, and so on) or from the top (a large invariant subspace, then invariant subspaces inside it). Any basis adapted to the flag will do, so the vectors can afterwards be changed freely within the flag, for instance orthonormalized.

Reach for it whenever a statement is about triangular matrices of an operator, both to produce them and to use them: “ ${[𝑇]}_{ℬ︀}$ is upper triangular” is the statement “ $𝑇$ maps $span (𝐛_{1}, \dots, 𝐛_{𝑗})$ into itself for every $𝑗$ ”, which survives any operation that preserves these spans. The canonical example is the second proof of Theorem 7.5.13. Later uses: Schur’s theorem (Theorem 7.5.18), where Gram–Schmidt keeps the flag, and simultaneous triangularization of commuting operators (Section 7.6).

Used in 7 places

Theorem 7.5.13, Theorem 7.5.18, Exercise 7.5.30, Exercise 7.5.34, Lemma 7.6.21, Theorem 7.6.32, Theorem 8.2.12.

Example 7.5.5 (Differentiation and shifts).

(a)Let $𝐷 \in L ({𝐹 [𝑥]}_{\leq 3})$ be differentiation, and use the basis $1, 𝑥, 𝑥^{2}, 𝑥^{3}$ . Differentiation lowers degrees, so $𝐷$ maps ${𝐹 [𝑥]}_{\leq 𝑘}$ into ${𝐹 [𝑥]}_{\leq 𝑘 - 1} \subseteq$ ${𝐹 [𝑥]}_{\leq 𝑘}$ . The flag ${𝐹 [𝑥]}_{\leq 0} \subseteq$ ${𝐹 [𝑥]}_{\leq 1} \subseteq$ ${𝐹 [𝑥]}_{\leq 2} \subseteq$ ${𝐹 [𝑥]}_{\leq 3}$ (plus ${𝟎}$ at the bottom) is $𝐷$ -invariant, and indeed
${[𝐷]}_{1, 𝑥, 𝑥^{2}, 𝑥^{3}} = (\begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 \end{matrix}) .$
(b)The shift $𝑁 \in L (𝐹^{𝑛})$ with $𝑁 𝐞_{1} = 𝟎$ and $𝑁 𝐞_{𝑗} = 𝐞_{𝑗 - 1}$ for $𝑗 \geq 2$ (Example 7.2.20) is upper triangular in the standard basis: the flag of coordinate subspaces $span (𝐞_{1}, \dots, 𝐞_{𝑗})$ is invariant.
(c)Every upper-triangular $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ preserves the coordinate subspaces $span (𝐞_{1}, \dots, 𝐞_{𝑗})$ , the vectors whose last $𝑛 - 𝑗$ coordinates vanish.

Non-example 7.5.6 (A rotation). Let

𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) \in ℝ^{2 \times 2}

, the rotation by a right angle. If

𝑇_{𝑅}

were upper triangular with respect to a basis

𝐛_{1}, 𝐛_{2}

ℝ^{2}

, then

𝐛_{1}

would be an eigenvector. But

𝑅

has no real eigenvalues (Example 7.2.18): it moves every line through

𝟎

. So

𝑅

is not triangularizable over

ℝ

. Over

ℂ

it is, and even diagonalizable:

𝑅 (1, - 𝑖) =

(𝑖, 1) =

𝑖 (1, - 𝑖)

and

𝑅 (1, 𝑖) =

- 𝑖 (1, 𝑖)

, and these two vectors form a basis of

ℂ^{2}

𝐴 = (\begin{matrix} 2 & 1 \\ 0 & 1 \end{matrix}), 𝐴 𝐞_{1} = 2 𝐞_{1}, 𝐴 𝐞_{2} = 𝐞_{1} + 𝐞_{2}

The upper-triangular matrix

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

. The

𝑥

-axis is invariant, since

𝐴 𝐞_{1} = 2 𝐞_{1}

, and

{𝟎} \subseteq span (𝐞_{1}) \subseteq ℝ^{2}

is an invariant flag. In the interactive version, drag

𝐴 𝐞_{1}

off the axis: the matrix is no longer upper triangular in the standard basis, but it is still triangularizable over

ℝ

as long as some line through

𝟎

is mapped into itself. A rotation by an angle that is not a multiple of

𝜋

leaves no line in place.

Exercise 7.5.7.routine Let

ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}

be a basis of

𝑉

and

{ℬ︀}^{'} = 𝐛_{𝑛}, \dots, 𝐛_{1}

the same basis in reverse order. Show that

{[𝑇]}_{ℬ︀}

is upper triangular if and only if

{[𝑇]}_{{ℬ︀}^{'}}

is lower triangular. Write down

{[𝐷]}_{{ℬ︀}^{'}}

for the differentiation operator of Example 7.5.5(a) and

{ℬ︀}^{'} = 𝑥^{3}, 𝑥^{2}, 𝑥, 1

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces)

Hint 1. The

(𝑖, 𝑗)

entry of

{[𝑇]}_{{ℬ︀}^{'}}

is the coefficient of

𝐛_{𝑛 + 1 - 𝑖}

𝑇 𝐛_{𝑛 + 1 - 𝑗}

. Relate it to an entry of

{[𝑇]}_{ℬ︀}

Hint 2. Reversing both the rows and the columns sends position

(𝑖, 𝑗)

(𝑛 + 1 - 𝑖, 𝑛 + 1 - 𝑗)

, and

𝑖 > 𝑗

if and only if

𝑛 +

1 -

𝑖 <

𝑛 +

1 -

𝑗

Sketch. The

(𝑖, 𝑗)

entry of

{[𝑇]}_{{ℬ︀}^{'}}

is the

(𝑛 + 1 - 𝑖, 𝑛 + 1 - 𝑗)

entry of

{[𝑇]}_{ℬ︀}

. Below-diagonal positions of one matrix correspond to above-diagonal positions of the other. For

𝐷

{[𝐷]}_{{ℬ︀}^{'}}

has

3, 2, 1

just below the diagonal.

Write $𝐛_{𝑗}^{'} = 𝐛_{𝑛 + 1 - 𝑗}$ . The $(𝑖, 𝑗)$ entry of ${[𝑇]}_{{ℬ︀}^{'}}$ is the coefficient of $𝐛_{𝑖}^{'} = 𝐛_{𝑛 + 1 - 𝑖}$ in $𝑇 𝐛_{𝑗}^{'} =$ $𝑇 𝐛_{𝑛 + 1 - 𝑗}$ (Definition 2.3.1), which is the $(𝑛 + 1 - 𝑖, 𝑛 + 1 - 𝑗)$ entry of ${[𝑇]}_{ℬ︀}$ . Now $𝑖 < 𝑗$ if and only if $𝑛 + 1 - 𝑖 > 𝑛 + 1 - 𝑗$ . So the entries of ${[𝑇]}_{{ℬ︀}^{'}}$ above the diagonal are exactly the entries of ${[𝑇]}_{ℬ︀}$ below the diagonal, and one set vanishes if and only if the other does.

For $𝐷$ , $𝐷 (𝑥^{3}) = 3 𝑥^{2}$ , $𝐷 (𝑥^{2}) = 2 𝑥$ , $𝐷 (𝑥) = 1$ , and $𝐷 (1) = 𝟎$ , so

{[𝐷]}_{𝑥^{3}, 𝑥^{2}, 𝑥, 1} = (\begin{matrix} 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}) .

This is ${[𝐷]}_{1, 𝑥, 𝑥^{2}, 𝑥^{3}}$ with the order of the rows and of the columns reversed.

Reading the diagonal

The diagonal of a triangular matrix carries the eigenvalues. We give two proofs: one computes a determinant, the other sees where a zero on the diagonal loses a dimension.

Proposition 7.5.8 (The diagonal of a triangular matrix). Suppose ${[𝑇]}_{ℬ︀}$ is upper triangular with diagonal entries $𝜆_{1}, \dots, 𝜆_{𝑛}$ .

(a) $𝑇$ is invertible if and only if $𝜆_{𝑗} \neq 0$ for every $𝑗$ .
(b)The eigenvalues of $𝑇$ are exactly $𝜆_{1}, \dots, 𝜆_{𝑛}$ .

Proof (via determinants).routine

Uses. Definition 5.4.18 (Determinant of an operator), Proposition 5.3.15 (Triangular matrices), Proposition 5.4.20 (Properties of the determinant of an operator), Theorem 7.2.9 (Eigenvalues and invertibility), Proposition 2.4.12 (Matrices of sums and scalar multiples)

Hint 1. What is

det 𝑇

, computed from

{[𝑇]}_{ℬ︀}

Hint 2. For (b),

{[𝑇 - 𝜆 {id}_{𝑉}]}_{ℬ︀} =

{[𝑇]}_{ℬ︀} -

𝜆 𝐼_{𝑛}

is again upper triangular. Apply (a) to

𝑇 - 𝜆 {id}_{𝑉}

Sketch.

det 𝑇 =

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

𝜆_{1} \dots 𝜆_{𝑛}

, which is nonzero exactly when every

𝜆_{𝑗}

is. For (b),

𝑇 - 𝜆 {id}_{𝑉}

has the upper-triangular matrix

{[𝑇]}_{ℬ︀} - 𝜆 𝐼_{𝑛}

with diagonal

𝜆_{𝑗} - 𝜆

, and

𝜆

is an eigenvalue exactly when

𝑇 - 𝜆 {id}_{𝑉}

is not invertible.

(a) By Definition 5.4.18 and Proposition 5.3.15, $det 𝑇 =$ $det {[𝑇]}_{ℬ︀} =$ $𝜆_{1} 𝜆_{2} \dots 𝜆_{𝑛}$ . By Proposition 5.4.20(c), $𝑇$ is invertible if and only if this product is nonzero, that is, if and only if every $𝜆_{𝑗}$ is nonzero.

(b) Let $𝜆 \in 𝐹$ . By Proposition 2.4.12, ${[𝑇 - 𝜆 {id}_{𝑉}]}_{ℬ︀} =$ ${[𝑇]}_{ℬ︀} -$ $𝜆 𝐼_{𝑛}$ , which is upper triangular with diagonal entries $𝜆_{1} - 𝜆, \dots, 𝜆_{𝑛} - 𝜆$ . By Theorem 7.2.9, $𝜆$ is an eigenvalue of $𝑇$ if and only if $𝑇 - 𝜆 {id}_{𝑉}$ is not invertible, which by (a) happens if and only if $𝜆_{𝑗} - 𝜆 = 0$ for some $𝑗$ . □

Intuition (Where the dimension goes). Suppose

𝜆_{𝑗} = 0

. Then

𝑇 𝐛_{𝑗}

has no

𝐛_{𝑗}

-component, so

𝑇

maps

𝑉_{𝑗} =

span (𝐛_{1}, \dots, 𝐛_{𝑗})

into the smaller space

𝑉_{𝑗 - 1}

. A map from a

𝑗

-dimensional space into a

(𝑗 - 1)

-dimensional one cannot be injective. Conversely, if every

𝜆_{𝑗} \neq 0

, we can solve for

𝐛_{𝑗}

𝑇 𝐛_{𝑗} =

𝜆_{𝑗} 𝐛_{𝑗} +

(\dots)

and see, one index at a time, that every basis vector lies in the image. This argument uses no determinants, and it is the version that survives where determinants are unavailable.

Proof (without determinants).standard

Uses. Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Theorem 4.2.11 (Rank–nullity), Corollary 4.2.18 (Injective if and only if surjective), Theorem 7.2.9 (Eigenvalues and invertibility), Proposition 2.4.12 (Matrices of sums and scalar multiples)

Techniques. Dimension counting (Technique 4.2.24), Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Let

𝑉_{𝑗} =

span (𝐛_{1}, \dots, 𝐛_{𝑗})

. If

𝜆_{𝑗} = 0

, where does

𝑇

send

𝑉_{𝑗}

Hint 2. If

𝜆_{𝑗} = 0

, then

𝑇

maps the

𝑗

-dimensional

𝑉_{𝑗}

into

𝑉_{𝑗 - 1}

, so

𝑇 ↾_{𝑉_{𝑗}}

has a nonzero kernel by rank–nullity.

Hint 3. If all

𝜆_{𝑗} \neq 0

, show

𝐛_{𝑗} \in im 𝑇

by strong induction on

𝑗

, solving

𝑇 𝐛_{𝑗} =

𝜆_{𝑗} 𝐛_{𝑗} +

\sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐛_{𝑖}

for

𝐛_{𝑗}

Sketch. If

𝜆_{𝑗} = 0

, then

𝑇 𝐛_{𝑖} \in

𝑉_{𝑖} \subseteq

𝑉_{𝑗 - 1}

for

𝑖 < 𝑗

and

𝑇 𝐛_{𝑗} =

\sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐛_{𝑖} \in

𝑉_{𝑗 - 1}

, so

𝑇 ↾_{𝑉_{𝑗}} : 𝑉_{𝑗} \to

𝑉_{𝑗 - 1}

is not injective. If all

𝜆_{𝑗} \neq 0

, then

𝐛_{𝑗} =

𝜆_{𝑗}^{- 1} (𝑇 𝐛_{𝑗} - \sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐛_{𝑖}) \in

im 𝑇

by induction, so

𝑇

is surjective, hence invertible. (b) follows from (a) applied to

𝑇 - 𝜆 {id}_{𝑉}

Write ${[𝑇]}_{ℬ︀} = (𝑎_{𝑖 𝑗})$ , so $𝑎_{𝑗 𝑗} = 𝜆_{𝑗}$ , and $𝑉_{𝑗} =$ $span (𝐛_{1}, \dots, 𝐛_{𝑗})$ . By Proposition 7.5.2, $𝑇 𝐛_{𝑗} =$ $𝜆_{𝑗} 𝐛_{𝑗} +$ $\sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐛_{𝑖}$ for each $𝑗$ .

(a) Suppose $𝜆_{𝑗} = 0$ for some $𝑗$ . For $𝑖 < 𝑗$ , $𝑇 𝐛_{𝑖} \in$ $𝑉_{𝑖} \subseteq$ $𝑉_{𝑗 - 1}$ , and $𝑇 𝐛_{𝑗} =$ $\sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐛_{𝑖} \in$ $𝑉_{𝑗 - 1}$ . So $𝑇$ maps the spanning list $𝐛_{1}, \dots, 𝐛_{𝑗}$ of $𝑉_{𝑗}$ into the subspace $𝑉_{𝑗 - 1}$ , and $im (𝑇 ↾_{𝑉_{𝑗}}) \subseteq$ $𝑉_{𝑗 - 1}$ . By rank–nullity (Theorem 4.2.11) applied to $𝑇 ↾_{𝑉_{𝑗}} : 𝑉_{𝑗} \to 𝑉$ ,

dim ker (𝑇 ↾_{𝑉_{𝑗}}) = 𝑗 - dim im (𝑇 ↾_{𝑉_{𝑗}}) \geq 𝑗 - (𝑗 - 1) = 1 .

So some nonzero vector of $𝑉_{𝑗}$ is sent to $𝟎$ , and $𝑇$ is not invertible.

Conversely, suppose every $𝜆_{𝑗} \neq 0$ . We show $𝐛_{𝑗} \in im 𝑇$ by strong induction on $𝑗$ . Assume $𝐛_{𝑖} \in im 𝑇$ for all $𝑖 < 𝑗$ (for $𝑗 = 1$ there is nothing to assume). Then

𝐛_{𝑗} = 𝜆_{𝑗}^{- 1} (𝑇 𝐛_{𝑗} - \sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} 𝐛_{𝑖})

is a linear combination of $𝑇 𝐛_{𝑗}$ and the $𝐛_{𝑖}$ with $𝑖 < 𝑗$ , all of which lie in the subspace $im 𝑇$ . So $𝐛_{𝑗} \in im 𝑇$ . Hence $im 𝑇$ contains a basis of $𝑉$ , and $𝑇$ is surjective, so it is invertible by Corollary 4.2.18.

(b) As in the first proof, ${[𝑇 - 𝜆 {id}_{𝑉}]}_{ℬ︀}$ is upper triangular with diagonal entries $𝜆_{𝑗} - 𝜆$ , and $𝜆$ is an eigenvalue if and only if $𝑇 - 𝜆 {id}_{𝑉}$ is not invertible (Theorem 7.2.9), that is, by (a), if and only if $𝜆 = 𝜆_{𝑗}$ for some $𝑗$ . □

The diagonal also records how often each eigenvalue occurs. Write $𝑝_{𝑇}$ for the characteristic polynomial of $𝑇$ (Definition 7.3.4), so that $𝑝_{𝑇} =$ $det (𝑥 𝐼_{𝑛} - 𝐴)$ for every matrix $𝐴$ of $𝑇$ . Here the determinant of a matrix with entries in $𝐹 [𝑥]$ is defined by the Leibniz formula, and Section 7.3 shows that the results of Chapter 5 proved by expanding that formula, such as Proposition 5.3.15 and Theorem 5.4.26, hold for such matrices.

Proposition 7.5.9 (Multiplicities on the diagonal). Suppose ${[𝑇]}_{ℬ︀}$ is upper triangular with diagonal entries $𝜆_{1}, \dots, 𝜆_{𝑛}$ . Then

𝑝_{𝑇} = (𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛}) .

Consequently each eigenvalue $𝜆$ of $𝑇$ occurs among $𝜆_{1}, \dots, 𝜆_{𝑛}$ exactly as many times as its algebraic multiplicity (Definition 7.4.11). In particular, this number is the same for every basis in which $𝑇$ is upper triangular.

Proof.routine

Uses. Definition 7.3.4 (Characteristic polynomial), Proposition 5.3.15 (Triangular matrices), Proposition 7.1.34 (Roots of a split polynomial), Definition 7.4.11 (Algebraic multiplicity)

Hint 1.

𝑥 𝐼_{𝑛} - {[𝑇]}_{ℬ︀}

is upper triangular. What is its determinant?

Hint 2. The algebraic multiplicity of

𝜆

is its multiplicity as a root of

𝑝_{𝑇}

. Use Proposition 7.1.34.

Sketch.

𝑥 𝐼_{𝑛} - {[𝑇]}_{ℬ︀}

is upper triangular with diagonal entries

𝑥 - 𝜆_{𝑗}

, so its determinant is their product. A root of a split polynomial occurs in its list of linear factors exactly as often as its multiplicity.

The matrix

𝑥 𝐼_{𝑛} - {[𝑇]}_{ℬ︀}

has entries in

𝐹 [𝑥]

; it is upper triangular, with diagonal entries

𝑥 - 𝜆_{1}, \dots, 𝑥 - 𝜆_{𝑛}

. By Proposition 5.3.15 (whose proof only uses the Leibniz formula),

𝑝_{𝑇} =

det (𝑥 𝐼_{𝑛} - {[𝑇]}_{ℬ︀}) =

(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})

. By Proposition 7.1.34, each root of

𝑝_{𝑇}

occurs in the list

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

exactly as many times as its multiplicity as a root of

𝑝_{𝑇}

, which is its algebraic multiplicity as an eigenvalue (Definition 7.4.11). The polynomial

𝑝_{𝑇}

does not depend on the basis, so neither do these counts. □

When $𝑝_{𝑇}$ splits over $𝐹$ , say $𝑝_{𝑇} =$ $(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ (Definition 7.1.33), we call $𝜆_{1}, \dots, 𝜆_{𝑛}$ the eigenvalues of $𝑇$ counted with multiplicity. Each eigenvalue occurs in this list as often as its algebraic multiplicity, and the list is determined by $𝑇$ up to order (Proposition 7.1.34). Over $ℂ$ , $𝑝_{𝑇}$ always splits (Corollary 7.1.35).

Exercise 7.5.10.routine Let $𝐛_{1}, 𝐛_{2}, 𝐛_{3}$ be a basis of a complex vector space $𝑉$ , and let $𝑇 \in L (𝑉)$ satisfy

𝑇 𝐛_{1} = 3 𝐛_{1}, 𝑇 𝐛_{2} = 𝐛_{1} - 𝐛_{2}, 𝑇 𝐛_{3} = 𝐛_{1} + 𝐛_{2} + 3 𝐛_{3} .

Find the eigenvalues of $𝑇$ with their algebraic multiplicities, decide whether $𝑇$ is invertible, and find an eigenvector for each eigenvalue. Is $𝑇$ diagonalizable?

Solution.

Uses. Proposition 7.5.8 (The diagonal of a triangular matrix), Proposition 7.5.9 (Multiplicities on the diagonal), Theorem 7.4.2 (Diagonalizable means an eigenbasis)

Hint 1. Each

𝑇 𝐛_{𝑗}

lies in

span (𝐛_{1}, \dots, 𝐛_{𝑗})

, so

{[𝑇]}_{ℬ︀}

is upper triangular. Read off the diagonal.

Hint 2. For the eigenvectors, solve

(𝑇 - 𝜆 id) (𝑥 𝐛_{1} + 𝑦 𝐛_{2} + 𝑧 𝐛_{3}) =

𝟎

coefficient by coefficient.

Sketch. The diagonal is

3, - 1, 3

, so the eigenvalues are

3

(multiplicity

2

) and

- 1

(multiplicity

1

), and

𝑇

is invertible.

𝐸_{3} = span (𝐛_{1})

and

𝐸_{- 1} =

span (𝐛_{1} - 4 𝐛_{2})

. Only two independent eigenvectors exist, so

𝑇

is not diagonalizable.

The matrix

{[𝑇]}_{ℬ︀} = (\begin{matrix} 3 & 1 & 1 \\ 0 & - 1 & 1 \\ 0 & 0 & 3 \end{matrix})

is upper triangular. By Proposition 7.5.8 and Proposition 7.5.9, the eigenvalues are $3$ , with algebraic multiplicity $2$ , and $- 1$ , with algebraic multiplicity $1$ . No diagonal entry is $0$ , so $𝑇$ is invertible.

For $𝜆 = 3$ : $(𝑇 - 3 id) (𝑥 𝐛_{1} + 𝑦 𝐛_{2} + 𝑧 𝐛_{3}) =$ $𝑦 (𝐛_{1} - 4 𝐛_{2}) +$ $𝑧 (𝐛_{1} + 𝐛_{2}) =$ $(𝑦 + 𝑧) 𝐛_{1} +$ $(𝑧 - 4 𝑦) 𝐛_{2}$ . This vanishes if and only if $𝑦 + 𝑧 = 0$ and $𝑧 = 4 𝑦$ , that is, $𝑦 = 𝑧 = 0$ . So $𝐸_{3} = span (𝐛_{1})$ .

For $𝜆 = - 1$ : $(𝑇 + id) (𝑥 𝐛_{1} + 𝑦 𝐛_{2} + 𝑧 𝐛_{3}) =$ $(4 𝑥 + 𝑦 + 𝑧) 𝐛_{1} +$ $𝑧 𝐛_{2} +$ $4 𝑧 𝐛_{3}$ , which vanishes if and only if $𝑧 = 0$ and $𝑦 = - 4 𝑥$ . So $𝐸_{- 1} =$ $span (𝐛_{1} - 4 𝐛_{2})$ . Check: $𝑇 (𝐛_{1} - 4 𝐛_{2}) =$ $3 𝐛_{1} -$ $4 𝐛_{1} +$ $4 𝐛_{2} =$ $- (𝐛_{1} - 4 𝐛_{2})$ .

Every eigenvector lies in $𝐸_{3} \cup 𝐸_{- 1}$ , a union of two lines, so there is no basis of eigenvectors, and $𝑇$ is not diagonalizable (Theorem 7.4.2).

7.5.2Triangularization over $ℂ$

Intuition (How to find an invariant flag). By Proposition 7.5.2 we need an invariant flag, and its bottom $𝑉_{1}$ is an invariant line, spanned by an eigenvector. So we need an eigenvalue, and over $ℂ$ there always is one (Theorem 7.3.27). Over $ℝ$ the rotation of Non-example 7.5.6 shows that the theorem can fail at this very first step.

Having found an eigenvector $𝐛_{1}$ , we would like to finish by induction on $dim 𝑉$ . The obvious move is to restrict $𝑇$ to a complement $𝑊$ of $span (𝐛_{1})$ and use the induction hypothesis there. It fails: $𝑇$ need not map $𝑊$ into $𝑊$ , so $𝑇 ↾_{𝑊}$ is a map $𝑊 \to 𝑉$ , not an operator on $𝑊$ , and the induction hypothesis says nothing about it. (Exercise A.2.13 makes exactly this mistake.) The fix is to throw away the part of $𝑇 𝐰$ that lies in $span (𝐛_{1})$ , by projecting $𝑇 𝐰$ back into $𝑊$ along $span (𝐛_{1})$ . That produces an honest operator on $𝑊$ . The part thrown away is harmless, because $span (𝐛_{1})$ sits at the bottom of the flag, and every $𝑉_{𝑗}$ will contain it anyway.

Lemma 7.5.11 (Compressing an operator to a complement). Let $𝑈$ be a $𝑇$ -invariant subspace of $𝑉$ , and let $𝑉 = 𝑈 \oplus 𝑊$ . The compression of $𝑇$ to $𝑊$ is the operator

𝑆 = {Pr}_{𝑊, 𝑈} \circ 𝑇 ↾_{𝑊} \in L (𝑊),

where ${Pr}_{𝑊, 𝑈}$ is the projection onto $𝑊$ along $𝑈$ (Definition 4.4.24).

(a) $𝑇 𝐰 - 𝑆 𝐰 \in 𝑈$ for every $𝐰 \in 𝑊$ .
(b)Let $𝒞︀$ be a basis of $𝑈$ and $𝒟︀$ a basis of $𝑊$ , both nonempty. Then $ℬ︀ = 𝒞︀, 𝒟︀$ is a basis of $𝑉$ , and
${[𝑇]}_{ℬ︀} = (\begin{matrix} {[𝑇 ↾_{𝑈}]}_{𝒞︀} & 𝑋 \\ 0 & {[𝑆]}_{𝒟︀} \end{matrix})$
for some matrix $𝑋$ , where $𝑇 ↾_{𝑈}$ is regarded as an operator on $𝑈$ .

Proof.routine

Uses. Definition 4.4.24 (Projection along a complement), Proposition 4.4.26 (Properties of projections), Theorem 4.4.13 (Bases and dimension of a sum), Proposition 4.5.35 (Preserved subspaces give block triangular matrices), Definition 2.3.1 (Matrix of a linear map)

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

Hint 1. For (a),

{Pr}_{𝑈, 𝑊} +

{Pr}_{𝑊, 𝑈} =

{id}_{𝑉}

. Apply both sides to

𝑇 𝐰

Hint 2. For (b), Proposition 4.5.35 gives the zero block and the top left block. For a column belonging to

𝐝_{𝑗} \in 𝒟︀

, write

𝑇 𝐝_{𝑗} =

(𝑇 𝐝_{𝑗} - 𝑆 𝐝_{𝑗}) +

𝑆 𝐝_{𝑗}

and read off the

𝒟︀

-coordinates.

Sketch.

𝑇 𝐰 =

{Pr}_{𝑈, 𝑊} (𝑇 𝐰) +

{Pr}_{𝑊, 𝑈} (𝑇 𝐰)

, and the first term lies in

𝑈

; this is (a). In (b),

ℬ︀

is a basis because the sum is direct, Proposition 4.5.35 gives the block form with

{[𝑇 ↾_{𝑈}]}_{𝒞︀}

in the corner, and by (a) the

𝒟︀

-coordinates of

𝑇 𝐝_{𝑗}

are those of

𝑆 𝐝_{𝑗}

, which form column

𝑗

{[𝑆]}_{𝒟︀}

(a) By Proposition 4.4.26, ${Pr}_{𝑈, 𝑊} +$ ${Pr}_{𝑊, 𝑈} =$ ${id}_{𝑉}$ and $im {Pr}_{𝑈, 𝑊} = 𝑈$ . So for $𝐰 \in 𝑊$ ,

𝑇 𝐰 - 𝑆 𝐰 = 𝑇 𝐰 - {Pr}_{𝑊, 𝑈} (𝑇 𝐰) = {Pr}_{𝑈, 𝑊} (𝑇 𝐰) \in 𝑈 .

(b) Since $𝑉 = 𝑈 \oplus 𝑊$ , the list $ℬ︀ = 𝒞︀, 𝒟︀$ is a basis of $𝑉$ (Theorem 4.4.13). Let $𝑘$ be the length of $𝒞︀$ . Since $𝑈 = span (𝒞︀)$ is $𝑇$ -invariant, Proposition 4.5.35 shows that ${[𝑇]}_{ℬ︀}$ has a zero block below the first $𝑘$ columns and that its top left block is ${[𝑇 ↾_{𝑈}]}_{𝒞︀}$ . Let $𝒟︀ = 𝐝_{1}, \dots, 𝐝_{𝑚}$ and ${[𝑆]}_{𝒟︀} = (𝑠_{𝑖 𝑗})$ , so $𝑆 𝐝_{𝑗} =$ $\sum_{𝑖} 𝑠_{𝑖 𝑗} 𝐝_{𝑖}$ (Definition 2.3.1). By (a), $𝑇 𝐝_{𝑗} =$ $𝐮 +$ $\sum_{𝑖} 𝑠_{𝑖 𝑗} 𝐝_{𝑖}$ for some $𝐮 \in 𝑈 = span (𝒞︀)$ . So the last $𝑚$ coordinates of $𝑇 𝐝_{𝑗}$ in $ℬ︀$ are $𝑠_{1 𝑗}, \dots, 𝑠_{𝑚 𝑗}$ , and the bottom right block of ${[𝑇]}_{ℬ︀}$ is ${[𝑆]}_{𝒟︀}$ . □

The compression depends on the choice of $𝑊$ , but its matrix is always the bottom right block of ${[𝑇]}_{ℬ︀}$ . This is the move the triangularization theorem needs, and it is an instance of a general technique.

Technique 7.5.12 (Induction on dimension via an invariant subspace). To prove that every operator on every finite-dimensional space (of some kind) has a property, induct on $dim 𝑉$ . In the inductive step, find a $𝑇$ -invariant subspace $𝑈$ with ${𝟎} \neq 𝑈 \neq 𝑉$ , apply the induction hypothesis to an operator on a smaller space built from $𝑈$ , and glue the pieces with the block triangular form of Proposition 4.5.35. The smaller operator can be

the restriction $𝑇 ↾_{𝑈}$ , an operator on $𝑈$ because $𝑈$ is invariant;
the compression of $𝑇$ to a complement $𝑊$ of $𝑈$ (Lemma 7.5.11), or to $𝑈^{⟂}$ when there is an inner product;
the quotient operator $𝑇 / 𝑈$ on $𝑉 / 𝑈$ (Proposition 4.6.32), if quotients are available.

The hypothesis applies only to operators, so whatever is passed down must map the smaller space into itself; a restriction to a subspace that is not invariant does not qualify (Exercise A.2.13). The invariant subspace usually comes from an eigenvector, which is why such inductions tend to need $ℂ$ , or from a kernel or image of a polynomial in $𝑇$ (Technique 7.2.31).

Reach for it for existence statements about bases adapted to an operator: triangular, block triangular, orthonormal and triangular, diagonal. The canonical example is Theorem 7.5.13. Later uses: Schur’s theorem (Theorem 7.5.18), the spectral theorems (Section 8.2), and the structure of nilpotent operators (Section 10.3).

Used in 16 places

Theorem 7.5.13, Theorem 7.5.17, Theorem 7.5.18, Theorem 7.5.27, Exercise 7.5.38, Exercise 7.5.42, Theorem 7.6.32, Exercise 7.7.13, Problem 7.14, Theorem 8.2.5, Theorem 8.2.12, Exercise 8.2.35, Exercise 8.2.48, Theorem 8.4.15, Theorem 8.4.25, Exercise 8.4.44.

Theorem 7.5.13 (Upper-triangular form). Let

𝑉

be a finite-dimensional complex vector space with

dim 𝑉 \geq 1

, and let

𝑇 \in L (𝑉)

. Then there is a basis

ℬ︀

𝑉

such that

{[𝑇]}_{ℬ︀}

is upper triangular. Its diagonal entries are the eigenvalues of

𝑇

, each occurring as many times as its algebraic multiplicity.

Proof (compress to a complement).standard

Uses. Theorem 7.3.27 (Existence of eigenvalues over $ℂ$ ), Proposition 7.2.7 (Invariant lines are spanned by eigenvectors), Proposition 4.4.16 (Complements exist), Lemma 7.5.11 (Compressing an operator to a complement), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Theorem 4.4.13 (Bases and dimension of a sum), Proposition 7.5.9 (Multiplicities on the diagonal)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12), Build a flag of invariant subspaces (Technique 7.5.4)

Hint 1. Induct on

𝑛 = dim 𝑉

. Over

ℂ

𝑇

has an eigenvector

𝐛_{1}

, and

span (𝐛_{1})

is invariant. It should be the bottom of the flag.

Hint 2. Choose a complement

𝑊

span (𝐛_{1})

. The restriction of

𝑇

𝑊

is not an operator on

𝑊

; what is?

Hint 3. Apply the induction hypothesis to the compression

𝑆

𝑇

𝑊

, getting

𝐛_{2}, \dots, 𝐛_{𝑛}

. Then use

𝑇 𝐰 -

𝑆 𝐰 \in

span (𝐛_{1})

to check that

𝑇 𝐛_{𝑗} \in

span (𝐛_{1}, \dots, 𝐛_{𝑗})

Sketch. Induct on

𝑛

;

𝑛 = 1

is trivial. Take an eigenvector

𝐛_{1}

(Theorem 7.3.27), a complement

𝑊

𝑈 = span (𝐛_{1})

, and the compression

𝑆 \in L (𝑊)

. By induction,

𝑊

has a basis

𝐛_{2}, \dots, 𝐛_{𝑛}

with

𝑆 𝐛_{𝑗} \in

span (𝐛_{2}, \dots, 𝐛_{𝑗})

. Then

𝑇 𝐛_{1} = 𝜆_{1} 𝐛_{1}

and

𝑇 𝐛_{𝑗} =

(𝑇 𝐛_{𝑗} - 𝑆 𝐛_{𝑗}) +

𝑆 𝐛_{𝑗} \in

span (𝐛_{1}, \dots, 𝐛_{𝑗})

, so

𝐛_{1}, \dots, 𝐛_{𝑛}

triangularizes

𝑇

. The diagonal is described by Proposition 7.5.9.

The statement about the diagonal is Proposition 7.5.9, so we prove existence, by induction on $𝑛 = dim 𝑉$ . If $𝑛 = 1$ , every $1 \times 1$ matrix is upper triangular, and any basis works.

Let $𝑛 \geq 2$ , and assume the theorem for complex vector spaces of dimension $𝑛 - 1$ . By Theorem 7.3.27, $𝑇$ has an eigenvalue $𝜆_{1}$ ; let $𝐛_{1}$ be an eigenvector for it. Then $𝑈 = span (𝐛_{1})$ is $𝑇$ -invariant (Proposition 7.2.7). By Proposition 4.4.16, $𝑈$ has a complement $𝑊$ , and $dim 𝑊 = 𝑛 - 1$ . Let $𝑆 \in L (𝑊)$ be the compression of $𝑇$ to $𝑊$ (Lemma 7.5.11). By the induction hypothesis and Proposition 7.5.2, $𝑊$ has a basis $𝐛_{2}, \dots, 𝐛_{𝑛}$ with

𝑆 𝐛_{𝑗} \in span (𝐛_{2}, \dots, 𝐛_{𝑗}) for 𝑗 = 2, \dots, 𝑛 .

The list $ℬ︀ = 𝐛_{1}, 𝐛_{2}, \dots, 𝐛_{𝑛}$ is a basis of $𝑉 = 𝑈 \oplus 𝑊$ (Theorem 4.4.13). We check condition (II) of Proposition 7.5.2. First, $𝑇 𝐛_{1} =$ $𝜆_{1} 𝐛_{1} \in$ $span (𝐛_{1})$ . For $𝑗 \geq 2$ , by Lemma 7.5.11(a),

𝑇 𝐛_{𝑗} = \underset{\in span (𝐛_{1})}{\underset{⏟}{(𝑇 𝐛_{𝑗} - 𝑆 𝐛_{𝑗})}} + \underset{\in span (𝐛_{2}, \dots, 𝐛_{𝑗})}{\underset{⏟}{𝑆 𝐛_{𝑗}}} \in span (𝐛_{1}, \dots, 𝐛_{𝑗}) .

So ${[𝑇]}_{ℬ︀}$ is upper triangular. In block form (Lemma 7.5.11(b)), ${[𝑇]}_{ℬ︀} =$ $(\begin{matrix} 𝜆_{1} & 𝑋 \\ 0 & {[𝑆]}_{𝐛_{2}, \dots, 𝐛_{𝑛}} \end{matrix})$ . □

Intuition (A second route, from the top). The first proof builds the flag from the bottom: an invariant line first, then whatever the smaller problem returns. The second proof (LADR’s) works from the top. Fix an eigenvalue

𝜆

, and consider

𝑈 = im (𝑇 - 𝜆 {id}_{𝑉})

. Since

𝑇 𝐯 =

𝜆 𝐯 +

(𝑇 - 𝜆 {id}_{𝑉}) 𝐯

, every subspace that contains

𝑈

𝑇

-invariant:

𝑇

moves each vector only within its own span plus

𝑈

. And

𝑈 \neq 𝑉

, because

𝑇 - 𝜆 {id}_{𝑉}

is not injective. So above

𝑈

the flag can be chosen arbitrarily, and the only real work happens inside

𝑈

, where the restriction of

𝑇

is an honest operator on a smaller space. This route needs no complement and no projection, only restriction.

Proof (via the invariant subspace $im (𝑇 - 𝜆 {id}_{𝑉})$ ).standard

Uses. Theorem 7.3.27 (Existence of eigenvalues over $ℂ$ ), Theorem 7.2.9 (Eigenvalues and invertibility), Corollary 4.2.18 (Injective if and only if surjective), Proposition 7.2.30 (Kernels and images of commuting operators are invariant), Theorem 4.1.16 (Extending to a basis), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12), Build a flag of invariant subspaces (Technique 7.5.4), Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Let

𝜆

be an eigenvalue and

𝑈 = im (𝑇 - 𝜆 {id}_{𝑉})

. Show that

𝑈

𝑇

-invariant and

dim 𝑈 < 𝑛

Hint 2. Apply the induction hypothesis to

𝑇 ↾_{𝑈}

(strong induction, since

dim 𝑈

can be anything below

𝑛

), and extend the resulting basis of

𝑈

to a basis of

𝑉

Hint 3. For an added vector

𝐯

, write

𝑇 𝐯 =

𝜆 𝐯 +

(𝑇 - 𝜆 {id}_{𝑉}) 𝐯

Sketch. By strong induction on

𝑛

. Let

𝜆

be an eigenvalue and

𝑈 = im (𝑇 - 𝜆 {id}_{𝑉})

; it is

𝑇

-invariant because

𝑇

commutes with

𝑇 - 𝜆 {id}_{𝑉}

, and

𝑈 \neq 𝑉

because

𝑇 - 𝜆 {id}_{𝑉}

is not injective, hence not surjective. Triangularize

𝑇 ↾_{𝑈}

𝐮_{1}, \dots, 𝐮_{𝑚}

and extend by

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

. Then

𝑇 𝐯_{𝑗} =

𝜆 𝐯_{𝑗} +

(𝑇 - 𝜆 {id}_{𝑉}) 𝐯_{𝑗} \in

span (𝐮_{1}, \dots, 𝐮_{𝑚}, 𝐯_{𝑗})

We use strong induction on $𝑛 = dim 𝑉$ . For $𝑛 = 1$ there is nothing to prove. Let $𝑛 \geq 2$ , and assume the theorem for all complex spaces of dimension less than $𝑛$ .

By Theorem 7.3.27, $𝑇$ has an eigenvalue $𝜆$ . Let $𝑈 = im (𝑇 - 𝜆 {id}_{𝑉})$ . Since $𝑇$ commutes with $𝑇 - 𝜆 {id}_{𝑉}$ , the image $𝑈$ is $𝑇$ -invariant (Proposition 7.2.30). Since $𝜆$ is an eigenvalue, $𝑇 - 𝜆 {id}_{𝑉}$ is not injective (Theorem 7.2.9), hence not surjective (Corollary 4.2.18), so $𝑚 = dim 𝑈 < 𝑛$ .

If $𝑚 = 0$ , then $𝑇 = 𝜆 {id}_{𝑉}$ , and every basis triangularizes $𝑇$ . Otherwise $𝑇 ↾_{𝑈}$ is an operator on $𝑈$ , and by the induction hypothesis and Proposition 7.5.2, $𝑈$ has a basis $𝐮_{1}, \dots, 𝐮_{𝑚}$ with $𝑇 𝐮_{𝑗} \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑗})$ for each $𝑗$ . Extend it to a basis $𝐮_{1},$ $\dots,$ $𝐮_{𝑚},$ $𝐯_{1},$ $\dots,$ $𝐯_{𝑘}$ of $𝑉$ (Theorem 4.1.16). For each $𝑗 \leq 𝑘$ ,

𝑇 𝐯_{𝑗} = 𝜆 𝐯_{𝑗} + \underset{\in 𝑈}{\underset{⏟}{(𝑇 - 𝜆 {id}_{𝑉}) 𝐯_{𝑗}}} \in span (𝐮_{1}, \dots, 𝐮_{𝑚}, 𝐯_{1}, \dots, 𝐯_{𝑗}) .

So every vector of the basis is sent into the span of itself and the vectors before it, and $𝑇$ is upper triangular with respect to this basis by Proposition 7.5.2. □

The two proofs pass different objects down the induction. The first passes a compression to a space of dimension exactly $𝑛 - 1$ , and so needs a complement and a projection; the second passes a restriction to a space of unknown smaller dimension, and so needs strong induction. The second proof also says something about the diagonal: the last $𝑘$ basis vectors have diagonal entry $𝜆$ , and $𝑘 =$ $𝑛 -$ $dim im (𝑇 - 𝜆 {id}_{𝑉}) =$ $dim ker (𝑇 - 𝜆 {id}_{𝑉})$ by rank–nullity. With Proposition 7.5.9, the algebraic multiplicity of $𝜆$ is at least $dim 𝐸_{𝜆}$ , its geometric multiplicity. So this argument recovers Theorem 7.4.15 for complex operators.

Corollary 7.5.14 (Triangularizing a matrix). Every

𝐴 \in ℂ^{𝑛 \times 𝑛}

is similar to an upper-triangular matrix:

𝐴 = 𝑆 𝑅 𝑆^{- 1}

with

𝑆 \in ℂ^{𝑛 \times 𝑛}

invertible and

𝑅

upper triangular. The columns of

𝑆

form a basis of

ℂ^{𝑛}

whose flag is

𝑇_{𝐴}

-invariant, and the diagonal of

𝑅

lists the eigenvalues of

𝐴

counted with multiplicity.

Proof.routine

Uses. Theorem 7.5.13 (Upper-triangular form), Theorem 4.5.17 (Change of basis)

Hint. Apply Theorem 7.5.13 to

𝑇_{𝐴}

and translate the change of basis into matrices.

Sketch. If

ℬ︀

triangularizes

𝑇_{𝐴}

and

𝑆

has the vectors of

ℬ︀

as columns, then

𝑆 = {[id]}_{ℰ︀ ℬ︀}

and

{[𝑇_{𝐴}]}_{ℬ︀} = 𝑆^{- 1} 𝐴 𝑆

by Theorem 4.5.17.

By Theorem 7.5.13 there is a basis

ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}

ℂ^{𝑛}

with

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

upper triangular. Let

𝑆

be the matrix with columns

𝐛_{1}, \dots, 𝐛_{𝑛}

, that is,

𝑆 = {[id]}_{ℰ︀ ℬ︀}

for the standard basis

ℰ︀

. It is invertible, and Theorem 4.5.17 gives

𝑅 =

𝑆^{- 1} {[𝑇_{𝐴}]}_{ℰ︀} 𝑆 =

𝑆^{- 1} 𝐴 𝑆

, so

𝐴 = 𝑆 𝑅 𝑆^{- 1}

. The rest is Theorem 7.5.13. □

Example 7.5.15 (Triangularizing a $3 \times 3$ matrix). Let

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

We follow the first proof of Theorem 7.5.13. Its characteristic polynomial is $(𝑥 - 2) {(𝑥 - 1)}^{2}$ , and $𝐛_{1} = (1, 1, 0)$ is an eigenvector: $𝐴 𝐛_{1} =$ $(2, 2, 0) =$ $2 𝐛_{1}$ . A convenient complement of $span (𝐛_{1})$ is $𝑊 = span (𝐞_{2}, 𝐞_{3})$ , since $𝐛_{1}$ has a nonzero first coordinate. Every vector decomposes as

(𝑥_{1}, 𝑥_{2}, 𝑥_{3}) = 𝑥_{1} 𝐛_{1} + (0, 𝑥_{2} - 𝑥_{1}, 𝑥_{3}),

so the projection onto $𝑊$ along $span (𝐛_{1})$ is $(𝑥_{1}, 𝑥_{2}, 𝑥_{3}) \mapsto$ $(0, 𝑥_{2} - 𝑥_{1}, 𝑥_{3})$ . The compression $𝑆$ sends

𝐞_{2} \mapsto Pr (𝐴 𝐞_{2}) = Pr (0, 2, 1) = 2 𝐞_{2} + 𝐞_{3}, 𝐞_{3} \mapsto Pr (𝐴 𝐞_{3}) = Pr (- 1, - 2, 0) = - 𝐞_{2},

so ${[𝑆]}_{𝐞_{2}, 𝐞_{3}} =$ $(\begin{matrix} 2 & - 1 \\ 1 & 0 \end{matrix})$ . This $2 \times 2$ problem has the eigenvalue $1$ with eigenvector $(1, 1)$ in these coordinates, that is, $𝐛_{2} = 𝐞_{2} + 𝐞_{3}$ , and we complete it with $𝐛_{3} = 𝐞_{3}$ . Now

𝐴 𝐛_{1} = 2 𝐛_{1}, 𝐴 𝐛_{2} = (- 1, 0, 1) = - 𝐛_{1} + 𝐛_{2}, 𝐴 𝐛_{3} = (- 1, - 2, 0) = - 𝐛_{1} - 𝐛_{2} + 𝐛_{3},

so with $𝑃 = (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})$ , whose columns are $𝐛_{1}, 𝐛_{2}, 𝐛_{3}$ ,

𝑃^{- 1} 𝐴 𝑃 = (\begin{matrix} 2 & - 1 & - 1 \\ 0 & 1 & - 1 \\ 0 & 0 & 1 \end{matrix}) .

The diagonal $2, 1, 1$ matches $𝑝_{𝐴} =$ $(𝑥 - 2) {(𝑥 - 1)}^{2}$ . The matrix $𝐴$ is not diagonalizable: $𝐴 - 𝐼_{3}$ has rank $2$ , so $𝐸_{1}$ is a line, while $1$ has algebraic multiplicity $2$ . The entries above the diagonal cannot all be removed.

Remark 7.5.16 (The quotient version).Beyond 21-242 With quotient spaces (Section 4.6), the first proof needs no choice of complement. Let

𝑈 = span (𝐛_{1})

. The operator

𝑇 / 𝑈

𝑉 / 𝑈

(Proposition 4.6.32) is triangularized by some

𝐛_{2} + 𝑈, \dots, 𝐛_{𝑛} + 𝑈

, by induction, since

dim 𝑉 / 𝑈 = 𝑛 - 1

. Then

𝐛_{1}, 𝐛_{2}, \dots, 𝐛_{𝑛}

is a basis of

𝑉

(Proposition 4.6.28), and Proposition 4.6.32(b) gives

[𝑇] =

(\begin{matrix} 𝜆_{1} & 𝑋 \\ 0 & [𝑇 / 𝑈] \end{matrix})

, which is upper triangular. The compression is

𝑇 / 𝑈

in disguise: the isomorphism

𝑊 \to 𝑉 / 𝑈

𝐰 \mapsto 𝐰 + 𝑈

(Proposition 4.6.29), carries

𝑆

𝑇 / 𝑈

, because

𝑆 𝐰 + 𝑈 = 𝑇 𝐰 + 𝑈

by Lemma 7.5.11(a). So different complements give different compressions, but they are all similar to one operator.

Only one step of the first proof used $ℂ$ : the existence of an eigenvalue, for $𝑇$ and then for each compression. Over a general field we can ask for exactly that, and the characteristic polynomial tells us when it holds.

Theorem 7.5.17 (Triangularizable means the characteristic polynomial splits).Beyond 21-242 Let

𝑉

be a finite-dimensional vector space over any field

𝐹

, with

dim 𝑉 \geq 1

, and let

𝑇 \in L (𝑉)

. Then

𝑇

is triangularizable if and only if

𝑝_{𝑇}

splits over

𝐹

Proof.hard

Uses. Proposition 7.5.9 (Multiplicities on the diagonal), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Lemma 7.5.11 (Compressing an operator to a complement), Theorem 5.4.26 (Block-triangular matrices), Proposition 7.1.34 (Roots of a split polynomial), Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 4.4.16 (Complements exist)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12)

Hint 1. One direction is Proposition 7.5.9. For the other, run the first proof of Theorem 7.5.13. What has to be checked at each step?

Hint 2. The eigenvalue for the first step is a root of

𝑝_{𝑇}

. For the induction, show that

𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}

for the compression

𝑆

, using Lemma 7.5.11(b) and block triangular determinants.

Hint 3. If

(𝑥 - 𝜆_{1}) 𝑞 =

(𝑥 - 𝜇_{1}) \dots (𝑥 - 𝜇_{𝑛})

, then

𝜆_{1}

is one of the

𝜇_{𝑖}

, and cancelling shows that

𝑞

splits.

Sketch. If

𝑇

is upper triangular,

𝑝_{𝑇} = \prod (𝑥 - 𝜆_{𝑗})

splits. Conversely, by induction on

𝑛

: a root

𝜆_{1}

𝑝_{𝑇}

is an eigenvalue; take an eigenvector, a complement

𝑊

and the compression

𝑆

. The block form of Lemma 7.5.11(b) gives

𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}

, so

𝑝_{𝑆}

splits after cancelling the factor

𝑥 - 𝜆_{1}

. Triangularize

𝑆

by induction and finish as in the first proof of Theorem 7.5.13.

If ${[𝑇]}_{ℬ︀}$ is upper triangular, then $𝑝_{𝑇}$ splits by Proposition 7.5.9.

Conversely, suppose $𝑝_{𝑇}$ splits. We induct on $𝑛 = dim 𝑉$ ; for $𝑛 = 1$ every basis works. Let $𝑛 \geq 2$ and $𝑝_{𝑇} =$ $(𝑥 - 𝜇_{1}) \dots (𝑥 - 𝜇_{𝑛})$ . Then $𝜆_{1} = 𝜇_{1}$ is a root of $𝑝_{𝑇}$ , hence an eigenvalue of $𝑇$ (Theorem 7.3.6); let $𝐛_{1}$ be an eigenvector, $𝑈 = span (𝐛_{1})$ , $𝑊$ a complement of $𝑈$ (Proposition 4.4.16), and $𝑆$ the compression of $𝑇$ to $𝑊$ . For any basis $𝒟︀$ of $𝑊$ and $ℬ︀ = 𝐛_{1}, 𝒟︀$ , Lemma 7.5.11(b) gives

𝑥 𝐼_{𝑛} - {[𝑇]}_{ℬ︀} = (\begin{matrix} 𝑥 - 𝜆_{1} & - 𝑋 \\ 0 & 𝑥 𝐼_{𝑛 - 1} - {[𝑆]}_{𝒟︀} \end{matrix}),

so by Theorem 5.4.26 (over $𝐹 [𝑥]$ ), $𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}$ . Hence $(𝑥 - 𝜇_{1}) 𝑝_{𝑆} =$ $(𝑥 - 𝜇_{1}) (𝑥 - 𝜇_{2}) \dots (𝑥 - 𝜇_{𝑛})$ , and cancelling the nonzero factor $𝑥 - 𝜇_{1}$ (Corollary 7.1.7) gives $𝑝_{𝑆} =$ $(𝑥 - 𝜇_{2}) \dots (𝑥 - 𝜇_{𝑛})$ , which splits. By the induction hypothesis, $𝑊$ has a basis $𝐛_{2}, \dots, 𝐛_{𝑛}$ in which $𝑆$ is upper triangular, and the computation in the first proof of Theorem 7.5.13, which used only Lemma 7.5.11(a), shows that $𝑇$ is upper triangular with respect to $𝐛_{1}, \dots, 𝐛_{𝑛}$ . □

For example, a real matrix is triangularizable over $ℝ$ exactly when all its complex eigenvalues are real, and $(\begin{matrix} 0 & 2 \\ 1 & 0 \end{matrix}) \in ℚ^{2 \times 2}$ is triangularizable over $ℝ$ but not over $ℚ$ , since $𝑥^{2} - 2$ splits over $ℝ$ but not over $ℚ$ .

7.5.3Schur’s theorem

Now let $𝑉$ be a finite-dimensional inner product space over $𝔽 = ℝ$ or $ℂ$ (Definition 6.1.2). Orthonormal bases are the best bases to compute in: coordinates are inner products (Proposition 6.3.18), the $(𝑖, 𝑗)$ entry of ${[𝑇]}_{𝒪︀}$ is $⟨ 𝑇 𝐮_{𝑗}, 𝐮_{𝑖} ⟩$ , and the change-of-basis matrix to an orthonormal basis of $𝔽^{𝑛}$ is unitary, so its inverse is its conjugate transpose (Definition 6.3.33). Can a triangularizing basis be chosen orthonormal?

By Proposition 7.5.2, being upper triangular depends only on the flag of the basis. And Gram–Schmidt replaces a basis by an orthonormal one with the same flag: $span (𝐮_{1}, \dots, 𝐮_{𝑗}) =$ $span (𝐛_{1}, \dots, 𝐛_{𝑗})$ for every $𝑗$ (Theorem 6.4.15(d)). So the answer is yes, at no extra cost.

Theorem 7.5.18 (Schur’s theorem). Let $𝑉$ be a finite-dimensional complex inner product space with $dim 𝑉 \geq 1$ , and let $𝑇 \in L (𝑉)$ .

(a)There is an orthonormal basis $𝒪︀$ of $𝑉$ such that ${[𝑇]}_{𝒪︀}$ is upper triangular.
(b)Every $𝐴 \in ℂ^{𝑛 \times 𝑛}$ can be written as $𝐴 = 𝑈 𝑅 𝑈^{*}$ with $𝑈$ unitary and $𝑅$ upper triangular. The diagonal entries of $𝑅$ are the eigenvalues of $𝐴$ , counted with multiplicity.

Proof (Gram–Schmidt on a triangularizing basis).routine

Uses. Theorem 7.5.13 (Upper-triangular form), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Theorem 6.4.15 (Gram–Schmidt is correct), Theorem 4.5.17 (Change of basis), Definition 6.3.33 (Unitary and orthogonal matrices), Theorem 6.3.29 (Orthonormal columns)

Techniques. Build a flag of invariant subspaces (Technique 7.5.4)

Hint 1. Start from a basis

ℬ︀

with

{[𝑇]}_{ℬ︀}

upper triangular. What does Proposition 7.5.2 say about the subspaces

span (𝐛_{1}, \dots, 𝐛_{𝑗})

Hint 2. Gram–Schmidt does not change these subspaces (Theorem 6.4.15(d)).

Sketch. Triangularize

𝑇

in some basis

ℬ︀

(Theorem 7.5.13), so the flag of

ℬ︀

is invariant. Gram–Schmidt turns

ℬ︀

into an orthonormal basis

𝒪︀

with the same flag, so

𝑇

is upper triangular with respect to

𝒪︀

. For (b), apply (a) to

𝑇_{𝐴}

ℂ^{𝑛}

with the dot product; the matrix

𝑈

whose columns are the vectors of

𝒪︀

is unitary.

(a) By Theorem 7.5.13, there is a basis $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ of $𝑉$ with ${[𝑇]}_{ℬ︀}$ upper triangular, and by Proposition 7.5.2 every $𝑉_{𝑗} =$ $span (𝐛_{1}, \dots, 𝐛_{𝑗})$ is $𝑇$ -invariant. Apply Gram–Schmidt to $ℬ︀$ . Since $ℬ︀$ is linearly independent, Theorem 6.4.15(c),(d) gives an orthonormal basis $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑛}$ of $𝑉$ with $span (𝐮_{1}, \dots, 𝐮_{𝑗}) =$ $𝑉_{𝑗}$ for every $𝑗$ . These subspaces are $𝑇$ -invariant, so ${[𝑇]}_{𝒪︀}$ is upper triangular by Proposition 7.5.2.

(b) Apply (a) to $𝑇_{𝐴}$ on $ℂ^{𝑛}$ with the dot product, and let $𝑈$ be the matrix whose columns are the vectors of $𝒪︀$ . Its columns are orthonormal, so $𝑈$ is unitary (Theorem 6.3.29, Definition 6.3.33) and $𝑈^{- 1} = 𝑈^{*}$ . By Theorem 4.5.17, $𝑅 =$ ${[𝑇_{𝐴}]}_{𝒪︀} =$ $𝑈^{- 1} 𝐴 𝑈 =$ $𝑈^{*} 𝐴 𝑈$ is upper triangular, and $𝐴 = 𝑈 𝑅 𝑈^{*}$ . The diagonal of $𝑅$ is described by Theorem 7.5.13. □

Intuition (The lecture’s proof). The second proof does the algebra and the geometry at once, without quoting Theorem 7.5.13. It is the first proof of Theorem 7.5.13 with the complement chosen orthogonal: take a unit eigenvector

𝐮_{1}

, use

𝑊 = {span (𝐮_{1})}^{⟂}

as the complement, and compress

𝑇

𝑊

with the orthogonal projection. The compression is the operator on a smaller space to which the induction hypothesis applies (Technique 7.5.12). This is the template for the spectral theorem in Section 8.2: for a self-adjoint

𝑇

, the complement

𝑊

turns out to be invariant itself, the compression is just the restriction, and the entries above the diagonal vanish too.

Proof (induction with an orthogonal complement).standard

Uses. Theorem 7.3.27 (Existence of eigenvalues over $ℂ$ ), Theorem 6.4.24 (Orthogonal decomposition), Corollary 6.4.25 (Dimension of the orthogonal complement), Theorem 4.4.13 (Bases and dimension of a sum), Definition 6.3.15 (Orthonormal list, orthonormal basis), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Definition 6.1.2 (Inner product)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12)

Hint 1. Induct on

𝑛 = dim 𝑉

. Take a unit eigenvector

𝐮_{1}

and

𝑊 = {span (𝐮_{1})}^{⟂}

. Which operator on

𝑊

should the induction hypothesis be applied to?

Hint 2. Define

𝑆 𝐰 =

𝑇 𝐰 -

⟨ 𝑇 𝐰, 𝐮_{1} ⟩ 𝐮_{1}

. Check that

𝑆 𝐰 \in 𝑊

Hint 3. With an orthonormal basis

𝐮_{2}, \dots, 𝐮_{𝑛}

𝑊

triangularizing

𝑆

, write

𝑇 𝐮_{𝑗} =

⟨ 𝑇 𝐮_{𝑗}, 𝐮_{1} ⟩ 𝐮_{1} +

𝑆 𝐮_{𝑗}

Sketch. Induct on

𝑛

. Take a unit eigenvector

𝐮_{1}

and

𝑊 = {span (𝐮_{1})}^{⟂}

, of dimension

𝑛 - 1

. The map

𝑆 𝐰 =

𝑇 𝐰 -

⟨ 𝑇 𝐰, 𝐮_{1} ⟩ 𝐮_{1}

is an operator on

𝑊

(the compression of

𝑇

). By induction,

𝑊

has an orthonormal basis

𝐮_{2}, \dots, 𝐮_{𝑛}

triangularizing

𝑆

. Then

𝐮_{1}, \dots, 𝐮_{𝑛}

is orthonormal, and

𝑇 𝐮_{𝑗} =

⟨ 𝑇 𝐮_{𝑗}, 𝐮_{1} ⟩ 𝐮_{1} +

𝑆 𝐮_{𝑗} \in

span (𝐮_{1}, \dots, 𝐮_{𝑗})

We prove (a) by induction on $𝑛 = dim 𝑉$ ; part (b) follows from (a) as in the first proof. If $𝑛 = 1$ , any unit vector forms an orthonormal basis, and $1 \times 1$ matrices are upper triangular.

Let $𝑛 \geq 2$ , and assume (a) for complex inner product spaces of dimension $𝑛 - 1$ . By Theorem 7.3.27, $𝑇$ has an eigenvector; dividing it by its norm gives an eigenvector $𝐮_{1}$ with $‖ 𝐮_{1} ‖ = 1$ and $𝑇 𝐮_{1} = 𝜆_{1} 𝐮_{1}$ . Let $𝑊 = {span (𝐮_{1})}^{⟂}$ , the set of vectors orthogonal to $𝐮_{1}$ . By Theorem 6.4.24 and Corollary 6.4.25, $𝑉 = span (𝐮_{1}) \oplus 𝑊$ and $dim 𝑊 = 𝑛 - 1$ ; with the inner product of $𝑉$ restricted to it, $𝑊$ is a complex inner product space. Define

𝑆 : 𝑊 \to 𝑊, 𝑆 𝐰 = 𝑇 𝐰 - ⟨ 𝑇 𝐰, 𝐮_{1} ⟩ 𝐮_{1} .

This lands in $𝑊$ , since $⟨ 𝑆 𝐰, 𝐮_{1} ⟩ =$ $⟨ 𝑇 𝐰, 𝐮_{1} ⟩ -$ $⟨ 𝑇 𝐰, 𝐮_{1} ⟩ ⟨ 𝐮_{1}, 𝐮_{1} ⟩ =$ $0$ , and it is linear because $𝑇$ is linear and the inner product is linear in its first slot (Definition 6.1.2). ( $𝑆 𝐰$ is the orthogonal projection of $𝑇 𝐰$ onto $𝑊$ , so $𝑆$ is the compression of $𝑇$ to $𝑊$ .)

By the induction hypothesis and Proposition 7.5.2, $𝑊$ has an orthonormal basis $𝐮_{2}, \dots, 𝐮_{𝑛}$ with $𝑆 𝐮_{𝑗} \in$ $span (𝐮_{2}, \dots, 𝐮_{𝑗})$ for $2 \leq 𝑗 \leq 𝑛$ . Each $𝐮_{𝑗}$ with $𝑗 \geq 2$ lies in $𝑊$ , so it is orthogonal to $𝐮_{1}$ , and $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑛}$ is orthonormal (Definition 6.3.15); it is a basis of $𝑉 = span (𝐮_{1}) \oplus 𝑊$ by Theorem 4.4.13. Finally, $𝑇 𝐮_{1} = 𝜆_{1} 𝐮_{1}$ , and for $𝑗 \geq 2$ ,

𝑇 𝐮_{𝑗} = ⟨ 𝑇 𝐮_{𝑗}, 𝐮_{1} ⟩ 𝐮_{1} + 𝑆 𝐮_{𝑗} \in span (𝐮_{1}, 𝐮_{2}, \dots, 𝐮_{𝑗}) .

By Proposition 7.5.2, ${[𝑇]}_{𝒪︀}$ is upper triangular. □

The first proof separates the two ingredients: the algebra (an invariant flag exists over $ℂ$ ) and the geometry (Gram–Schmidt keeps flags). It shows that any triangularizing basis can be orthonormalized, so for instance the basis of Example 7.5.15 turns into a Schur basis of that matrix. The second proof is self-contained and computes the entries as it goes: ${[𝑇]}_{𝒪︀}$ has $(𝑖, 𝑗)$ entry $⟨ 𝑇 𝐮_{𝑗}, 𝐮_{𝑖} ⟩ =$ $⟨ 𝑆 𝐮_{𝑗}, 𝐮_{𝑖} ⟩$ for $𝑖, 𝑗 \geq 2$ .

Example 7.5.19 (A Schur form). Let $𝐴 = (\begin{matrix} 1 & 2 \\ - 2 & 5 \end{matrix}) \in ℂ^{2 \times 2}$ . Then $det (𝐴 - 𝜆 𝐼_{2}) =$ $(1 - 𝜆) (5 - 𝜆) +$ $4 =$ ${(𝜆 - 3)}^{2}$ , so $3$ is the only eigenvalue, and $𝐴 - 3 𝐼_{2} = (\begin{matrix} - 2 & 2 \\ - 2 & 2 \end{matrix})$ gives the unit eigenvector $𝐮_{1} = \frac{1}{\sqrt{2}} (1, 1)$ . Complete it to the orthonormal basis $𝐮_{1}, 𝐮_{2}$ with $𝐮_{2} = \frac{1}{\sqrt{2}} (- 1, 1)$ . Since $𝐴 𝐮_{2} = \frac{1}{\sqrt{2}} (1, 7)$ ,

⟨ 𝐴 𝐮_{2}, 𝐮_{1} ⟩ = \frac{1}{2} (1 + 7) = 4, ⟨ 𝐴 𝐮_{2}, 𝐮_{2} ⟩ = \frac{1}{2} (- 1 + 7) = 3,

and so

𝐴 = 𝑈 𝑅 𝑈^{*}, 𝑈 = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & - 1 \\ 1 & 1 \end{matrix}), 𝑅 = (\begin{matrix} 3 & 4 \\ 0 & 3 \end{matrix}) .

Here $𝐸_{3}$ is a line, so $𝐴$ is not diagonalizable, and no unitary change of basis can remove the entry $4$ . In fact no change of basis at all can make it $0$ , although a non-orthonormal one can make it $1$ .

Remark 7.5.20 (What is unique). A Schur form is far from unique. The eigenvalues can be made to appear on the diagonal in any order (Exercise 7.5.38), and even for a fixed order, replacing $𝑈$ by $𝑈 𝐷$ with $𝐷 =$ $diag (𝑒^{𝑖 𝜃_{1}}, \dots, 𝑒^{𝑖 𝜃_{𝑛}})$ replaces $𝑅$ by $𝐷^{*} 𝑅 𝐷$ , which multiplies $𝑟_{𝑖 𝑗}$ by $𝑒^{𝑖 (𝜃_{𝑗} - 𝜃_{𝑖})}$ . What does not change is the list of diagonal entries, up to order (Proposition 7.5.9), and the total size $\sum_{𝑖, 𝑗} {| 𝑟_{𝑖 𝑗} |}^{2} =$ $tr (𝐴^{*} 𝐴)$ (Exercise 7.5.41).

For a real matrix with nonreal eigenvalues, $𝑈$ and $𝑅$ cannot both be real, since a real upper-triangular $𝑅$ has real eigenvalues. If all eigenvalues of $𝐴 \in ℝ^{𝑛 \times 𝑛}$ are real, then $𝐴 = 𝑄 𝑅 𝑄^{𝖳}$ with $𝑄$ orthogonal and $𝑅$ real (Exercise 7.5.42). For general real matrices, see Section 7.5.5.

Exercise 7.5.21.routine Find a unitary

𝑈

and an upper-triangular

𝑅

with

(\begin{matrix} 3 & - 1 \\ 1 & 1 \end{matrix}) = 𝑈 𝑅 𝑈^{*}

Solution.

Uses. Theorem 7.5.18 (Schur’s theorem), Theorem 7.2.9 (Eigenvalues and invertibility), Proposition 6.3.18 (Coordinates in an orthonormal basis)

Hint 1. Find an eigenvalue and a unit eigenvector

𝐮_{1}

; complete it to an orthonormal basis of

ℂ^{2}

Hint 2. The entries of

𝑅

are

𝑟_{𝑖 𝑗} =

⟨ 𝐴 𝐮_{𝑗}, 𝐮_{𝑖} ⟩

Sketch.

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

{(𝜆 - 2)}^{2}

;

𝐮_{1} = \frac{1}{\sqrt{2}} (1, 1)

𝐮_{2} = \frac{1}{\sqrt{2}} (- 1, 1)

;

𝐴 𝐮_{2} = \frac{1}{\sqrt{2}} (- 4, 0)

, so

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

$det (𝐴 - 𝜆 𝐼_{2}) =$ $(3 - 𝜆) (1 - 𝜆) +$ $1 =$ $𝜆^{2} -$ $4 𝜆 +$ $4 =$ ${(𝜆 - 2)}^{2}$ , so $2$ is the only eigenvalue. From $𝐴 - 2 𝐼_{2} = (\begin{matrix} 1 & - 1 \\ 1 & - 1 \end{matrix})$ , a unit eigenvector is $𝐮_{1} = \frac{1}{\sqrt{2}} (1, 1)$ ; complete it with $𝐮_{2} = \frac{1}{\sqrt{2}} (- 1, 1)$ . Then $𝐴 𝐮_{1} = 2 𝐮_{1}$ , and $𝐴 𝐮_{2} = \frac{1}{\sqrt{2}} (- 4, 0)$ , so by Proposition 6.3.18

𝑟_{12} = ⟨ 𝐴 𝐮_{2}, 𝐮_{1} ⟩ = \frac{1}{2} (- 4) = - 2, 𝑟_{22} = ⟨ 𝐴 𝐮_{2}, 𝐮_{2} ⟩ = \frac{1}{2} (4) = 2 .

Hence $𝐴 = 𝑈 𝑅 𝑈^{*}$ with $𝑈 = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & - 1 \\ 1 & 1 \end{matrix})$ and $𝑅 = (\begin{matrix} 2 & - 2 \\ 0 & 2 \end{matrix})$ . Check: $𝐴 𝑈 =$ $\frac{1}{\sqrt{2}} (\begin{matrix} 2 & - 4 \\ 2 & 0 \end{matrix}) =$ $𝑈 𝑅$ .

7.5.4Trace and determinant from eigenvalues

Every operator on a complex space has a triangular matrix whose diagonal lists its eigenvalues. Trace and determinant are both read off the diagonal of a triangular matrix, and both are independent of the basis. Putting these facts together gives formulas for them that mention no basis at all.

Theorem 7.5.22 (Trace and determinant from eigenvalues). Let $𝑉$ be a finite-dimensional vector space over $𝐹$ with $dim 𝑉 = 𝑛 \geq 1$ , let $𝑇 \in L (𝑉)$ , and suppose that $𝑝_{𝑇}$ splits over $𝐹$ , as it always does when $𝐹 = ℂ$ . Let $𝜆_{1}, \dots, 𝜆_{𝑛}$ be the eigenvalues of $𝑇$ counted with multiplicity. Then

tr 𝑇 = 𝜆_{1} + 𝜆_{2} + \dots + 𝜆_{𝑛} and det 𝑇 = 𝜆_{1} 𝜆_{2} \dots 𝜆_{𝑛} .

In particular, for $𝐴 \in ℂ^{𝑛 \times 𝑛}$ , and so for every real matrix regarded as a complex one, $tr 𝐴$ is the sum and $det 𝐴$ the product of the complex eigenvalues of $𝐴$ , counted with multiplicity.

Proof (triangularize).routine

Uses. Theorem 7.5.13 (Upper-triangular form), Theorem 7.5.17 (Triangularizable means the characteristic polynomial splits), Definition 4.5.30 (Trace of an operator), Definition 5.4.18 (Determinant of an operator), Definition 2.4.26 (Trace), Proposition 5.3.15 (Triangular matrices), Proposition 7.5.9 (Multiplicities on the diagonal)

Techniques. Prove it for triangular matrices first (Technique 7.5.23), Choose a convenient basis (Technique 4.5.33)

Hint 1. Both sides do not depend on the basis. Which basis makes the left sides easy to compute?

Hint 2. In a triangularizing basis

ℬ︀

, what are

tr {[𝑇]}_{ℬ︀}

and

det {[𝑇]}_{ℬ︀}

, and what is the diagonal?

Sketch. Choose

ℬ︀

with

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

upper triangular (Theorem 7.5.13 over

ℂ

, Theorem 7.5.17 in general). Then

tr 𝑇 = tr 𝑅

and

det 𝑇 = det 𝑅

are the sum and the product of the diagonal entries, and the diagonal entries are the eigenvalues counted with multiplicity (Proposition 7.5.9).

By Theorem 7.5.13 when $𝐹 = ℂ$ , and by Theorem 7.5.17 in general, there is a basis $ℬ︀$ with $𝑅 = {[𝑇]}_{ℬ︀}$ upper triangular. By Definition 4.5.30 and Definition 5.4.18, $tr 𝑇 = tr 𝑅$ and $det 𝑇 = det 𝑅$ . By Definition 2.4.26 and Proposition 5.3.15,

tr 𝑅 = 𝑟_{11} + \dots + 𝑟_{𝑛 𝑛}, det 𝑅 = 𝑟_{11} 𝑟_{22} \dots 𝑟_{𝑛 𝑛} .

By Proposition 7.5.9, $𝑝_{𝑇} =$ $(𝑥 - 𝑟_{11}) \dots (𝑥 - 𝑟_{𝑛 𝑛})$ , so $𝑟_{11}, \dots, 𝑟_{𝑛 𝑛}$ are the eigenvalues of $𝑇$ counted with multiplicity, in some order. Sums and products do not depend on the order. □

Technique 7.5.23 (Prove it for triangular matrices first). If a statement about an operator $𝑇$ (or a square matrix $𝐴$ ) does not change under change of basis (or similarity), it is enough to prove it for an upper-triangular matrix of $𝑇$ , which exists over $ℂ$ (Theorem 7.5.13), or over any field once the characteristic polynomial splits. Triangular matrices are easy to compute with: products, powers, inverses, and polynomials of upper-triangular matrices are upper triangular, and their diagonals are computed entry by entry (Proposition 2.4.36, Exercise 7.5.34), while the diagonal itself is the list of eigenvalues.

Reach for it for identities that involve eigenvalues together with similarity invariants: trace, determinant, the characteristic polynomial, $tr (𝐴^{𝑘})$ , invertibility, nilpotence. It is a special case of Technique 4.5.33. Over $ℝ$ , either check that the characteristic polynomial splits, or regard the real matrix as a complex one first. The canonical example is Theorem 7.5.22. Later it proves the Cayley–Hamilton theorem (Section 7.6).

Used in 12 places

Theorem 7.5.22, Exercise 7.5.34, Exercise 7.5.36, Exercise 7.5.45, Lemma 7.6.21, Theorem 7.6.28, Exercise 7.6.51, Problem 7.5, Problem 7.10, Theorem 8.2.5, Theorem 8.2.12, Theorem 8.4.25.

The second proof avoids triangularization. It compares two descriptions of the coefficients of the characteristic polynomial.

Proof (read off the characteristic polynomial).standard

Uses. Definition 7.3.4 (Characteristic polynomial), Proposition 7.1.36 (Sum and product of the roots)

Techniques. Read structure off the Leibniz expansion (Technique 5.3.12), Polynomial identity arguments (Technique 5.5.24)

Hint 1. Section 7.3 computes two coefficients of

𝑝_{𝐴} =

det (𝑥 𝐼_{𝑛} - 𝐴)

directly from the entries of

𝐴

. Which ones?

Hint 2. Compare them with the coefficients of

(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})

from Proposition 7.1.36.

Sketch. For any matrix

𝐴

𝑇

, Section 7.3 shows

𝑝_{𝑇} =

𝑥^{𝑛} -

(tr 𝐴) 𝑥^{𝑛 - 1} +

\dots +

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

: the constant term is

det (- 𝐴)

, and in the Leibniz expansion only the identity permutation reaches degree

𝑛 - 1

. On the other hand

𝑝_{𝑇} = \prod (𝑥 - 𝜆_{𝑖})

has these coefficients equal to

- \sum 𝜆_{𝑖}

and

{(- 1)}^{𝑛} \prod 𝜆_{𝑖}

Let

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

for some basis

ℬ︀

, so

𝑝_{𝑇} =

det (𝑥 𝐼_{𝑛} - 𝐴)

tr 𝑇 = tr 𝐴

, and

det 𝑇 = det 𝐴

. By Section 7.3, the coefficient of

𝑥^{𝑛 - 1}

𝑝_{𝑇}

- tr 𝐴

and its constant term is

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

. (The constant term is

det (- 𝐴)

, by setting

𝑥 = 0

; for the other coefficient, a permutation other than the identity moves at least two indices, so its term in the Leibniz expansion has at most

𝑛 - 2

factors containing

𝑥

, and only

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

contributes.) On the other hand

𝑝_{𝑇} =

(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})

, whose coefficient of

𝑥^{𝑛 - 1}

- (𝜆_{1} + \dots + 𝜆_{𝑛})

and whose constant term is

{(- 1)}^{𝑛} 𝜆_{1} \dots 𝜆_{𝑛}

(Proposition 7.1.36). Comparing coefficients,

tr 𝐴 = 𝜆_{1} + \dots + 𝜆_{𝑛}

and

det 𝐴 = 𝜆_{1} \dots 𝜆_{𝑛}

. □

The first proof is the more flexible one: the same reduction gives the eigenvalues of $𝐴^{𝑘}$ and of $𝐴^{- 1}$ (Exercise 7.5.34). The second proof needs no triangular form, only two coefficients of the characteristic polynomial, which are $- tr 𝑇$ and ${(- 1)}^{𝑛} det 𝑇$ over every field, whether or not $𝑝_{𝑇}$ splits.

Example 7.5.24 (Rotations and a $3 \times 3$ check). The rotation $𝑅_{𝜃} =$ $(\begin{matrix} cos 𝜃 & - sin 𝜃 \\ sin 𝜃 & cos 𝜃 \end{matrix}) \in$ $ℝ^{2 \times 2}$ has the complex eigenvalues $cos 𝜃 \pm 𝑖 sin 𝜃$ (Exercise 7.2.42). Their sum is $2 cos 𝜃 = tr 𝑅_{𝜃}$ and their product is ${cos}^{2} 𝜃 +$ ${sin}^{2} 𝜃 =$ $1 =$ $det 𝑅_{𝜃}$ . For a real matrix the nonreal eigenvalues come in conjugate pairs (Proposition 7.1.38), and each pair $𝜆, 𝜆$ contributes $2 Re 𝜆$ to the trace and ${| 𝜆 |}^{2} > 0$ to the determinant.

For the matrix $𝐴$ of Example 7.5.15, with eigenvalues $2, 1, 1$ , the theorem predicts $tr 𝐴 = 4$ and $det 𝐴 = 2$ . Directly: $tr 𝐴 = 2 + 2 + 0 = 4$ , and expanding along the first row, $det 𝐴 =$ $2 (0 + 2) -$ $0 +$ $(- 1) (0 + 2) =$ $2$ .

The trace of an operator

The trace of an operator was defined through a matrix (Definition 4.5.30). Over $ℂ$ , Theorem 7.5.22 gives it a meaning without any basis: it is the sum of the eigenvalues. The matrix identities of Section 2.4.7 also have versions for maps, and for those, maps between different spaces are allowed.

Proposition 7.5.25 (Cyclicity of the trace for linear maps). Let $𝑉$ and $𝑊$ be finite-dimensional, both of dimension at least $1$ , and let $𝑆 \in L (𝑉, 𝑊)$ and $𝑇 \in L (𝑊, 𝑉)$ . Then

tr (𝑇 𝑆) = tr (𝑆 𝑇),

where $𝑇 𝑆 \in L (𝑉)$ and $𝑆 𝑇 \in L (𝑊)$ . In particular $tr (𝑆 𝑇) = tr (𝑇 𝑆)$ for all $𝑆, 𝑇 \in L (𝑉)$ .

Proof.routine

Uses. Definition 4.5.30 (Trace of an operator), Theorem 2.4.2 (The matrix of a composite), Proposition 2.4.28 (Cyclicity of the trace)

Techniques. Translate between maps and matrices (Technique 2.3.27), Cyclicity of trace (Technique 2.4.29)

Hint 1. Choose bases

ℬ︀

𝑉

and

𝒞︀

𝑊

, and write the matrices of

𝑇 𝑆

and

𝑆 𝑇

as products.

Hint 2. Proposition 2.4.28 holds for rectangular matrices.

Sketch. With

𝑋 = {[𝑆]}_{𝒞︀ ℬ︀}

and

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

, we have

{[𝑇 𝑆]}_{ℬ︀} = 𝑌 𝑋

and

{[𝑆 𝑇]}_{𝒞︀} = 𝑋 𝑌

, and

tr (𝑌 𝑋) = tr (𝑋 𝑌)

Let $ℬ︀$ and $𝒞︀$ be bases of $𝑉$ and $𝑊$ , with $dim 𝑉 = 𝑛$ and $dim 𝑊 = 𝑚$ , and let $𝑋 =$ ${[𝑆]}_{𝒞︀ ℬ︀} \in$ $𝐹^{𝑚 \times 𝑛}$ and $𝑌 =$ ${[𝑇]}_{ℬ︀ 𝒞︀} \in$ $𝐹^{𝑛 \times 𝑚}$ . By Theorem 2.4.2, ${[𝑇 𝑆]}_{ℬ︀} = 𝑌 𝑋$ and ${[𝑆 𝑇]}_{𝒞︀} = 𝑋 𝑌$ . So by Definition 4.5.30 and Proposition 2.4.28,

tr (𝑇 𝑆) = tr (𝑌 𝑋) = tr (𝑋 𝑌) = tr (𝑆 𝑇) .

□

Corollary 7.5.26 (

𝑆 𝑇 - 𝑇 𝑆 \neq {id}_{𝑉}

). Let

𝑉

be finite-dimensional with

𝑛 = dim 𝑉 \geq 1

, and suppose that

𝑛 * 1 \neq 0

𝐹

(for instance,

𝐹 = ℝ

ℂ

). Then

𝑆 𝑇 - 𝑇 𝑆 \neq {id}_{𝑉}

for all

𝑆, 𝑇 \in L (𝑉)

Proof.routine

Uses. Proposition 7.5.25 (Cyclicity of the trace for linear maps), Definition 4.5.30 (Trace of an operator), Proposition 2.4.12 (Matrices of sums and scalar multiples), Proposition 2.4.27 (The trace is linear)

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint. Take the trace of both sides.

Sketch.

tr (𝑆 𝑇 - 𝑇 𝑆) =

tr (𝑆 𝑇) -

tr (𝑇 𝑆) =

0

, while

tr {id}_{𝑉} =

tr 𝐼_{𝑛} =

𝑛 * 1 \neq

0

The trace of operators is linear, by Definition 4.5.30, Proposition 2.4.12, and Proposition 2.4.27. So by Proposition 7.5.25,

tr (𝑆 𝑇 - 𝑇 𝑆) =

tr (𝑆 𝑇) -

tr (𝑇 𝑆) =

0

. But

tr {id}_{𝑉} =

tr 𝐼_{𝑛} =

𝑛 * 1 \neq

0

. Hence

𝑆 𝑇 - 𝑇 𝑆 \neq {id}_{𝑉}

. □

This is Proposition 2.4.30 restated for maps, and the hypotheses matter in the same ways. On the infinite-dimensional space $𝐹 [𝑥]$ , differentiation and multiplication by $𝑥$ satisfy $𝐷 𝑀 - 𝑀 𝐷 = id$ (Exercise 2.4.51), and over $𝔽_{𝑝}$ there are $𝑝 \times 𝑝$ matrices with $𝐴 𝐵 - 𝐵 𝐴 = 𝐼_{𝑝}$ (Exercise 2.4.52). The trace argument shows more than the corollary states: $𝑆 𝑇 - 𝑇 𝑆$ always has trace $0$ . Over $ℂ$ the converse also holds, a theorem of Shoda: every matrix of trace $0$ is of the form $𝐴 𝐵 - 𝐵 𝐴$ . The practice bank has a proof.

7.5.5Real operators: block upper-triangular form Beyond 21-242

The real block form and the real Schur form are not covered in lecture.

Over $ℝ$ an operator need not have any eigenvalue, so it need not be triangularizable. But it always comes close: the bottom of an invariant flag may have to be a plane instead of a line, and the matrix becomes upper triangular with some $2 \times 2$ blocks on the diagonal. The key fact, proved in Section 7.3, is that small invariant subspaces always exist: every operator on a nonzero finite-dimensional real vector space has an invariant subspace of dimension $1$ or $2$ . One proof complexifies a matrix $𝐴$ of $𝑇$ : a complex eigenvector $𝐱 + 𝑖 𝐲$ ( $𝐱, 𝐲 \in ℝ^{𝑛}$ ) for an eigenvalue $𝑎 + 𝑏 𝑖$ gives $𝐴 𝐱 = 𝑎 𝐱 - 𝑏 𝐲$ and $𝐴 𝐲 = 𝑏 𝐱 + 𝑎 𝐲$ , by comparing real and imaginary parts, so the vectors with coordinates $𝐱$ and $𝐲$ span an invariant subspace. The induction of Theorem 7.5.13 then goes through with this subspace in place of an eigenvector.

Theorem 7.5.27 (Real block upper-triangular form). Let $𝑉$ be a real vector space with $1 \leq dim 𝑉 < \infty$ , and let $𝑇 \in L (𝑉)$ .

(a)There is a basis $ℬ︀$ of $𝑉$ such that ${[𝑇]}_{ℬ︀}$ is block upper triangular, with every diagonal block of size $1 \times 1$ or $2 \times 2$ , and with no $2 \times 2$ diagonal block having a real eigenvalue.
(b)If $𝑉$ is a real inner product space, $ℬ︀$ can be chosen orthonormal. In particular, every $𝐴 \in ℝ^{𝑛 \times 𝑛}$ can be written as $𝐴 = 𝑄 𝑅 𝑄^{𝖳}$ with $𝑄$ orthogonal and $𝑅$ block upper triangular as in (a) (the real Schur form).

Proof.hard

Uses. an invariant subspace of dimension $1$ or $2$ exists (Section 7.3), Proposition 7.2.7 (Invariant lines are spanned by eigenvectors), Proposition 4.4.16 (Complements exist), Lemma 7.5.11 (Compressing an operator to a complement), Theorem 6.4.24 (Orthogonal decomposition), Theorem 4.4.13 (Bases and dimension of a sum), Theorem 4.5.17 (Change of basis)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12)

Hint 1. Strong induction on

dim 𝑉

. Choose an invariant subspace

𝑈

of dimension

1

𝑇

has a real eigenvalue, and of dimension

2

otherwise.

Hint 2. Compress

𝑇

to a complement

𝑊

𝑈

, apply the induction hypothesis to the compression, and read off the block form from Lemma 7.5.11(b).

Hint 3. For (b), use the orthogonal complement and orthonormal bases throughout.

Sketch. If

𝑇

has a real eigenvalue, let

𝑈

be an eigenvector’s span; otherwise an invariant subspace of dimension

1

2

(Section 7.3) must be a plane

𝑈

, and

𝑇 ↾_{𝑈}

has no real eigenvalue. If

𝑈 = 𝑉

we are done. Otherwise compress

𝑇

to a complement

𝑊

(for (b), to

𝑈^{⟂}

), use the induction hypothesis on the compression, and assemble with Lemma 7.5.11(b): the first diagonal block is

[𝑇 ↾_{𝑈}]

, the rest are the blocks of the compression.

(a) We use strong induction on $𝑛 = dim 𝑉$ . Choose a $𝑇$ -invariant subspace $𝑈$ as follows. If $𝑇$ has a real eigenvalue, let $𝑈$ be the span of an eigenvector, of dimension $1$ (Proposition 7.2.7). Otherwise, by Section 7.3 there is an invariant subspace $𝑈$ of dimension $1$ or $2$ , and dimension $1$ is impossible since it would be spanned by an eigenvector; so $dim 𝑈 = 2$ . In that case $𝑇 ↾_{𝑈}$ has no real eigenvalue, since an eigenvector of $𝑇 ↾_{𝑈}$ would be an eigenvector of $𝑇$ .

If $𝑈 = 𝑉$ , any basis of $𝑉$ works: ${[𝑇]}_{ℬ︀}$ is a single block of size $1$ , or of size $2$ with no real eigenvalue. Otherwise let $𝑊$ be a complement of $𝑈$ (Proposition 4.4.16), so $1 \leq dim 𝑊 < 𝑛$ , and let $𝑆 \in L (𝑊)$ be the compression of $𝑇$ to $𝑊$ . By the induction hypothesis, $𝑊$ has a basis $𝒟︀$ with ${[𝑆]}_{𝒟︀}$ block upper triangular as in (a). Let $𝒞︀$ be any basis of $𝑈$ , and $ℬ︀ = 𝒞︀, 𝒟︀$ . By Lemma 7.5.11(b),

{[𝑇]}_{ℬ︀} = (\begin{matrix} {[𝑇 ↾_{𝑈}]}_{𝒞︀} & 𝑋 \\ 0 & {[𝑆]}_{𝒟︀} \end{matrix}),

which is block upper triangular, with first diagonal block ${[𝑇 ↾_{𝑈}]}_{𝒞︀}$ and the remaining diagonal blocks those of ${[𝑆]}_{𝒟︀}$ . All of them have the required form.

(b) Run the same induction with $𝑊 = 𝑈^{⟂}$ , which is a complement of $𝑈$ by Theorem 6.4.24, and with an orthonormal basis $𝒞︀$ of $𝑈$ and, by the induction hypothesis applied to the real inner product space $𝑊$ , an orthonormal basis $𝒟︀$ of $𝑊$ . Then $𝒞︀, 𝒟︀$ is orthonormal, since vectors of $𝑈$ and of $𝑈^{⟂}$ are orthogonal. For $𝐴 \in ℝ^{𝑛 \times 𝑛}$ , apply this to $𝑇_{𝐴}$ on $ℝ^{𝑛}$ with the dot product, and let $𝑄$ have the resulting orthonormal basis as columns. Then $𝑄$ is orthogonal, and $𝑅 =$ $𝑄^{𝖳} 𝐴 𝑄 =$ ${[𝑇_{𝐴}]}_{ℬ︀}$ by Theorem 4.5.17. □

Example 7.5.28 (An invariant plane). Let

𝐴 = (\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ - 2 & 2 & - 1 \end{matrix}) \in ℝ^{3 \times 3} .

Its characteristic polynomial is $(𝑥 - 1) (𝑥^{2} + 1)$ , so $1$ is its only real eigenvalue, with eigenvector $𝐯 = (1, 1, 0)$ . Over $ℂ$ , $𝐳 = (1, 0, - 1 + 𝑖)$ is an eigenvector for $𝑖$ , as one checks: $𝐴 𝐳 =$ $(𝑖, 0, - 1 - 𝑖) =$ $𝑖 𝐳$ . As above, split $𝐳 = 𝐱 + 𝑖 𝐲$ with $𝐱 = (1, 0, - 1)$ and $𝐲 = (0, 0, 1)$ . Then

𝐴 𝐱 = (0, 0, - 1) = - 𝐲, 𝐴 𝐲 = (1, 0, - 1) = 𝐱,

so $span (𝐱, 𝐲)$ is an invariant plane on which $𝐴$ acts by $(\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$ , a rotation by a right angle, with eigenvalues $\pm 𝑖$ . In the basis $𝐱, 𝐲, 𝐯$ ,

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

Here the plane happens to have an invariant complement, $span (𝐯)$ , so the matrix is even block diagonal. As a check, $tr 𝐴 = 1 = 𝑖 + (- 𝑖) + 1$ and $det 𝐴 =$ $1 =$ $𝑖 \cdot$ $(- 𝑖) \cdot$ $1$ .

Exercises

Exercise 7.5.29.routine Find an invertible $𝑆$ and an upper-triangular $𝑅$ with diagonal $1, 1, 2$ such that $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ , where

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

Solution.

Uses. Theorem 7.5.13 (Upper-triangular form), Lemma 7.5.11 (Compressing an operator to a complement), Corollary 7.5.14 (Triangularizing a matrix)

Hint 1.

(2, 1, 1)

is an eigenvector. Use the complement

span (𝐞_{2}, 𝐞_{3})

and compute the compression.

Hint 2. In the basis

(2, 1, 1), 𝐞_{2}, 𝐞_{3}

, the matrix is

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

. Triangularize the bottom right

2 \times 2

block, starting with an eigenvector for

1

Sketch.

𝐴 (2, 1, 1) = (2, 1, 1)

. With

𝑀

having columns

(2, 1, 1), 𝐞_{2}, 𝐞_{3}

𝑀^{- 1} 𝐴 𝑀 =

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

. The block

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

has eigenvector

(- 2, 1)

for

1

, giving

𝐛_{2} = (0, - 2, 1)

. With

𝑆

having columns

(2, 1, 1),

(0, - 2, 1),

𝐞_{3}

𝑆^{- 1} 𝐴 𝑆 =

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

First, $𝐴 (2, 1, 1) =$ $(4 - 2, 4 - 1 - 2, - 2 + 3) =$ $(2, 1, 1)$ , so $𝐛_{1} = (2, 1, 1)$ is an eigenvector for $1$ . Since its first coordinate is nonzero, $𝐛_{1}, 𝐞_{2}, 𝐞_{3}$ is a basis, and $𝑊 = span (𝐞_{2}, 𝐞_{3})$ is a complement of $span (𝐛_{1})$ . Writing $(𝑥_{1}, 𝑥_{2}, 𝑥_{3}) =$ $(𝑥_{1} / 2) 𝐛_{1} +$ $(0, 𝑥_{2} - 𝑥_{1} / 2, 𝑥_{3} - 𝑥_{1} / 2)$ , the projection onto $𝑊$ along $span (𝐛_{1})$ is $(𝑥_{1}, 𝑥_{2}, 𝑥_{3}) \mapsto$ $(0, 𝑥_{2} - 𝑥_{1} / 2, 𝑥_{3} - 𝑥_{1} / 2)$ . Since $𝐴 𝐞_{2} = (- 2, - 1, 0)$ and $𝐴 𝐞_{3} = (0, - 2, 3)$ , the compression sends

𝐞_{2} \mapsto (0, - 1 + 1, 0 + 1) = 𝐞_{3}, 𝐞_{3} \mapsto (0, - 2, 3) = - 2 𝐞_{2} + 3 𝐞_{3},

so its matrix is $(\begin{matrix} 0 & - 2 \\ 1 & 3 \end{matrix})$ , with characteristic polynomial $𝑥^{2} -$ $3 𝑥 +$ $2 =$ $(𝑥 - 1) (𝑥 - 2)$ . An eigenvector for $1$ is $(- 2, 1)$ , that is, $𝐛_{2} =$ $- 2 𝐞_{2} +$ $𝐞_{3} =$ $(0, - 2, 1)$ . Complete with $𝐛_{3} = 𝐞_{3}$ . Then

\begin{aligned} 𝐴 𝐛_{2} & = (4, 0, 3) = 2 𝐛_{1} + 𝐛_{2}, \\ 𝐴 𝐛_{3} & = (0, - 2, 3) = 𝐛_{2} + 2 𝐛_{3} . \end{aligned}

So with

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

we have $𝐴 𝑆 = 𝑆 𝑅$ column by column, that is, $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ . The diagonal $1, 1, 2$ agrees with $𝑝_{𝐴} =$ ${(𝑥 - 1)}^{2} (𝑥 - 2)$ : the first entry comes from $𝐛_{1}$ and the other two from the compression. (Starting instead with the eigenvector $(1, 0, 1)$ for $2$ gives a triangular form with diagonal $2, 1, 1$ .)

Exercise 7.5.30.standard

(a)Let $𝑉$ be a complex vector space with $dim 𝑉 = 𝑛 \geq 1$ , and $𝑇 \in L (𝑉)$ . Show that for each $𝑘 = 0, 1, \dots, 𝑛$ , there is a $𝑇$ -invariant subspace of $𝑉$ of dimension $𝑘$ .
(b)Let $𝑇 \in L (ℝ^{4})$ be $𝑇 (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}) =$ $(- 𝑥_{2}, 𝑥_{1}, - 𝑥_{4}, 𝑥_{3})$ . Show that $𝑇$ has no invariant subspace of dimension $1$ or $3$ .

Solution.

Uses. Theorem 7.5.13 (Upper-triangular form), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Proposition 7.2.7 (Invariant lines are spanned by eigenvectors), Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Corollary 7.1.43 (Odd degree gives a real root)

Techniques. Build a flag of invariant subspaces (Technique 7.5.4)

Hint 1. For (a), a triangularizing basis comes with an invariant flag.

Hint 2. For (b), compute

𝑇^{2}

. Why does it follow that

𝑇

has no real eigenvalue?

Hint 3. If

𝑈

is invariant of dimension

3

, then

𝑇 ↾_{𝑈}

is an operator on a

3

-dimensional real space. Its characteristic polynomial has odd degree.

Sketch. (a) The flag

span (𝐛_{1}, \dots, 𝐛_{𝑘})

of a triangularizing basis. (b)

𝑇^{2} = - id

, so

𝑇 𝐯 = 𝜆 𝐯

forces

(𝜆^{2} + 1) 𝐯 = 𝟎

and

𝑇

has no eigenvector, hence no invariant line. An invariant

𝑈

of dimension

3

would give an operator

𝑇 ↾_{𝑈}

whose characteristic polynomial has odd degree, hence a real root, hence an eigenvector of

𝑇

(a) By Theorem 7.5.13 there is a basis $𝐛_{1}, \dots, 𝐛_{𝑛}$ with $[𝑇]$ upper triangular, and by Proposition 7.5.2 the subspaces $span (𝐛_{1}, \dots, 𝐛_{𝑘})$ , of dimension $𝑘$ , are $𝑇$ -invariant ( $𝑘 = 0$ gives ${𝟎}$ ).

(b) $𝑇^{2} (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}) =$ $𝑇 (- 𝑥_{2}, 𝑥_{1}, - 𝑥_{4}, 𝑥_{3}) =$ $(- 𝑥_{1}, - 𝑥_{2}, - 𝑥_{3}, - 𝑥_{4})$ , so $𝑇^{2} = - id$ . If $𝑇 𝐯 = 𝜆 𝐯$ with $𝜆 \in ℝ$ , then $- 𝐯 = 𝑇^{2} 𝐯 = 𝜆^{2} 𝐯$ , so $(𝜆^{2} + 1) 𝐯 = 𝟎$ and $𝐯 = 𝟎$ , as $𝜆^{2} + 1 > 0$ . So $𝑇$ has no eigenvector, and no invariant subspace of dimension $1$ (Proposition 7.2.7).

Suppose $𝑈$ were invariant with $dim 𝑈 = 3$ . Then $𝑇 ↾_{𝑈}$ is an operator on $𝑈$ , and its characteristic polynomial has degree $3$ , so it has a real root (Corollary 7.1.43), which is an eigenvalue of $𝑇 ↾_{𝑈}$ (Theorem 7.3.6). An eigenvector of $𝑇 ↾_{𝑈}$ is an eigenvector of $𝑇$ , which we just showed does not exist. So no such $𝑈$ exists. (Invariant subspaces of dimension $2$ do exist, such as $span (𝐞_{1}, 𝐞_{2})$ .)

Exercise 7.5.31.standard How many of the

16

matrices in

𝔽_{2}^{2 \times 2}

are triangularizable over

𝔽_{2}

? List the ones that are not.

Solution.

Uses. Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Theorem 4.1.16 (Extending to a basis), Theorem 7.2.9 (Eigenvalues and invertibility), Theorem 5.1.13 (The $2 \times 2$ determinant)

Techniques. Try small cases and small fields (Technique 1.2.38)

Hint 1. In dimension

2

, triangularizable means: there is an eigenvector. Why is that enough?

Hint 2.

𝜆

is an eigenvalue if and only if

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

. There are only two candidates,

𝜆 = 0

and

𝜆 = 1

. Express both determinants in terms of

tr 𝐴

and

det 𝐴

Sketch. A

2 \times 2

matrix is triangularizable if and only if it has an eigenvector

𝐛_{1}

: extend it to a basis, and

𝑇 𝐛_{2} \in

span (𝐛_{1}, 𝐛_{2}) =

𝔽_{2}^{2}

automatically. Since

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

𝜆^{2} -

(tr 𝐴) 𝜆 +

det 𝐴

, the candidates fail exactly when

det 𝐴 = 1

and

tr 𝐴 = 1

, which forces

𝑏 = 𝑐 = 1

and

{𝑎, 𝑑} = {0, 1}

. So

14

are triangularizable, and the exceptions are

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

and

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

In dimension $2$ , $𝐴$ is triangularizable if and only if it has an eigenvector. If $𝑇_{𝐴}$ is upper triangular with respect to $𝐛_{1}, 𝐛_{2}$ , then $𝐛_{1}$ is an eigenvector. Conversely, if $𝐛_{1}$ is an eigenvector, extend it to a basis $𝐛_{1}, 𝐛_{2}$ (Theorem 4.1.16); then $𝑇 𝐛_{1} \in span (𝐛_{1})$ and $𝑇 𝐛_{2} \in$ $span (𝐛_{1}, 𝐛_{2})$ , so $𝑇_{𝐴}$ is upper triangular by Proposition 7.5.2.

For $𝐴 = (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})$ , Theorem 5.1.13 gives $det (𝐴 - 𝜆 𝐼_{2}) =$ $(𝑎 - 𝜆) (𝑑 - 𝜆) -$ $𝑏 𝑐 =$ $𝜆^{2} -$ $(𝑎 + 𝑑) 𝜆 +$ $(𝑎 𝑑 - 𝑏 𝑐)$ . By Theorem 7.2.9, $𝐴$ has no eigenvalue in $𝔽_{2}$ if and only if this is nonzero for $𝜆 = 0$ and $𝜆 = 1$ , that is,

det 𝐴 = 1 and 1 + tr 𝐴 + det 𝐴 = 1,

using $- 1 = 1$ in $𝔽_{2}$ . Substituting $det 𝐴 = 1$ into the second condition gives $tr 𝐴 = 1$ , since $1 + 1 = 0$ . From $𝑎 + 𝑑 = 1$ , one of $𝑎, 𝑑$ is $0$ , so $𝑎 𝑑 = 0$ and $det 𝐴 =$ $- 𝑏 𝑐 =$ $𝑏 𝑐 =$ $1$ , giving $𝑏 = 𝑐 = 1$ . So the matrices with no eigenvalue are exactly

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

whose characteristic polynomial is $𝑥^{2} + 𝑥 + 1$ , the one irreducible quadratic over $𝔽_{2}$ . The other $14$ matrices are triangularizable.

Exercise 7.5.32.routine

(a)Find $𝐴 \in ℚ^{2 \times 2}$ that is triangularizable over $ℝ$ but not over $ℚ$ .
(b)Find $𝐴 \in ℝ^{3 \times 3}$ that has a real eigenvalue but is not triangularizable over $ℝ$ .

Solution.

Uses. Proposition 7.2.7 (Invariant lines are spanned by eigenvectors), Proposition 7.5.9 (Multiplicities on the diagonal), Theorem 7.2.9 (Eigenvalues and invertibility)

Hint 1. A triangularizable operator has an eigenvector. Look for a rational matrix whose eigenvalues are irrational.

Hint 2. For (b), if

𝐴

is upper triangular in a real basis, its characteristic polynomial is a product of real linear factors (Proposition 7.5.9). Put a rotation block next to a

1 \times 1

block.

Sketch. (a)

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

has eigenvalues

\pm \sqrt{2}

: no eigenvector in

ℚ^{2}

, but an eigenvector

(\sqrt{2}, 1)

ℝ^{2}

, which a second vector completes to a triangularizing basis. (b)

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

has eigenvalue

1

, but

𝑝_{𝐴} =

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

is not a product of real linear factors.

(a) Let $𝐴 = (\begin{matrix} 0 & 2 \\ 1 & 0 \end{matrix})$ . Then $det (𝐴 - 𝜆 𝐼_{2}) =$ $𝜆^{2} -$ $2$ , which has no rational root, so $𝐴$ has no eigenvalue in $ℚ$ (Theorem 7.2.9). The first vector of a triangularizing basis would be an eigenvector, so $𝐴$ is not triangularizable over $ℚ$ . Over $ℝ$ , $𝐴 (\sqrt{2}, 1) =$ $(2, \sqrt{2}) =$ $\sqrt{2} (\sqrt{2}, 1)$ , and in the basis $(\sqrt{2}, 1), 𝐞_{2}$ the first vector spans an invariant line, so the flag ${𝟎} \subseteq$ $span ((\sqrt{2}, 1)) \subseteq$ $ℝ^{2}$ is invariant and $𝐴$ is triangularizable over $ℝ$ .

(b) Let $𝐴 = (\begin{matrix} 0 & - 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix})$ . Then $𝐴 𝐞_{3} = 𝐞_{3}$ , so $1$ is an eigenvalue. By cofactor expansion along the last row, $𝑝_{𝐴} =$ $(𝑥 - 1) (𝑥^{2} + 1)$ . If $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ with $𝑆, 𝑅$ real and $𝑅$ upper triangular, then $𝑝_{𝐴} =$ $(𝑥 - 𝑟_{11}) (𝑥 - 𝑟_{22}) (𝑥 - 𝑟_{33})$ with real $𝑟_{𝑗 𝑗}$ (Proposition 7.5.9). Evaluating at $𝑖$ gives $0 =$ $𝑝_{𝐴} (𝑖) =$ $(𝑖 - 𝑟_{11}) (𝑖 - 𝑟_{22}) (𝑖 - 𝑟_{33})$ , a product of nonzero complex numbers, which is impossible. So $𝐴$ is not triangularizable over $ℝ$ .

Exercise 7.5.33.standard Prove or disprove.

(a)If $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is triangularizable, then so is $𝐴^{𝖳}$ .
(b)If $𝐴, 𝐵 \in ℝ^{2 \times 2}$ are triangularizable over $ℝ$ , then so is $𝐴 + 𝐵$ .
(c)If $𝑇$ is upper triangular with respect to both $𝐛_{1}, \dots, 𝐛_{𝑛}$ and $𝐜_{1}, \dots, 𝐜_{𝑛}$ , then $𝐜_{1}$ is a multiple of $𝐛_{1}$ .
(d)Two upper-triangular matrices with the same diagonal are similar.

Solution.

Uses. Definition 7.5.1 (Triangularizable), Exercise 7.5.7, Non-example 7.5.6 (A rotation), Proposition 4.5.27 (Similarity invariants)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a), transpose

𝐴 = 𝑆 𝑅 𝑆^{- 1}

. The result has a lower-triangular middle factor; reverse the order of a basis.

Hint 2. For (b), add an upper-triangular and a lower-triangular nilpotent matrix.

Hint 3. For (c) and (d), look at diagonal matrices, and at the identity.

Sketch. (a) True:

𝐴^{𝖳} =

{(𝑆^{𝖳})}^{- 1} 𝑅^{𝖳} 𝑆^{𝖳}

, and

𝑅^{𝖳}

is lower triangular, so with the reversal permutation matrix

𝑃

𝑃 𝑅^{𝖳} 𝑃

is upper triangular and similar to

𝐴^{𝖳}

. (b) False:

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

is a rotation. (c) False:

diag (1, 2)

with the bases

𝐞_{1}, 𝐞_{2}

and

𝐞_{2}, 𝐞_{1}

. (d) False:

𝐼_{2}

and

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

(a) True. Write $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ with $𝑅$ upper triangular. Then $𝐴^{𝖳} =$ ${(𝑆^{- 1})}^{𝖳} 𝑅^{𝖳} 𝑆^{𝖳}$ , and $𝑅^{𝖳}$ is lower triangular. Let $𝑃$ be the permutation matrix with $𝑃 𝐞_{𝑗} = 𝐞_{𝑛 + 1 - 𝑗}$ , so $𝑃^{2} = 𝐼_{𝑛}$ . The $(𝑖, 𝑗)$ entry of $𝑃 𝑅^{𝖳} 𝑃$ is the $(𝑛 + 1 - 𝑖, 𝑛 + 1 - 𝑗)$ entry of $𝑅^{𝖳}$ , which is $𝑟_{𝑛 + 1 - 𝑗, 𝑛 + 1 - 𝑖}$ ; it vanishes when $𝑛 + 1 - 𝑗 > 𝑛 + 1 - 𝑖$ , that is, when $𝑖 > 𝑗$ . So $𝑅^{'} = 𝑃 𝑅^{𝖳} 𝑃$ is upper triangular (this is Exercise 7.5.7 in matrix form), and with $𝑀 = {(𝑆^{- 1})}^{𝖳} 𝑃$ ,

𝐴^{𝖳} = {(𝑆^{- 1})}^{𝖳} 𝑃 𝑅^{'} 𝑃 𝑆^{𝖳} = 𝑀 𝑅^{'} 𝑀^{- 1},

since $𝑀^{- 1} =$ $𝑃^{- 1} 𝑆^{𝖳} =$ $𝑃 𝑆^{𝖳}$ .

(b) False. $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ is upper triangular, and $𝐵 = (\begin{matrix} 0 & 0 \\ - 1 & 0 \end{matrix})$ is lower triangular, hence triangularizable by (a). But $𝐴 + 𝐵 = (\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$ is the rotation by $- 𝜋 / 2$ , which has no real eigenvalue and is not triangularizable over $ℝ$ (as in Non-example 7.5.6).

(c) False. $𝑇 = 𝑇_{𝐷}$ with $𝐷 = diag (1, 2)$ is upper triangular (even diagonal) with respect to $𝐞_{1}, 𝐞_{2}$ and with respect to $𝐞_{2}, 𝐞_{1}$ , and $𝐞_{2}$ is not a multiple of $𝐞_{1}$ .

(d) False. $𝐼_{2}$ and $𝐽 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ have the same diagonal, but $𝑆^{- 1} 𝐼_{2} 𝑆 = 𝐼_{2} \neq 𝐽$ for every invertible $𝑆$ , so $𝐼_{2}$ is similar only to itself.

Exercise 7.5.34.standard Let $𝐴 \in ℂ^{𝑛 \times 𝑛}$ have eigenvalues $𝜆_{1}, \dots, 𝜆_{𝑛}$ , counted with multiplicity.

(a)Show that for every $𝑘 \geq 1$ , the eigenvalues of $𝐴^{𝑘}$ counted with multiplicity are $𝜆_{1}^{𝑘}, \dots, 𝜆_{𝑛}^{𝑘}$ . Deduce that $tr (𝐴^{𝑘}) =$ $𝜆_{1}^{𝑘} +$ $\dots +$ $𝜆_{𝑛}^{𝑘}$ .
(b)Suppose $𝐴$ is invertible. Show that the eigenvalues of $𝐴^{- 1}$ counted with multiplicity are $𝜆_{1}^{- 1}, \dots, 𝜆_{𝑛}^{- 1}$ , and that $tr (𝐴^{- 1}) =$ $𝜆_{1}^{- 1} +$ $\dots +$ $𝜆_{𝑛}^{- 1}$ .

Solution.

Uses. Corollary 7.5.14 (Triangularizing a matrix), Proposition 2.4.36 (Products of upper triangular matrices), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Proposition 7.5.9 (Multiplicities on the diagonal), Theorem 7.5.22 (Trace and determinant from eigenvalues), Proposition 7.5.8 (The diagonal of a triangular matrix)

Techniques. Build a flag of invariant subspaces (Technique 7.5.4), Prove it for triangular matrices first (Technique 7.5.23)

Hint 1. Write

𝐴 = 𝑆 𝑅 𝑆^{- 1}

with

𝑅

upper triangular. Then

𝐴^{𝑘} = 𝑆 𝑅^{𝑘} 𝑆^{- 1}

and

𝐴^{- 1} = 𝑆 𝑅^{- 1} 𝑆^{- 1}

Hint 2. Powers of

𝑅

are upper triangular with the powers of the diagonal entries on the diagonal (Proposition 2.4.36). For

𝑅^{- 1}

, use flags:

𝑇_{𝑅}

maps each

span (𝐞_{1}, \dots, 𝐞_{𝑗})

into itself and is injective.

Sketch. (a)

𝑅^{𝑘}

is upper triangular with diagonal

𝑟_{𝑗 𝑗}^{𝑘}

by Proposition 2.4.36 and induction, and

𝐴^{𝑘} = 𝑆 𝑅^{𝑘} 𝑆^{- 1}

, so Proposition 7.5.9 applies. (b)

𝑇_{𝑅}

maps

𝑉_{𝑗} =

span (𝐞_{1}, \dots, 𝐞_{𝑗})

injectively into itself, hence onto it, so

𝑇_{𝑅}^{- 1}

also preserves every

𝑉_{𝑗}

and

𝑅^{- 1}

is upper triangular;

𝑅 𝑅^{- 1} = 𝐼_{𝑛}

and Proposition 2.4.36 give diagonal entries

𝑟_{𝑗 𝑗}^{- 1}

. Then take traces.

By Corollary 7.5.14, $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ with $𝑅$ upper triangular and diagonal entries $𝑟_{𝑗 𝑗} = 𝜆_{𝑗}$ , after reordering the $𝜆_{𝑗}$ .

(a) $𝐴^{𝑘} = 𝑆 𝑅^{𝑘} 𝑆^{- 1}$ , by induction on $𝑘$ , since $𝑆^{- 1} 𝑆 = 𝐼_{𝑛}$ cancels between consecutive factors. By Proposition 2.4.36 and induction on $𝑘$ , $𝑅^{𝑘}$ is upper triangular with diagonal entries $𝜆_{1}^{𝑘}, \dots, 𝜆_{𝑛}^{𝑘}$ . So $𝑇_{𝐴^{𝑘}}$ is upper triangular with respect to the columns of $𝑆$ , with this diagonal, and by Proposition 7.5.9 these are the eigenvalues of $𝐴^{𝑘}$ counted with multiplicity. By Theorem 7.5.22, $tr (𝐴^{𝑘}) =$ $\sum_{𝑗} 𝜆_{𝑗}^{𝑘}$ .

(b) $𝐴$ is invertible, so $𝑅 = 𝑆^{- 1} 𝐴 𝑆$ is too, and $𝐴^{- 1} = 𝑆 𝑅^{- 1} 𝑆^{- 1}$ . Let $𝑉_{𝑗} =$ $span (𝐞_{1}, \dots, 𝐞_{𝑗})$ . By Proposition 7.5.2, $𝑇_{𝑅}$ maps $𝑉_{𝑗}$ into $𝑉_{𝑗}$ , and it is injective, so $𝑇_{𝑅} ↾_{𝑉_{𝑗}}$ is an injective map from $𝑉_{𝑗}$ into itself, hence onto $𝑉_{𝑗}$ (Corollary 4.2.18). So each $𝐯 \in 𝑉_{𝑗}$ is $𝑇_{𝑅} 𝐰$ for some $𝐰 \in 𝑉_{𝑗}$ , and $𝑇_{𝑅}^{- 1} 𝐯 = 𝐰 \in 𝑉_{𝑗}$ . Thus $𝑇_{𝑅}^{- 1} = 𝑇_{𝑅^{- 1}}$ preserves every $𝑉_{𝑗}$ , and $𝑅^{- 1}$ is upper triangular by Proposition 7.5.2. By Proposition 2.4.36, the diagonal entries of $𝑅 𝑅^{- 1} = 𝐼_{𝑛}$ are $𝑟_{𝑗 𝑗} {(𝑅^{- 1})}_{𝑗 𝑗} =$ $1$ , so ${(𝑅^{- 1})}_{𝑗 𝑗} = 𝜆_{𝑗}^{- 1}$ (each $𝜆_{𝑗} \neq 0$ by Proposition 7.5.8). Now argue as in (a).

Exercise 7.5.35.standard A matrix

𝐴 \in ℂ^{3 \times 3}

satisfies

tr 𝐴 = 2

tr (𝐴^{2}) = 6

, and

det 𝐴 = - 2

. Find the eigenvalues of

𝐴

, and decide whether

𝐴

is diagonalizable.

Solution.

Uses. Theorem 7.5.22 (Trace and determinant from eigenvalues), Exercise 7.5.34, Proposition 7.5.9 (Multiplicities on the diagonal), Theorem 7.2.21 (Eigenvectors for distinct eigenvalues are independent), Theorem 7.4.2 (Diagonalizable means an eigenbasis)

Hint 1. Let

𝜆_{1}, 𝜆_{2}, 𝜆_{3}

be the eigenvalues. You know

\sum 𝜆_{𝑖}

\sum 𝜆_{𝑖}^{2}

, and

\prod 𝜆_{𝑖}

Hint 2.

{(𝜆_{1} + 𝜆_{2} + 𝜆_{3})}^{2} =

\sum 𝜆_{𝑖}^{2} +

2 (𝜆_{1} 𝜆_{2} + 𝜆_{1} 𝜆_{3} + 𝜆_{2} 𝜆_{3})

. This gives every coefficient of

𝑝_{𝐴} =

(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) (𝑥 - 𝜆_{3})

Sketch.

𝑒_{1} = \sum 𝜆_{𝑖} = 2

\sum 𝜆_{𝑖}^{2} = 6

gives

𝑒_{2} =

\sum_{𝑖 < 𝑗} 𝜆_{𝑖} 𝜆_{𝑗} =

(4 - 6) / 2 =

- 1

, and

𝑒_{3} = \prod 𝜆_{𝑖} = - 2

. So

𝑝_{𝐴} =

𝑥^{3} -

2 𝑥^{2} -

𝑥 +

2 =

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

, with three distinct eigenvalues, so

𝐴

is diagonalizable.

Let $𝜆_{1}, 𝜆_{2}, 𝜆_{3}$ be the eigenvalues of $𝐴$ counted with multiplicity. By Theorem 7.5.22 and Exercise 7.5.34(a),

𝜆_{1} + 𝜆_{2} + 𝜆_{3} = 2, 𝜆_{1}^{2} + 𝜆_{2}^{2} + 𝜆_{3}^{2} = 6, 𝜆_{1} 𝜆_{2} 𝜆_{3} = - 2 .

Let $𝑒_{2} =$ $𝜆_{1} 𝜆_{2} +$ $𝜆_{1} 𝜆_{3} +$ $𝜆_{2} 𝜆_{3}$ . Expanding the square, ${(𝜆_{1} + 𝜆_{2} + 𝜆_{3})}^{2} =$ $\sum 𝜆_{𝑖}^{2} +$ $2 𝑒_{2}$ , so $4 = 6 + 2 𝑒_{2}$ and $𝑒_{2} = - 1$ . Expanding the product,

𝑝_{𝐴} = (𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) (𝑥 - 𝜆_{3}) = 𝑥^{3} - 2 𝑥^{2} + 𝑒_{2} 𝑥 - 𝜆_{1} 𝜆_{2} 𝜆_{3} = 𝑥^{3} - 2 𝑥^{2} - 𝑥 + 2 .

This factors as $𝑥^{2} (𝑥 - 2) -$ $(𝑥 - 2) =$ $(𝑥 - 2) (𝑥 - 1) (𝑥 + 1)$ , so the eigenvalues are $1$ , $- 1$ , and $2$ . (Check: $1 + 1 + 4 = 6$ .) Eigenvectors for the three distinct eigenvalues are linearly independent (Theorem 7.2.21), so they form a basis of $ℂ^{3}$ , and $𝐴$ is diagonalizable (Theorem 7.4.2).

Exercise 7.5.36.standard

(a)Let $𝐴 \in ℂ^{𝑛 \times 𝑛}$ . Show that $0$ is the only eigenvalue of $𝐴$ if and only if $𝐴^{𝑛} = 0$ .
(b)Find $𝐴 \in ℝ^{3 \times 3}$ whose only real eigenvalue is $0$ but with $𝐴^{𝑘} \neq 0$ for every $𝑘 \geq 1$ .

Solution.

Uses. Corollary 7.5.14 (Triangularizing a matrix), Proposition 7.5.8 (The diagonal of a triangular matrix), Example 2.8.3 (Strictly upper triangular matrices are nilpotent, three ways), Theorem 7.3.27 (Existence of eigenvalues over $ℂ$ )

Techniques. Prove it for triangular matrices first (Technique 7.5.23)

Hint 1. If

0

is the only eigenvalue, a triangular form of

𝐴

has zeros on the diagonal.

Hint 2. Strictly upper-triangular

𝑛 \times 𝑛

matrices satisfy

𝑁^{𝑛} = 0

(Example 2.8.3). For the converse, apply

𝐴^{𝑛}

to an eigenvector.

Hint 3. For (b), the real eigenvalues do not see a rotation block.

Sketch. (a)

𝐴 = 𝑆 𝑅 𝑆^{- 1}

with

𝑅

upper triangular and diagonal the eigenvalues, all

0

; so

𝑅

is strictly upper triangular,

𝑅^{𝑛} = 0

, and

𝐴^{𝑛} = 𝑆 𝑅^{𝑛} 𝑆^{- 1} = 0

. Conversely

𝐴 𝐯 = 𝜆 𝐯

gives

𝟎 = 𝐴^{𝑛} 𝐯 = 𝜆^{𝑛} 𝐯

, so

𝜆 = 0

, and an eigenvalue exists over

ℂ

. (b)

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

(a) Suppose $0$ is the only eigenvalue. By Corollary 7.5.14, $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ with $𝑅$ upper triangular, and the diagonal entries of $𝑅$ are eigenvalues of $𝐴$ (Proposition 7.5.8), hence all $0$ . So $𝑅$ is strictly upper triangular, and $𝑅^{𝑛} = 0$ by Example 2.8.3. Then $𝐴^{𝑛} = 𝑆 𝑅^{𝑛} 𝑆^{- 1} = 0$ .

Conversely, suppose $𝐴^{𝑛} = 0$ , and let $𝐴 𝐯 = 𝜆 𝐯$ with $𝐯 \neq 𝟎$ . Then $𝐴^{𝑛} 𝐯 = 𝜆^{𝑛} 𝐯$ (induction), so $𝜆^{𝑛} 𝐯 = 𝟎$ , $𝜆^{𝑛} = 0$ , and $𝜆 = 0$ . Since $𝐴$ has at least one eigenvalue (Theorem 7.3.27), $0$ is the only one.

(b) Let $𝐴 = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & - 1 \\ 0 & 1 & 0 \end{matrix})$ , which is block diagonal with blocks $(0)$ and the rotation $𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ . A real eigenvector $(𝑥, 𝑦, 𝑧)$ with eigenvalue $𝜆$ satisfies $0 = 𝜆 𝑥$ , $- 𝑧 = 𝜆 𝑦$ , $𝑦 = 𝜆 𝑧$ , so $𝑦 = - 𝜆^{2} 𝑦$ and $𝑧 = - 𝜆^{2} 𝑧$ , which forces $𝑦 = 𝑧 = 0$ , and then $𝑥 \neq 0$ and $𝜆 = 0$ . So $0$ is the only real eigenvalue. But $𝐴^{𝑘}$ is block diagonal with blocks $(0)$ and $𝑅^{𝑘}$ , and $𝑅^{𝑘} \neq 0$ since $𝑅$ is invertible. Over $ℂ$ , $𝐴$ also has the eigenvalues $\pm 𝑖$ , which is why (a) does not apply.

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

Claim. If $𝐴, 𝐵 \in ℂ^{𝑛 \times 𝑛}$ have eigenvalues $𝜆_{1}, \dots, 𝜆_{𝑛}$ and $𝜇_{1}, \dots, 𝜇_{𝑛}$ (counted with multiplicity), then the eigenvalues of $𝐴 𝐵$ are $𝜆_{1} 𝜇_{1}, \dots, 𝜆_{𝑛} 𝜇_{𝑛}$ , in some order.

Proof. By Schur’s theorem, $𝐴 = 𝑈 𝑅 𝑈^{*}$ and $𝐵 = 𝑈 𝑅^{'} 𝑈^{*}$ with $𝑈$ unitary and $𝑅, 𝑅^{'}$ upper triangular, with diagonals $𝜆_{1}, \dots, 𝜆_{𝑛}$ and $𝜇_{1}, \dots, 𝜇_{𝑛}$ . Then $𝐴 𝐵 = 𝑈 𝑅 𝑅^{'} 𝑈^{*}$ , and $𝑅 𝑅^{'}$ is upper triangular with diagonal $𝜆_{1} 𝜇_{1}, \dots, 𝜆_{𝑛} 𝜇_{𝑛}$ .

Solution.

Uses. Theorem 7.5.18 (Schur’s theorem), Theorem 5.4.10 (Multiplicativity), Theorem 7.5.22 (Trace and determinant from eigenvalues)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Schur’s theorem gives a unitary

𝑈

for each matrix separately. Does it give one

𝑈

that works for both?

Hint 2. Try

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

and

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

Sketch. The proof uses the same

𝑈

for

𝐴

and

𝐵

, but Schur’s theorem only provides a

𝑈

depending on the matrix. The claim is false:

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

and

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

have only the eigenvalue

0

, but

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

has the eigenvalue

1

Schur’s theorem applied to $𝐴$ gives some unitary $𝑈$ , and applied to $𝐵$ gives some unitary $𝑈^{'}$ , which in general differs from $𝑈$ . The argument silently takes $𝑈^{'} = 𝑈$ . A common triangularizing basis exists only in special situations, for instance for commuting matrices (Section 7.6).

The claim itself is false. Take $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ ; both have $0$ as their only eigenvalue, with multiplicity $2$ . But $𝐴 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ has the eigenvalues $1$ and $0$ , while the claim predicts $0, 0$ . What survives is the product of all of them: $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ (Theorem 5.4.10), so by Theorem 7.5.22 the product of the eigenvalues of $𝐴 𝐵$ is $\prod 𝜆_{𝑖} \prod 𝜇_{𝑖}$ .

Exercise 7.5.38.hard Let

𝑉

be a complex vector space with

dim 𝑉 = 𝑛 \geq 1

, and let

𝑇 \in L (𝑉)

have eigenvalues

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

, counted with multiplicity and listed in any order chosen in advance. Show that there is a basis

ℬ︀

𝑉

such that

{[𝑇]}_{ℬ︀}

is upper triangular with diagonal entries

𝜆_{1}, 𝜆_{2}, \dots, 𝜆_{𝑛}

in this order. If

𝑉

is an inner product space, show that

ℬ︀

can be taken orthonormal.

Solution.

Uses. Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Lemma 7.5.11 (Compressing an operator to a complement), Theorem 5.4.26 (Block-triangular matrices), Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 4.4.16 (Complements exist), Theorem 6.4.24 (Orthogonal decomposition)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12)

Hint 1. Follow the first proof of Theorem 7.5.13, but choose the first eigenvector for

𝜆_{1}

Hint 2. For the induction, you need the eigenvalues of the compression

𝑆

. Show

𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}

from the block form of Lemma 7.5.11(b).

Hint 3. For the orthonormal version, use

𝑊 = {span (𝐛_{1})}^{⟂}

with

𝐛_{1}

a unit vector, as in the second proof of Theorem 7.5.18.

Sketch. Induct on

𝑛

𝜆_{1}

is a root of

𝑝_{𝑇}

, hence an eigenvalue; take an eigenvector

𝐛_{1}

, a complement

𝑊

, and the compression

𝑆

. The block form

[𝑇] = (\begin{matrix} 𝜆_{1} & 𝑋 \\ 0 & [𝑆] \end{matrix})

gives

𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}

, so

𝑝_{𝑆} =

(𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛})

. By induction

𝑊

has a basis triangularizing

𝑆

with diagonal

𝜆_{2}, \dots, 𝜆_{𝑛}

, and the block form gives the diagonal

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

for

𝑇

. With a unit

𝐛_{1}

and

𝑊 = {span (𝐛_{1})}^{⟂}

everything can be made orthonormal.

We induct on $𝑛$ ; for $𝑛 = 1$ there is nothing to show. Let $𝑛 \geq 2$ . Since $𝑝_{𝑇} =$ $(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ , $𝜆_{1}$ is a root of $𝑝_{𝑇}$ , hence an eigenvalue (Theorem 7.3.6). Let $𝐛_{1}$ be an eigenvector for $𝜆_{1}$ , $𝑊$ a complement of $span (𝐛_{1})$ (Proposition 4.4.16), and $𝑆$ the compression of $𝑇$ to $𝑊$ . For a basis $𝒟︀$ of $𝑊$ and $ℬ︀ = 𝐛_{1}, 𝒟︀$ , Lemma 7.5.11(b) gives

{[𝑇]}_{ℬ︀} = (\begin{matrix} 𝜆_{1} & 𝑋 \\ 0 & {[𝑆]}_{𝒟︀} \end{matrix}),

so, taking $det (𝑥 𝐼_{𝑛} - \cdot)$ with Theorem 5.4.26, $𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}$ . Cancelling $𝑥 - 𝜆_{1}$ from $(𝑥 - 𝜆_{1}) 𝑝_{𝑆} =$ $(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛})$ (Corollary 7.1.7) gives $𝑝_{𝑆} =$ $(𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛})$ : the eigenvalues of $𝑆$ counted with multiplicity are $𝜆_{2}, \dots, 𝜆_{𝑛}$ . By the induction hypothesis, $𝑊$ has a basis $𝒟︀ = 𝐛_{2}, \dots, 𝐛_{𝑛}$ with ${[𝑆]}_{𝒟︀}$ upper triangular with diagonal $𝜆_{2}, \dots, 𝜆_{𝑛}$ in this order. Then the displayed block matrix is upper triangular with diagonal $𝜆_{1}, 𝜆_{2}, \dots, 𝜆_{𝑛}$ .

If $𝑉$ is an inner product space, choose $𝐛_{1}$ of norm $1$ and $𝑊 = {span (𝐛_{1})}^{⟂}$ , a complement by Theorem 6.4.24, and apply the inner product version of the induction hypothesis to $𝑊$ . Then $𝐛_{1}, 𝐛_{2}, \dots, 𝐛_{𝑛}$ is orthonormal.

Exercise 7.5.39.standardBeyond 21-242 Let

𝐴 \in ℂ^{𝑛 \times 𝑛}

, and write

𝐴 = 𝑆 𝑅 𝑆^{- 1}

as in Corollary 7.5.14. Let

𝑆 = 𝑄 𝑅^{'}

be the QR factorization of

𝑆

(Theorem 6.4.38). Show that

𝐴 = 𝑄 𝑅^{″} 𝑄^{*}

with

𝑅^{″} = 𝑅^{'} 𝑅 𝑅^{' - 1}

upper triangular with the same diagonal as

𝑅

. Explain why this is the first proof of Theorem 7.5.18 in matrix form.

Solution.

Uses. Theorem 6.4.38 (QR factorization), Corollary 7.5.14 (Triangularizing a matrix), Proposition 2.4.36 (Products of upper triangular matrices), Exercise 7.5.34, Definition 6.3.33 (Unitary and orthogonal matrices)

Hint 1.

𝑆

is invertible, so its columns are independent and Theorem 6.4.38 applies, with

𝑄

square.

Hint 2. Substitute

𝑆 = 𝑄 𝑅^{'}

into

𝐴 = 𝑆 𝑅 𝑆^{- 1}

. Inverses and products of invertible upper-triangular matrices are upper triangular (Exercise 7.5.34(b), Proposition 2.4.36).

Sketch.

𝐴 =

𝑄 𝑅^{'} 𝑅 𝑅^{' - 1} 𝑄^{- 1}

and

𝑄^{- 1} = 𝑄^{*}

. The product

𝑅^{'} 𝑅 𝑅^{' - 1}

is upper triangular with diagonal

𝑟_{𝑗 𝑗}^{'} 𝑟_{𝑗 𝑗} 𝑟_{𝑗 𝑗}^{' - 1} =

𝑟_{𝑗 𝑗}

. The columns of

𝑄

are Gram–Schmidt applied to the columns of

𝑆

, the triangularizing basis, which is exactly the first proof.

The columns of $𝑆$ form a basis of $ℂ^{𝑛}$ , so by Theorem 6.4.38, $𝑆 = 𝑄 𝑅^{'}$ with $𝑄 \in ℂ^{𝑛 \times 𝑛}$ having orthonormal columns, hence unitary (Definition 6.3.33), and $𝑅^{'}$ upper triangular with positive diagonal entries, hence invertible. Then

𝐴 = 𝑆 𝑅 𝑆^{- 1} = 𝑄 𝑅^{'} 𝑅 𝑅^{' - 1} 𝑄^{- 1} = 𝑄 𝑅^{″} 𝑄^{*} .

By Exercise 7.5.34(b) (whose argument applies to any invertible upper-triangular matrix), $𝑅^{' - 1}$ is upper triangular with diagonal entries $1 / 𝑟_{𝑗 𝑗}^{'}$ , and by Proposition 2.4.36, $𝑅^{″} = 𝑅^{'} 𝑅 𝑅^{' - 1}$ is upper triangular with diagonal entries $𝑟_{𝑗 𝑗}^{'} 𝑟_{𝑗 𝑗} (1 / 𝑟_{𝑗 𝑗}^{'}) =$ $𝑟_{𝑗 𝑗}$ .

By Theorem 6.4.38, the columns of $𝑄$ are the output of Gram–Schmidt applied to the columns of $𝑆$ , which form a basis triangularizing $𝑇_{𝐴}$ . So this is the first proof of Theorem 7.5.18: Gram–Schmidt applied to a triangularizing basis. The triangular factor $𝑅^{'}$ records the change of basis between the two bases with the same flag, and conjugating by it keeps $𝑅$ triangular.

Exercise 7.5.40.standard

(a)Show that an upper-triangular unitary matrix $𝑅 \in ℂ^{𝑛 \times 𝑛}$ is diagonal, with $| 𝑟_{𝑗 𝑗} | = 1$ for every $𝑗$ .
(b)Deduce that every unitary $𝐴 \in ℂ^{𝑛 \times 𝑛}$ can be written as $𝐴 = 𝑈 𝐷 𝑈^{*}$ with $𝑈$ unitary and $𝐷$ diagonal.

Solution.

Uses. Definition 6.3.33 (Unitary and orthogonal matrices), Exercise 7.5.34, Theorem 7.5.18 (Schur’s theorem), Exercise 6.3.37, Proposition 6.3.27 (Properties of the conjugate transpose)

Hint 1.

𝑅^{- 1} = 𝑅^{*}

. One side is upper triangular and the other lower triangular.

Hint 2. Alternatively, look at the columns: the first column

(𝑟_{11}, 0, \dots, 0)

is a unit vector, and every other column is orthogonal to it.

Hint 3. For (b), apply Schur’s theorem and check that

𝑅 = 𝑈^{*} 𝐴 𝑈

is unitary.

Sketch. (a)

𝑅^{*} = 𝑅^{- 1}

is upper triangular (Exercise 7.5.34(b)) and lower triangular (as the conjugate transpose of an upper-triangular matrix), so it is diagonal, and so is

𝑅

; then

𝑅^{*} 𝑅 = 𝐼_{𝑛}

gives

{| 𝑟_{𝑗 𝑗} |}^{2} = 1

. (b) Schur gives

𝐴 = 𝑈 𝑅 𝑈^{*}

, and

𝑅 = 𝑈^{*} 𝐴 𝑈

is a product of unitary matrices.

(a) Since $𝑅$ is unitary, $𝑅^{- 1} = 𝑅^{*}$ . By (the argument of) Exercise 7.5.34(b), the inverse of an invertible upper-triangular matrix is upper triangular, so $𝑅^{*}$ is upper triangular. But the $(𝑖, 𝑗)$ entry of $𝑅^{*}$ is $𝑟_{𝑗 𝑖}$ , which is $0$ for $𝑖 < 𝑗$ , so $𝑅^{*}$ is also lower triangular. Hence $𝑅^{*}$ is diagonal, and so is $𝑅 = {(𝑅^{*})}^{*}$ . Finally the $(𝑗, 𝑗)$ entry of $𝑅^{*} 𝑅 = 𝐼_{𝑛}$ is $𝑟_{𝑗 𝑗} 𝑟_{𝑗 𝑗} =$ ${| 𝑟_{𝑗 𝑗} |}^{2} =$ $1$ .

(b) By Theorem 7.5.18, $𝐴 = 𝑈 𝑅 𝑈^{*}$ with $𝑈$ unitary and $𝑅$ upper triangular. Then $𝑅 = 𝑈^{*} 𝐴 𝑈$ is a product of unitary matrices, so it is unitary (Exercise 6.3.37). By (a), $𝑅$ is diagonal; take $𝐷 = 𝑅$ .

Exercise 7.5.41.hard Let $𝐴 \in ℂ^{𝑛 \times 𝑛}$ have eigenvalues $𝜆_{1}, \dots, 𝜆_{𝑛}$ , counted with multiplicity. Prove Schur’s inequality

\sum_{𝑗 = 1}^{𝑛} {| 𝜆_{𝑗} |}^{2} \leq \sum_{𝑖, 𝑗 = 1}^{𝑛} {| 𝑎_{𝑖 𝑗} |}^{2},

with equality if and only if $𝐴 = 𝑈 𝐷 𝑈^{*}$ for some unitary $𝑈$ and diagonal $𝐷$ .

Solution.

Uses. Theorem 7.5.18 (Schur’s theorem), Proposition 6.1.16 (Frobenius inner product), Proposition 2.4.28 (Cyclicity of the trace), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 7.5.8 (The diagonal of a triangular matrix)

Techniques. The trace of $𝐴^{*} 𝐴$ (Technique 6.1.18), Cyclicity of trace (Technique 2.4.29)

Hint 1. The right side is

tr (𝐴^{*} 𝐴)

(Proposition 6.1.16). How does it change when

𝐴

is replaced by

𝑈^{*} 𝐴 𝑈

Hint 2. For a Schur form

𝑅 = 𝑈^{*} 𝐴 𝑈

tr (𝐴^{*} 𝐴) =

tr (𝑅^{*} 𝑅) =

\sum_{𝑖, 𝑗} {| 𝑟_{𝑖 𝑗} |}^{2}

, and the diagonal of

𝑅

lists the eigenvalues.

Sketch. With

𝐴 = 𝑈 𝑅 𝑈^{*}

𝐴^{*} 𝐴 = 𝑈 𝑅^{*} 𝑅 𝑈^{*}

, so

tr (𝐴^{*} 𝐴) =

tr (𝑅^{*} 𝑅 𝑈^{*} 𝑈) =

tr (𝑅^{*} 𝑅)

. Hence

\sum {| 𝑎_{𝑖 𝑗} |}^{2} =

\sum {| 𝑟_{𝑖 𝑗} |}^{2} =

\sum_{𝑗} {| 𝜆_{𝑗} |}^{2} +

\sum_{𝑖 < 𝑗} {| 𝑟_{𝑖 𝑗} |}^{2}

. Equality holds exactly when

𝑅

is diagonal.

By Theorem 7.5.18, $𝐴 = 𝑈 𝑅 𝑈^{*}$ with $𝑈$ unitary and $𝑅$ upper triangular with diagonal $𝜆_{1}, \dots, 𝜆_{𝑛}$ (in some order). By Proposition 6.3.27, $𝐴^{*} = 𝑈 𝑅^{*} 𝑈^{*}$ , so $𝐴^{*} 𝐴 =$ $𝑈 𝑅^{*} 𝑈^{*} 𝑈 𝑅 𝑈^{*} =$ $𝑈 𝑅^{*} 𝑅 𝑈^{*}$ . By Proposition 6.1.16 and Proposition 2.4.28,

\sum_{𝑖, 𝑗} {| 𝑎_{𝑖 𝑗} |}^{2} = tr (𝐴^{*} 𝐴) = tr (𝑈 (𝑅^{*} 𝑅 𝑈^{*})) = tr (𝑅^{*} 𝑅 𝑈^{*} 𝑈) = tr (𝑅^{*} 𝑅) = \sum_{𝑖, 𝑗} {| 𝑟_{𝑖 𝑗} |}^{2} .

Since $𝑅$ is upper triangular,

\sum_{𝑖, 𝑗} {| 𝑟_{𝑖 𝑗} |}^{2} = \sum_{𝑗 = 1}^{𝑛} {| 𝜆_{𝑗} |}^{2} + \sum_{𝑖 < 𝑗} {| 𝑟_{𝑖 𝑗} |}^{2} \geq \sum_{𝑗 = 1}^{𝑛} {| 𝜆_{𝑗} |}^{2},

which is the inequality.

If equality holds, then $𝑟_{𝑖 𝑗} = 0$ for all $𝑖 < 𝑗$ , so $𝑅$ is diagonal and $𝐴 = 𝑈 𝑅 𝑈^{*}$ has the required form. Conversely, if $𝐴 = 𝑈 𝐷 𝑈^{*}$ with $𝐷$ diagonal, then $𝐷$ is upper triangular, its diagonal lists the eigenvalues of $𝐴$ (Proposition 7.5.8, Proposition 7.5.9), and the computation above with $𝑅 = 𝐷$ gives equality. (In Section 8.2 such matrices are identified as the normal ones, $𝐴^{*} 𝐴 = 𝐴 𝐴^{*}$ .)

Exercise 7.5.42.hard Let

𝐴 \in ℝ^{𝑛 \times 𝑛}

, and suppose that

𝑝_{𝐴}

splits over

ℝ

, that is, all eigenvalues of

𝐴

are real. Show that

𝐴 = 𝑄 𝑅 𝑄^{𝖳}

with

𝑄 \in ℝ^{𝑛 \times 𝑛}

orthogonal and

𝑅 \in ℝ^{𝑛 \times 𝑛}

upper triangular.

Solution.

Uses. Theorem 7.3.6 (Eigenvalues are the roots of the characteristic polynomial), Lemma 7.5.11 (Compressing an operator to a complement), Theorem 5.4.26 (Block-triangular matrices), Corollary 7.1.7 (No zero divisors, cancellation, and units), Theorem 6.4.24 (Orthogonal decomposition), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Theorem 4.5.17 (Change of basis)

Techniques. Induction on dimension via an invariant subspace (Technique 7.5.12)

Hint 1. The second proof of Theorem 7.5.18 only used

ℂ

to find an eigenvalue. Over

ℝ

, with a split characteristic polynomial, an eigenvalue exists. What has to be checked for the compression?

Hint 2. Show that the compression

𝑆

{span (𝐮_{1})}^{⟂}

satisfies

𝑝_{𝐴} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}

, so

𝑝_{𝑆}

splits too.

Sketch. Prove the operator version on a real inner product space by induction on the dimension: a real root

𝜆_{1}

𝑝_{𝑇}

gives a unit eigenvector

𝐮_{1}

; the compression

𝑆

𝑊 = {span (𝐮_{1})}^{⟂}

has

𝑝_{𝑇} = (𝑥 - 𝜆_{1}) 𝑝_{𝑆}

by Lemma 7.5.11(b), so

𝑝_{𝑆}

splits; by induction

𝑊

has an orthonormal basis triangularizing

𝑆

, and

𝐮_{1}

followed by it triangularizes

𝑇

. Apply this to

𝑇_{𝐴}

ℝ^{𝑛}

We prove: if $𝑉$ is a real inner product space with $1 \leq dim 𝑉 = 𝑛 < \infty$ and $𝑇 \in L (𝑉)$ has $𝑝_{𝑇}$ splitting over $ℝ$ , then $𝑉$ has an orthonormal basis triangularizing $𝑇$ . Applied to $𝑇_{𝐴}$ on $ℝ^{𝑛}$ with the dot product, with $𝑄$ the matrix whose columns are that basis, this gives $𝑄^{𝖳} 𝐴 𝑄 = 𝑅$ upper triangular by Theorem 4.5.17, since $𝑄^{- 1} = 𝑄^{𝖳}$ for orthogonal $𝑄$ .

Induct on $𝑛$ ; for $𝑛 = 1$ any unit vector works. Let $𝑛 \geq 2$ and $𝑝_{𝑇} =$ $(𝑥 - 𝜇_{1}) \dots (𝑥 - 𝜇_{𝑛})$ with real $𝜇_{𝑖}$ . Then $𝜇_{1}$ is an eigenvalue (Theorem 7.3.6); let $𝐮_{1}$ be an eigenvector of norm $1$ . Let $𝑊 = {span (𝐮_{1})}^{⟂}$ , a complement of $span (𝐮_{1})$ of dimension $𝑛 - 1$ (Theorem 6.4.24), and let $𝑆 𝐰 =$ $𝑇 𝐰 -$ $⟨ 𝑇 𝐰, 𝐮_{1} ⟩ 𝐮_{1}$ , the compression of $𝑇$ to $𝑊$ (as in the second proof of Theorem 7.5.18). For any basis $𝒟︀$ of $𝑊$ , Lemma 7.5.11(b) and Theorem 5.4.26 give $𝑝_{𝑇} = (𝑥 - 𝜇_{1}) 𝑝_{𝑆}$ , and cancelling (Corollary 7.1.7) gives $𝑝_{𝑆} =$ $(𝑥 - 𝜇_{2}) \dots (𝑥 - 𝜇_{𝑛})$ , which splits. By the induction hypothesis, $𝑊$ has an orthonormal basis $𝐮_{2}, \dots, 𝐮_{𝑛}$ with $𝑆 𝐮_{𝑗} \in$ $span (𝐮_{2}, \dots, 𝐮_{𝑗})$ . Exactly as in the second proof of Theorem 7.5.18, $𝐮_{1}, \dots, 𝐮_{𝑛}$ is an orthonormal basis of $𝑉$ and $𝑇 𝐮_{𝑗} =$ $⟨ 𝑇 𝐮_{𝑗}, 𝐮_{1} ⟩ 𝐮_{1} +$ $𝑆 𝐮_{𝑗} \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑗})$ , so $𝑇$ is upper triangular with respect to it (Proposition 7.5.2).

Exercise 7.5.43.hard Let

𝐴 \in ℂ^{𝑛 \times 𝑛}

with

tr (𝐴^{𝑘}) = 0

for

𝑘 = 1, 2, \dots, 𝑛

. Show that

𝐴^{𝑛} = 0

. Then show that the statement fails over

𝔽_{𝑝}

Solution.

Uses. Exercise 7.5.34, Exercise 7.5.36, Theorem 5.5.21 (The Vandermonde determinant), Corollary 3.5.25 (The invertible matrix theorem), Theorem 5.4.14 (The transpose)

Hint 1. Group the nonzero eigenvalues: let

𝜇_{1}, \dots, 𝜇_{𝑟}

be the distinct nonzero ones, with algebraic multiplicities

𝑚_{1}, \dots, 𝑚_{𝑟} \geq 1

. By Exercise 7.5.36 it suffices to show

𝑟 = 0

Hint 2. By Exercise 7.5.34(a),

\sum_{𝑗} 𝑚_{𝑗} 𝜇_{𝑗}^{𝑘} = 0

for

𝑘 = 1, \dots, 𝑟

. This is a square linear system for

(𝑚_{1}, \dots, 𝑚_{𝑟})

Hint 3. Its matrix is a Vandermonde matrix times

diag (𝜇_{1}, \dots, 𝜇_{𝑟})

. For

𝔽_{𝑝}

, try

𝐼_{𝑝}

Sketch. If there are distinct nonzero eigenvalues

𝜇_{1}, \dots, 𝜇_{𝑟}

with multiplicities

𝑚_{𝑗}

, then

\sum_{𝑗} 𝑚_{𝑗} 𝜇_{𝑗}^{𝑘} =

tr (𝐴^{𝑘}) =

0

for

𝑘 = 1, \dots, 𝑟

. The coefficient matrix

{(𝜇_{𝑗}^{𝑘})}_{𝑘, 𝑗}

has determinant

𝜇_{1} \dots 𝜇_{𝑟} \prod_{𝑖 < 𝑗} (𝜇_{𝑗} - 𝜇_{𝑖}) \neq

0

, so all

𝑚_{𝑗} = 0

ℂ

, which is absurd. So

0

is the only eigenvalue, and

𝐴^{𝑛} = 0

. Over

𝔽_{𝑝}

tr (𝐼_{𝑝}^{𝑘}) = 𝑝 * 1 = 0

for all

𝑘

, but

𝐼_{𝑝}^{𝑝} \neq 0

Let $𝜇_{1}, \dots, 𝜇_{𝑟}$ be the distinct nonzero eigenvalues of $𝐴$ , with algebraic multiplicities $𝑚_{1}, \dots, 𝑚_{𝑟} \geq 1$ , and suppose $𝑟 \geq 1$ . The eigenvalues of $𝐴$ counted with multiplicity are these, each repeated $𝑚_{𝑗}$ times, together with $0$ repeated $𝑛 - \sum 𝑚_{𝑗}$ times. By Exercise 7.5.34(a), for $𝑘 = 1, \dots, 𝑟$ (note $𝑟 \leq 𝑛$ ),

0 = tr (𝐴^{𝑘}) = 𝑚_{1} 𝜇_{1}^{𝑘} + 𝑚_{2} 𝜇_{2}^{𝑘} + \dots + 𝑚_{𝑟} 𝜇_{𝑟}^{𝑘},

where $𝑚_{𝑗}$ stands for $𝑚_{𝑗} * 1 \in ℂ$ . So $𝑀 𝐜 = 𝟎$ , where $𝐜 = (𝑚_{1}, \dots, 𝑚_{𝑟})$ and $𝑀 \in ℂ^{𝑟 \times 𝑟}$ has entries $𝑀_{𝑘 𝑗} = 𝜇_{𝑗}^{𝑘}$ . Factoring $𝜇_{𝑗}$ out of column $𝑗$ , $𝑀 =$ $𝑉^{'} diag (𝜇_{1}, \dots, 𝜇_{𝑟})$ with $𝑉_{𝑘 𝑗}^{'} = 𝜇_{𝑗}^{𝑘 - 1}$ , the transpose of the Vandermonde matrix of $𝜇_{1}, \dots, 𝜇_{𝑟}$ . By Theorem 5.5.21 and Theorem 5.4.14,

det 𝑀 = 𝜇_{1} 𝜇_{2} \dots 𝜇_{𝑟} \prod_{𝑖 < 𝑗} (𝜇_{𝑗} - 𝜇_{𝑖}) \neq 0,

since the $𝜇_{𝑗}$ are nonzero and distinct. So $𝑀$ is invertible (Corollary 3.5.25), $𝐜 = 𝟎$ , and $𝑚_{1} = 0$ in $ℂ$ , contradicting $𝑚_{1} \geq 1$ . Hence $𝑟 = 0$ : $0$ is the only eigenvalue of $𝐴$ , and $𝐴^{𝑛} = 0$ by Exercise 7.5.36.

Over $𝔽_{𝑝}$ , take $𝐴 = 𝐼_{𝑝} \in 𝔽_{𝑝}^{𝑝 \times 𝑝}$ . Then $tr (𝐴^{𝑘}) =$ $tr 𝐼_{𝑝} =$ $𝑝 * 1 =$ $0$ for every $𝑘$ , but $𝐴^{𝑝} = 𝐼_{𝑝} \neq 0$ . The proof breaks at its last step: in $𝔽_{𝑝}$ , the conclusion $𝑚_{1} * 1 = 0$ is no contradiction when $𝑝$ divides $𝑚_{1}$ , as here, where $𝑚_{1} = 𝑝$ .

Exercise 7.5.44.hard Let

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

satisfy

𝐴 𝐵 - 𝐵 𝐴 = 𝐴

. Show that

𝐴^{𝑛} = 0

Solution (traces of powers).

Uses. Proposition 2.4.28 (Cyclicity of the trace), Proposition 2.4.27 (The trace is linear), Exercise 7.5.43

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. Compute

𝐴^{2} 𝐵 - 𝐵 𝐴^{2}

in terms of

𝐴^{2}

. Guess a formula for

𝐴^{𝑘} 𝐵 - 𝐵 𝐴^{𝑘}

Hint 2. Prove

𝐴^{𝑘} 𝐵 -

𝐵 𝐴^{𝑘} =

𝑘 𝐴^{𝑘}

by induction, then take the trace.

Sketch. By induction,

𝐴^{𝑘 + 1} 𝐵 -

𝐵 𝐴^{𝑘 + 1} =

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

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

𝑘 𝐴^{𝑘 + 1} +

𝐴^{𝑘 + 1}

, so

𝐴^{𝑘} 𝐵 -

𝐵 𝐴^{𝑘} =

𝑘 𝐴^{𝑘}

. Taking traces,

𝑘 tr (𝐴^{𝑘}) = 0

, so

tr (𝐴^{𝑘}) = 0

for all

𝑘 \geq 1

, and Exercise 7.5.43 gives

𝐴^{𝑛} = 0

We show $𝐴^{𝑘} 𝐵 -$ $𝐵 𝐴^{𝑘} =$ $𝑘 𝐴^{𝑘}$ for $𝑘 \geq 1$ by induction. For $𝑘 = 1$ this is the hypothesis. If it holds for $𝑘$ , then

\begin{aligned} 𝐴^{𝑘 + 1} 𝐵 - 𝐵 𝐴^{𝑘 + 1} & = 𝐴 (𝐴^{𝑘} 𝐵 - 𝐵 𝐴^{𝑘}) + (𝐴 𝐵 - 𝐵 𝐴) 𝐴^{𝑘} \\ = 𝐴 (𝑘 𝐴^{𝑘}) + 𝐴 𝐴^{𝑘} = (𝑘 + 1) 𝐴^{𝑘 + 1} . \end{aligned}

Taking traces, using Proposition 2.4.27 and Proposition 2.4.28, $𝑘 tr (𝐴^{𝑘}) =$ $tr (𝐴^{𝑘} 𝐵) -$ $tr (𝐵 𝐴^{𝑘}) =$ $0$ , so $tr (𝐴^{𝑘}) = 0$ for every $𝑘 \geq 1$ , since $𝑘 \neq 0$ in $ℂ$ . By Exercise 7.5.43, $𝐴^{𝑛} = 0$ .

Solution (eigenvalues of a map on matrices).

Uses. Corollary 7.2.22 (At most $dim 𝑉$ eigenvalues), Corollary 4.1.27 (A nilpotent operator dies within $dim 𝑉$ steps)

Techniques. Study a linear map on a space of matrices (Technique 4.2.29), Cyclicity of trace (Technique 2.4.29)

Hint 1. Consider the operator

𝐿 (𝑋) = 𝐵 𝑋 - 𝑋 𝐵

ℂ^{𝑛 \times 𝑛}

. What does it do to

𝐴

, to

𝐴^{2}

, to

𝐴^{𝑘}

Hint 2. If no power of

𝐴

were

0

𝐿

would have infinitely many eigenvalues.

Sketch. The identity

𝐴^{𝑘} 𝐵 -

𝐵 𝐴^{𝑘} =

𝑘 𝐴^{𝑘}

says

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

for

𝐿 (𝑋) = 𝐵 𝑋 - 𝑋 𝐵

. If

𝐴^{𝑘} \neq 0

for every

𝑘

, then

- 1, - 2, - 3, \dots

are all eigenvalues of

𝐿

, an operator on the

𝑛^{2}

-dimensional space

ℂ^{𝑛 \times 𝑛}

, which has at most

𝑛^{2}

eigenvalues. So some

𝐴^{𝑘} = 0

, and then

𝐴^{𝑛} = 0

As in the first approach,

𝐴^{𝑘} 𝐵 -

𝐵 𝐴^{𝑘} =

𝑘 𝐴^{𝑘}

for all

𝑘 \geq 1

. Let

𝐿 \in L (ℂ^{𝑛 \times 𝑛})

𝐿 (𝑋) = 𝐵 𝑋 - 𝑋 𝐵

. Then

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

. If

𝐴^{𝑘} \neq 0

for every

𝑘 \geq 1

, then

- 1, - 2, \dots, - (𝑛^{2} + 1)

are

𝑛^{2} + 1

distinct eigenvalues of

𝐿

, which is impossible, since

dim ℂ^{𝑛 \times 𝑛} = 𝑛^{2}

(Corollary 7.2.22). So

𝐴^{𝑘} = 0

for some

𝑘

, and then

𝐴^{𝑛} = 0

(Corollary 4.1.27).

Exercise 7.5.45.hard Let $𝐴 \in ℂ^{𝑛 \times 𝑛}$ have eigenvalues $𝜆_{1}, \dots, 𝜆_{𝑛}$ , counted with multiplicity, and let $𝐿_{𝐴} \in L (ℂ^{𝑛 \times 𝑛})$ be $𝐿_{𝐴} (𝑋) =$ $𝐴 𝑋 -$ $𝑋 𝐴$ . Use the matrix units $𝑈_{𝑖 𝑗} = 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ (Lemma 2.4.24).

(a)Suppose $𝐴$ is upper triangular. List the matrix units row by row, and within each row from right to left: $𝑈_{1 𝑛},$ $𝑈_{1, 𝑛 - 1},$ $\dots,$ $𝑈_{11},$ $𝑈_{2 𝑛},$ $\dots,$ $𝑈_{21},$ $\dots,$ $𝑈_{𝑛 1}$ . Show that $𝐿_{𝐴}$ is upper triangular with respect to this basis, with diagonal entry $𝑎_{𝑖 𝑖} - 𝑎_{𝑗 𝑗}$ at $𝑈_{𝑖 𝑗}$ .
(b)Deduce that for every $𝐴$ , the eigenvalues of $𝐿_{𝐴}$ counted with multiplicity are the $𝑛^{2}$ numbers $𝜆_{𝑖} - 𝜆_{𝑗}$ ( $1 \leq 𝑖, 𝑗 \leq 𝑛$ ).
(c)Deduce again that $tr 𝐿_{𝐴} = 0$ , and that $𝐿_{𝐴}$ is not invertible.

Solution.

Uses. Lemma 2.4.24 (Matrix units), Proposition 7.5.2 (Upper-triangular matrices and invariant subspaces), Proposition 7.5.9 (Multiplicities on the diagonal), Corollary 7.5.14 (Triangularizing a matrix), Theorem 7.5.22 (Trace and determinant from eigenvalues)

Techniques. Study a linear map on a space of matrices (Technique 4.2.29), Prove it for triangular matrices first (Technique 7.5.23)

Hint 1. Compute

𝐴 𝑈_{𝑖 𝑗}

(column

𝑖

𝐴

, moved to column

𝑗

) and

𝑈_{𝑖 𝑗} 𝐴

(row

𝑗

𝐴

, moved to row

𝑖

), using that

𝐴

is upper triangular.

Hint 2. Which matrix units appear in

𝐿_{𝐴} (𝑈_{𝑖 𝑗})

besides

𝑈_{𝑖 𝑗}

? Do they come before

𝑈_{𝑖 𝑗}

in the given order?

Hint 3. For (b), if

𝐴 = 𝑆 𝑅 𝑆^{- 1}

, then

𝐿_{𝐴}

is conjugate to

𝐿_{𝑅}

by the invertible operator

𝑋 \mapsto 𝑆 𝑋 𝑆^{- 1}

Sketch. (a)

𝐴 𝑈_{𝑖 𝑗} =

\sum_{𝑘 \leq 𝑖} 𝑎_{𝑘 𝑖} 𝑈_{𝑘 𝑗}

and

𝑈_{𝑖 𝑗} 𝐴 =

\sum_{𝑙 \geq 𝑗} 𝑎_{𝑗 𝑙} 𝑈_{𝑖 𝑙}

, so

𝐿_{𝐴} (𝑈_{𝑖 𝑗}) =

(𝑎_{𝑖 𝑖} - 𝑎_{𝑗 𝑗}) 𝑈_{𝑖 𝑗}

plus units

𝑈_{𝑘 𝑗}

with

𝑘 < 𝑖

(earlier rows) and

𝑈_{𝑖 𝑙}

with

𝑙 > 𝑗

(earlier in the same row). (b) With

𝐴 = 𝑆 𝑅 𝑆^{- 1}

and

𝐶 (𝑋) = 𝑆 𝑋 𝑆^{- 1}

𝐿_{𝐴} \circ 𝐶 = 𝐶 \circ 𝐿_{𝑅}

, so

𝐿_{𝐴}

is upper triangular in the basis

𝐶 (𝑈_{𝑖 𝑗})

with diagonal

𝑟_{𝑖 𝑖} - 𝑟_{𝑗 𝑗}

. (c) The sum of all

𝜆_{𝑖} - 𝜆_{𝑗}

0

, and the terms with

𝑖 = 𝑗

are

0

, so

det 𝐿_{𝐴} = 0

(a) By Lemma 2.4.24, $𝐴 𝑈_{𝑖 𝑗} =$ $(𝐴 𝐞_{𝑖}) 𝐞_{𝑗}^{𝖳} =$ $\sum_{𝑘} 𝑎_{𝑘 𝑖} 𝑈_{𝑘 𝑗}$ and $𝑈_{𝑖 𝑗} 𝐴 =$ $𝐞_{𝑖} (𝐞_{𝑗}^{𝖳} 𝐴) =$ $\sum_{𝑙} 𝑎_{𝑗 𝑙} 𝑈_{𝑖 𝑙}$ . Since $𝐴$ is upper triangular, $𝑎_{𝑘 𝑖} = 0$ for $𝑘 > 𝑖$ and $𝑎_{𝑗 𝑙} = 0$ for $𝑙 < 𝑗$ , so

𝐿_{𝐴} (𝑈_{𝑖 𝑗}) = (𝑎_{𝑖 𝑖} - 𝑎_{𝑗 𝑗}) 𝑈_{𝑖 𝑗} + \sum_{𝑘 < 𝑖} 𝑎_{𝑘 𝑖} 𝑈_{𝑘 𝑗} - \sum_{𝑙 > 𝑗} 𝑎_{𝑗 𝑙} 𝑈_{𝑖 𝑙} .

In the given order, every $𝑈_{𝑘 𝑗}$ with $𝑘 < 𝑖$ lies in an earlier row, and every $𝑈_{𝑖 𝑙}$ with $𝑙 > 𝑗$ lies earlier in the same row. So $𝐿_{𝐴} (𝑈_{𝑖 𝑗})$ lies in the span of $𝑈_{𝑖 𝑗}$ and the units before it, and by Proposition 7.5.2, $𝐿_{𝐴}$ is upper triangular in this basis, with diagonal entry $𝑎_{𝑖 𝑖} - 𝑎_{𝑗 𝑗}$ at $𝑈_{𝑖 𝑗}$ .

(b) By Corollary 7.5.14, $𝐴 = 𝑆 𝑅 𝑆^{- 1}$ with $𝑅$ upper triangular, $𝑟_{𝑖 𝑖} = 𝜆_{𝑖}$ after reordering. Let $𝐶 \in L (ℂ^{𝑛 \times 𝑛})$ be $𝐶 (𝑋) = 𝑆 𝑋 𝑆^{- 1}$ , which is invertible with inverse $𝑋 \mapsto 𝑆^{- 1} 𝑋 𝑆$ . For every $𝑋$ ,

𝐿_{𝐴} (𝐶 (𝑋)) = 𝑆 𝑅 𝑆^{- 1} 𝑆 𝑋 𝑆^{- 1} - 𝑆 𝑋 𝑆^{- 1} 𝑆 𝑅 𝑆^{- 1} = 𝑆 (𝑅 𝑋 - 𝑋 𝑅) 𝑆^{- 1} = 𝐶 (𝐿_{𝑅} (𝑋)) .

So if $𝒰︀$ is the ordered basis of (a), then $𝐶 (𝒰︀)$ is a basis (the image of a basis under an isomorphism), and $𝐿_{𝐴}$ sends $𝐶 (𝑈_{𝑖 𝑗})$ to $𝐶 (𝐿_{𝑅} (𝑈_{𝑖 𝑗}))$ , which has the same coordinates in $𝐶 (𝒰︀)$ as $𝐿_{𝑅} (𝑈_{𝑖 𝑗})$ has in $𝒰︀$ . Hence ${[𝐿_{𝐴}]}_{𝐶 (𝒰︀)} =$ ${[𝐿_{𝑅}]}_{𝒰︀}$ is upper triangular with diagonal entries $𝜆_{𝑖} - 𝜆_{𝑗}$ , and by Proposition 7.5.9 these are the eigenvalues of $𝐿_{𝐴}$ counted with multiplicity.

(c) By Theorem 7.5.22, $tr 𝐿_{𝐴} =$ $\sum_{𝑖, 𝑗} (𝜆_{𝑖} - 𝜆_{𝑗}) =$ $𝑛 \sum_{𝑖} 𝜆_{𝑖} -$ $𝑛 \sum_{𝑗} 𝜆_{𝑗} =$ $0$ , and $det 𝐿_{𝐴} =$ $\prod_{𝑖, 𝑗} (𝜆_{𝑖} - 𝜆_{𝑗}) =$ $0$ , because the factors with $𝑖 = 𝑗$ vanish. So $𝐿_{𝐴}$ is not invertible. (Directly: $𝐿_{𝐴} (𝐼_{𝑛}) = 0$ .)

Exercise 7.5.46.standardBeyond 21-242 Let $𝐴 =$ $(\begin{matrix} 0 & 2 & - 1 \\ 0 & 1 & 0 \\ 1 & - 1 & 0 \end{matrix}) \in$ $ℝ^{3 \times 3}$ .

(a)Check that $(1, 0, - 𝑖)$ is an eigenvector of $𝐴$ over $ℂ$ , and use it to find a two-dimensional $𝑇_{𝐴}$ -invariant subspace of $ℝ^{3}$ .
(b)Find a basis of $ℝ^{3}$ in which $𝑇_{𝐴}$ has the form of Theorem 7.5.27(a).
(c)Find an orthogonal $𝑄$ such that $𝑄^{𝖳} 𝐴 𝑄$ is a real Schur form.

Solution.

Uses. Theorem 7.5.27 (Real block upper-triangular form), Lemma 7.5.11 (Compressing an operator to a complement)

Hint 1. Split

(1, 0, - 𝑖)

into real and imaginary parts

𝐱 + 𝑖 𝐲

and compute

𝐴 𝐱

and

𝐴 𝐲

Hint 2. For (b), add a real eigenvector. For (c), the invariant plane already has an orthonormal basis; compress to its orthogonal complement.

Sketch.

𝐴 (1, 0, - 𝑖) =

(𝑖, 0, 1) =

𝑖 (1, 0, - 𝑖)

. With

𝐱 = 𝐞_{1}

𝐲 = - 𝐞_{3}

𝐴 𝐱 = - 𝐲

𝐴 𝐲 = 𝐱

, so

span (𝐞_{1}, 𝐞_{3})

is invariant. (b)

(3, 2, 1)

is an eigenvector for

1

, and in the basis

𝐱, 𝐲, (3, 2, 1)

the matrix is

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

. (c)

𝑄

with columns

𝐞_{1}, - 𝐞_{3}, 𝐞_{2}

gives

𝑄^{𝖳} 𝐴 𝑄 =

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

(a) $𝐴 (1, 0, - 𝑖) =$ $(0 + 0 + 𝑖, 0, 1 + 0 + 0) =$ $(𝑖, 0, 1) =$ $𝑖 (1, 0, - 𝑖)$ , since $𝑖 (- 𝑖) = 1$ . Write $(1, 0, - 𝑖) = 𝐱 + 𝑖 𝐲$ with $𝐱 = (1, 0, 0)$ and $𝐲 = (0, 0, - 1)$ . Then

𝐴 𝐱 = (0, 0, 1) = - 𝐲, 𝐴 𝐲 = (1, 0, 0) = 𝐱,

as in the complexification argument before Theorem 7.5.27, with $𝑎 = 0$ and $𝑏 = 1$ . So $span (𝐱, 𝐲) =$ $span (𝐞_{1}, 𝐞_{3})$ is invariant, and $𝐴$ acts on it by $(\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$ in the basis $𝐱, 𝐲$ , a block with eigenvalues $\pm 𝑖$ .

(b) For the eigenvalue $1$ , $𝐴 -$ $𝐼_{3} =$ $(\begin{matrix} - 1 & 2 & - 1 \\ 0 & 0 & 0 \\ 1 & - 1 & - 1 \end{matrix})$ ; adding the first and last rows gives $𝑦 - 2 𝑧 = 0$ , so $𝑦 = 2 𝑧$ and $𝑥 = 𝑦 + 𝑧 = 3 𝑧$ , and $𝐯 = (3, 2, 1)$ is an eigenvector. In the basis $𝐱, 𝐲, 𝐯$ ,

[𝑇_{𝐴}] = (\begin{matrix} 0 & 1 & 0 \\ - 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}),

a $2 \times 2$ block without real eigenvalues followed by a $1 \times 1$ block.

(c) The plane $𝑈 = span (𝐞_{1}, 𝐞_{3})$ has the orthonormal basis $𝐞_{1}, - 𝐞_{3}$ , and $𝑈^{⟂} = span (𝐞_{2})$ . Let $𝑄$ have columns $𝐞_{1}, - 𝐞_{3}, 𝐞_{2}$ :

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

Its columns are orthonormal, so $𝑄$ is orthogonal. The columns of $𝑄^{𝖳} 𝐴 𝑄$ are the coordinates of $𝐴 𝐞_{1} = - (- 𝐞_{3})$ , $𝐴 (- 𝐞_{3}) = 𝐞_{1}$ , and $𝐴 𝐞_{2} =$ $(2, 1, - 1) =$ $2 𝐞_{1} +$ $(- 𝐞_{3}) +$ $𝐞_{2}$ in this basis:

𝑄^{𝖳} 𝐴 𝑄 = (\begin{matrix} 0 & 1 & 2 \\ - 1 & 0 & 1 \\ 0 & 0 & 1 \end{matrix}) .

The compression of $𝑇_{𝐴}$ to $𝑈^{⟂}$ is multiplication by $1$ on $span (𝐞_{2})$ , which is the bottom right entry.

More practice

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