2.8 Proof patterns · Matrix Theory

A linear map can be handled at four levels: as a map, through its values on a basis, through a matrix, or through the entries of that matrix. Once bases are fixed, all four carry the same information (Section 2.3.6), so most proofs in this chapter begin by choosing a level, and the choice decides how long the proof is. This section sorts the chapter’s proofs by the question they answer, compares the levels on examples from the chapter, and says when a tool is the wrong one. The exercises at the end practice one move at a time, and the problem set (Problems for Chapter 2) mixes them.

2.8.1Showing that a map is linear, or building one

There are three moves, and they answer different questions.

Check the definition. Expand $𝑇 (𝑎 𝐮 + 𝐯)$ and regroup, as in (iii) of Theorem 2.1.3. This verifies a map that is given by a formula, and it is the default for formulas in coordinates or coefficients (Example 2.1.7, Example 2.1.9).
Assemble the map from sums, scalar multiples, and composites of maps already known to be linear (Technique 2.1.26). This transfers linearity without computing, but it only covers the operations of $L (𝑉, 𝑊)$ . A pointwise product of two linear maps, such as $𝑥 \mapsto 𝑥 \cdot 𝑥$ , is not covered, and neither is an inverse function, whose linearity needed its own argument (Proposition 2.7.7).
Define the map on a basis and extend it (Technique 2.2.4). This creates a map with prescribed behaviour, and linearity is free. It does not show that a given formula is linear: to identify a given map with the one built on the basis, we have to evaluate the given map at a general vector, which is the first move again. The exception is a formula that already has the form (2.2.1), as for the maps of $𝐹 [𝑥]$ that move each coefficient to a fixed place (Proposition 2.2.20).

Constructions go wrong at the choices. A map defined by choosing a value for each vector separately is usually not linear (Non-example 2.7.10), and values prescribed on a spanning list must respect its linear relations (Proposition 2.2.11, Exercise 2.2.24, Exercise 2.2.26). Choices made on a basis are always safe. To show that a map is not linear, the tests $𝑇 (𝟎)$ and $𝑇 (2 𝐯)$ catch most formulas, but not over $𝔽_{2}$ , where $2 = 0$ and every function that fixes $𝟎$ is homogeneous. There, test additivity (Exercise 2.1.15(d), Exercise 2.8.5).

Example 2.8.1 (One map, three routes). The reflection $𝑆_{ℓ}$ across a line $ℓ$ through $𝟎$ appeared three times in the chapter. In Example 2.1.11 it came with a coordinate formula, obtained from the double angle formulas, and the formula has the shape of Example 2.1.7, so $𝑆_{ℓ}$ is linear by the first move. In Example 2.1.27(a) we noticed that $𝑆_{ℓ} = 2 {Pr}_{ℓ} - {id}_{ℝ^{2}}$ , which proves linearity with no trigonometry, once ${Pr}_{ℓ}$ is known to be linear. In Example 2.2.3, for the line $𝑦 = 𝑥$ , we chose $𝐛_{1} = (1, 1)$ on the line and $𝐛_{2} = (1, - 1)$ across it, and defined $𝑆$ by $𝑆 (𝐛_{1}) = 𝐛_{1}$ and $𝑆 (𝐛_{2}) = - 𝐛_{2}$ . Linearity came for free, the formula $𝑆 (𝑥, 𝑦) = (𝑦, 𝑥)$ came out of (2.2.1), and identities such as $𝑆^{2} = id$ became one-line checks on the basis (Example 2.2.8).

The formula verifies a map that is already given, assembly transfers linearity from maps we trust, and the basis creates a map from a description of what it should do. The last route has a cost: the basis must exist and must be found. Over $𝔽_{2}$ the vectors $(1, 1)$ and $(1, - 1)$ coincide, and the construction of Example 2.2.3 breaks down, although $(𝑥, 𝑦) \mapsto (𝑦, 𝑥)$ is still linear there.

Practice: Exercise 2.8.5 and Exercise 2.8.7.

2.8.2Showing that two maps or two matrices are equal

For linear maps, the default is to compare them on a basis, or on any spanning list (Technique 2.2.7, Corollary 2.2.6); on $𝐹 [𝑥]$ the monomials play the role of the basis (Proposition 2.2.20). Matrices can be compared entry by entry, column by column ( $𝐴 = 𝐵$ as soon as $𝐴 𝐞_{𝑗} = 𝐵 𝐞_{𝑗}$ for every $𝑗$ , by Lemma 2.4.24(b)), or through their maps ( $𝐴 = 𝐵$ as soon as $𝑇_{𝐴} = 𝑇_{𝐵}$ , by Proposition 2.3.17). Two maps are also equal when their matrices in one pair of bases are (Theorem 2.3.20(a)). Often the shortest route compares no values at all and derives the identity from identities already known, with the algebra of Proposition 2.1.24 and Proposition 2.4.14.

Before checking on a basis, check two things. Both sides must be linear in the vector being tested. An identity between sums and composites of linear maps is, but a condition such as “ $𝑇 (𝐯) \in span (𝐯)$ ” is not, and it can hold on a basis without holding everywhere (Exercise 2.2.25). And the list must be a basis over the field at hand: $(1, 1), (1, - 1)$ is a basis of $𝐹^{2}$ only when $1 + 1 \neq 0$ (Exercise 2.3.31).

Example 2.8.2 ( $𝑆^{2} = id$ , three ways). Let $ℓ$ be the line $𝑦 = 2 𝑥$ in $ℝ^{2}$ and $𝑆 = 𝑆_{ℓ}$ , whose standard matrix is $\frac{1}{5} (\begin{matrix} - 3 & 4 \\ 4 & 3 \end{matrix})$ (Example 2.3.19).

Entries. $\frac{1}{25} {(\begin{matrix} - 3 & 4 \\ 4 & 3 \end{matrix})}^{2} =$ $\frac{1}{25} (\begin{matrix} 9 + 16 & - 12 + 12 \\ - 12 + 12 & 16 + 9 \end{matrix}) =$ $𝐼_{2}$ . This settles one line; for a general line the same computation needs ${cos}^{2} 𝜃 + {sin}^{2} 𝜃 = 1$ again.

On an adapted basis. With $𝐮_{1} = (1, 2)$ on $ℓ$ and $𝐮_{2} = (- 2, 1)$ across it, $𝑆 (𝐮_{1}) = 𝐮_{1}$ and $𝑆 (𝐮_{2}) = - 𝐮_{2}$ (Example 2.3.23). So $𝑆^{2}$ fixes both basis vectors, and $𝑆^{2} = id$ by Corollary 2.2.6. This explains the identity: reflecting twice flips the perpendicular direction twice.

By algebra. $𝑆 = 2 𝑃 - id$ with $𝑃 = {Pr}_{ℓ}$ and $𝑃^{2} = 𝑃$ (Exercise 2.1.42), so by Proposition 2.1.24,

𝑆^{2} = 4 𝑃^{2} - 4 𝑃 + id = id .

This uses no basis and no coordinates, and it proves more: ${(2 𝑃 - id)}^{2} = id$ for every operator $𝑃$ with $𝑃^{2} = 𝑃$ , on every vector space over every field.

Each route is the wrong one somewhere. The entries do not show why the identity holds, the adapted basis must be found first, and the algebra needs the right identity to start from. When no convenient identity is at hand, as for $𝐷 𝑀 - 𝑀 𝐷 = id$ on $𝐹 [𝑥]$ , the computation has to be done, and the monomials are the natural place to do it (Exercise 2.4.51); the product rule gives another proof, but it is a fact about products of polynomials, which is more than the identity needs.

Practice: Exercise 2.8.6 and Exercise 2.8.8.

2.8.3Proving a matrix identity

The chapter proved its matrix identities in four ways, and many identities admit more than one.

Translate to maps (Technique 2.3.27). If both sides are built from products, sums, and scalar multiples, read them as composites and use a fact about maps. Associativity and distributivity came this way (first proof of Proposition 2.4.14), and all the work went into the dictionary, Theorem 2.4.2. The translation does not see entries, which depend on the bases while maps do not. So it does not reach the transpose, which needs more structure to mean anything for a map (Section 13.1).
Compute entry by entry (Technique 2.4.15). This is the tool for statements about entries: transposes (Proposition 2.4.23), traces (Proposition 2.4.28), triangular shapes (Proposition 2.4.36). It is mechanical, and it uses only the ring laws of the entries, which is why it also proves associativity for block matrices, whose entries do not commute (second proof of Proposition 2.4.14).
Use a view of the product (Proposition 2.4.8). Statements about the columns or rows of a product take one line in the right view: right multiplication recombines columns (Exercise 2.4.11), and left multiplication by a diagonal matrix scales rows (Example 2.4.10).
Split into blocks (Technique 2.4.35). This exploits zero blocks and identity blocks, and it sets up induction on the size.

When the identity is linear in one of the matrices, Technique 2.2.7 on the matrix units is a fifth option, as in the second proof of Proposition 2.4.28.

Example 2.8.3 (Strictly upper triangular matrices are nilpotent, three ways). Let $𝑁 \in 𝐹^{𝑛 \times 𝑛}$ be strictly upper triangular, $𝑁_{𝑖 𝑗} = 0$ whenever $𝑖 \geq 𝑗$ . We show $𝑁^{𝑛} = 0$ .

Maps. Let $𝑉_{𝑘} =$ $span (𝐞_{1}, \dots, 𝐞_{𝑘})$ , with $𝑉_{0} = {𝟎}$ . Column $𝑗$ of $𝑁$ is zero from row $𝑗$ down, so $𝑁 𝐞_{𝑗} \in 𝑉_{𝑗 - 1}$ . Hence $𝑁$ maps $𝑉_{𝑘}$ into $𝑉_{𝑘 - 1}$ (Proposition 2.1.16), $𝑁^{𝑘}$ maps $𝑉_{𝑘}$ into $𝑉_{0}$ , and $𝑁^{𝑛}$ kills $𝐹^{𝑛} = 𝑉_{𝑛}$ . This is Exercise 2.2.36 for $𝑇_{𝑁}$ .

Entries. We claim ${(𝑁^{𝑘})}_{𝑖 𝑗} = 0$ whenever $𝑗 - 𝑖 < 𝑘$ . For $𝑘 = 1$ this is the hypothesis. If it holds for $𝑘$ , then a term of

{(𝑁^{𝑘 + 1})}_{𝑖 𝑗} = \sum_{𝑙 = 1}^{𝑛} {(𝑁^{𝑘})}_{𝑖 𝑙} 𝑁_{𝑙 𝑗}

can be nonzero only if $𝑙 - 𝑖 \geq 𝑘$ and $𝑗 - 𝑙 \geq 1$ , so only if $𝑗 - 𝑖 \geq 𝑘 + 1$ . For $𝑘 = 𝑛$ , every pair has $𝑗 - 𝑖 \leq 𝑛 - 1 < 𝑛$ .

Blocks. We induct on $𝑛$ ; for $𝑛 = 1$ , $𝑁 = 0$ . For $𝑛 \geq 2$ , write $𝑁 = (\begin{matrix} 0 & 𝐫^{𝖳} \\ 𝟎 & 𝑁^{'} \end{matrix})$ with $𝐫 \in 𝐹^{𝑛 - 1}$ and $𝑁^{'}$ strictly upper triangular of size $𝑛 - 1$ . Block multiplication and induction on $𝑘$ give $𝑁^{𝑘} =$ $(\begin{matrix} 0 & 𝐫^{𝖳} 𝑁^{' 𝑘 - 1} \\ 𝟎 & 𝑁^{' 𝑘} \end{matrix})$ , and by the induction hypothesis $𝑁^{' 𝑛 - 1} = 0$ , so $𝑁^{𝑛} = 0$ .

The map proof explains the result: each application of $𝑁$ pushes vectors one step down the chain $𝑉_{𝑛} \supseteq \dots \supseteq 𝑉_{0}$ , so $𝑁^{𝑘}$ maps $𝑉_{𝑗}$ into $𝑉_{𝑗 - 𝑘}$ , which is exactly the band of zeros ${(𝑁^{𝑘})}_{𝑖 𝑗} = 0$ for $𝑗 - 𝑖 < 𝑘$ that the entrywise proof computes. In the form of Exercise 2.2.36 it needs no particular basis: any basis in which each vector is sent into the span of the earlier ones will do, while the entrywise proof needs the matrix already in triangular shape. The entrywise proof, in turn, is the most mechanical, and needs no subspaces at all. For $𝑛 \geq 2$ the shift $𝑁 =$ $\sum_{𝑖 < 𝑛} 𝐞_{𝑖} 𝐞_{𝑖 + 1}^{𝖳}$ has ${(𝑁^{𝑛 - 1})}_{1 𝑛} = 1$ , so the bound $𝑛$ cannot be lowered. The block proof is the longest here, but it is the template for every later induction on the size of a triangular matrix (Proposition 2.4.36).

Practice: Exercise 2.8.9 and Exercise 2.8.12.

2.8.4Proving injectivity, surjectivity, or invertibility

The chapter collected certificates for each property.

Injective: a nonzero vector has a nonzero value (the kernel test, Technique 2.6.12); the values on a basis are independent (Proposition 2.6.22(a)); a left inverse (Proposition 2.5.4); an injective composite $𝑇 𝑆$ , which makes $𝑆$ injective (Proposition 2.6.15(c)).
Surjective: a solution of $𝑇 (𝐯) = 𝐰$ for a general $𝐰$ ; the values on a spanning list span (Proposition 2.6.22(b), Remark 2.6.23); a right inverse (Proposition 2.5.5); a surjective composite $𝑇 𝑆$ , which makes $𝑇$ surjective.
Invertible: a candidate inverse, checked on both sides (Technique 2.5.16); injective and surjective, after which the inverse is linear for free (Proposition 2.7.7); the values on a basis form a basis (Proposition 2.6.22(c)); an invertible matrix in some pair of bases (Proposition 2.5.20, Corollary 2.7.16); for a $2 \times 2$ matrix, $𝑎 𝑑 - 𝑏 𝑐 \neq 0$ (Proposition 2.5.28).

The kernel test is usually the shortest, but it proves injectivity and nothing else. Nothing in this chapter turns injectivity into surjectivity. For square matrices that is a theorem of the next chapter (Theorem 3.5.23), for operators on finite-dimensional spaces it is Corollary 4.2.18, and on $𝐹 [𝑥]$ it is false (Example 2.6.4(e)).

Example 2.8.4 (One operator, four certificates). Let $𝑇 = id + 𝐷$ on $𝐹 [𝑥]$ , over any field, where $𝐷$ is differentiation.

The kernel test. For $𝑝 \neq 𝟎$ the degrees of $𝑝$ and $𝐷 (𝑝)$ differ, so $𝑇 (𝑝)$ has the degree of $𝑝$ and is nonzero (Example 2.6.13(a)). So $𝑇$ is injective, and that is all this argument gives.

Values on a basis. On ${𝐹 [𝑥]}_{\leq 2}$ , $𝑇$ sends $1, 𝑥, 𝑥^{2}$ to $1, 1 + 𝑥, 2 𝑥 + 𝑥^{2}$ . Their span contains $1$ , then $𝑥 = (1 + 𝑥) - 1$ , then $𝑥^{2} = (2 𝑥 + 𝑥^{2}) - 2 𝑥$ , so it is ${𝐹 [𝑥]}_{\leq 2}$ . Together with the kernel test, Proposition 2.6.22 shows that $𝑇$ is bijective on ${𝐹 [𝑥]}_{\leq 2}$ , and the same works on each ${𝐹 [𝑥]}_{\leq 𝑛}$ . Since every polynomial lies in some ${𝐹 [𝑥]}_{\leq 𝑛}$ , which $𝑇$ maps onto itself, $𝑇$ is surjective on $𝐹 [𝑥]$ as well. This reaches $𝐹 [𝑥]$ only through its finite pieces, and it gives no formula for the inverse.

A guessed inverse. The series $1 / (1 + 𝑡) =$ $1 -$ $𝑡 +$ $𝑡^{2} -$ $\dots$ suggests $𝑆 = id - 𝐷 + 𝐷^{2} - \dots$ . On a polynomial of degree at most $𝑑$ the series stops, since $𝐷^{𝑑 + 1} (𝑝) = 𝟎$ (Example 2.1.19(a)). So set $𝑆 (𝑝) =$ $\sum_{𝑘 = 0}^{𝑑} {(- 1)}^{𝑘} 𝐷^{𝑘} (𝑝)$ for any $𝑑 \geq deg 𝑝$ . The extra terms are $𝟎$ , so the choice of $𝑑$ does not matter, and $𝑆$ agrees on each ${𝐹 [𝑥]}_{\leq 𝑑}$ with the linear map $\sum_{𝑘 \leq 𝑑} {(- 1)}^{𝑘} 𝐷^{𝑘}$ , so $𝑆$ is linear. For $deg 𝑝 \leq 𝑑$ the sum telescopes:

\begin{aligned} 𝑇 (𝑆 (𝑝)) & = \sum_{𝑘 = 0}^{𝑑} {(- 1)}^{𝑘} 𝐷^{𝑘} (𝑝) + \sum_{𝑘 = 0}^{𝑑} {(- 1)}^{𝑘} 𝐷^{𝑘 + 1} (𝑝) \\ = 𝑝 + {(- 1)}^{𝑑} 𝐷^{𝑑 + 1} (𝑝) = 𝑝, \end{aligned}

and $𝑆 (𝑇 (𝑝)) = 𝑝$ in the same way, since $𝑇 (𝑝)$ also has degree at most $𝑑$ . By Technique 2.5.16, $𝑇$ is invertible on all of $𝐹 [𝑥]$ , with $𝑇^{- 1} = id - 𝐷 + 𝐷^{2} - \dots$ .

A matrix. In the basis $1, 𝑥, 𝑥^{2}$ of ${𝐹 [𝑥]}_{\leq 2}$ , the matrix of $𝑇$ is upper triangular with every diagonal entry equal to $1$ , and back substitution solves every system (Example 2.7.17).

The kernel test cannot finish on $𝐹 [𝑥]$ , and the basis argument needs pieces ${𝐹 [𝑥]}_{\leq 𝑛}$ that $𝑇$ maps into themselves. The guessed inverse works on all of $𝐹 [𝑥]$ at once and gives a formula. The heuristic behind it is not a proof. The same guess for $id + 𝑀$ , with $𝑀$ multiplication by $𝑥$ , gives $id - 𝑀 + 𝑀^{2} - \dots$ , which never stops; $id + 𝑀$ does not map any ${𝐹 [𝑥]}_{\leq 𝑛}$ into itself either, and indeed it is injective but not surjective: every value $(1 + 𝑥) 𝑞$ vanishes at $- 1$ , and the constant $1$ does not (Example 2.6.29). The series becomes a proof when it terminates.

Practice: Exercise 2.8.10 and Exercise 2.8.15.

2.8.5Proving that conditions are equivalent

The chapter’s equivalence theorems use each shape of Technique 2.7.1. Theorem 2.1.3 is a cycle: (i) $\Rightarrow$ (iii) $\Rightarrow$ (ii) are choices of special values, and (ii) $\Rightarrow$ (i) is an induction on the length of a combination. Theorem 2.7.2 and Theorem 2.7.4 are hubs: the three spokes and the arrow (V) $\Rightarrow$ (I) are earlier results read in the right language (Remark 2.7.3), and one arrow, the construction of a one-sided inverse, needs an idea. Theorem 2.7.8 inherits the equivalence of (I)–(IV) from the first two, since each of these conditions is the conjunction of the corresponding conditions there, and only (V) needs an argument of its own. Corollary 2.7.16 carries all three from $𝐹^{𝑛}$ to spaces with bases by composing with coordinate maps.

Two decisions shape such a proof. The first is where to spend the construction. Arrows out of a condition that hands us an object, such as a left inverse, are short (Proposition 2.5.4). Arrows into it are the hard ones, so they should start from whichever equivalent condition makes the construction easiest. For a left inverse that is (III) of Theorem 2.7.2, since independent columns can be completed to a basis. For a right inverse it is (II) of Theorem 2.7.4, since the solutions of $𝐴 𝐱 = 𝐞_{𝑖}$ are exactly the values the construction needs. The second decision is to check connectivity. Two separately proved groups of equivalent statements say nothing about each other (Exercise 2.7.21), and no arrow may use the theorem it belongs to. Practice: Exercise 2.8.11.

2.8.6Reading the chapter’s proofs

Definitions that are theorems in disguise. The products $𝐴 𝐱$ and $𝐴 𝐵$ were not chosen. Each was derived from a statement we wanted to be true, Theorem 2.3.9 and Theorem 2.4.2, and shown to be the only choice that makes it true (Proposition 2.3.10, Proposition 2.4.3). So the entry formula $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}$ is a consequence, not a convention to memorize, and every algebraic law of the product is a law of composition seen through coordinates. Associativity is the clearest case. The composite of three functions does not depend on how they are grouped, for trivial reasons, so $(𝐴 𝐵) 𝐶 = 𝐴 (𝐵 𝐶)$ as soon as the dictionary is in place (first proof of Proposition 2.4.14). The failures come from composition too: $𝐴 𝐵 \neq 𝐵 𝐴$ and zero divisors are already visible for maps of the plane (Example 2.1.19, Exercise 2.1.40). The entrywise proof of associativity looks more elementary, but its reach is different: it uses only the ring laws of the entries, so it covers block matrices, where no single linear map is in sight (Section 2.4.8).

Uniqueness first, then existence. The proof of Theorem 2.2.1 assumed that a linear map with the given values exists and computed what it had to be. That proved uniqueness and produced the only candidate, which was then checked. The same move found the inverse of a bijective linear map, which can only be the inverse function (Proposition 2.7.7), and it compared a left and a right inverse through the single expression $𝑆_{𝑙} 𝑇 𝑆_{𝑟}$ (Theorem 2.5.10).

Well-definedness. A definition that refers to a choice must not depend on it. When values are prescribed on a spanning list, a vector may have several representations, and the first proof of Proposition 2.2.11 checks that any two give the same value: two representations differ by a linear relation, and the hypothesis says that the prescribed values respect it. Skipping this check is the error in Exercise 2.2.24.

Which hypothesis was used where. Remark 2.2.2 and Remark 2.6.23 record which half of “basis” each argument used, and the record tells us how far a result extends: spanning alone gives uniqueness of a map and the surjectivity test, and independence alone gives existence on the span. In the same way, Proposition 2.4.30 uses $𝑛 * 1 \neq 0$ at exactly one step, and over $𝔽_{𝑝}$ with $𝑝$ dividing $𝑛$ that step fails (Remark 2.4.31).

Forced and free. A left inverse of $𝑇$ is forced on the image of $𝑇$ and free off it. That is why an injective map that is not surjective has many left inverses, and why two different left inverses rule out a right inverse (Corollary 2.5.11, Remark 2.7.11). Counting the free choices counts the one-sided inverses (Problem 2.3).

2.8.7Common errors

Most of these appear in the chapter as find-the-error exercises.

Commuting factors. In general $𝐴 𝐵 \neq 𝐵 𝐴$ (Example 2.4.18), so ${(𝐴 + 𝐵)}^{2} \neq$ $𝐴^{2} +$ $2 𝐴 𝐵 +$ $𝐵^{2}$ (Exercise 2.4.17) and ${(𝐴 𝐵)}^{2} \neq 𝐴^{2} 𝐵^{2}$ (Exercise 2.4.44(c)). Inside a trace, a product may be rotated but not rearranged (Exercise 2.4.32).
Cancelling. $𝐴 𝐵 = 𝐴 𝐶$ gives $𝐵 = 𝐶$ when $𝐴$ is left-invertible (Corollary 2.5.6), but not in general (Example 2.4.19), and $𝐴 𝐵 = 0$ does not force $𝐴 = 0$ or $𝐵 = 0$ (Exercise 2.4.20). The idempotent version, $𝑃 (𝑃 - id) = 0$ hence $𝑃 \in {0, id}$ , is Exercise 2.1.41, and cancelling on the side where no inverse exists is Exercise 2.8.15.
Inverting or transposing a product. ${(𝐴 𝐵)}^{- 1} = 𝐵^{- 1} 𝐴^{- 1}$ and ${(𝐴 𝐵)}^{𝖳} = 𝐵^{𝖳} 𝐴^{𝖳}$ , in reversed order (Exercise 2.8.14, Exercise 2.4.48).
One side for two. A one-sided inverse need not be an inverse: $𝐴 𝐵 = 𝐼_{𝑚}$ does not give $𝐵 𝐴 = 𝐼_{𝑛}$ (Exercise 2.5.34), and on $ℚ [𝑥]$ , $𝐷 𝐽 = id$ while $𝐽 𝐷 \neq id$ (Example 2.5.24).
Injective for surjective. For operators on $𝐹 [𝑥]$ neither implies the other: multiplication by $𝑥$ is injective but not surjective, and its left inverse $𝐿$ of Exercise 2.5.41 is surjective but not injective (Example 2.6.4(e), Exercise 2.6.37(e)). For square matrices the implication is a theorem that this chapter does not have (Theorem 3.5.23).
Swapped bases. ${[𝑇]}_{𝒞︀ ℬ︀}$ takes $ℬ︀$ -coordinates to $𝒞︀$ -coordinates, so ${[id]}_{ℰ︀ ℬ︀}$ converts $ℬ︀$ -coordinates into standard ones and not the other way (Exercise 2.3.30). In a product of matrices of maps, the inner subscripts must match (Exercise 2.8.13, Problem 2.2).
Tests that are not tests. A list that is a basis over one field need not be one over another (Exercise 2.3.31); a condition that is not linear in the vector cannot be checked on a basis (Exercise 2.2.25); and nonzero values on a basis do not make a map injective (Exercise 2.6.40).
Values on a dependent list. They must respect every relation of the list (Exercise 2.2.24, Exercise 2.2.26).
Integer multiples for all scalars. Additivity gives $𝑇 (𝑛 𝐯) = 𝑛 𝑇 (𝐯)$ for integers $𝑛$ , not for all scalars (Exercise 2.1.35).
Partial equivalences and partial inverses. Equivalences proved inside two groups of conditions do not connect the groups (Exercise 2.7.21), and an inverse defined on the image of $𝑇$ only is not a left inverse of $𝑇$ (Exercise 2.7.24).
The kernel test without linearity. On $ℝ$ , $𝑥 \mapsto 𝑥^{2}$ sends only $0$ to $0$ and is not injective; for maps that are homogeneous but not additive the test fails as well (Problem 2.1).

Exercises

Exercise 2.8.5.routine Decide which of the following maps are linear, and give the shortest argument you can.

(a) $𝐹^{𝑛 \times 𝑛} \to 𝐹^{𝑛 \times 𝑛}$ , $𝑋 \mapsto 𝐴 𝑋 𝐵 - 𝑋^{𝖳}$ , where $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ are fixed.
(b) $𝐹 [𝑥] \to 𝐹 [𝑥]$ , $𝑝 \mapsto$ $𝑝 (𝑥 + 1) -$ $2 𝑝 +$ $𝑝 (𝑥 - 1)$ .
(c) $𝐹^{𝑛 \times 𝑛} \to 𝐹$ , $𝑋 \mapsto tr (𝑋^{2})$ , where $𝑛 \geq 1$ . (The answer depends on $𝐹$ .)

Solution.

Uses. Proposition 2.4.14 (Algebra of matrices), Proposition 2.4.22 (Transpose is a linear involution), Proposition 2.1.23 ( $L (𝑉, 𝑊)$ is a vector space), Proposition 2.1.17 (Compositions of linear maps are linear), Exercise 2.1.32, Definition 2.4.26 (Trace), Lemma 2.4.24 (Matrix units)

Techniques. Assemble linear maps from linear pieces (Technique 2.1.26), Try small cases and small fields (Technique 1.2.38)

Hint 1. (a) and (b) are built from maps you already know to be linear. For (c), the formula is a product of entries, which suggests testing homogeneity with a scalar

𝑐

. Which scalars satisfy

𝑐^{2} = 𝑐

Hint 2. For (c) over

𝔽_{2}

, expand

tr (𝑋^{2}) =

\sum_{𝑖} \sum_{𝑘} 𝑥_{𝑖 𝑘} 𝑥_{𝑘 𝑖}

and pair the term for

(𝑖, 𝑘)

with the term for

(𝑘, 𝑖)

Sketch. (a) A difference of the composite

𝑋 \mapsto 𝐴 𝑋 \mapsto 𝐴 𝑋 𝐵

and the transpose, all linear. (b)

𝐶_{𝑥 + 1} - 2 id + 𝐶_{𝑥 - 1}

, with the substitution maps of Exercise 2.1.32. (c) Over

𝔽_{2}

, the off-diagonal terms of

tr (𝑋^{2})

cancel in pairs and

𝑥_{𝑖 𝑖}^{2} = 𝑥_{𝑖 𝑖}

, so

tr (𝑋^{2}) = tr 𝑋

, which is linear. Over any other field pick

𝑐 \notin {0, 1}

; then

tr ({(𝑐 𝐞_{1} 𝐞_{1}^{𝖳})}^{2}) =

𝑐^{2} \neq

𝑐

(a) Linear. The maps $𝑋 \mapsto 𝐴 𝑋$ and $𝑋 \mapsto 𝑋 𝐵$ are linear by Proposition 2.4.14(c) and (d), so their composite $𝑋 \mapsto 𝐴 𝑋 𝐵$ is linear (Proposition 2.1.17). The transpose is linear by Proposition 2.4.22, and a difference of linear maps is linear (Proposition 2.1.23).

(b) Linear. For $𝑞 \in 𝐹 [𝑥]$ , the substitution $𝐶_{𝑞} : 𝑝 \mapsto 𝑝 (𝑞)$ is linear (Exercise 2.1.32), so the map is $𝐶_{𝑥 + 1} -$ $2 {id}_{𝐹 [𝑥]} +$ $𝐶_{𝑥 - 1}$ , a combination of linear maps.

(c) Write $𝜑 (𝑋) = tr (𝑋^{2})$ . By the entry formula,

𝜑 (𝑋) = \sum_{𝑖 = 1}^{𝑛} {(𝑋^{2})}_{𝑖 𝑖} = \sum_{𝑖 = 1}^{𝑛} \sum_{𝑘 = 1}^{𝑛} 𝑥_{𝑖 𝑘} 𝑥_{𝑘 𝑖} = \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖 𝑖}^{2} + \sum_{𝑖 < 𝑘} (𝑥_{𝑖 𝑘} 𝑥_{𝑘 𝑖} + 𝑥_{𝑘 𝑖} 𝑥_{𝑖 𝑘}) .

Over $𝔽_{2}$ . Each pair in the last sum is $(1 + 1) 𝑥_{𝑖 𝑘} 𝑥_{𝑘 𝑖} =$ $0$ , and $𝑐^{2} = 𝑐$ for both elements $𝑐$ of $𝔽_{2}$ . So $𝜑 (𝑋) =$ $\sum_{𝑖} 𝑥_{𝑖 𝑖} =$ $tr 𝑋$ , and $𝜑$ is linear by Proposition 2.4.27.

Over any other field. $𝐹$ has an element $𝑐$ with $𝑐 \neq 0$ and $𝑐 \neq 1$ . Let $𝑋 = 𝐞_{1} 𝐞_{1}^{𝖳}$ , the matrix unit with a single $1$ in position $(1, 1)$ , so $𝑋^{2} = 𝑋$ by Lemma 2.4.24(c). Then $𝜑 (𝑐 𝑋) =$ $tr (𝑐^{2} 𝑋^{2}) =$ $𝑐^{2}$ , while $𝑐 𝜑 (𝑋) = 𝑐$ . Since $𝑐^{2} - 𝑐 = 𝑐 (𝑐 - 1) \neq 0$ , $𝜑$ is not homogeneous, so it is not linear.

Over $𝔽_{2}$ the squares collapse, since $𝑐^{2} = 𝑐$ for both scalars, and the cross terms cancel in pairs; a product of two different inputs, such as $(𝑥, 𝑦) \mapsto 𝑥 𝑦$ , is still not linear there (Exercise 2.1.15(d)). So the rule of thumb in Technique 2.1.26, that a product of inputs is a candidate for a counterexample, has exceptions over small fields, which is a reason to test them separately (Technique 1.2.38).

Exercise 2.8.6.standard Let $𝑈_{𝑖 𝑗} =$ $𝐞_{𝑖} 𝐞_{𝑗}^{𝖳} \in$ $𝐹^{𝑛 \times 𝑛}$ be the matrix units.

(a)Show that $\sum_{𝑖 = 1}^{𝑛} \sum_{𝑗 = 1}^{𝑛} 𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖} =$ $(tr 𝐴) 𝐼_{𝑛}$ for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , twice: by checking on the matrix units, and entry by entry.
(b)Suppose $𝐴$ commutes with every matrix in $𝐹^{𝑛 \times 𝑛}$ . Show that $(𝑛 * 1) 𝐴 =$ $(tr 𝐴) 𝐼_{𝑛}$ . Deduce that if $𝑛 * 1 \neq 0$ in $𝐹$ , the matrices that commute with every matrix are exactly the scalar multiples of $𝐼_{𝑛}$ .

Solution.

Uses. Lemma 2.4.24 (Matrix units), Proposition 2.4.27 (The trace is linear), Proposition 2.4.14 (Algebra of matrices), Corollary 2.2.6 (Agreeing on a spanning list)

Techniques. Check it on a basis (Technique 2.2.7), Compute entry by entry (Technique 2.4.15)

Hint 1. Both sides of (a) are linear functions of

𝐴

. By Lemma 2.4.24(c),

𝑈_{𝑖 𝑗} 𝑈_{𝑘 𝑙} =

𝛿_{𝑗 𝑘} 𝑈_{𝑖 𝑙}

Hint 2. Entry by entry:

𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖} =

𝐞_{𝑖} (𝐞_{𝑗}^{𝖳} 𝐴 𝐞_{𝑗}) 𝐞_{𝑖}^{𝖳}

, and the middle factor is a scalar. For (b), move

𝐴

to the right in each term.

Sketch. (a) On units:

𝑈_{𝑖 𝑗} 𝑈_{𝑘 𝑙} 𝑈_{𝑗 𝑖} =

𝛿_{𝑗 𝑘} 𝛿_{𝑙 𝑗} 𝑈_{𝑖 𝑖}

, which sums to

𝛿_{𝑘 𝑙} 𝐼_{𝑛} =

(tr 𝑈_{𝑘 𝑙}) 𝐼_{𝑛}

; both sides are linear in

𝐴

and the units form a basis. Entrywise:

𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖} =

𝑎_{𝑗 𝑗} 𝑈_{𝑖 𝑖}

, which sums to

(\sum_{𝑗} 𝑎_{𝑗 𝑗}) (\sum_{𝑖} 𝑈_{𝑖 𝑖}) =

(tr 𝐴) 𝐼_{𝑛}

. (b) If

𝐴

commutes with

𝑈_{𝑖 𝑗}

, the term is

𝑈_{𝑖 𝑗} 𝑈_{𝑗 𝑖} 𝐴 =

𝑈_{𝑖 𝑖} 𝐴

, and the sum is

𝑛

copies of

𝐼_{𝑛} 𝐴

(a) On the matrix units. The map $𝐴 \mapsto$ $\sum_{𝑖, 𝑗} 𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖}$ is a sum of maps $𝐴 \mapsto 𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖}$ , each linear by Proposition 2.4.14(c) and (d), and $𝐴 \mapsto (tr 𝐴) 𝐼_{𝑛}$ is linear by Proposition 2.4.27. The matrix units form a basis of $𝐹^{𝑛 \times 𝑛}$ (Lemma 2.4.24(a)), so by Corollary 2.2.6 it suffices to take $𝐴 = 𝑈_{𝑘 𝑙}$ . By Lemma 2.4.24(c), applied twice,

𝑈_{𝑖 𝑗} 𝑈_{𝑘 𝑙} 𝑈_{𝑗 𝑖} = 𝛿_{𝑗 𝑘} 𝑈_{𝑖 𝑙} 𝑈_{𝑗 𝑖} = 𝛿_{𝑗 𝑘} 𝛿_{𝑙 𝑗} 𝑈_{𝑖 𝑖} .

Summing over $𝑗$ leaves only $𝑗 = 𝑘$ , with the factor $𝛿_{𝑙 𝑘}$ , and summing over $𝑖$ then gives $𝛿_{𝑘 𝑙} \sum_{𝑖} 𝑈_{𝑖 𝑖} =$ $𝛿_{𝑘 𝑙} 𝐼_{𝑛}$ . On the other side, $tr 𝑈_{𝑘 𝑙} = 𝛿_{𝑘 𝑙}$ . The two sides agree.

Entry by entry. By associativity and Lemma 2.4.24(b),

𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖} = 𝐞_{𝑖} (𝐞_{𝑗}^{𝖳} 𝐴 𝐞_{𝑗}) 𝐞_{𝑖}^{𝖳} = 𝑎_{𝑗 𝑗} 𝑈_{𝑖 𝑖} .

So the sum is $\sum_{𝑖} \sum_{𝑗} 𝑎_{𝑗 𝑗} 𝑈_{𝑖 𝑖} =$ $(\sum_{𝑗} 𝑎_{𝑗 𝑗}) (\sum_{𝑖} 𝑈_{𝑖 𝑖}) =$ $(tr 𝐴) 𝐼_{𝑛}$ .

The second proof is shorter here, because each term collapses to a single entry of $𝐴$ . The first uses nothing but the multiplication table of the matrix units, and it is the version to use when the terms do not collapse so visibly.

(b) If $𝐴$ commutes with every matrix, then $𝑈_{𝑖 𝑗} 𝐴 𝑈_{𝑗 𝑖} =$ $𝑈_{𝑖 𝑗} 𝑈_{𝑗 𝑖} 𝐴 =$ $𝑈_{𝑖 𝑖} 𝐴$ , since $𝑈_{𝑖 𝑗} 𝑈_{𝑗 𝑖} =$ $𝛿_{𝑗 𝑗} 𝑈_{𝑖 𝑖} =$ $𝑈_{𝑖 𝑖}$ . By (a),

(tr 𝐴) 𝐼_{𝑛} = \sum_{𝑗 = 1}^{𝑛} \sum_{𝑖 = 1}^{𝑛} 𝑈_{𝑖 𝑖} 𝐴 = \sum_{𝑗 = 1}^{𝑛} 𝐼_{𝑛} 𝐴 = (𝑛 * 1) 𝐴 .

If $𝑛 * 1 \neq 0$ , then $𝐴 =$ ${(𝑛 * 1)}^{- 1} (tr 𝐴) 𝐼_{𝑛}$ is a scalar multiple of $𝐼_{𝑛}$ . Conversely $𝑐 𝐼_{𝑛}$ commutes with every matrix, since $(𝑐 𝐼_{𝑛}) 𝑋 =$ $𝑐 𝑋 =$ $𝑋 (𝑐 𝐼_{𝑛})$ by Proposition 2.4.14(b) and (d).

Exercise 2.8.7.standard In $ℚ^{4}$ , let $𝐾 =$ $span ((1, 1, 0, 0), (0, 0, 1, 1))$ and $𝐿 =$ $span ((1, 0, 1, 0), (0, 1, 0, 1))$ .

(a)Construct $𝑇 \in L (ℚ^{4})$ with $ker 𝑇 = 𝐾$ and $im 𝑇 = 𝐿$ , and give its standard matrix.
(b)Show that no $𝑇 \in L (ℚ^{4})$ with $ker 𝑇 = 𝐾$ and $im 𝑇 = 𝐿$ satisfies $𝑇^{2} = 𝑇$ .

Solution.

Uses. Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 2.1.16 (Linear maps preserve spans and linear relations), Definition 2.6.5 (Kernel), Definition 2.6.6 (Image), Proposition 2.3.17 (Every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ is some $𝑇_{𝐴}$ )

Techniques. Construct a map by choosing it on a basis (Technique 2.2.4), Test injectivity at $𝟎$ (Technique 2.6.12)

Hint 1. Complete

(1, 1, 0, 0),

(0, 0, 1, 1)

to a basis of

ℚ^{4}

with two standard basis vectors. Send the first two vectors to

𝟎

and the other two to the spanning vectors of

𝐿

Hint 2. For (b), look for a nonzero vector in

𝐾 \cap 𝐿

. What does

𝑇^{2} = 𝑇

do to a vector that is both a value of

𝑇

and in

ker 𝑇

Sketch. (a)

𝐤_{1} = (1, 1, 0, 0)

𝐤_{2} = (0, 0, 1, 1)

𝐞_{1}

𝐞_{3}

is a basis; let

𝑇

kill

𝐤_{1}, 𝐤_{2}

and send

𝐞_{1}, 𝐞_{3}

𝐥_{1} = (1, 0, 1, 0)

𝐥_{2} = (0, 1, 0, 1)

. Then

𝑇 (𝑥) =

(𝑥_{1} - 𝑥_{2}) 𝐥_{1} +

(𝑥_{3} - 𝑥_{4}) 𝐥_{2}

, a vector is killed exactly when its coefficients on

𝐞_{1}

and

𝐞_{3}

vanish, so

ker 𝑇 = 𝐾

, and

im 𝑇 =

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

𝐿

. (b)

𝐮 =

(1, 1, 1, 1) =

𝐤_{1} +

𝐤_{2} =

𝐥_{1} +

𝐥_{2}

. If

𝐮 = 𝑇 (𝐰)

and

𝑇^{2} = 𝑇

, then

𝐮 =

𝑇 (𝑇 (𝐰)) =

𝑇 (𝐮) =

𝟎

(a) Let $𝐤_{1} = (1, 1, 0, 0)$ , $𝐤_{2} = (0, 0, 1, 1)$ , $𝐥_{1} = (1, 0, 1, 0)$ , and $𝐥_{2} = (0, 1, 0, 1)$ . The list $𝐤_{1}, 𝐤_{2}, 𝐞_{1}, 𝐞_{3}$ is a basis of $ℚ^{4}$ : the equation

(𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}) = 𝑎 𝐤_{1} + 𝑏 𝐤_{2} + 𝑐 𝐞_{1} + 𝑑 𝐞_{3} = (𝑎 + 𝑐, 𝑎, 𝑏 + 𝑑, 𝑏)

has exactly one solution, $𝑎 = 𝑥_{2}$ , $𝑏 = 𝑥_{4}$ , $𝑐 = 𝑥_{1} - 𝑥_{2}$ , $𝑑 = 𝑥_{3} - 𝑥_{4}$ . By Theorem 2.2.1 there is a linear map $𝑇$ with

𝑇 (𝐤_{1}) = 𝑇 (𝐤_{2}) = 𝟎, 𝑇 (𝐞_{1}) = 𝐥_{1}, 𝑇 (𝐞_{3}) = 𝐥_{2},

and (2.2.1) gives

𝑇 (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}) = (𝑥_{1} - 𝑥_{2}) 𝐥_{1} + (𝑥_{3} - 𝑥_{4}) 𝐥_{2} = (𝑥_{1} - 𝑥_{2}, 𝑥_{3} - 𝑥_{4}, 𝑥_{1} - 𝑥_{2}, 𝑥_{3} - 𝑥_{4}) .

Kernel. $𝑇$ kills $𝐤_{1}$ and $𝐤_{2}$ , so it kills $𝐾$ . Conversely, if $𝑇 (𝐯) = 𝟎$ for $𝐯 =$ $𝑎 𝐤_{1} +$ $𝑏 𝐤_{2} +$ $𝑐 𝐞_{1} +$ $𝑑 𝐞_{3}$ , then $𝑐 𝐥_{1} +$ $𝑑 𝐥_{2} =$ $(𝑐, 𝑑, 𝑐, 𝑑) =$ $𝟎$ , so $𝑐 = 𝑑 = 0$ and $𝐯 \in 𝐾$ .

Image. By Proposition 2.1.16, $im 𝑇$ is spanned by the values on the basis, $𝟎, 𝟎, 𝐥_{1}, 𝐥_{2}$ , so $im 𝑇 = 𝐿$ .

The standard matrix has the columns $𝑇 (𝐞_{𝑗})$ :

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

(b) The vector $𝐮 = (1, 1, 1, 1)$ is $𝐤_{1} + 𝐤_{2} \in 𝐾$ and $𝐥_{1} + 𝐥_{2} \in 𝐿$ . Let $𝑇$ have kernel $𝐾$ and image $𝐿$ , and suppose $𝑇^{2} = 𝑇$ . Since $𝐮 \in im 𝑇$ , $𝐮 = 𝑇 (𝐰)$ for some $𝐰$ , and then

𝐮 = 𝑇 (𝐰) = 𝑇 (𝑇 (𝐰)) = 𝑇 (𝐮) = 𝟎,

because $𝐮 \in ker 𝑇$ . This is a contradiction. The construction in (a) needed nothing about how $𝐾$ and $𝐿$ sit relative to each other, but an operator with $𝑇^{2} = 𝑇$ fixes its image pointwise, so its kernel and image can share only $𝟎$ .

Exercise 2.8.8.standard Let $𝑝$ be a prime and $𝐷$ differentiation on $𝔽_{𝑝} [𝑥]$ .

(a)Show that $𝐷^{𝑝} = 0$ .
(b)Let $𝑛 \geq 1$ , and let $𝑁$ be the matrix of $𝐷$ on $𝔽_{𝑝} {[𝑥]}_{\leq 𝑛}$ with respect to $1, 𝑥, \dots, 𝑥^{𝑛}$ . Show that $𝑁^{𝑝} = 0$ without multiplying matrices. Show also that over $ℚ$ the corresponding matrix satisfies $𝑁^{𝑛} \neq 0$ .
(c)Show that $id + 𝐷$ is invertible on $𝔽_{𝑝} [𝑥]$ , with inverse ${(id + 𝐷)}^{𝑝 - 1}$ . You may use the binomial theorem for commuting operators, which has the same proof as for numbers, and that $𝑝$ divides $(\binom{𝑝}{𝑘})$ for $0 < 𝑘 < 𝑝$ .

Solution.

Uses. Example 2.1.9 (Maps of polynomials), Proposition 2.2.20 (Linear maps out of $𝐹 [𝑥]$ ), Notation 2.4.16 (Powers of a matrix), Theorem 2.3.20 (Linear maps correspond to matrices), Proposition 2.1.24 (Algebra of composition)

Techniques. Check it on a basis (Technique 2.2.7), Translate between maps and matrices (Technique 2.3.27)

Hint 1.

𝐷^{𝑝}

is linear, so it is enough to compute

𝐷^{𝑝} (𝑥^{𝑘})

. Show by induction on

𝑗

that

𝐷^{𝑗} (𝑥^{𝑘}) =

𝑘 (𝑘 - 1) \dots (𝑘 - 𝑗 + 1) 𝑥^{𝑘 - 𝑗}

for

𝑗 \leq 𝑘

, and

𝐷^{𝑗} (𝑥^{𝑘}) = 𝟎

for

𝑗 > 𝑘

Hint 2. Among

𝑝

consecutive integers, one is divisible by

𝑝

. For (b), translate

𝐷^{𝑝} = 0

into a statement about matrices with Notation 2.4.16. For (c), expand

{(id + 𝐷)}^{𝑝}

Sketch. (a) For

𝑘 < 𝑝

𝐷^{𝑝} (𝑥^{𝑘}) = 𝟎

because

𝐷

kills constants; for

𝑘 \geq 𝑝

𝐷^{𝑝} (𝑥^{𝑘}) =

𝑘 (𝑘 - 1) \dots (𝑘 - 𝑝 + 1) 𝑥^{𝑘 - 𝑝}

, and the integer coefficient is a product of

𝑝

consecutive integers, hence divisible by

𝑝

. So

𝐷^{𝑝}

vanishes on the monomials. (b)

𝐷

maps

𝔽_{𝑝} {[𝑥]}_{\leq 𝑛}

into itself, and

𝑁^{𝑝}

is the matrix of the restriction of

𝐷^{𝑝}

, which is

0

. Over

ℚ

𝐷^{𝑛} (𝑥^{𝑛}) = 𝑛! \neq 0

. (c)

{(id + 𝐷)}^{𝑝} =

id +

𝐷^{𝑝} =

id

, so

{(id + 𝐷)}^{𝑝 - 1}

is a two-sided inverse.

(a) By Example 2.1.9, $𝐷 (𝑥^{𝑘}) =$ $(𝑘 * 1) 𝑥^{𝑘 - 1}$ for $𝑘 \geq 1$ and $𝐷 (1) = 𝟎$ . By induction on $𝑗$ ,

𝐷^{𝑗} (𝑥^{𝑘}) = (𝑘 (𝑘 - 1) \dots (𝑘 - 𝑗 + 1) * 1) 𝑥^{𝑘 - 𝑗} (𝑗 \leq 𝑘), 𝐷^{𝑗} (𝑥^{𝑘}) = 𝟎 (𝑗 > 𝑘) :

one more application of $𝐷$ multiplies by the current exponent $𝑘 - 𝑗$ and lowers it by one, and once the constant $𝐷^{𝑘} (𝑥^{𝑘}) = 𝑘! * 1$ is reached, the next application gives $𝟎$ . Now take $𝑗 = 𝑝$ . If $𝑘 < 𝑝$ , then $𝐷^{𝑝} (𝑥^{𝑘}) = 𝟎$ . If $𝑘 \geq 𝑝$ , the integer $𝑘 (𝑘 - 1) \dots (𝑘 - 𝑝 + 1)$ is a product of $𝑝$ consecutive integers, one of which is divisible by $𝑝$ , so its image in $𝔽_{𝑝}$ is $0$ and $𝐷^{𝑝} (𝑥^{𝑘}) = 𝟎$ . So the linear map $𝐷^{𝑝}$ agrees with $0$ on every monomial, and $𝐷^{𝑝} = 0$ by the uniqueness in Proposition 2.2.20.

(b) $𝐷$ lowers degrees, so it maps $𝑉 = 𝔽_{𝑝} {[𝑥]}_{\leq 𝑛}$ into itself; call the restriction $𝐷_{𝑉}$ . Then $𝐷_{𝑉}^{𝑝}$ is the restriction of $𝐷^{𝑝} = 0$ , so $𝐷_{𝑉}^{𝑝} = 0$ . By Notation 2.4.16, $𝑁^{𝑝} =$ ${[𝐷_{𝑉}^{𝑝}]}_{ℬ︀ ℬ︀} =$ ${[0]}_{ℬ︀ ℬ︀} =$ $0$ , where $ℬ︀ = 1, 𝑥, \dots, 𝑥^{𝑛}$ .

Over $ℚ$ , the computation in (a) gives $𝐷^{𝑛} (𝑥^{𝑛}) = 𝑛! \neq 0$ , so $𝐷_{𝑉}^{𝑛} \neq 0$ , and its matrix $𝑁^{𝑛}$ is not $0$ by Theorem 2.3.20. (In both cases $𝑁^{𝑛 + 1} = 0$ , since $𝐷_{𝑉}^{𝑛 + 1}$ kills every polynomial of degree at most $𝑛$ .) So over $𝔽_{𝑝}$ with $𝑝 \leq 𝑛$ , the matrix $𝑁$ dies earlier than the size forces it to.

(c) The operators $id$ and $𝐷$ commute, so the binomial theorem gives

{(id + 𝐷)}^{𝑝} = \sum_{𝑘 = 0}^{𝑝} (\binom{𝑝}{𝑘}) 𝐷^{𝑘} = id + 𝐷^{𝑝} = id,

because the coefficients $(\binom{𝑝}{𝑘})$ with $0 < 𝑘 < 𝑝$ are $0$ in $𝔽_{𝑝}$ , and $𝐷^{𝑝} = 0$ by (a). Hence

(id + 𝐷) {(id + 𝐷)}^{𝑝 - 1} = {(id + 𝐷)}^{𝑝 - 1} (id + 𝐷) = {(id + 𝐷)}^{𝑝} = id,

and by Technique 2.5.16, $id + 𝐷$ is invertible with inverse ${(id + 𝐷)}^{𝑝 - 1}$ . This agrees with the inverse $id - 𝐷 + 𝐷^{2} - \dots$ found in Example 2.8.4, as it must, since an inverse is unique: over $𝔽_{𝑝}$ the series stops at $𝐷^{𝑝 - 1}$ for every polynomial.

Exercise 2.8.9.standard Let $𝑝, 𝑞, 𝑟 \geq 1$ , let $𝐴 \in 𝐹^{𝑝 \times 𝑞}$ , $𝐵 \in 𝐹^{𝑝 \times 𝑟}$ , and $𝐶 \in 𝐹^{𝑞 \times 𝑟}$ , and let

𝑀 = (\begin{matrix} 𝐼_{𝑝} & 𝐴 & 𝐵 \\ 0 & 𝐼_{𝑞} & 𝐶 \\ 0 & 0 & 𝐼_{𝑟} \end{matrix}) .

(a)Write $𝑀 = 𝐼 + 𝑁$ , compute $𝑁^{2}$ and $𝑁^{3}$ by block multiplication, and deduce $𝑀^{- 1}$ .
(b)For numbers,
${(\begin{matrix} 1 & 𝑎 & 𝑏 \\ 0 & 1 & 𝑐 \\ 0 & 0 & 1 \end{matrix})}^{- 1} = (\begin{matrix} 1 & - 𝑎 & 𝑎 𝑐 - 𝑏 \\ 0 & 1 & - 𝑐 \\ 0 & 0 & 1 \end{matrix}),$
and the corner entry $𝑎 𝑐 - 𝑏$ could also be written $𝑐 𝑎 - 𝑏$ . Which block version is correct, and why does the other one fail?

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Exercise 2.5.39, Proposition 2.4.14 (Algebra of matrices)

Techniques. Block decomposition (Technique 2.4.35), Guess the inverse, then check both products (Technique 2.5.16)

Hint 1.

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

. Only one block of

𝑁^{2}

is nonzero.

Hint 2. Since

𝑁^{3} = 0

, the geometric series

𝐼 - 𝑁 + 𝑁^{2}

is a candidate for

𝑀^{- 1}

. Check the sizes of

𝐴 𝐶

and

𝐶 𝐴

Sketch.

𝑁^{2}

has the single nonzero block

𝐴 𝐶

in position

(1, 3)

, and

𝑁^{3} = 0

. So

(𝐼 + 𝑁) (𝐼 - 𝑁 + 𝑁^{2}) =

𝐼 +

𝑁^{3} =

𝐼

in both orders, and

𝑀^{- 1} =

(\begin{matrix} 𝐼_{𝑝} & - 𝐴 & 𝐴 𝐶 - 𝐵 \\ 0 & 𝐼_{𝑞} & - 𝐶 \\ 0 & 0 & 𝐼_{𝑟} \end{matrix})

. The product

𝐶 𝐴

is defined only when

𝑟 = 𝑝

, and the corner of

𝑀^{- 1}

𝑝 \times 𝑟

, which

𝐴 𝐶

is.

(a) $𝑀 = 𝐼 + 𝑁$ with

𝑁 = (\begin{matrix} 0 & 𝐴 & 𝐵 \\ 0 & 0 & 𝐶 \\ 0 & 0 & 0 \end{matrix}) .

By Theorem 2.4.34, the $(𝐼, 𝐽)$ block of $𝑁^{2}$ is $\sum_{𝐾} 𝑁_{𝐼 𝐾} 𝑁_{𝐾 𝐽}$ , and a term is nonzero only if $𝐼 < 𝐾 < 𝐽$ . So the only nonzero block of $𝑁^{2}$ is in position $(1, 3)$ , and it equals $𝑁_{12} 𝑁_{23} = 𝐴 𝐶$ :

𝑁^{2} = (\begin{matrix} 0 & 0 & 𝐴 𝐶 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) .

The only nonzero block row of $𝑁^{2}$ is the first, and its only nonzero block sits in block column $3$ , which multiplies the third block row of $𝑁$ , which is zero. So $𝑁^{3} = 𝑁^{2} 𝑁 = 0$ . Since $𝐼$ commutes with $𝑁$ ,

(𝐼 + 𝑁) (𝐼 - 𝑁 + 𝑁^{2}) = 𝐼 - 𝑁 + 𝑁^{2} + 𝑁 - 𝑁^{2} + 𝑁^{3} = 𝐼,

and the product in the other order is the same expansion. By Technique 2.5.16 (this is Exercise 2.5.39 with $𝑘 = 3$ ),

𝑀^{- 1} = 𝐼 - 𝑁 + 𝑁^{2} = (\begin{matrix} 𝐼_{𝑝} & - 𝐴 & 𝐴 𝐶 - 𝐵 \\ 0 & 𝐼_{𝑞} & - 𝐶 \\ 0 & 0 & 𝐼_{𝑟} \end{matrix}) .

(b) $𝐴 𝐶 - 𝐵$ is correct. The product $𝐶 𝐴$ is defined only when $𝑟 = 𝑝$ , since $𝐶$ has $𝑟$ columns and $𝐴$ has $𝑝$ rows, and even then it is not the right block. As a check, the $(1, 3)$ block of $𝑀 𝑀^{- 1}$ is

𝐼_{𝑝} (𝐴 𝐶 - 𝐵) + 𝐴 (- 𝐶) + 𝐵 𝐼_{𝑟} = 𝐴 𝐶 - 𝐵 - 𝐴 𝐶 + 𝐵 = 0,

which works because $𝐴 𝐶$ appears twice in the same order. In the scalar formula the order did not matter, and that is exactly the information the scalar formula loses.

Exercise 2.8.10.standard Let $𝑐 \in 𝐹$ , and let $𝑀$ and $𝐷$ be multiplication by $𝑥$ and differentiation on $𝐹 [𝑥]$ .

(a)Show that $𝑀 - 𝑐 id$ is injective but not surjective.
(b)Suppose $𝑐 \neq 0$ . Show that $𝐷 - 𝑐 id$ is invertible, and find its inverse.
(c)Explain why the kernel test alone could not have decided (b).

Solution.

Uses. Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Proposition 1.2.18 (Degree and evaluation versus the operations), Example 2.6.29 (Evaluation at $0$ , and multiplication by $𝑥$ ), Example 2.1.19 (Composites), Proposition 2.1.24 (Algebra of composition)

Techniques. Test injectivity at $𝟎$ (Technique 2.6.12), Guess the inverse, then check both products (Technique 2.5.16)

Hint 1. (a) Compare degrees for injectivity. For surjectivity, evaluate a value

(𝑀 - 𝑐 id) (𝑞)

𝑐

Hint 2. (b)

𝐷 -

𝑐 id =

- 𝑐 (id - 𝑐^{- 1} 𝐷)

. Expand

1 / (1 - 𝑡)

as a geometric series, and use that

𝐷^{𝑑 + 1}

kills polynomials of degree at most

𝑑

Sketch. (a) For

𝑞 \neq 𝟎

of degree

𝑑

𝑥 𝑞

has degree

𝑑 + 1

and

𝑐 𝑞

degree at most

𝑑

, so

(𝑀 - 𝑐 id) (𝑞) \neq 𝟎

. Every value vanishes at

𝑐

, and

1

does not. (b)

𝑆 =

- \sum_{𝑘 \geq 0} 𝑐^{- 𝑘 - 1} 𝐷^{𝑘}

, a finite sum on each polynomial;

(𝐷 - 𝑐 id) 𝑆

and

𝑆 (𝐷 - 𝑐 id)

telescope to

id

. (c) Both maps are injective by the kernel test, but only one is surjective.

(a) Injective. Let $𝑞 \neq 𝟎$ have degree $𝑑$ . Then $𝑥 𝑞$ has degree $𝑑 + 1$ and $𝑐 𝑞$ has degree at most $𝑑$ , so their degrees differ and $(𝑀 - 𝑐 id) (𝑞) =$ $𝑥 𝑞 -$ $𝑐 𝑞$ has degree $𝑑 + 1$ (Proposition 1.2.18(a)). In particular it is not $𝟎$ , and $𝑀 - 𝑐 id$ is injective by Theorem 2.6.11.

Not surjective. Every value $(𝑀 - 𝑐 id) (𝑞) =$ $𝑥 𝑞 -$ $𝑐 𝑞$ vanishes at $𝑐$ (Example 2.6.29). The constant polynomial $1$ does not, so it is not a value.

(b) Since $𝐷 -$ $𝑐 id =$ $- 𝑐 (id - 𝑐^{- 1} 𝐷)$ and $1 / (1 - 𝑡) =$ $1 +$ $𝑡 +$ $𝑡^{2} +$ $\dots$ , the candidate is

𝑆 = - 𝑐^{- 1} \sum_{𝑘 \geq 0} 𝑐^{- 𝑘} 𝐷^{𝑘} = - \sum_{𝑘 \geq 0} 𝑐^{- 𝑘 - 1} 𝐷^{𝑘} .

On a polynomial of degree at most $𝑑$ only the terms with $𝑘 \leq 𝑑$ can be nonzero, since $𝐷^{𝑑 + 1}$ kills it (Example 2.1.19(a)). So define $𝑆 (𝑓) =$ $- \sum_{𝑘 = 0}^{𝑑} 𝑐^{- 𝑘 - 1} 𝐷^{𝑘} (𝑓)$ for any $𝑑 \geq deg 𝑓$ ; the choice of $𝑑$ does not matter, and on ${𝐹 [𝑥]}_{\leq 𝑑}$ , $𝑆$ agrees with a linear combination of powers of $𝐷$ , so $𝑆$ is linear. For $deg 𝑓 \leq 𝑑$ ,

\begin{aligned} (𝐷 - 𝑐 id) (𝑆 (𝑓)) & = - \sum_{𝑘 = 0}^{𝑑} 𝑐^{- 𝑘 - 1} 𝐷^{𝑘 + 1} (𝑓) + \sum_{𝑘 = 0}^{𝑑} 𝑐^{- 𝑘} 𝐷^{𝑘} (𝑓) \\ = 𝑓 - 𝑐^{- 𝑑 - 1} 𝐷^{𝑑 + 1} (𝑓) = 𝑓, \end{aligned}

since the two sums cancel except for the term $𝑘 = 0$ of the second and the term $𝑘 = 𝑑$ of the first. The same computation gives $𝑆 ((𝐷 - 𝑐 id) (𝑓)) =$ $𝑓$ , because $(𝐷 - 𝑐 id) (𝑓)$ also has degree at most $𝑑$ . By Technique 2.5.16, $𝐷 - 𝑐 id$ is invertible and ${(𝐷 - 𝑐 id)}^{- 1} =$ $- \sum_{𝑘 \geq 0} 𝑐^{- 𝑘 - 1} 𝐷^{𝑘}$ .

(c) The kernel test proves that $𝐷 - 𝑐 id$ is injective for $𝑐 \neq 0$ : if $𝐷 (𝑓) = 𝑐 𝑓$ with $𝑓 \neq 𝟎$ , the left side has smaller degree than the right. But it proves the same about $𝑀 - 𝑐 id$ , which is not surjective. On $𝐹 [𝑥]$ injectivity does not imply surjectivity, so a second argument was needed, and the guessed inverse supplied both halves at once.

Exercise 2.8.11.standard Let

𝑛 \geq 1

𝐴 \in 𝐹^{𝑛 \times 𝑛}

, and

𝑈_{𝑖 𝑗} = 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

. Show that the following are equivalent, and arrange the proof so that as many arrows as possible are citations of earlier results.

(i) $𝐴 = 𝜆 𝐼_{𝑛}$ for some $𝜆 \in 𝐹$ .
(ii) $𝐴 𝑋 = 𝑋 𝐴$ for every $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ .
(iii) $𝐴 𝑈_{𝑖 𝑗} = 𝑈_{𝑖 𝑗} 𝐴$ for all $𝑖, 𝑗$ .
(iv) $𝐴 𝐱 \in span (𝐱)$ for every $𝐱 \in 𝐹^{𝑛}$ .
(v) ${[𝑇_{𝐴}]}_{ℬ︀ ℬ︀} = 𝐴$ for every basis $ℬ︀$ of $𝐹^{𝑛}$ of length $𝑛$ .

Solution.

Uses. Proposition 2.4.14 (Algebra of matrices), Lemma 2.4.24 (Matrix units), Example 2.3.28 (Translating in both directions), Exercise 2.3.40, Proposition 2.3.16 (The matrix of $𝑇_{𝐴}$ ), Proposition 2.3.17 (Every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ is some $𝑇_{𝐴}$ ), Example 2.3.6 (The zero map and the identity map), Proposition 2.4.12 (Matrices of sums and scalar multiples)

Techniques. Proving TFAE (Technique 2.7.1), Compute entry by entry (Technique 2.4.15)

Hint 1. Use (i) as a hub. Which spokes are already in the chapter? Look at Example 2.3.28(b) and Exercise 2.3.40.

Hint 2. For (iii)

\Rightarrow

(i), compute both sides of

𝐴 𝑈_{𝑖 𝑗} = 𝑈_{𝑖 𝑗} 𝐴

: one has only column

𝑗

nonzero, the other only row

𝑖

Sketch. Hub at (i). The cycle (i)

\Rightarrow

(ii)

\Rightarrow

(iii)

\Rightarrow

(i): scalars commute with everything, (iii) is a special case of (ii), and

𝐴 𝑈_{𝑖 𝑗}

has column

𝑗

equal to column

𝑖

𝐴

while

𝑈_{𝑖 𝑗} 𝐴

has row

𝑖

equal to row

𝑗

𝐴

, which forces

𝑎_{𝑘 𝑖} = 0

for

𝑘 \neq 𝑖

and

𝑎_{𝑖 𝑖} = 𝑎_{𝑗 𝑗}

. (i)

\Leftrightarrow

(iv) is Example 2.3.28(b) plus a one-line converse. (i)

\Leftrightarrow

(v): since

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

, (v) says that the matrix of

𝑇_{𝐴}

is the same in every basis, which is Exercise 2.3.40.

We use (i) as a hub. Each spoke is either a citation or a short computation.

(i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i). If $𝐴 = 𝜆 𝐼_{𝑛}$ , then $𝐴 𝑋 = 𝜆 𝑋 = 𝑋 𝐴$ by Proposition 2.4.14(b) and (d). (iii) is the special case $𝑋 = 𝑈_{𝑖 𝑗}$ of (ii). For (iii) $\Rightarrow$ (i), fix $𝑖$ and $𝑗$ . By associativity and Lemma 2.4.24(b),

𝐴 𝑈_{𝑖 𝑗} = (𝐴 𝐞_{𝑖}) 𝐞_{𝑗}^{𝖳}, 𝑈_{𝑖 𝑗} 𝐴 = 𝐞_{𝑖} (𝐞_{𝑗}^{𝖳} 𝐴) .

The first matrix has column $𝑗$ equal to column $𝑖$ of $𝐴$ and every other column zero. The second has row $𝑖$ equal to row $𝑗$ of $𝐴$ and every other row zero. If they are equal, then column $𝑗$ of the first, $𝐴_{\cdot, 𝑖}$ , is zero outside row $𝑖$ , so $𝑎_{𝑘 𝑖} = 0$ for $𝑘 \neq 𝑖$ ; and comparing the entries in position $(𝑖, 𝑗)$ gives $𝑎_{𝑖 𝑖} = 𝑎_{𝑗 𝑗}$ . As $𝑖$ and $𝑗$ range over all indices, $𝐴$ is diagonal with all diagonal entries equal to $𝑎_{11}$ , so $𝐴 = 𝑎_{11} 𝐼_{𝑛}$ .

(i) $\Leftrightarrow$ (iv). If $𝐴 = 𝜆 𝐼_{𝑛}$ , then $𝐴 𝐱 =$ $𝜆 𝐱 \in$ $span (𝐱)$ . The converse is Example 2.3.28(b).

(i) $\Leftrightarrow$ (v). By Proposition 2.3.16, ${[𝑇_{𝐴}]}_{ℰ︀ ℰ︀} = 𝐴$ , so (v) says that ${[𝑇_{𝐴}]}_{ℬ︀ ℬ︀}$ is the same matrix for every basis $ℬ︀$ of length $𝑛$ . By Exercise 2.3.40, this holds if and only if $𝑇_{𝐴} = 𝜆 id$ for some $𝜆$ , that is, $𝑇_{𝐴} = 𝑇_{𝜆 𝐼_{𝑛}}$ , which by Proposition 2.3.17 means $𝐴 = 𝜆 𝐼_{𝑛}$ . (For the direction (i) $\Rightarrow$ (v) one can also compute directly: ${[𝜆 id]}_{ℬ︀ ℬ︀} = 𝜆 𝐼_{𝑛}$ by Example 2.3.6 and Proposition 2.4.12.)

Every condition is connected to the hub in both directions, so all five are equivalent. Only one arrow, (iii) $\Rightarrow$ (i), needed new work; the others were earlier results read as statements about $𝐴$ .

Exercise 2.8.12.standard Let $𝑛 \geq 1$ .

(a)Show that there are no $𝐴, 𝐵 \in ℝ^{𝑛 \times 𝑛}$ with $𝐴 𝐵 -$ $𝐵 𝐴 =$ $𝐴 𝐴^{𝖳} +$ $𝐼_{𝑛}$ .
(b)Show that the statement of (a) is false over $ℂ$ and over $𝔽_{2}$ .
(c)Show that $tr (𝐴 𝐴^{𝖳}) = 0$ forces $𝐴 = 0$ for $𝐴 \in ℝ^{𝑛 \times 𝑛}$ , but find nonzero $𝐴 \in ℂ^{2 \times 2}$ and $𝐴 \in 𝔽_{2}^{2 \times 2}$ with $tr (𝐴 𝐴^{𝖳}) = 0$ .

Solution.

Uses. Proposition 2.4.28 (Cyclicity of the trace), Proposition 2.4.27 (The trace is linear), Definition 2.4.26 (Trace), Definition 2.4.21 (Transpose)

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. Take the trace of both sides. The left side has trace

0

Hint 2.

tr (𝐴 𝐴^{𝖳}) =

\sum_{𝑗, 𝑘} 𝑎_{𝑗 𝑘}^{2}

. Over

ℝ

this is a sum of squares. Over

ℂ

and

𝔽_{2}

, find

𝐴

with

𝐴 𝐴^{𝖳} = - 𝐼_{𝑛}

Sketch. (a)

tr (𝐴 𝐵 - 𝐵 𝐴) = 0

by cyclicity, while

tr (𝐴 𝐴^{𝖳} + 𝐼_{𝑛}) =

\sum_{𝑗, 𝑘} 𝑎_{𝑗 𝑘}^{2} +

𝑛 \geq

𝑛 >

0

. (b)

𝐴 = 𝑖 𝐼_{𝑛}

over

ℂ

and

𝐴 = 𝐼_{𝑛}

over

𝔽_{2}

give

𝐴 𝐴^{𝖳} = - 𝐼_{𝑛}

, so with

𝐵 = 0

both sides are

0

. (c) Over

ℝ

a sum of squares is

0

only if every term is. Over

ℂ

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

; over

𝔽_{2}

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

The $(𝑗, 𝑗)$ entry of $𝐴 𝐴^{𝖳}$ is $\sum_{𝑘} 𝑎_{𝑗 𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗} =$ $\sum_{𝑘} 𝑎_{𝑗 𝑘}^{2}$ , so

tr (𝐴 𝐴^{𝖳}) = \sum_{𝑗 = 1}^{𝑛} \sum_{𝑘 = 1}^{𝑛} 𝑎_{𝑗 𝑘}^{2} .

(a) By Proposition 2.4.27 and Proposition 2.4.28, $tr (𝐴 𝐵 - 𝐵 𝐴) =$ $tr (𝐴 𝐵) -$ $tr (𝐵 𝐴) =$ $0$ . Over $ℝ$ , every $𝑎_{𝑗 𝑘}^{2} \geq 0$ , so $tr (𝐴 𝐴^{𝖳} + 𝐼_{𝑛}) =$ $tr (𝐴 𝐴^{𝖳}) +$ $𝑛 \geq$ $𝑛 >$ $0$ . The two sides have different traces, so they are not equal.

(b) Over $ℂ$ , let $𝐴 = 𝑖 𝐼_{𝑛}$ and $𝐵 = 0$ . Then $𝐴 𝐵 - 𝐵 𝐴 = 0$ and $𝐴 𝐴^{𝖳} +$ $𝐼_{𝑛} =$ $𝑖^{2} 𝐼_{𝑛} +$ $𝐼_{𝑛} =$ $0$ . Over $𝔽_{2}$ , let $𝐴 = 𝐼_{𝑛}$ and $𝐵 = 0$ ; then $𝐴 𝐴^{𝖳} +$ $𝐼_{𝑛} =$ $(1 + 1) 𝐼_{𝑛} =$ $0 =$ $𝐴 𝐵 -$ $𝐵 𝐴$ .

(c) Over $ℝ$ , a sum of squares of real numbers is $0$ only if every square is $0$ , so $tr (𝐴 𝐴^{𝖳}) = 0$ gives every $𝑎_{𝑗 𝑘} = 0$ . Over $ℂ$ , $𝐴 = (\begin{matrix} 1 & 𝑖 \\ 0 & 0 \end{matrix})$ has $tr (𝐴 𝐴^{𝖳}) =$ $1^{2} +$ $𝑖^{2} =$ $0$ . Over $𝔽_{2}$ , $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$ has $tr (𝐴 𝐴^{𝖳}) = 1 + 1 = 0$ .

The trace argument used one fact beyond cyclicity, the positivity of sums of real squares, and (c) shows exactly where that fact lives. The same positivity drives the inner products of Section 6.1, where $tr (𝐴^{𝖳} 𝐴)$ is the squared length of $𝐴$ .

Exercise 2.8.13.routine Let $𝑇 \in L (ℚ^{2})$ , $𝑇 (𝑥, 𝑦) = (𝑦, 𝑥)$ , and let $ℬ︀$ be the basis $𝐛_{1} = (1, 0)$ , $𝐛_{2} = (1, 1)$ . Find the error in the following computation, and compute ${[𝑇]}_{ℬ︀ ℬ︀}$ correctly.

Computation. Let $𝑃 =$ ${[id]}_{ℰ︀ ℬ︀} =$ $(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ , whose columns are $𝐛_{1}$ and $𝐛_{2}$ . Changing from the standard basis to $ℬ︀$ means applying $𝑃$ , so

{[𝑇]}_{ℬ︀ ℬ︀} = 𝑃 {[𝑇]}_{ℰ︀ ℰ︀} 𝑃^{- 1} = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 1 & - 1 \end{matrix}) .

Solution.

Uses. Theorem 2.4.2 (The matrix of a composite), Definition 2.3.1 (Matrix of a linear map), Example 2.5.21 (Change of coordinates is invertible)

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Write

𝑇 = id \circ 𝑇 \circ id

and apply Theorem 2.4.2 with the bases chosen so that the inner subscripts match.

Hint 2. Which way does

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

convert coordinates? Check the answer by computing

𝑇 (𝐛_{1})

and

𝑇 (𝐛_{2})

ℬ︀

-coordinates.

Sketch.

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

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

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

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

. The computation multiplied in the wrong order:

𝑃

converts

ℬ︀

-coordinates to standard ones, so it must act first. Directly,

𝑇 (𝐛_{1}) =

(0, 1) =

- 𝐛_{1} +

𝐛_{2}

and

𝑇 (𝐛_{2}) = 𝐛_{2}

The error. By Theorem 2.4.2, applied to $𝑇 = id \circ 𝑇 \circ id$ with the bases arranged so that the inner subscripts match,

{[𝑇]}_{ℬ︀ ℬ︀} = {[id]}_{ℬ︀ ℰ︀} {[𝑇]}_{ℰ︀ ℰ︀} {[id]}_{ℰ︀ ℬ︀} = 𝑃^{- 1} {[𝑇]}_{ℰ︀ ℰ︀} 𝑃,

where ${[id]}_{ℬ︀ ℰ︀} = 𝑃^{- 1}$ by Example 2.5.21. The matrix $𝑃 = {[id]}_{ℰ︀ ℬ︀}$ converts $ℬ︀$ -coordinates into standard coordinates, so it is applied first, on the right; the computation put it on the left. In $𝑃 {[𝑇]}_{ℰ︀ ℰ︀} 𝑃^{- 1}$ the subscripts do not match: the factor $𝑃 = {[id]}_{ℰ︀ ℬ︀}$ expects $ℬ︀$ -coordinates, but it receives the standard coordinates produced by ${[𝑇]}_{ℰ︀ ℰ︀}$ .

The correct matrix.

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

As a check, $𝑇 (𝐛_{1}) =$ $(0, 1) =$ $- 𝐛_{1} +$ $𝐛_{2}$ and $𝑇 (𝐛_{2}) = (1, 1) = 𝐛_{2}$ , whose $ℬ︀$ -coordinates $(- 1, 1)$ and $(0, 1)$ are the columns found.

The wrong answer is not meaningless: $𝑃 {[𝑇]}_{ℰ︀ ℰ︀} 𝑃^{- 1}$ is the matrix of $𝑇$ in the basis $(1, 0), (- 1, 1)$ formed by the columns of $𝑃^{- 1}$ . That is one way to see that the error produces a plausible-looking matrix, which is why checking one column directly is worth the effort.

Exercise 2.8.14.routine Find the error in the following argument, show that its claim is false, and determine exactly when its conclusion holds.

Claim. If $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ are invertible, then ${(𝐴 𝐵)}^{- 1} = 𝐴^{- 1} 𝐵^{- 1}$ .

Proof. By associativity, $(𝐴 𝐵) (𝐴^{- 1} 𝐵^{- 1}) =$ $𝐴 𝐴^{- 1} 𝐵 𝐵^{- 1} =$ $𝐼_{𝑛}$ , and similarly $(𝐴^{- 1} 𝐵^{- 1}) (𝐴 𝐵) =$ $𝐼_{𝑛}$ . So ${(𝐴 𝐵)}^{- 1} = 𝐴^{- 1} 𝐵^{- 1}$ by Technique 2.5.16.

Solution.

Uses. Proposition 2.5.17 (Algebra of inverses), Proposition 2.4.14 (Algebra of matrices), Exercise 2.5.19

Techniques. Guess the inverse, then check both products (Technique 2.5.16), Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Associativity moves parentheses. Does it move factors past each other?

Hint 2.

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

always. When is

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

? Invert both sides.

Sketch. Associativity gives

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

𝐴 𝐵 𝐴^{- 1} 𝐵^{- 1}

; replacing

𝐵 𝐴^{- 1}

𝐴^{- 1} 𝐵

needs commutativity. With

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

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

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

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

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

{(𝐴 𝐵)}^{- 1}

. The conclusion holds exactly when

𝐴 𝐵 = 𝐵 𝐴

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

, and

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

iff, inverting both sides,

𝐴 𝐵 = 𝐵 𝐴

The error. Associativity regroups a product but keeps the order of its factors: $(𝐴 𝐵) (𝐴^{- 1} 𝐵^{- 1}) =$ $𝐴 𝐵 𝐴^{- 1} 𝐵^{- 1}$ . The step to $𝐴 𝐴^{- 1} 𝐵 𝐵^{- 1}$ moves $𝐴^{- 1}$ past $𝐵$ , which requires $𝐵 𝐴^{- 1} = 𝐴^{- 1} 𝐵$ .

The claim is false. Take $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$ , as in Exercise 2.5.19. There, ${(𝐴 𝐵)}^{- 1} =$ $𝐵^{- 1} 𝐴^{- 1} =$ $(\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix})$ , while $𝐴^{- 1} 𝐵^{- 1} = (\begin{matrix} 2 & - 1 \\ - 1 & 1 \end{matrix})$ .

When it holds. By Proposition 2.5.17(d), the matrix version of (b), ${(𝐴 𝐵)}^{- 1} = 𝐵^{- 1} 𝐴^{- 1}$ always. So the conclusion holds if and only if $𝐵^{- 1} 𝐴^{- 1} = 𝐴^{- 1} 𝐵^{- 1}$ . By the same result together with Proposition 2.5.17(a), both sides are invertible, with inverses $𝐴 𝐵$ and $𝐵 𝐴$ , and two invertible matrices are equal exactly when their inverses are. So the conclusion holds if and only if $𝐴 𝐵 = 𝐵 𝐴$ . In particular it holds for every pair when $𝑛 = 1$ , and fails for some pair whenever $𝑛 \geq 2$ (put the example above in the top left corner).

Exercise 2.8.15.standard Find the error in the following argument, show that its claim is false, and add a hypothesis under which the argument becomes correct.

Claim. If $𝑇 \in L (𝑉)$ has a left inverse, then $𝑇$ is invertible.

Proof. Let $𝑆 𝑇 = {id}_{𝑉}$ . Then $𝑇 𝑆 𝑇 = 𝑇 = {id}_{𝑉} 𝑇$ , so $(𝑇 𝑆 - {id}_{𝑉}) 𝑇 =$ $0 =$ $0 𝑇$ . Cancelling $𝑇$ on the right gives $𝑇 𝑆 - {id}_{𝑉} = 0$ . So $𝑇 𝑆 = {id}_{𝑉}$ , and $𝑆$ is a two-sided inverse of $𝑇$ .

Solution.

Uses. Corollary 2.5.6 (One-sided cancellation), Exercise 2.5.41, Exercise 2.5.33, Theorem 3.5.23 (One-sided inverses of square matrices)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Which property of

𝑇

allows cancelling it on the right (Corollary 2.5.6)? Does

𝑇

have it?

Hint 2. Try

𝑉 = 𝐹 [𝑥]

and

𝑇 = 𝑀

, multiplication by

𝑥

, with the left inverse

𝐿

of Exercise 2.5.41.

Sketch. Cancelling

𝑇

on the right requires

𝑇

to be right-invertible, which is what the argument is trying to prove. On

𝐹 [𝑥]

𝐿 𝑀 = id

but

𝑀 𝐿 (1) = 𝟎

, and

𝑀

is not surjective, so it has no right inverse. If

𝑇

is surjective, then

(𝑇 𝑆 - id) 𝑇 = 0

says that

𝑇 𝑆 - id

vanishes on

im 𝑇 = 𝑉

, and the argument is correct (Exercise 2.5.33(a)).

The error. By Corollary 2.5.6(b), $𝑇$ can be cancelled on the right when $𝑇$ is right-invertible. That is exactly what the argument is trying to prove, so the cancellation assumes the conclusion. The first two steps are fine; only the cancellation is not.

The claim is false. Let $𝑉 = 𝐹 [𝑥]$ , let $𝑀$ be multiplication by $𝑥$ , and let $𝐿 (𝑎_{0} + 𝑎_{1} 𝑥 + \dots + 𝑎_{𝑛} 𝑥^{𝑛}) =$ $𝑎_{1} +$ $𝑎_{2} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛 - 1}$ . Then $𝐿 𝑀 = {id}_{𝐹 [𝑥]}$ (Exercise 2.5.41), so $𝑀$ has a left inverse. But $𝑀$ is not surjective, since every value $𝑥 𝑞$ has constant term $0$ , so $𝑀$ has no right inverse (Proposition 2.5.5) and is not invertible. Indeed $(𝑀 𝐿 - id) (1) =$ $𝑀 (𝟎) -$ $1 =$ $- 1 \neq$ $𝟎$ , although $(𝑀 𝐿 - id) 𝑀 =$ $𝑀 (𝐿 𝑀) -$ $𝑀 =$ $0$ .

A repair. Suppose in addition that $𝑇$ is surjective. Then $(𝑇 𝑆 - {id}_{𝑉}) 𝑇 = 0$ says that $𝑇 𝑆 - {id}_{𝑉}$ vanishes at every $𝑇 (𝐯)$ , that is, on $im 𝑇 = 𝑉$ , so $𝑇 𝑆 = {id}_{𝑉}$ . This is Exercise 2.5.33(a). For $𝑉 = 𝐹^{𝑛}$ the claim itself is true (Theorem 3.5.23), but the argument above does not prove it, because it never uses that $𝑉$ is finite-dimensional.