4.8 Proof patterns · Matrix Theory

Chapter 4 attaches a number to every finite-dimensional space, and most of its proofs either compute such a number or use one to force a conclusion: a list that is too long has a relation, and an injective operator on a finite-dimensional space is onto. This section sorts the chapter’s arguments by the question they answer, solves two problems in three ways each to compare the moves, and lists the errors that the chapter’s exercises warn against. The exercises at the end practice one move at a time, and the problem set (Problems for Chapter 4) mixes them with earlier chapters.

4.8.1Relations and independent lists

There are three ways to get information about a list from its length.

Too many vectors (Technique 4.1.30). More than $dim 𝑉$ vectors in $𝑉$ satisfy a nontrivial relation. Nobody computes the relation; it exists, and often that is all we need: every square matrix satisfies a nonzero polynomial (Proposition 4.1.31), the inverse of an injective operator is a polynomial in it (Exercise 4.1.56), and a statement about subsets of ${1, \dots, 𝑛}$ follows from a relation among $𝑛 + 1$ vectors (Exercise 4.1.57). The smaller the space that contains the vectors, the shorter the relation, so it pays to look for a small one. The powers of an upper triangular $2 \times 2$ matrix stay in a space of dimension $3$ , not $4$ (Exercise 4.8.4(a)).
The right length. A list of length $dim 𝑉$ is a basis as soon as it is independent or spanning (Theorem 4.1.10(b), Corollary 4.1.11(b)), so half of the definition of a basis comes for free (Example 4.1.12). The same count squeezes the dimension of a subspace between an independent list inside it and a vector outside it (Example 4.1.22).
Kill terms (Technique 4.1.25). To show that a particular list is independent, apply an operator to a relation so that all but one term dies. Counting says nothing about a particular list; this move does.

The canonical use of the third move is the nilpotent chain (Proposition 4.1.26): if $𝑇^{𝑘} 𝐯 \neq 𝟎$ and $𝑇^{𝑘 + 1} 𝐯 = 𝟎$ , then $𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯$ is independent. It returns in every later chapter about operators, so here is why it works. The hypothesis $𝑇^{𝑘 + 1} 𝐯 = 𝟎$ is what makes $𝑇^{𝑘}$ kill every term except the first, and without it the argument collapses (Exercise 4.8.5). Nothing about $dim 𝑉$ is used, so the fact holds on $𝐹 [𝑥]$ as well. And it is a statement about one vector at a time, which is what lets it combine with counting: an independent list in $𝑉$ has at most $dim 𝑉$ entries, so when $𝑇$ is nilpotent, every vector dies within $dim 𝑉$ steps, and that is Corollary 4.1.27. When $𝑘 + 1 = dim 𝑉$ , the chain is a basis in which $𝑇$ is the shift (Exercise 4.5.50), and the vectors $𝐰$ whose chains span the same space are easy to describe (Exercise 4.8.8). In Section 7.2 the same proof runs with $𝑇$ replaced by $𝑁 = 𝑇 - 𝜆 id$ (Proposition 7.2.37). The last nonzero vector $𝑁^{𝑘} 𝐯$ is then an eigenvector, and the span of the chain is the smallest subspace that contains $𝐯$ and is mapped into itself by $𝑇$ (Corollary 7.2.38). Chains glued together are the Jordan bases of Section 10.3, and whether several chains can be glued is decided by their last vectors alone (Exercise 7.2.51).

Example 4.8.1 (A nilpotent operator dies within $𝑛$ steps, three ways). Let $dim 𝑉 = 𝑛$ , and let $𝑇 \in L (𝑉)$ satisfy $𝑇^{𝑚} = 0$ for some $𝑚 \geq 1$ . We show $𝑇^{𝑛} = 0$ .

Chains. Let $𝐯 \neq 𝟎$ , and let $𝑘$ be the largest index with $𝑇^{𝑘} 𝐯 \neq 𝟎$ ; it exists and $𝑘 < 𝑚$ , since $𝑇^{𝑚} 𝐯 = 𝟎$ . By Proposition 4.1.26, $𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯$ is an independent list of length $𝑘 + 1$ , so $𝑘 + 1 \leq 𝑛$ (Theorem 4.1.10(a)), and $𝑇^{𝑛} 𝐯 =$ $𝑇^{𝑛 - 𝑘 - 1} (𝑇^{𝑘 + 1} 𝐯) =$ $𝟎$ . This is the proof of Corollary 4.1.27.

Kernels. The kernels $ker 𝑇^{0} \subseteq$ $ker 𝑇 \subseteq$ $ker 𝑇^{2} \subseteq$ $\dots$ grow, and once two consecutive ones are equal, all later ones are equal (Exercise 4.2.51(b)). Let $𝑘$ be the first index with $ker 𝑇^{𝑘} = ker 𝑇^{𝑘 + 1}$ ; it exists, since the dimensions of the kernels are at most $𝑛$ and cannot increase forever. Before $𝑘$ every step is strict and raises the dimension by at least $1$ , so $𝑘 \leq dim ker 𝑇^{𝑘} \leq 𝑛$ . After $𝑘$ nothing changes, so $ker 𝑇^{𝑘} = ker 𝑇^{𝑗}$ for $𝑗 = max (𝑘, 𝑚)$ , which contains $ker 𝑇^{𝑚} = 𝑉$ . Hence $𝑇^{𝑘} = 0$ and $𝑇^{𝑛} =$ $𝑇^{𝑛 - 𝑘} 𝑇^{𝑘} =$ $0$ .

Restriction and induction on $dim 𝑉$ . We induct on $𝑛$ , assuming the statement for all spaces of dimension less than $𝑛$ . For $𝑛 = 0$ there is nothing to prove. Let $𝑛 \geq 1$ . If $𝑇$ were injective, every power of $𝑇$ would be injective, which is false for $𝑇^{𝑚} = 0$ on $𝑉 \neq {𝟎}$ . So $dim ker 𝑇 \geq 1$ , and $𝑈 = im 𝑇$ has $dim 𝑈 \leq 𝑛 - 1$ by Theorem 4.2.11. The operator $𝑇$ maps $𝑈$ into itself, and its restriction $𝑇_{𝑈} \in L (𝑈)$ satisfies $𝑇_{𝑈}^{𝑚} = 0$ . By the induction hypothesis, applied to $𝑈$ , $𝑇_{𝑈}^{dim 𝑈} = 0$ , so $𝑇_{𝑈}^{𝑛 - 1} = 0$ , and for every $𝐯$ ,

𝑇^{𝑛} 𝐯 = 𝑇^{𝑛 - 1} (𝑇 𝐯) = 𝑇_{𝑈}^{𝑛 - 1} (𝑇 𝐯) = 𝟎 .

The chain proof works one vector at a time, and when $𝑇^{𝑛 - 1} \neq 0$ it produces a basis. The kernel proof never looks at a vector. It only counts, and the numbers it counts, $dim ker 𝑇^{𝑘} -$ $dim ker 𝑇^{𝑘 - 1}$ , are the data from which the Jordan form is built (Exercise 4.2.52, Section 10.3). The restriction proof is an induction on the dimension, which is the shape of the triangularization proofs of Section 7.5, and it proves a little more: $rank 𝑇^{𝑘} \leq 𝑛 - 𝑘$ for $𝑘 \leq 𝑛$ . A fourth version runs the chain argument in a quotient, relative to a subspace that $𝑇$ maps into itself (Exercise 4.8.14). The bound $𝑛$ cannot be lowered, as the shift on $𝐹^{𝑛}$ shows.

Practice: Exercise 4.8.4, Exercise 4.8.8, and Exercise 4.8.9.

4.8.2Rank–nullity and restriction

Rank–nullity says that the kernel and the image of one map have complementary dimensions, so whichever is easier to find gives the other (Technique 4.2.24). Sometimes the image is easy, because the map is visibly onto a space of known dimension; this is how kernels of nonzero functionals were found to be hyperplanes (Example 4.2.25). Sometimes the kernel is easy, because degrees or a leading coefficient force it to be small, and then the image is everything (Example 4.2.28). The cleanest instance is Corollary 4.2.18: between spaces of the same finite dimension, uniqueness of solutions gives existence (Example 4.2.19). Counting also produces vectors that nobody constructs, in an intersection of large subspaces (Proposition 4.2.26) or in the kernel of a map into a smaller space (Corollary 4.2.21). For matrix equations that are linear in the unknown matrix, the same count applies to the map $𝑋 \mapsto 𝐴 𝑋 - 𝑋 𝐴$ or its relatives (Technique 4.2.29).

When only part of the domain matters, restrict first and then count (Technique 4.2.5). The restriction $𝑇 ↾_{𝑈}$ has kernel $𝑈 \cap ker 𝑇$ , so

dim im (𝑇 ↾_{𝑈}) = dim 𝑈 - dim (𝑈 \cap ker 𝑇)

(Exercise 4.2.44), and with $𝑈 = im 𝑆$ this is the exact rank of a composite, Proposition 4.3.5. Restriction to a hyperplane is a small model of the whole move (Exercise 4.8.7). Two cautions. A restriction is a map $𝑈 \to 𝑊$ , and it is an operator on $𝑈$ only when $𝑇$ maps $𝑈$ into itself, as $𝑇$ does with $im 𝑇$ in the third proof of Example 4.8.1. And none of this counting means anything when the dimensions are infinite (Exercise 4.8.6).

4.8.3Rank inequalities

An inequality between ranks is almost always a containment of subspaces followed by a count. For a product, the two easy containments are $im (𝐴 𝐵) \subseteq im 𝐴$ and $ker 𝐵 \subseteq ker (𝐴 𝐵)$ ; the first bounds $rank (𝐴 𝐵)$ by $rank 𝐴$ , and the second, through rank–nullity, by $rank 𝐵$ (Theorem 4.3.3, Remark 4.3.9). For an exact count, restrict $𝐴$ to $im 𝐵$ :

rank (𝐴 𝐵) = rank 𝐵 - dim (im 𝐵 \cap ker 𝐴)

((4.3.1)), and every lower bound for $rank (𝐴 𝐵)$ is an upper bound for the subtracted term. The transpose exchanges rows and columns without changing the rank (Theorem 4.3.8), so each statement about column spaces has a mirror statement about row spaces. Sums are handled by images, $im (𝐴 + 𝐵) \subseteq$ $im 𝐴 +$ $im 𝐵$ (Proposition 4.3.20), or by counting rank-one pieces (Corollary 4.3.24, Technique 4.3.17). Finally, several matrices can be packed into one block matrix, whose rank does not change under invertible block row and column operations (Proposition 4.3.1). The block method needs one fact about block triangular matrices.

Lemma 4.8.2 (Ranks of block triangular matrices). Let

𝑋 \in 𝐹^{𝑝 \times 𝑞}

𝑌 \in 𝐹^{𝑝 \times 𝑠}

𝑌^{'} \in 𝐹^{𝑟 \times 𝑞}

, and

𝑍 \in 𝐹^{𝑟 \times 𝑠}

(a) $rank (\begin{matrix} 𝑋 & 𝑌 \\ 0 & 𝑍 \end{matrix}) \geq$ $rank 𝑋 +$ $rank 𝑍$ and $rank (\begin{matrix} 𝑋 & 0 \\ 𝑌^{'} & 𝑍 \end{matrix}) \geq$ $rank 𝑋 +$ $rank 𝑍$ .
(b) $rank (\begin{matrix} 𝑋 & 0 \\ 0 & 𝑍 \end{matrix}) =$ $rank 𝑋 +$ $rank 𝑍$ .

Proof.standard

Uses. Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Proposition 2.6.18 (The column space is spanned by the columns), Theorem 1.5.5 (Independence is decided at zero), Theorem 4.1.10 (Independent lists are short), Theorem 4.3.8 (Row rank equals column rank), Proposition 4.4.2 (Sums are the smallest containing subspaces), Theorem 4.4.13 (Bases and dimension of a sum)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Take

rank 𝑋

independent columns of

𝑋

and

rank 𝑍

independent columns of

𝑍

, and look at the corresponding columns of the block matrix.

Hint 2. In a relation among these columns, read the bottom block first: the columns coming from

𝑋

have zero bottom part. For the lower triangular matrix, transpose.

Sketch. (a) Let

𝐱_{𝑗}

(

𝑗 \in 𝐽

) be

rank 𝑋

independent columns of

𝑋

and

𝐳_{𝑘}

(

𝑘 \in 𝐾

) be

rank 𝑍

independent columns of

𝑍

. The columns

(𝐱_{𝑗}, 𝟎)

and

(𝐲_{𝑘}, 𝐳_{𝑘})

(\begin{matrix} 𝑋 & 𝑌 \\ 0 & 𝑍 \end{matrix})

are independent: the bottom block of a relation kills the coefficients of the

𝐳_{𝑘}

, and then the top block kills the rest. Transposing gives the lower triangular case. (b) With

𝑌 = 0

, the column space lies in the sum of the column spaces of

(\begin{matrix} 𝑋 \\ 0 \end{matrix})

and

(\begin{matrix} 0 \\ 𝑍 \end{matrix})

, of dimension at most

rank 𝑋 + rank 𝑍

(a) Write $𝑀 = (\begin{matrix} 𝑋 & 𝑌 \\ 0 & 𝑍 \end{matrix})$ , and write vectors of $𝐹^{𝑝 + 𝑟}$ as pairs $(𝐚, 𝐛)$ with $𝐚 \in 𝐹^{𝑝}$ and $𝐛 \in 𝐹^{𝑟}$ . By Theorem 4.2.7, $𝑋$ has a set $𝐽$ of $𝑎 = rank 𝑋$ columns $𝐱_{𝑗}$ that are independent, and $𝑍$ has a set $𝐾$ of $𝑏 = rank 𝑍$ columns $𝐳_{𝑘}$ that are independent. The corresponding columns of $𝑀$ are $(𝐱_{𝑗}, 𝟎)$ for $𝑗 \in 𝐽$ and $(𝐲_{𝑘}, 𝐳_{𝑘})$ for $𝑘 \in 𝐾$ , where $𝐲_{𝑘}$ is the column of $𝑌$ above $𝐳_{𝑘}$ . Suppose

\sum_{𝑗 \in 𝐽} 𝛼_{𝑗} (𝐱_{𝑗}, 𝟎) + \sum_{𝑘 \in 𝐾} 𝛽_{𝑘} (𝐲_{𝑘}, 𝐳_{𝑘}) = (𝟎, 𝟎) .

The bottom block reads $\sum_{𝑘} 𝛽_{𝑘} 𝐳_{𝑘} = 𝟎$ , so every $𝛽_{𝑘} = 0$ . Then the top block reads $\sum_{𝑗} 𝛼_{𝑗} 𝐱_{𝑗} = 𝟎$ , so every $𝛼_{𝑗} = 0$ . So $𝑀$ has $𝑎 + 𝑏$ independent columns in its column space, and $rank 𝑀 \geq 𝑎 + 𝑏$ (Proposition 2.6.18, Theorem 4.1.10(a)). For the lower triangular matrix,

{(\begin{matrix} 𝑋 & 0 \\ 𝑌^{'} & 𝑍 \end{matrix})}^{𝖳} = (\begin{matrix} 𝑋^{𝖳} & 𝑌^{' 𝖳} \\ 0 & 𝑍^{𝖳} \end{matrix}),

and by Theorem 4.3.8 and the first case its rank is at least $rank 𝑋^{𝖳} +$ $rank 𝑍^{𝖳} =$ $rank 𝑋 +$ $rank 𝑍$ .

(b) By (a) the rank is at least $rank 𝑋 + rank 𝑍$ . Every column of $(\begin{matrix} 𝑋 & 0 \\ 0 & 𝑍 \end{matrix})$ is a column of $(\begin{matrix} 𝑋 \\ 0 \end{matrix})$ or of $(\begin{matrix} 0 \\ 𝑍 \end{matrix})$ , so the column space is contained in the sum of their column spaces (Proposition 4.4.2), which have dimensions $rank 𝑋$ and $rank 𝑍$ . By Theorem 4.4.13(a), its dimension is at most $rank 𝑋 + rank 𝑍$ . □

Example 4.8.3 (Sylvester’s inequality, three ways). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ . We show $rank (𝐴 𝐵) \geq$ $rank 𝐴 +$ $rank 𝐵 -$ $𝑛$ .

By restriction. By (4.3.1), $rank (𝐴 𝐵) =$ $rank 𝐵 -$ $dim (im 𝐵 \cap ker 𝐴)$ , and the subtracted space lies in $ker 𝐴$ , which has dimension $𝑛 - rank 𝐴$ . So $rank (𝐴 𝐵) \geq$ $rank 𝐵 -$ $(𝑛 - rank 𝐴)$ . This is the solution of Exercise 4.3.30(a).

By kernels. A vector $𝐱 \in 𝐹^{𝑝}$ lies in $ker (𝐴 𝐵)$ exactly when $𝐵 𝐱 \in ker 𝐴$ . So $𝑇_{𝐵}$ restricts to a linear map $𝑅 : ker (𝐴 𝐵) \to$ $ker 𝐴$ , whose kernel is $ker (𝐴 𝐵) \cap$ $ker 𝐵 =$ $ker 𝐵$ . Rank–nullity for $𝑅$ gives

dim ker (𝐴 𝐵) = dim ker 𝐵 + dim im 𝑅 \leq dim ker 𝐵 + dim ker 𝐴,

and rank–nullity for $𝐴 𝐵$ , $𝐵$ , and $𝐴$ turns this into $𝑝 -$ $rank (𝐴 𝐵) \leq$ $(𝑝 - rank 𝐵) +$ $(𝑛 - rank 𝐴)$ , which is the claim.

By blocks. Let $𝑀 =$ $(\begin{matrix} 𝐵 & 𝐼_{𝑛} \\ 0 & 𝐴 \end{matrix}) \in$ $𝐹^{(𝑛 + 𝑚) \times (𝑝 + 𝑛)}$ . By Lemma 4.8.2(a), $rank 𝑀 \geq$ $rank 𝐵 +$ $rank 𝐴$ . Clear the blocks with block row and column operations (Theorem 2.4.34):

(\begin{matrix} 𝐼_{𝑛} & 0 \\ - 𝐴 & 𝐼_{𝑚} \end{matrix}) (\begin{matrix} 𝐵 & 𝐼_{𝑛} \\ 0 & 𝐴 \end{matrix}) (\begin{matrix} 𝐼_{𝑝} & 0 \\ - 𝐵 & 𝐼_{𝑛} \end{matrix}) = (\begin{matrix} 𝐵 & 𝐼_{𝑛} \\ - 𝐴 𝐵 & 0 \end{matrix}) (\begin{matrix} 𝐼_{𝑝} & 0 \\ - 𝐵 & 𝐼_{𝑛} \end{matrix}) = (\begin{matrix} 0 & 𝐼_{𝑛} \\ - 𝐴 𝐵 & 0 \end{matrix}) .

The outer factors are invertible, with inverses obtained by changing the signs of $𝐴$ and $𝐵$ , so $𝑀$ has the rank of the last matrix (Proposition 4.3.1). Exchanging its two block columns is multiplication by an invertible permutation matrix and gives $(\begin{matrix} 𝐼_{𝑛} & 0 \\ 0 & - 𝐴 𝐵 \end{matrix})$ , of rank $𝑛 + rank (𝐴 𝐵)$ by Lemma 4.8.2(b). So $𝑛 +$ $rank (𝐴 𝐵) \geq$ $rank 𝐴 +$ $rank 𝐵$ .

The restriction proof is the most informative. It identifies the rank lost in the product, $rank 𝐵 -$ $rank (𝐴 𝐵) =$ $dim (im 𝐵 \cap ker 𝐴)$ , and the slack in Sylvester’s bound, $dim ker 𝐴 -$ $dim (im 𝐵 \cap ker 𝐴)$ , so it also gives the equality case, $ker 𝐴 \subseteq im 𝐵$ (Exercise 4.8.10). The kernel proof proves the inequality $dim ker (𝐴 𝐵) \leq$ $dim ker 𝐴 +$ $dim ker 𝐵$ , which makes sense for linear maps between any spaces as long as the two kernels are finite-dimensional, and it is the ingredient of the index formula in Problem 4.18. The block proof is mechanical: once the right block matrix is written down, everything is multiplication, and the same computation proves Frobenius’s inequality (Exercise 4.8.13). Its price is that the dimension argument hides inside Lemma 4.8.2, and the proof does not say where the rank goes.

Practice: Exercise 4.8.10, Exercise 4.8.13, and Exercise 4.8.11.

4.8.4Sums and direct sums

To show that a sum $𝑈_{1} + \dots + 𝑈_{𝑘}$ is direct, show that $𝟎$ has only the trivial decomposition, by sorting the terms of an equation into the summands they belong to (Technique 4.4.8). For two subspaces this is the single condition $𝑈 \cap 𝑊 = {𝟎}$ . For more, the induction of Technique 4.4.10 needs each $𝑈_{𝑘}$ to meet the sum of the previous ones trivially, and pairwise intersections are not enough (Non-example 4.4.6). In finite dimension there are two shortcuts. Counting: the sum is direct exactly when bases of the summands concatenate to an independent list, that is, when the dimensions add up (Theorem 4.4.13, Technique 4.4.14), and for $𝑉 = 𝑈 \oplus 𝑊$ any two of $𝑈 \cap 𝑊 = {𝟎}$ , $𝑈 + 𝑊 = 𝑉$ , and $dim 𝑈 + dim 𝑊 = dim 𝑉$ suffice (Proposition 4.4.21). Idempotents: an operator $𝑃$ with $𝑃^{2} = 𝑃$ splits $𝑉 = im 𝑃 \oplus ker 𝑃$ with no computation (Technique 4.4.28). In Problem 4.12 the decomposition $𝐹^{𝑛} = im 𝐴 \oplus ker 𝐴$ comes from a rank count instead (Exercise 4.2.50), and $𝐴 𝐵$ then turns out to be the idempotent that splits it.

The formula $dim (𝑈 + 𝑊) =$ $dim 𝑈 +$ $dim 𝑊 -$ $dim (𝑈 \cap 𝑊)$ received three proofs in Section 4.4.5, and the discussion after them compares them. Extending a basis of $𝑈 \cap 𝑊$ produces a basis of $𝑈 + 𝑊$ ; choosing a complement of $𝑈 \cap 𝑊$ inside $𝑈$ reduces the formula to the direct case; rank–nullity for a map onto $𝑈 + 𝑊$ is the one that computes. Read from the point of view of this section, they are Technique 4.1.18, Technique 4.4.14, and Technique 4.2.24, and a fourth proof uses quotients (Exercise 4.6.49). A fifth method, a single row reduction that produces bases of both $𝑈 + 𝑊$ and $𝑈 \cap 𝑊$ , is Problem 4.6.

4.8.5Choosing a basis, and transporting

Extend a basis (Technique 4.1.18) when a subspace $𝑈$ must be compared with the whole space or a map must be prescribed on $𝑈$ and left free elsewhere. Complements (Proposition 4.4.16), extensions of maps (Proposition 4.1.19), and functionals separating a vector from a subspace all come from one extended basis.

Choose a convenient basis (Technique 4.5.33) after checking that the statement does not depend on the basis. For statements that survive $𝐴 \mapsto 𝐺 𝐴 𝐻$ with $𝐺$ and $𝐻$ invertible, the convenient matrix is the rank normal form $(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix})$ (Corollary 4.5.22), as in Exercise 4.8.12. For statements about operators that survive similarity, the basis has to be the same on both sides, and the useful bases come from the operator: a basis adapted to a subspace that $𝑇$ maps into itself (Technique 4.5.36), or a chain $𝐯, 𝑇 𝐯, \dots$ . For instance, an idempotent $𝑃$ of rank $𝑟$ has, in a basis of $im 𝑃$ followed by a basis of $ker 𝑃$ , the matrix $(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix})$ , so $tr 𝑃 = 𝑟 * 1$ in one line, and its commutant can be read off the same matrix (Problem 4.4). The proof of $tr 𝑃 = 𝑟 * 1$ through a column–row factorization (Exercise 4.3.43) chooses no basis of $𝑉$ , but it computes where this proof only looks.

Transport along an isomorphism (Technique 4.5.7) when the space is made of polynomials, matrices, or maps and the question concerns only the linear structure. Coordinates make every $𝑛$ -dimensional space into $𝐹^{𝑛}$ , and $L (𝑉, 𝑊)$ into $𝐹^{𝑚 \times 𝑛}$ (Theorem 4.5.8). Only linear notions survive the trip. The degree of a polynomial, the product of two matrices, and the rank of a matrix seen as a vector of $𝐹^{𝑚 \times 𝑛}$ mean nothing in $𝐹^{𝑛}$ , and in infinite dimension an isomorphism can even land in a proper subspace (Exercise 4.5.54). To show that two matrices are not similar, transport nothing: compare invariants (Technique 4.5.29).

Practice: Exercise 4.8.12 and Exercise 4.8.4(e).

4.8.6Quotients and affine arguments Beyond 21-242

Quotients and affine geometry (Section 4.6, Section 4.7) are not part of 21-242.

A complement of $𝑈$ is a choice, and the quotient $𝑉 / 𝑈$ is the canonical object that every complement is isomorphic to (Proposition 4.6.29, Intuition (A complement is a choice; the quotient is not)). So proofs that choose a complement can usually be rewritten with a quotient, and the result no longer depends on the choice: rank–nullity becomes the first isomorphism theorem (Corollary 4.6.35), the dimension formula becomes the second (Exercise 4.6.49), and Frobenius’s inequality has a quotient proof (Exercise 4.6.53) next to the block proof of Exercise 4.8.13. The price is one check before anything else, that every definition on $𝑉 / 𝑈$ is independent of the representative (Technique 4.6.18). The second use of quotients is to split an operator that maps $𝑈$ into itself into a piece on $𝑈$ and a piece on $𝑉 / 𝑈$ (Proposition 4.6.32) and to induct on the dimension (Technique 4.6.31). Applied to the nilpotent chain, this gives a version of Proposition 4.1.26 relative to a subspace (Exercise 4.8.14). Quotients also make sense of rank–nullity in infinite dimension, where $dim 𝑉$ is not a number but the index $dim ker 𝑇 -$ $dim (𝑊 / im 𝑇)$ can be (Problem 4.18).

In affine geometry, a point of an affine subspace can serve as the origin (Technique 4.7.4), or every point can be given an extra coordinate $1$ (Technique 4.7.21). The first is shorter when one point is special, and the second treats all points alike. The affine version of too many vectors is that $𝑛 + 2$ points of an $𝑛$ -dimensional space are affinely dependent (Corollary 4.7.23), and splitting an affine dependence by the signs of its coefficients gives Radon’s theorem (Exercise 4.7.59), Carathéodory’s theorem (Technique 4.7.33), and Helly’s theorem (Problem 4.15).

4.8.7Reading the chapter’s proofs

Where finite dimension enters. The exchange lemma compares an independent list with a finite spanning list, and everything about dimension rests on it (Lemma 4.1.2). Extending an independent list to a basis terminates because independent lists are short (Theorem 4.1.16). Rank–nullity is an equation between numbers, and its corollary that injective operators are surjective fails on $𝐹 [𝑥]$ (Example 2.6.4). On the other hand, Proposition 4.1.26 and the restriction formula for $im (𝑇 𝑆)$ use no dimension at all, and the inequality $dim ker (𝐴 𝐵) \leq$ $dim ker 𝐴 +$ $dim ker 𝐵$ needs only finite-dimensional kernels. For each result, ask which of its steps needed finite dimension.

Inequalities come with their equality cases. Each inequality of the chapter came from a containment of subspaces and a count, and Proposition 4.1.21(b) says that equality of dimensions turns a containment into an equality. So the equality case can be read off the proof. $rank (𝑇 𝑆) = rank 𝑆$ exactly when $im 𝑆 \cap ker 𝑇 = {𝟎}$ (Proposition 4.3.5), Sylvester’s inequality is an equality exactly when $ker 𝐴 \subseteq im 𝐵$ (Exercise 4.8.10), and $dim (𝑈 + 𝑊) =$ $dim 𝑈 +$ $dim 𝑊$ exactly when $𝑈 \cap 𝑊 = {𝟎}$ . A proof that drops the subspace it is bounding, instead of writing it down, loses its equality case.

Existence without construction. Counting proves that a relation, a nonzero vector, or a solution exists, and says nothing about what it is: Proposition 4.1.31, Proposition 4.2.26, Corollary 4.2.18. Often the count also says where to look and how many unknowns to use, after which a small computation finds the object (Exercise 4.1.33, Example 4.2.28).

The field is part of the data. $ℂ^{𝑛}$ has dimension $2 𝑛$ over $ℝ$ (Remark 4.1.6, Exercise 4.2.37), and $1 + 1 = 0$ in $𝔽_{2}$ makes some sums direct over $ℚ$ and not over $𝔽_{2}$ (Problem 4.6). The rank of a matrix with rational entries is the same over $ℚ$ , $ℝ$ , and $ℂ$ , since Gauss–Jordan elimination never leaves $ℚ$ and the reduced form is unique (Theorem 3.3.17). For an integer matrix read modulo a prime $𝑝$ , the rank can only drop, so a rank computed modulo $𝑝$ is a lower bound over $ℚ$ (Problem 4.17), and it can drop (Exercise 4.2.36).

4.8.8Common errors

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

Pairwise for all at once. Subspaces that meet pairwise in ${𝟎}$ need not form a direct sum (Non-example 4.4.6, Exercise 4.4.37), and there is no inclusion–exclusion formula for three subspaces (Remark 4.4.22, Exercise 4.4.39).
Bases that are not adapted. A basis of $𝑉$ need not contain a basis of a subspace (Exercise 4.1.48), and bases of $𝑈$ and $𝑊$ need not contain a basis of $𝑈 \cap 𝑊$ (Exercise 4.4.38). Adapted bases have to be built, by extending a basis of the smaller space.
A subspace of the wrong space. The columns of $rref (𝐴)$ that span its column space are not columns of $𝐴$ , and $im (rref (𝐴)) \neq im 𝐴$ in general (Non-example 4.2.8, Exercise 4.3.35). Containments such as $ker (𝐴 𝐵) \subseteq$ $ker 𝐴 +$ $ker 𝐵$ compare subspaces of spaces that are different, or are false even when they are the same space (Exercise 4.8.11).
Order of factors. $rank (𝐴 𝐵) \neq$ $rank (𝐵 𝐴)$ in general, even for square matrices (Example 4.3.4, Exercise 4.3.36), although the difference is limited (Problem 4.11).
One invariant for all. Equal ranks do not make matrices similar (Exercise 4.5.45), and equal traces do not either.
Infinite dimension. Rank–nullity, injective if and only if surjective, and “a subspace of the same dimension is everything” all need finite dimension (Exercise 4.8.6, Exercise 4.5.54).
A missing hypothesis in a chain. $𝑇^{𝑘} 𝐯 \neq 𝟎$ alone does not make $𝐯, \dots, 𝑇^{𝑘} 𝐯$ independent (Exercise 4.8.5).
Extending the wrong list. A basis whose last vectors map to a basis of the image does not have its first vectors in the kernel (Exercise 4.2.45).
Uniqueness of choices that are not unique. Complements are not unique (Example 4.4.17), so “the complement” of a subspace means nothing. In quotients, well-definedness is the implication from equal cosets to equal values, not its converse (Exercise 4.6.43), and affine independence is not linear independence (Exercise 4.7.56).

Exercises

Exercise 4.8.4.routine Prove or disprove each statement with the shortest argument you can, and name the move you used.

(a)For every upper triangular $𝐴 \in 𝐹^{2 \times 2}$ there are $𝑐_{0},$ $𝑐_{1},$ $𝑐_{2},$ $𝑐_{3} \in$ $𝐹$ , not all $0$ , with $𝑐_{0} 𝐼_{2} +$ $𝑐_{1} 𝐴 +$ $𝑐_{2} 𝐴^{2} +$ $𝑐_{3} 𝐴^{3} =$ $0$ .
(b)There are $𝐴 \in 𝐹^{2 \times 3}$ and $𝐵 \in 𝐹^{3 \times 2}$ with $𝐵 𝐴 = 𝐼_{3}$ .
(c)Any two $4$ -dimensional subspaces of $𝐹^{7}$ have a nonzero vector in common.
(d)If $𝑇 \in L (𝐹^{5})$ satisfies $𝑇^{3} = 0$ , then $rank 𝑇 \leq 3$ .
(e)For every $𝐴 \in 𝐹^{2 \times 2}$ , the matrices $𝐴$ and $𝐴 + 𝐼_{2}$ are not similar. (The answer depends on $𝐹$ : decide for which fields it holds.)

Solution.

Uses. Proposition 2.4.36 (Products of upper triangular matrices), Lemma 2.4.24 (Matrix units), Theorem 4.1.10 (Independent lists are short), Theorem 4.3.3 (Rank of a product), Proposition 4.2.26 (Subspaces that must meet), Exercise 4.3.30, Proposition 4.5.27 (Similarity invariants), Proposition 2.4.27 (The trace is linear)

Techniques. Too many vectors force a dependence (Technique 4.1.30), Dimension counting (Technique 4.2.24), Rule out similarity with an invariant (Technique 4.5.29)

Hint 1. (a) In which subspace of

𝐹^{2 \times 2}

do the powers of

𝐴

lie, and what is its dimension? (b) Compare ranks. (c) Use Proposition 4.2.26.

Hint 2. (d) Iterate Sylvester’s inequality. (e) Traces differ by

2

. What happens when

2 = 0

Sketch. (a) True:

𝐼_{2}, 𝐴, 𝐴^{2}, 𝐴^{3}

lie in the

3

-dimensional space of upper triangular matrices (Technique 4.1.30). (b) False:

rank (𝐵 𝐴) \leq

rank 𝐴 \leq

2

. (c) True:

dim (𝑈 \cap 𝑊) \geq

4 +

4 -

7 =

1

. (d) True:

0 =

rank 𝑇^{3} \geq

3 rank 𝑇 -

10

; the bound is attained by a shift of size

3

next to one of size

2

. (e) True exactly when

1 + 1 \neq 0

𝐹

: then

tr (𝐴 + 𝐼_{2}) =

tr 𝐴 +

2 \neq

tr 𝐴

. When

1 + 1 = 0

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

and

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

are similar.

(a) True. The upper triangular matrices form a subspace of $𝐹^{2 \times 2}$ of dimension $3$ , with basis the matrix units $𝑈_{11}, 𝑈_{12}, 𝑈_{22}$ (Lemma 2.4.24), and products of upper triangular matrices are upper triangular (Proposition 2.4.36). So $𝐼_{2}, 𝐴, 𝐴^{2}, 𝐴^{3}$ are four vectors in a $3$ -dimensional space, and they are dependent (Theorem 4.1.10(a)). The move is Technique 4.1.30 in the smallest space available; in all of $𝐹^{2 \times 2}$ it would only give a relation among $𝐼_{2}, 𝐴, \dots, 𝐴^{4}$ .

(b) False. By Theorem 4.3.3, $rank (𝐵 𝐴) \leq$ $rank 𝐴 \leq$ $2$ , while $rank 𝐼_{3} = 3$ .

(c) True. By Proposition 4.2.26, $dim (𝑈 \cap 𝑊) \geq$ $4 +$ $4 -$ $7 =$ $1$ .

(d) True. Let $𝐴$ be the standard matrix of $𝑇$ , so $𝐴^{3} = 0$ . By Exercise 4.3.30(c) with $𝐴_{1} = 𝐴_{2} = 𝐴_{3} = 𝐴$ ,

0 = rank 𝐴^{3} \geq 3 rank 𝐴 - 2 \cdot 5,

so $rank 𝐴 \leq 10 / 3$ , and $rank 𝐴 \leq 3$ . The bound is attained: the operator that sends $𝐞_{3} \mapsto 𝐞_{2} \mapsto 𝐞_{1} \mapsto 𝟎$ and $𝐞_{5} \mapsto 𝐞_{4} \mapsto 𝟎$ has rank $3$ and cube $0$ .

(e) True exactly when $1 + 1 \neq 0$ in $𝐹$ , as over $ℚ$ , $ℝ$ , $ℂ$ , and $𝔽_{𝑝}$ for odd $𝑝$ . Similar matrices have the same trace (Proposition 4.5.27(b)), and $tr (𝐴 + 𝐼_{2}) = tr 𝐴 + 2$ (Proposition 2.4.27). If $2 \neq 0$ , the traces differ, so $𝐴 ≁ 𝐴 + 𝐼_{2}$ . If $2 = 0$ , as over $𝔽_{2}$ , the traces agree, and for $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ we get $𝐴 + 𝐼_{2} = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})$ , which is $𝑆^{- 1} 𝐴 𝑆$ for the swap $𝑆 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) = 𝑆^{- 1}$ . The move, comparing an invariant, can only prove that two matrices are not similar; to prove similarity, a matrix $𝑆$ has to be found (Technique 4.5.29).

Exercise 4.8.5.routine Find the error in the following argument, and show that the claim is false.

Claim. Let $𝑇 \in L (𝑉)$ , $𝐯 \in 𝑉$ , and $𝑘 \geq 1$ with $𝑇^{𝑘} 𝐯 \neq 𝟎$ . Then $𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯$ is linearly independent.

Proof. Suppose $𝑎_{0} 𝐯 +$ $𝑎_{1} 𝑇 𝐯 +$ $\dots +$ $𝑎_{𝑘} 𝑇^{𝑘} 𝐯 =$ $𝟎$ . Applying $𝑇^{𝑘}$ , every term except the first becomes a vector $𝑇^{𝑘 + 𝑗} 𝐯$ with $𝑗 \geq 1$ , which is $𝟎$ . So $𝑎_{0} 𝑇^{𝑘} 𝐯 = 𝟎$ , and $𝑎_{0} = 0$ . Applying $𝑇^{𝑘 - 1}$ to the remaining relation gives $𝑎_{1} = 0$ in the same way, and so on.

Solution.

Uses. Proposition 4.1.26 (Nilpotent chains are independent), Proposition 1.5.15 (Short lists, zeros, and repeats), Theorem 4.1.10 (Independent lists are short)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25), Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Why should

𝑇^{𝑘 + 1} 𝐯

𝟎

Hint 2. Try

𝑇 = {id}_{𝑉}

Sketch. The step “

𝑇^{𝑘 + 𝑗} 𝐯 = 𝟎

for

𝑗 \geq 1

” needs

𝑇^{𝑘 + 1} 𝐯 = 𝟎

, which is not assumed. For

𝑇 = {id}_{𝑉}

𝐯 \neq 𝟎

, and

𝑘 = 1

, the list

𝐯, 𝐯

is dependent. With the missing hypothesis the argument is the proof of Proposition 4.1.26.

The error. The argument uses $𝑇^{𝑘 + 𝑗} 𝐯 = 𝟎$ for $𝑗 \geq 1$ , which follows from $𝑇^{𝑘 + 1} 𝐯 = 𝟎$ but not from anything in the hypotheses. Only $𝑇^{𝑘} 𝐯 \neq 𝟎$ is assumed, and that says nothing about later powers.

The claim is false. Let $𝑇 = {id}_{𝑉}$ and $𝐯 \neq 𝟎$ , and $𝑘 = 1$ . Then $𝑇 𝐯 = 𝐯 \neq 𝟎$ , but the list $𝐯, 𝑇 𝐯 = 𝐯, 𝐯$ has a repeated vector and is dependent (Proposition 1.5.15). A less trivial example is the rotation $𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ on $ℝ^{2}$ , with $𝐯 = 𝐞_{1}$ and $𝑘 = 2$ : $𝑅^{2} 𝐞_{1} = - 𝐞_{1} \neq 𝟎$ , and $𝐞_{1}, 𝐞_{2}, - 𝐞_{1}$ is dependent. In fact, whenever $𝑘 \geq dim 𝑉$ , the list has more than $dim 𝑉$ entries and is dependent (Theorem 4.1.10(a)), whatever $𝑇$ is.

With the hypothesis $𝑇^{𝑘 + 1} 𝐯 = 𝟎$ added, every step of the argument is correct, and it is the proof of Proposition 4.1.26.

Exercise 4.8.6.routine Find the error in the following argument, and show that the claim is false.

Claim. Every injective operator $𝑇 \in L (𝑉)$ is surjective.

Proof. Since $𝑇$ is injective, $ker 𝑇 = {𝟎}$ . By rank–nullity, $dim im 𝑇 =$ $dim 𝑉 -$ $dim ker 𝑇 =$ $dim 𝑉$ . So $im 𝑇$ is a subspace of $𝑉$ of the same dimension as $𝑉$ , and therefore $im 𝑇 = 𝑉$ .

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Example 2.6.4 (Injective, surjective, both, neither), Exercise 4.5.54, Corollary 4.2.18 (Injective if and only if surjective)

Techniques. Dimension counting (Technique 4.2.24), Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Which results does the argument use, and what are their hypotheses?

Hint 2. Look at multiplication by

𝑥

𝐹 [𝑥]

Sketch. Rank–nullity and Proposition 4.1.21(b) assume

𝑉

finite-dimensional; for infinite-dimensional

𝑉

the equation

dim im 𝑇 = dim 𝑉 - 0

has no meaning as a computation with numbers. Multiplication by

𝑥

𝐹 [𝑥]

is injective, and

1

is not in its image. For finite-dimensional

𝑉

the argument is correct (Corollary 4.2.18).

The error. Both steps need $𝑉$ to be finite-dimensional. Rank–nullity (Theorem 4.2.11(b)) is stated for finite-dimensional domains, and “a subspace of the same dimension is everything” (Proposition 4.1.21(b)) is stated for finite-dimensional $𝑉$ . If $𝑉$ is infinite-dimensional, “ $dim 𝑉$ ” is not a number, and subtracting $dim ker 𝑇 = 0$ from it carries no information. Even the conclusion that $im 𝑇$ and $𝑉$ are isomorphic, which is true for an injective $𝑇$ , does not make them equal: $𝐹 [𝑥]$ is isomorphic to its proper subspace $𝑥 𝐹 [𝑥]$ (Exercise 4.5.54).

The claim is false. Let $𝑀 \in L (𝐹 [𝑥])$ be multiplication by $𝑥$ . If $𝑥 𝑝 = 𝟎$ , then $𝑝 = 𝟎$ , so $𝑀$ is injective. Every value $𝑥 𝑝$ has constant coefficient $0$ , so the constant polynomial $1$ is not a value, and $𝑀$ is not surjective (Example 2.6.4).

For finite-dimensional $𝑉$ the argument is correct, and it is the proof of Corollary 4.2.18.

Exercise 4.8.7.routine Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛 \geq 1$ , let $𝑇 \in L (𝑉, 𝑊)$ , and let $𝐻$ be a subspace of $𝑉$ with $dim 𝐻 = 𝑛 - 1$ .

(a)Show that $rank (𝑇 ↾_{𝐻})$ is $rank 𝑇$ or $rank 𝑇 - 1$ , and that it is $rank 𝑇 - 1$ if and only if $ker 𝑇 \subseteq 𝐻$ .
(b)Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ with $𝑛 \geq 2$ , and let $𝐴^{'}$ be $𝐴$ with column $𝑗$ deleted. Show that $rank 𝐴^{'} = rank 𝐴 - 1$ if column $𝑗$ is not a linear combination of the other columns, and $rank 𝐴^{'} = rank 𝐴$ otherwise. Prove this twice: from (a), and directly from the column spaces.
(c)Deduce that deleting $𝑘$ rows and $𝑙$ columns of a matrix, so that at least one row and one column remain, lowers its rank by at most $𝑘 + 𝑙$ .

Solution.

Uses. Exercise 4.2.44, Proposition 4.2.26 (Subspaces that must meet), Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.2.11 (Rank–nullity), Proposition 4.2.3 (Properties of restriction), Proposition 2.6.18 (The column space is spanned by the columns), Proposition 4.4.2 (Sums are the smallest containing subspaces), Theorem 4.3.8 (Row rank equals column rank), Proposition 1.5.14 (Appending a vector)

Techniques. Restrict to a subspace (Technique 4.2.5), Dimension counting (Technique 4.2.24)

Hint 1. (a)

rank (𝑇 ↾_{𝐻}) =

dim 𝐻 -

dim (𝐻 \cap ker 𝑇)

. How small can

𝐻 \cap ker 𝑇

be inside

ker 𝑇

Hint 2. (b)

𝐴^{'} 𝐱^{'} = 𝐴 𝐱

, where

𝐱

𝐱^{'}

with a

0

inserted in position

𝑗

. So

𝐴^{'}

𝑇_{𝐴}

restricted to the hyperplane

𝑥_{𝑗} = 0

. Directly:

im 𝐴 =

im 𝐴^{'} +

span (𝐚_{𝑗})

Sketch. (a)

rank (𝑇 ↾_{𝐻}) =

(𝑛 - 1) -

dim (𝐻 \cap ker 𝑇)

, and

dim ker 𝑇 -

1 \leq

dim (𝐻 \cap ker 𝑇) \leq

dim ker 𝑇

by Proposition 4.2.26; the upper value is attained exactly when

ker 𝑇 \subseteq 𝐻

. (b)

im 𝐴^{'} =

im (𝑇_{𝐴} ↾_{𝐻_{𝑗}})

with

𝐻_{𝑗} = {𝐱 | 𝑥_{𝑗} = 0}

, and

ker 𝐴 \subseteq 𝐻_{𝑗}

means no solution of

𝐴 𝐱 = 𝟎

has

𝑥_{𝑗} \neq 0

, which means that

𝐚_{𝑗}

is not a combination of the others. Directly,

im 𝐴 =

im 𝐴^{'} +

span (𝐚_{𝑗})

. (c) One column at a time, and rows by transposing.

(a) By Exercise 4.2.44(a), $rank (𝑇 ↾_{𝐻}) =$ $(𝑛 - 1) -$ $dim (𝐻 \cap ker 𝑇)$ . Since $𝐻 \cap ker 𝑇 \subseteq ker 𝑇$ , its dimension is at most $dim ker 𝑇$ , with equality if and only if $𝐻 \cap ker 𝑇 = ker 𝑇$ , that is, $ker 𝑇 \subseteq 𝐻$ (Proposition 4.1.21). By Proposition 4.2.26, $dim (𝐻 \cap ker 𝑇) \geq$ $(𝑛 - 1) +$ $dim ker 𝑇 -$ $𝑛 =$ $dim ker 𝑇 -$ $1$ . So $dim (𝐻 \cap ker 𝑇)$ is $dim ker 𝑇$ or $dim ker 𝑇 - 1$ , and with $rank 𝑇 =$ $𝑛 -$ $dim ker 𝑇$ (Theorem 4.2.11(b)),

rank (𝑇 ↾_{𝐻}) = {\begin{cases} rank 𝑇 - 1 & if ker 𝑇 \subseteq 𝐻 \\ rank 𝑇 & otherwise . \end{cases}

(b) From (a). Let $𝐻_{𝑗} =$ ${𝐱 \in 𝐹^{𝑛} | 𝑥_{𝑗} = 0}$ , a subspace of dimension $𝑛 - 1$ . For $𝐱^{'} \in 𝐹^{𝑛 - 1}$ , let $𝐱 \in 𝐻_{𝑗}$ be $𝐱^{'}$ with a $0$ inserted in position $𝑗$ ; this is a bijection $𝐹^{𝑛 - 1} \to 𝐻_{𝑗}$ , and $𝐴^{'} 𝐱^{'} = 𝐴 𝐱$ . So $im 𝐴^{'} =$ $im (𝑇_{𝐴} ↾_{𝐻_{𝑗}})$ , and by (a) the rank drops if and only if $ker 𝐴 \subseteq 𝐻_{𝑗}$ , that is, if and only if every solution of $𝐴 𝐱 = 𝟎$ has $𝑥_{𝑗} = 0$ . If $𝐚_{𝑗} =$ $\sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝐚_{𝑖}$ , then $𝐱 =$ $𝐞_{𝑗} -$ $\sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝐞_{𝑖}$ solves $𝐴 𝐱 = 𝟎$ with $𝑥_{𝑗} = 1$ . Conversely, if $𝐴 𝐱 = 𝟎$ with $𝑥_{𝑗} \neq 0$ , then $𝐚_{𝑗} =$ $- 𝑥_{𝑗}^{- 1} \sum_{𝑖 \neq 𝑗} 𝑥_{𝑖} 𝐚_{𝑖}$ . So $ker 𝐴 \subseteq 𝐻_{𝑗}$ exactly when $𝐚_{𝑗}$ is not a combination of the other columns.

Directly. By Proposition 2.6.18, $im 𝐴^{'}$ is spanned by the columns other than $𝐚_{𝑗}$ , and $im 𝐴 =$ $im 𝐴^{'} +$ $span (𝐚_{𝑗})$ (Proposition 4.4.2). If $𝐚_{𝑗} \in im 𝐴^{'}$ , the two images are equal. Otherwise a basis of $im 𝐴^{'}$ followed by $𝐚_{𝑗}$ is independent (Proposition 1.5.14) and spans $im 𝐴$ , so $rank 𝐴 = rank 𝐴^{'} + 1$ . The direct proof is shorter here, because deleting a column has an obvious effect on the column space; the restriction proof is the one that also applies to an arbitrary hyperplane, where there are no columns to delete.

(c) By (b), deleting one column lowers the rank by at most $1$ . Deleting a row of $𝐴$ deletes a column of $𝐴^{𝖳}$ , and $rank 𝐴^{𝖳} = rank 𝐴$ (Theorem 4.3.8), so it also lowers the rank by at most $1$ . Deleting $𝑘$ rows and $𝑙$ columns one at a time, each time from a matrix with at least two rows or two columns respectively, lowers the rank by at most $𝑘 + 𝑙$ .

Exercise 4.8.8.standard Let $𝑇 \in L (𝑉)$ , $𝐯 \in 𝑉$ , and $𝑘 \geq 0$ with $𝑇^{𝑘} 𝐯 \neq 𝟎$ and $𝑇^{𝑘 + 1} 𝐯 = 𝟎$ , and let $𝑊 =$ $span (𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯)$ .

(a)Let $𝐰 =$ $𝑎_{0} 𝐯 +$ $𝑎_{1} 𝑇 𝐯 +$ $\dots +$ $𝑎_{𝑘} 𝑇^{𝑘} 𝐯$ . Show that $𝐰, 𝑇 𝐰, \dots, 𝑇^{𝑘} 𝐰$ is a basis of $𝑊$ if and only if $𝑎_{0} \neq 0$ .
(b)Let $𝐹$ have $𝑞$ elements. How many $𝐰 \in 𝑊$ satisfy $𝑊 =$ $span (𝐰, 𝑇 𝐰, \dots, 𝑇^{𝑘} 𝐰)$ ?

Solution.

Uses. Proposition 4.1.26 (Nilpotent chains are independent), Theorem 4.1.10 (Independent lists are short), Proposition 1.5.15 (Short lists, zeros, and repeats), Proposition 1.2.35 (Zero products), Proposition 4.1.34 (Size of a vector space over a finite field)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25), Dimension counting (Technique 4.2.24)

Hint 1. Compute

𝑇^{𝑘} 𝐰

and

𝑇^{𝑘 + 1} 𝐰

. Only one term of

𝐰

survives

𝑇^{𝑘}

Hint 2. If

𝑎_{0} \neq 0

, the chain of

𝐰

is independent by Proposition 4.1.26, and it has the right length. If

𝑎_{0} = 0

, what is

𝑇^{𝑘} 𝐰

Sketch. (a)

𝑇^{𝑗} 𝐰 \in 𝑊

𝑇^{𝑘} 𝐰 = 𝑎_{0} 𝑇^{𝑘} 𝐯

, and

𝑇^{𝑘 + 1} 𝐰 = 𝟎

. If

𝑎_{0} \neq 0

, the chain of

𝐰

is independent of length

𝑘 + 1 = dim 𝑊

, so it is a basis. If

𝑎_{0} = 0

, its last vector is

𝟎

. (b) The coordinates

(𝑎_{0}, \dots, 𝑎_{𝑘})

𝐰

are unique, with

𝑎_{0} \neq 0

(𝑞 - 1) 𝑞^{𝑘}

vectors.

(a) By Proposition 4.1.26, $𝐯, \dots, 𝑇^{𝑘} 𝐯$ is a basis of $𝑊$ , so $dim 𝑊 = 𝑘 + 1$ . For $𝑗 \geq 0$ ,

𝑇^{𝑗} 𝐰 = \sum_{𝑖 = 0}^{𝑘} 𝑎_{𝑖} 𝑇^{𝑖 + 𝑗} 𝐯 \in 𝑊,

and since $𝑇^{𝑙} 𝐯 = 𝟎$ for $𝑙 \geq 𝑘 + 1$ , only the terms with $𝑖 + 𝑗 \leq 𝑘$ survive. In particular $𝑇^{𝑘} 𝐰 = 𝑎_{0} 𝑇^{𝑘} 𝐯$ and $𝑇^{𝑘 + 1} 𝐰 = 𝟎$ .

If $𝑎_{0} \neq 0$ , then $𝑇^{𝑘} 𝐰 \neq 𝟎$ (Proposition 1.2.35), so $𝐰, 𝑇 𝐰, \dots, 𝑇^{𝑘} 𝐰$ is independent by Proposition 4.1.26. It is a list of $𝑘 + 1 = dim 𝑊$ vectors in $𝑊$ , so it is a basis of $𝑊$ (Theorem 4.1.10(b)). If $𝑎_{0} = 0$ , then $𝑇^{𝑘} 𝐰 = 𝟎$ is an entry of the list, which is therefore dependent (Proposition 1.5.15) and not a basis.

(b) If $span (𝐰, \dots, 𝑇^{𝑘} 𝐰) =$ $𝑊$ , then this spanning list of length $dim 𝑊$ is a basis (Corollary 4.1.11(b)), so by (a) the condition is again $𝑎_{0} \neq 0$ . The vectors of $𝑊$ correspond bijectively to their coordinate vectors $(𝑎_{0}, \dots, 𝑎_{𝑘}) \in$ $𝐹^{𝑘 + 1}$ , and those with $𝑎_{0} \neq 0$ number $(𝑞 - 1) 𝑞^{𝑘}$ . So exactly $(𝑞 - 1) 𝑞^{𝑘}$ of the $𝑞^{𝑘 + 1}$ vectors of $𝑊$ (Proposition 4.1.34) generate it, that is, all except those in the hyperplane $span (𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯) =$ $im (𝑇 ↾_{𝑊})$ .

Exercise 4.8.9.standard Let $𝑛 \geq 1$ , and let $𝑆 \subseteq 𝐹^{𝑛 \times 𝑛}$ be a subspace with $𝐼_{𝑛} \in 𝑆$ and $𝑋 𝑌 \in 𝑆$ for all $𝑋, 𝑌 \in 𝑆$ . Let $𝐴 \in 𝑆$ be invertible.

(a)Show that $𝐴^{- 1} \in 𝑆$ by finding a relation among $𝐼_{𝑛},$ $𝐴,$ $𝐴^{2},$ $\dots,$ $𝐴^{𝑑}$ , where $𝑑 = dim 𝑆$ .
(b)Show again that $𝐴^{- 1} \in 𝑆$ , by applying rank–nullity to the map $𝑆 \to 𝑆$ , $𝑋 \mapsto 𝐴 𝑋$ .
(c)Deduce that the inverse of an invertible upper triangular matrix is upper triangular.

Solution.

Uses. Theorem 4.1.10 (Independent lists are short), Proposition 2.4.14 (Algebra of matrices), Corollary 4.2.18 (Injective if and only if surjective), Theorem 3.5.23 (One-sided inverses of square matrices), Proposition 2.4.36 (Products of upper triangular matrices), Exercise 4.1.56

Techniques. Too many vectors force a dependence (Technique 4.1.30), Dimension counting (Technique 4.2.24)

Hint 1. (a) The

𝑑 + 1

matrices

𝐼_{𝑛}, 𝐴, \dots, 𝐴^{𝑑}

lie in

𝑆

. In a relation among them, look at the smallest index with a nonzero coefficient, and multiply by a power of

𝐴^{- 1}

Hint 2. (b)

𝑋 \mapsto 𝐴 𝑋

maps

𝑆

into

𝑆

and is injective. Which

𝑋 \in 𝑆

does surjectivity produce?

Sketch. (a)

\sum_{𝑖 \geq 𝑗} 𝑐_{𝑖} 𝐴^{𝑖} = 0

with

𝑐_{𝑗} \neq 0

; multiplying by

𝐴^{- 𝑗}

gives

𝑐_{𝑗} 𝐼_{𝑛} =

- 𝐴 (𝑐_{𝑗 + 1} 𝐼_{𝑛} + \dots + 𝑐_{𝑑} 𝐴^{𝑑 - 𝑗 - 1})

, so

𝐴^{- 1}

is a polynomial in

𝐴

, hence in

𝑆

. (b)

𝐿 (𝑋) = 𝐴 𝑋

is injective on

𝑆

, hence surjective, so

𝐴 𝑋 = 𝐼_{𝑛}

for some

𝑋 \in 𝑆

, and

𝑋 = 𝐴^{- 1}

. (c) Upper triangular matrices form such an

𝑆

By induction, $𝐴^{𝑖} \in 𝑆$ for every $𝑖 \geq 0$ : $𝐴^{0} = 𝐼_{𝑛} \in 𝑆$ , and $𝐴^{𝑖 + 1} = 𝐴^{𝑖} 𝐴$ is a product of two elements of $𝑆$ .

(a) The $𝑑 + 1$ matrices $𝐼_{𝑛}, 𝐴, \dots, 𝐴^{𝑑}$ lie in the $𝑑$ -dimensional space $𝑆$ , so they satisfy a relation $\sum_{𝑖 = 0}^{𝑑} 𝑐_{𝑖} 𝐴^{𝑖} = 0$ with not all $𝑐_{𝑖} = 0$ (Theorem 4.1.10(a)). Let $𝑗$ be the smallest index with $𝑐_{𝑗} \neq 0$ . Multiplying $\sum_{𝑖 = 𝑗}^{𝑑} 𝑐_{𝑖} 𝐴^{𝑖} =$ $0$ by ${(𝐴^{- 1})}^{𝑗}$ gives

𝑐_{𝑗} 𝐼_{𝑛} + 𝑐_{𝑗 + 1} 𝐴 + \dots + 𝑐_{𝑑} 𝐴^{𝑑 - 𝑗} = 0 .

If $𝑗 = 𝑑$ this says $𝑐_{𝑑} 𝐼_{𝑛} = 0$ , which is impossible since $𝑛 \geq 1$ . So $𝑗 < 𝑑$ , and

𝐴 (𝑐_{𝑗 + 1} 𝐼_{𝑛} + 𝑐_{𝑗 + 2} 𝐴 + \dots + 𝑐_{𝑑} 𝐴^{𝑑 - 𝑗 - 1}) = - 𝑐_{𝑗} 𝐼_{𝑛} .

The matrix $𝐵 =$ $- 𝑐_{𝑗}^{- 1} (𝑐_{𝑗 + 1} 𝐼_{𝑛} + \dots + 𝑐_{𝑑} 𝐴^{𝑑 - 𝑗 - 1})$ lies in $𝑆$ and satisfies $𝐴 𝐵 = 𝐼_{𝑛}$ , so $𝐵 = 𝐴^{- 1}$ (multiply by $𝐴^{- 1}$ on the left). This is the argument of Exercise 4.1.56, run inside $𝑆$ .

(b) Let $𝐿 : 𝑆 \to 𝑆$ , $𝐿 (𝑋) = 𝐴 𝑋$ . It maps $𝑆$ into $𝑆$ by hypothesis, and it is linear by Proposition 2.4.14. It is injective: if $𝐴 𝑋 = 0$ , then $𝑋 = 𝐴^{- 1} 𝐴 𝑋 = 0$ . Since $𝑆$ is finite-dimensional, $𝐿$ is surjective (Corollary 4.2.18), so $𝐴 𝑋 = 𝐼_{𝑛}$ for some $𝑋 \in 𝑆$ , and then $𝑋 = 𝐴^{- 1}$ (Theorem 3.5.23).

The second proof is shorter and gives no formula; the first expresses $𝐴^{- 1}$ as a polynomial in $𝐴$ of degree less than $dim 𝑆$ , and so shows that $𝐴^{- 1}$ lies in every such $𝑆$ that contains $𝐴$ .

(c) The upper triangular matrices form a subspace of $𝐹^{𝑛 \times 𝑛}$ that contains $𝐼_{𝑛}$ and is closed under products (Proposition 2.4.36). By (a) or (b), it contains the inverse of each of its invertible elements.

Exercise 4.8.10.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ .

(a)Show that $rank (𝐴 𝐵) =$ $rank 𝐴 +$ $rank 𝐵 -$ $𝑛$ if and only if $ker 𝐴 \subseteq im 𝐵$ .
(b)Suppose $𝐴 𝐵 = 0$ . Show that $rank 𝐴 + rank 𝐵 \leq 𝑛$ , with equality if and only if $im 𝐵 = ker 𝐴$ .
(c)Let $𝑁 \in 𝐹^{𝑛 \times 𝑛}$ . Show that $rank (𝑁^{2}) =$ $2 rank 𝑁 -$ $𝑛$ if and only if $ker 𝑁 \subseteq im 𝑁$ , and check this on the shift $𝑁$ with $𝑁 𝐞_{1} = 𝟎$ and $𝑁 𝐞_{𝑗} = 𝐞_{𝑗 - 1}$ for $𝑗 \geq 2$ .

Solution.

Uses. Proposition 4.3.5 (Rank of a product, exactly), Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Proposition 2.6.15 (Kernels and images of composites)

Techniques. Restrict to a subspace (Technique 4.2.5)

Hint 1. Write both sides with (4.3.1):

rank (𝐴 𝐵) =

rank 𝐵 -

dim (im 𝐵 \cap ker 𝐴)

and

rank 𝐴 +

rank 𝐵 -

𝑛 =

rank 𝐵 -

dim ker 𝐴

Hint 2. When does a subspace of

ker 𝐴

have the dimension of

ker 𝐴

Sketch. (a) The difference of the two sides is

dim ker 𝐴 -

dim (im 𝐵 \cap ker 𝐴)

, which is

0

exactly when

im 𝐵 \cap ker 𝐴 = ker 𝐴

. (b)

𝐴 𝐵 = 0

means

im 𝐵 \subseteq ker 𝐴

, so

rank 𝐵 \leq 𝑛 - rank 𝐴

, with equality exactly when the containment is an equality. (c) (a) with

𝐴 = 𝐵 = 𝑁

; for the shift with

𝑛 \geq 2

ker 𝑁 =

span (𝐞_{1}) \subseteq

im 𝑁

and

rank 𝑁^{2} = 𝑛 - 2

(a) By (4.3.1) and Theorem 4.2.11(a),

rank (𝐴 𝐵) - (rank 𝐴 + rank 𝐵 - 𝑛) = dim ker 𝐴 - dim (im 𝐵 \cap ker 𝐴) .

Since $im 𝐵 \cap ker 𝐴 \subseteq ker 𝐴$ , this is $0$ if and only if $im 𝐵 \cap ker 𝐴 = ker 𝐴$ (Proposition 4.1.21(b)), that is, if and only if $ker 𝐴 \subseteq im 𝐵$ .

(b) $𝐴 𝐵 = 0$ means $𝐴 (𝐵 𝐱) = 𝟎$ for all $𝐱$ , that is, $im 𝐵 \subseteq ker 𝐴$ . So $rank 𝐵 \leq$ $dim ker 𝐴 =$ $𝑛 -$ $rank 𝐴$ , with equality if and only if $im 𝐵 = ker 𝐴$ (Proposition 4.1.21(b)). (This also follows from (a), since $rank (𝐴 𝐵) = 0$ .)

(c) Take $𝐴 = 𝐵 = 𝑁$ in (a). For the shift, $ker 𝑁 = span (𝐞_{1})$ and $im 𝑁 =$ $span (𝐞_{1}, \dots, 𝐞_{𝑛 - 1})$ , so $ker 𝑁 \subseteq im 𝑁$ when $𝑛 \geq 2$ . Indeed $𝑁^{2}$ sends $𝐞_{𝑗}$ to $𝐞_{𝑗 - 2}$ for $𝑗 \geq 3$ and kills $𝐞_{1}, 𝐞_{2}$ , so $rank 𝑁^{2} =$ $𝑛 -$ $2 =$ $2 (𝑛 - 1) -$ $𝑛$ . For $𝑛 = 1$ the shift is $0$ , and $ker 𝑁 = 𝐹^{1}$ is not contained in $im 𝑁 = {𝟎}$ ; indeed $rank 𝑁^{2} = 0 \neq 2 \cdot 0 - 1$ .

Exercise 4.8.11.standard Find the error in the following argument. Is the claim true? Give matrices for which the false step fails, and repair the argument.

Claim. For $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ , $dim ker (𝐴 𝐵) \leq$ $dim ker 𝐴 +$ $dim ker 𝐵$ , and hence $rank (𝐴 𝐵) \geq$ $rank 𝐴 +$ $rank 𝐵 -$ $𝑛$ .

Proof. If $𝐴 𝐵 𝐱 = 𝟎$ , then $𝐴$ kills $𝐵 𝐱$ , so either $𝐵 𝐱 = 𝟎$ or $𝐴$ kills $𝐱$ . Hence $ker (𝐴 𝐵) \subseteq$ $ker 𝐴 \cup$ $ker 𝐵 \subseteq$ $ker 𝐴 +$ $ker 𝐵$ , and by Theorem 4.4.19, $dim ker (𝐴 𝐵) \leq$ $dim (ker 𝐴 + ker 𝐵) \leq$ $dim ker 𝐴 +$ $dim ker 𝐵$ . Rank–nullity for $𝐴 𝐵$ , $𝐴$ , and $𝐵$ gives the second inequality.

Solution.

Uses. Theorem 4.4.19 (Dimension of a sum), Theorem 4.2.11 (Rank–nullity), Proposition 4.2.3 (Properties of restriction), Example 4.8.3 (Sylvester’s inequality, three ways)

Techniques. Restrict to a subspace (Technique 4.2.5), Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Does

𝐴 (𝐵 𝐱) = 𝟎

say anything about

𝐴 𝐱

Hint 2. Try

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

. For the repair, restrict

𝑇_{𝐵}

ker (𝐴 𝐵)

Sketch. “

𝐴

kills

𝐵 𝐱

” is not “

𝐴

kills

𝐱

”, and

ker (𝐴 𝐵) \subseteq

ker 𝐴 +

ker 𝐵

is false: for

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

ker 𝑁^{2} = 𝐹^{2}

but

ker 𝑁 +

ker 𝑁 =

span (𝐞_{1})

. The claim is true (Sylvester):

𝑇_{𝐵}

maps

ker (𝐴 𝐵)

into

ker 𝐴

with kernel

ker 𝐵

, so

dim ker (𝐴 𝐵) \leq

dim ker 𝐵 +

dim ker 𝐴

The error. From $𝐴 (𝐵 𝐱) = 𝟎$ we learn that $𝐵 𝐱 \in ker 𝐴$ , which says nothing about $𝐴 𝐱$ . The step treats $𝐴 𝐵 𝐱 = 𝟎$ like a product of numbers that vanishes only if a factor does. The resulting containment $ker (𝐴 𝐵) \subseteq$ $ker 𝐴 +$ $ker 𝐵$ is false. For $𝐴 = 𝐵 = 𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , we have $𝑁^{2} = 0$ , so $ker (𝐴 𝐵) = 𝐹^{2}$ , while $ker 𝑁 +$ $ker 𝑁 =$ $span (𝐞_{1})$ .

The claim is true. It is Sylvester’s inequality for square matrices. A repair is the kernel proof of Example 4.8.3. The vector $𝐵 𝐱$ lies in $ker 𝐴$ for every $𝐱 \in ker (𝐴 𝐵)$ , so $𝑇_{𝐵}$ restricts to a linear map $𝑅 : ker (𝐴 𝐵) \to$ $ker 𝐴$ (Proposition 4.2.3), and $ker 𝑅 =$ $ker (𝐴 𝐵) \cap$ $ker 𝐵 =$ $ker 𝐵$ . Rank–nullity for $𝑅$ gives

dim ker (𝐴 𝐵) = dim ker 𝐵 + dim im 𝑅 \leq dim ker 𝐵 + dim ker 𝐴 .

The repaired argument uses $𝐵$ to move $ker (𝐴 𝐵)$ into $ker 𝐴$ , where the false argument tried to place $ker (𝐴 𝐵)$ inside $ker 𝐴 + ker 𝐵$ directly. In the example, $𝑅$ is $𝑁$ restricted to $𝐹^{2}$ , which maps $𝐹^{2}$ onto $ker 𝑁$ with kernel $ker 𝑁$ , and the inequality $2 \leq 1 + 1$ is an equality.

Exercise 4.8.12.hard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have rank $𝑟$ , and let

Σ_{𝐴} = {𝑋 \in 𝐹^{𝑛 \times 𝑚} | 𝐴 𝑋 𝐴 = 𝐴} .

(a)Show that $Σ_{𝐴}$ is nonempty, and that $Σ_{𝐴} = 𝑋_{0} + 𝐾$ for any $𝑋_{0} \in Σ_{𝐴}$ , where $𝐾 = {𝑋 | 𝐴 𝑋 𝐴 = 0}$ is a subspace of $𝐹^{𝑛 \times 𝑚}$ with $dim 𝐾 = 𝑚 𝑛 - 𝑟^{2}$ .
(b)Let $𝐹$ have $𝑞$ elements. How many $𝑋$ satisfy $𝐴 𝑋 𝐴 = 𝐴$ ?
(c)For $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) \in ℚ^{2 \times 2}$ , describe $Σ_{𝐴}$ .

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Theorem 2.4.34 (Block multiplication), Corollary 2.6.31 (Fibers are translates of the kernel), Proposition 4.5.5 (Isomorphisms preserve linear structure), Proposition 4.1.34 (Size of a vector space over a finite field)

Techniques. Choose a convenient basis (Technique 4.5.33), Transport along an isomorphism (Technique 4.5.7)

Hint 1. The condition

𝐴 𝑋 𝐴 = 𝐴

survives

𝐴 \mapsto 𝐺 𝐴 𝐻

: if

𝐴 = 𝐺^{'} 𝑁 𝐻^{'}

with

𝐺^{'}, 𝐻^{'}

invertible, substitute and set

𝑌 = 𝐻^{'} 𝑋 𝐺^{'}

Hint 2. For

𝑁 =

(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix}) \in

𝐹^{𝑚 \times 𝑛}

and

𝑌 \in 𝐹^{𝑛 \times 𝑚}

in blocks,

𝑁 𝑌 𝑁 = (\begin{matrix} 𝑌_{11} & 0 \\ 0 & 0 \end{matrix})

Sketch. By Theorem 3.5.27,

𝐴 = 𝐺^{'} 𝑁 𝐻^{'}

with

𝐺^{'} = 𝐺^{- 1}

and

𝐻^{'} = 𝐻^{- 1}

invertible. Then

𝐴 𝑋 𝐴 =

𝐺^{'} (𝑁 𝑌 𝑁) 𝐻^{'}

with

𝑌 = 𝐻^{'} 𝑋 𝐺^{'}

, and

𝑋 \mapsto 𝐻^{'} 𝑋 𝐺^{'}

is an isomorphism of

𝐹^{𝑛 \times 𝑚}

𝑁 𝑌 𝑁 = (\begin{matrix} 𝑌_{11} & 0 \\ 0 & 0 \end{matrix})

, so

𝐾

corresponds to

𝑌_{11} = 0

, of dimension

𝑛 𝑚 - 𝑟^{2}

, and

𝑋_{0} =

𝐻^{' - 1} 𝑁^{𝖳} 𝐺^{' - 1}

solves

𝐴 𝑋 𝐴 = 𝐴

. Over

𝔽_{𝑞}

𝑞^{𝑚 𝑛 - 𝑟^{2}}

. (c)

𝐴 𝑋 𝐴 = 𝑠 𝐴

with

𝑠

the sum of the entries of

𝑋

, so

Σ_{𝐴}

is the set of

𝑋

whose entries add up to

1

(a) By Theorem 3.5.27 there are invertible $𝐺$ and $𝐻$ with $𝐺 𝐴 𝐻 = 𝑁$ , where $𝑁 =$ $(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix}) \in$ $𝐹^{𝑚 \times 𝑛}$ . Let $𝐺^{'} = 𝐺^{- 1}$ and $𝐻^{'} = 𝐻^{- 1}$ , so $𝐴 = 𝐺^{'} 𝑁 𝐻^{'}$ . For $𝑋 \in 𝐹^{𝑛 \times 𝑚}$ , put $𝑌 =$ $𝐻^{'} 𝑋 𝐺^{'} \in$ $𝐹^{𝑛 \times 𝑚}$ . Then

𝐴 𝑋 𝐴 = 𝐺^{'} 𝑁 𝐻^{'} 𝑋 𝐺^{'} 𝑁 𝐻^{'} = 𝐺^{'} (𝑁 𝑌 𝑁) 𝐻^{'} .

Since $𝐺^{'}$ and $𝐻^{'}$ are invertible, $𝐴 𝑋 𝐴 = 0$ if and only if $𝑁 𝑌 𝑁 = 0$ , and $𝐴 𝑋 𝐴 = 𝐴$ if and only if $𝑁 𝑌 𝑁 = 𝑁$ .

Write $𝑌 =$ $(\begin{matrix} 𝑌_{11} & 𝑌_{12} \\ 𝑌_{21} & 𝑌_{22} \end{matrix})$ with $𝑌_{11} \in 𝐹^{𝑟 \times 𝑟}$ . By Theorem 2.4.34,

𝑁 𝑌 𝑁 = (\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 𝑌_{11} & 𝑌_{12} \\ 𝑌_{21} & 𝑌_{22} \end{matrix}) (\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 𝑌_{11} & 0 \\ 0 & 0 \end{matrix}) .

So $𝑁 𝑌 𝑁 = 0$ exactly when $𝑌_{11} = 0$ , and $𝑁 𝑌 𝑁 = 𝑁$ exactly when $𝑌_{11} = 𝐼_{𝑟}$ . The map $Φ (𝑋) = 𝐻^{'} 𝑋 𝐺^{'}$ is linear and invertible on $𝐹^{𝑛 \times 𝑚}$ , with inverse $𝑌 \mapsto 𝐻 𝑌 𝐺$ . It carries $𝐾$ onto $𝐾_{0} = {𝑌 | 𝑌_{11} = 0}$ , the matrices whose top left $𝑟 \times 𝑟$ block is zero, a subspace of dimension $𝑛 𝑚 - 𝑟^{2}$ . By Proposition 4.5.5, $𝐾$ is a subspace and $dim 𝐾 = 𝑚 𝑛 - 𝑟^{2}$ .

The matrix $𝑌_{0} = 𝑁^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ has $𝑌_{11} = 𝐼_{𝑟}$ , so $𝑋_{0} =$ $Φ^{- 1} (𝑌_{0}) =$ $𝐻 𝑁^{𝖳} 𝐺$ lies in $Σ_{𝐴}$ . Finally, $Σ_{𝐴}$ is the set of solutions of $Ψ (𝑋) = 𝐴$ for the linear map $Ψ (𝑋) = 𝐴 𝑋 𝐴$ , so it is $𝑋_{0} + ker Ψ = 𝑋_{0} + 𝐾$ for any solution $𝑋_{0}$ (Corollary 2.6.31).

(b) $𝑋 \mapsto 𝑋 - 𝑋_{0}$ is a bijection from $Σ_{𝐴}$ onto $𝐾$ , which has $𝑞^{𝑚 𝑛 - 𝑟^{2}}$ elements (Proposition 4.1.34). So there are $𝑞^{𝑚 𝑛 - 𝑟^{2}}$ solutions. For an invertible $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , this is $𝑞^{0} = 1$ : the only solution is $𝐴^{- 1}$ .

(c) Here $𝐴 = 𝟏 𝟏^{𝖳}$ with $𝟏 = (1, 1)$ , so $𝐴 𝑋 𝐴 =$ $𝟏 (𝟏^{𝖳} 𝑋 𝟏) 𝟏^{𝖳} =$ $𝑠 𝐴$ , where $𝑠 = 𝟏^{𝖳} 𝑋 𝟏$ is the sum of the four entries of $𝑋$ . So $𝐴 𝑋 𝐴 = 𝐴$ if and only if the entries of $𝑋$ add up to $1$ . This is a translate of the $3$ -dimensional subspace of matrices whose entries add up to $0$ , in agreement with $𝑚 𝑛 - 𝑟^{2} = 4 - 1$ .

Exercise 4.8.13.hard (Frobenius’s inequality by blocks.) Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ , and $𝐶 \in 𝐹^{𝑝 \times 𝑞}$ , and let

𝑀 = (\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 𝐵 𝐶 \end{matrix}) \in 𝐹^{(𝑚 + 𝑛) \times (𝑝 + 𝑞)} .

(a)Compute $(\begin{matrix} 𝐼_{𝑚} & - 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix}) 𝑀 (\begin{matrix} 𝐼_{𝑝} & - 𝐶 \\ 0 & 𝐼_{𝑞} \end{matrix})$ .
(b)Deduce $rank (𝐴 𝐵) +$ $rank (𝐵 𝐶) \leq$ $rank 𝐵 +$ $rank (𝐴 𝐵 𝐶)$ .
(c)Recover Sylvester’s inequality as a special case.

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Proposition 4.3.1 (Invertible factors preserve rank), Lemma 4.8.2 (Ranks of block triangular matrices), Example 4.8.3 (Sylvester’s inequality, three ways), Exercise 4.3.31

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. The left factor subtracts

𝐴

times the second block row from the first, and the right factor subtracts the first block column times

𝐶

from the second.

Hint 2. The result is

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

. Compare its rank with that of

𝑀

, using Lemma 4.8.2.

Sketch. (a)

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

. (b) The outer factors are invertible, so

rank 𝑀 =

rank 𝐵 +

rank (𝐴 𝐵 𝐶)

(swap the block columns and use the block diagonal case of the lemma), while

rank 𝑀 \geq

rank (𝐴 𝐵) +

rank (𝐵 𝐶)

by the lower triangular case. (c)

𝐵 = 𝐼_{𝑛}

(a) By Theorem 2.4.34,

(\begin{matrix} 𝐼_{𝑚} & - 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix}) (\begin{matrix} 𝐴 𝐵 & 0 \\ 𝐵 & 𝐵 𝐶 \end{matrix}) = (\begin{matrix} 𝐴 𝐵 - 𝐴 𝐵 & - 𝐴 𝐵 𝐶 \\ 𝐵 & 𝐵 𝐶 \end{matrix}) = (\begin{matrix} 0 & - 𝐴 𝐵 𝐶 \\ 𝐵 & 𝐵 𝐶 \end{matrix}),

and

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

(b) The matrices $(\begin{matrix} 𝐼_{𝑚} & - 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})$ and $(\begin{matrix} 𝐼_{𝑝} & - 𝐶 \\ 0 & 𝐼_{𝑞} \end{matrix})$ are invertible, with inverses $(\begin{matrix} 𝐼_{𝑚} & 𝐴 \\ 0 & 𝐼_{𝑛} \end{matrix})$ and $(\begin{matrix} 𝐼_{𝑝} & 𝐶 \\ 0 & 𝐼_{𝑞} \end{matrix})$ , as block multiplication checks. So $rank 𝑀 =$ $rank (\begin{matrix} 0 & - 𝐴 𝐵 𝐶 \\ 𝐵 & 0 \end{matrix})$ by Proposition 4.3.1. Exchanging the two block columns of the last matrix (multiplication on the right by an invertible permutation matrix) gives $(\begin{matrix} - 𝐴 𝐵 𝐶 & 0 \\ 0 & 𝐵 \end{matrix})$ , whose rank is $rank (𝐴 𝐵 𝐶) +$ $rank 𝐵$ by Lemma 4.8.2(b). On the other hand, $𝑀$ is block lower triangular with diagonal blocks $𝐴 𝐵$ and $𝐵 𝐶$ , so $rank 𝑀 \geq$ $rank (𝐴 𝐵) +$ $rank (𝐵 𝐶)$ by Lemma 4.8.2(a). Together,

rank (𝐴 𝐵) + rank (𝐵 𝐶) \leq rank 𝑀 = rank 𝐵 + rank (𝐴 𝐵 𝐶) .

(c) Take $𝑛 = 𝑝$ and $𝐵 = 𝐼_{𝑛}$ , with $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐶 \in 𝐹^{𝑛 \times 𝑞}$ . Then (b) reads $rank 𝐴 +$ $rank 𝐶 \leq$ $𝑛 +$ $rank (𝐴 𝐶)$ , which is Sylvester’s inequality for the product $𝐴 𝐶$ , and the computation in (a) becomes the one in Example 4.8.3 (up to the order of the blocks). Exercise 4.3.31 proves the same inequality by restriction.

Exercise 4.8.14.standardBeyond 21-242 Let $𝑇 \in L (𝑉)$ , and let $𝑈$ be a subspace of $𝑉$ with $𝑇 (𝐮) \in 𝑈$ for all $𝐮 \in 𝑈$ . Let $𝐯 \in 𝑉$ and $𝑘 \geq 0$ with $𝑇^{𝑘} 𝐯 \notin 𝑈$ and $𝑇^{𝑘 + 1} 𝐯 \in 𝑈$ .

(a)Show that the cosets $𝐯 +$ $𝑈,$ $𝑇 𝐯 +$ $𝑈,$ $\dots,$ $𝑇^{𝑘} 𝐯 +$ $𝑈$ are linearly independent in $𝑉 / 𝑈$ . Deduce that $𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯$ is linearly independent and that its span meets $𝑈$ only in $𝟎$ .
(b)Let $𝑉$ be finite-dimensional, and suppose $𝑇^{𝑚} (𝑉) \subseteq 𝑈$ for some $𝑚 \geq 1$ . Show that $𝑇^{𝑑} (𝑉) \subseteq 𝑈$ , where $𝑑 = dim 𝑉 - dim 𝑈$ . Which earlier result is the case $𝑈 = {𝟎}$ ?

Solution.

Uses. Proposition 4.6.32 (Operators on a quotient), Proposition 4.1.26 (Nilpotent chains are independent), Corollary 4.6.15 (Cosets partition $𝑉$ ), Theorem 4.6.27 (Dimension of a quotient), Theorem 4.1.10 (Independent lists are short), Corollary 4.1.27 (A nilpotent operator dies within $dim 𝑉$ steps)

Techniques. Pass to a quotient (Technique 4.6.31), Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. Apply Proposition 4.1.26 to the induced operator

𝑇 / 𝑈

𝑉 / 𝑈

and the vector

𝐯 + 𝑈

Hint 2. For (b), let

𝑘

be the largest index with

𝑇^{𝑘} 𝐯 \notin 𝑈

, and count in

𝑉 / 𝑈

Sketch. (a)

{(𝑇 / 𝑈)}^{𝑗} (𝐯 + 𝑈) =

𝑇^{𝑗} 𝐯 +

𝑈

, which is nonzero for

𝑗 = 𝑘

and zero for

𝑗 = 𝑘 + 1

; Proposition 4.1.26 in

𝑉 / 𝑈

gives independence. A combination of the

𝑇^{𝑖} 𝐯

that lies in

𝑈

gives a relation among the cosets, so all coefficients vanish. (b) For

𝐯

with

𝑇^{𝑘} 𝐯 \notin 𝑈

𝑇^{𝑘 + 1} 𝐯 \in 𝑈

, (a) gives

𝑘 + 1 \leq dim 𝑉 / 𝑈 = 𝑑

; if

𝐯 \in 𝑈

already, every

𝑇^{𝑗} 𝐯 \in 𝑈

. The case

𝑈 = {𝟎}

is Corollary 4.1.27.

(a) By Proposition 4.6.32(a), there is an operator $𝑇 / 𝑈$ on $𝑉 / 𝑈$ with $(𝑇 / 𝑈) (𝐱 + 𝑈) =$ $𝑇 𝐱 +$ $𝑈$ , and by induction on $𝑗$ , ${(𝑇 / 𝑈)}^{𝑗} (𝐯 + 𝑈) =$ $𝑇^{𝑗} 𝐯 +$ $𝑈$ . By Corollary 4.6.15(c), $𝑇^{𝑘} 𝐯 + 𝑈$ is not the zero coset, since $𝑇^{𝑘} 𝐯 \notin 𝑈$ , and $𝑇^{𝑘 + 1} 𝐯 + 𝑈$ is the zero coset. By Proposition 4.1.26, applied to $𝑇 / 𝑈$ and $𝐯 + 𝑈$ , the cosets $𝐯 + 𝑈, \dots, 𝑇^{𝑘} 𝐯 + 𝑈$ are independent.

Now suppose $𝐲 =$ $\sum_{𝑖 = 0}^{𝑘} 𝑎_{𝑖} 𝑇^{𝑖} 𝐯 \in$ $𝑈$ . Then $\sum_{𝑖} 𝑎_{𝑖} (𝑇^{𝑖} 𝐯 + 𝑈) =$ $𝐲 +$ $𝑈 =$ $𝑈$ , the zero of $𝑉 / 𝑈$ , so every $𝑎_{𝑖} = 0$ and $𝐲 = 𝟎$ . Taking $𝐲 = 𝟎$ shows that the list is independent, and in general this shows that its span meets $𝑈$ only in $𝟎$ .

(b) Let $𝐯 \in 𝑉$ . If $𝐯 \in 𝑈$ , then $𝑇^{𝑗} 𝐯 \in 𝑈$ for every $𝑗$ , because $𝑇$ maps $𝑈$ into itself. Otherwise let $𝑘$ be the largest index with $𝑇^{𝑘} 𝐯 \notin 𝑈$ ; it exists and $𝑘 < 𝑚$ , since $𝑇^{𝑚} 𝐯 \in 𝑈$ and, once a vector $𝑇^{𝑗} 𝐯$ lies in $𝑈$ , so do all later ones. By (a), $𝑉 / 𝑈$ contains $𝑘 + 1$ independent cosets, and $dim 𝑉 / 𝑈 =$ $dim 𝑉 -$ $dim 𝑈 =$ $𝑑$ (Theorem 4.6.27), so $𝑘 + 1 \leq 𝑑$ (Theorem 4.1.10(a)). Hence $𝑇^{𝑑} 𝐯 =$ $𝑇^{𝑑 - 𝑘 - 1} (𝑇^{𝑘 + 1} 𝐯) \in$ $𝑈$ . So $𝑇^{𝑑} (𝑉) \subseteq 𝑈$ .

For $𝑈 = {𝟎}$ , the hypothesis says that $𝑇$ is nilpotent, and the conclusion is $𝑇^{dim 𝑉} = 0$ , which is Corollary 4.1.27. In general $𝑇$ is only nilpotent “modulo $𝑈$ ”, and the bound is the dimension of what is left, $𝑉 / 𝑈$ .