4.2 Rank–nullity · Matrix Theory

A linear map $𝑇 : 𝑉 \to 𝑊$ collapses $ker 𝑇$ to $𝟎$ and reaches $im 𝑇$ . In Section 2.6 we measured the two separately; with dimension available we can compare them. The answer is the rank–nullity theorem: if $𝑉$ is finite-dimensional, then

dim ker 𝑇 + dim im 𝑇 = dim 𝑉 .

Informally, each of the $dim 𝑉$ independent directions in $𝑉$ is either collapsed by $𝑇$ or carried over to $𝑊$ . For a matrix, the statement is that every column is either a pivot column or a free column.

We follow the lecture’s route. Restricting a map to a subspace (Section 4.2.1) lets us compute $dim im 𝑇_{𝐴} = rank 𝐴$ (Section 4.2.3), and counting free columns then proves rank–nullity for matrices. A second proof, which extends a basis of $ker 𝑇$ , works directly for every linear map (Section 4.2.4). The rest of the section draws consequences. Among them are the fact that the rank of a matrix of a linear map does not depend on the bases, which closes a question left open in Section 3.5, and dimension counting, a way to prove that vectors with some property exist without finding them. We end with an application outside the course, error-correcting codes over $𝔽_{2}$ .

Throughout, $𝑉$ and $𝑊$ are vector spaces over a field $𝐹$ .

4.2.1Restriction

Restricting a function keeps its rule and shrinks its set of inputs. We have already written $im (𝑇 ↾_{𝑋})$ for the set of values of $𝑇$ on a subset $𝑋$ (Proposition 2.1.16, Proposition 2.6.15). Here is the definition behind the notation.

Definition 4.2.1 (Restriction). Let $𝑔 : 𝑋 \to 𝑌$ be a function and let $𝐴 \subseteq 𝑋$ . The restriction of $𝑔$ to $𝐴$ is the function

𝑔 ↾_{𝐴} : 𝐴 \to 𝑌, 𝑎 \mapsto 𝑔 (𝑎) .

Only the domain changes. The target is still $𝑌$ , even when every value of $𝑔 ↾_{𝐴}$ happens to lie in some smaller set. The image of the restriction,

im (𝑔 ↾_{𝐴}) = {𝑔 (𝑎) | 𝑎 \in 𝐴},

is the set of values of $𝑔$ on $𝐴$ , which Section 2.1.4 wrote as $𝑇 (𝐴)$ ; from now on we always write $im (𝑔 ↾_{𝐴})$ . (For any function $𝑔 : 𝑋 \to 𝑌$ , $im 𝑔 =$ ${𝑔 (𝑥) | 𝑥 \in 𝑋}$ , as for linear maps.)

Example 4.2.2 (What restriction can change).

(a)Let $𝑃 : ℝ^{2} \to ℝ^{2}$ , $𝑃 (𝑥, 𝑦) = (𝑥, 0)$ , be the projection onto the $𝑥$ -axis, and let $ℓ = span ((1, 1))$ . Then $𝑃 ↾_{ℓ} : ℓ \to ℝ^{2}$ sends $(𝑡, 𝑡) \mapsto (𝑡, 0)$ . It is injective, although $𝑃$ is not, and its image is the $𝑥$ -axis, all of $im 𝑃$ . Restricted to the $𝑦$ -axis instead, $𝑃$ becomes the zero map.
(b)Let $𝑄 : ℝ^{2} \to ℝ$ , $𝑄 (𝑥, 𝑦) = 𝑥 + 𝑦$ . It is surjective. Its restriction to the $𝑥$ -axis is still surjective (and now injective as well), but its restriction to the line $𝑦 = - 𝑥$ is the zero map, which is not surjective.

The lecture records the general behavior.

Proposition 4.2.3 (Properties of restriction).

(a)If $𝑔 : 𝑋 \to 𝑌$ is injective, then $𝑔 ↾_{𝐴}$ is injective for every $𝐴 \subseteq 𝑋$ .
(b)If $𝑓 : 𝑋 \to 𝑌$ and $𝑔 : 𝑌 \to 𝑍$ are functions, then $im (𝑔 \circ 𝑓) =$ $im (𝑔 ↾_{im 𝑓})$ .
(c)If $𝑇 \in L (𝑉, 𝑊)$ and $𝑈$ is a subspace of $𝑉$ , then $𝑇 ↾_{𝑈} \in L (𝑈, 𝑊)$ and $ker (𝑇 ↾_{𝑈}) =$ $𝑈 \cap$ $ker 𝑇$ . In particular, $𝑇 ↾_{𝑈}$ is injective if and only if $𝑈 \cap ker 𝑇 = {𝟎}$ .

Proof.routine

Uses. Definition 4.2.1 (Restriction), Definition 1.4.1 (Subspace), Definition 2.1.1 (Linear map), Definition 2.6.5 (Kernel), Theorem 2.6.11 (Injectivity is decided at $𝟎$ )

Techniques. Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. Each part is an unwinding of definitions. For (b), write out both sides as sets of values.

Hint 2. For (c), the operations of

𝑈

are those of

𝑉

, so the linearity identities for

𝑇 ↾_{𝑈}

are instances of those for

𝑇

. Which

𝐮 \in 𝑈

does

𝑇 ↾_{𝑈}

send to

𝟎

Sketch. (a)

𝑔 (𝑎) = 𝑔 (𝑎^{'})

forces

𝑎 = 𝑎^{'}

already in

𝑋

. (b) Both sides are

{𝑔 (𝑓 (𝑥)) | 𝑥 \in 𝑋}

. (c) Linearity is inherited, since

𝑈

is closed under the operations; the kernel is the set of

𝐮 \in 𝑈

with

𝑇 (𝐮) = 𝟎

, which is

𝑈 \cap ker 𝑇

; apply Theorem 2.6.11.

(a) If $𝑎, 𝑎^{'} \in 𝐴$ and $𝑔 ↾_{𝐴} (𝑎) =$ $𝑔 ↾_{𝐴} (𝑎^{'})$ , then $𝑔 (𝑎) = 𝑔 (𝑎^{'})$ , so $𝑎 = 𝑎^{'}$ because $𝑔$ is injective.

(b) By definition,

im (𝑔 \circ 𝑓) = {𝑔 (𝑓 (𝑥)) | 𝑥 \in 𝑋} = {𝑔 (𝑦) | 𝑦 \in im 𝑓} = im (𝑔 ↾_{im 𝑓}) .

For linear maps this is Proposition 2.6.15(b), whose proof did not use linearity.

(c) By Definition 1.4.1, $𝑈$ is a vector space with the operations of $𝑉$ . For $𝐮, 𝐮^{'} \in 𝑈$ and $𝑎 \in 𝐹$ , the vectors $𝐮 + 𝐮^{'}$ and $𝑎 𝐮$ lie in $𝑈$ , and

𝑇 ↾_{𝑈} (𝐮 + 𝐮^{'}) = 𝑇 (𝐮) + 𝑇 (𝐮^{'}), 𝑇 ↾_{𝑈} (𝑎 𝐮) = 𝑎 𝑇 (𝐮)

because $𝑇$ is linear. So $𝑇 ↾_{𝑈}$ is linear (Definition 2.1.1). Its kernel is ${𝐮 \in 𝑈 | 𝑇 (𝐮) = 𝟎} =$ $𝑈 \cap$ $ker 𝑇$ . The last statement is Theorem 2.6.11 applied to $𝑇 ↾_{𝑈}$ . □

Part (a) and Example 4.2.2(b) are the lecture’s remarks that restriction preserves injectivity but not surjectivity. Shrinking the domain removes inputs, which can remove coincidences of values but can also remove values. Part (b) says that the composite $𝑔 \circ 𝑓$ uses $𝑔$ only on the part of $𝑌$ that $𝑓$ reaches.

Exercise 4.2.4.routine Let $𝐷 : {ℝ [𝑥]}_{\leq 3} \to$ ${ℝ [𝑥]}_{\leq 3}$ be differentiation.

(a)Let $𝑈 = span (𝑥^{2}, 𝑥^{3})$ . Find $ker (𝐷 ↾_{𝑈})$ and $im (𝐷 ↾_{𝑈})$ .
(b)Let $𝑈^{'} = span (1, 𝑥)$ . Find $ker (𝐷 ↾_{𝑈^{'}})$ and $im (𝐷 ↾_{𝑈^{'}})$ .
(c)Find a subspace $𝑈^{″}$ such that $𝐷 ↾_{𝑈^{″}}$ is injective and $im (𝐷 ↾_{𝑈^{″}}) = im 𝐷$ .

Solution.

Uses. Proposition 4.2.3 (Properties of restriction), Proposition 2.1.16 (Linear maps preserve spans and linear relations), Example 2.1.9 (Maps of polynomials)

Hint 1.

ker 𝐷

is the constants. Intersect it with each subspace.

Hint 2. The image of a restriction to

span (ℒ︀)

is spanned by the values on

ℒ︀

(Proposition 2.1.16(a)).

Sketch.

ker 𝐷 = span (1)

. (a)

𝑈 \cap ker 𝐷 = {𝟎}

, so the kernel is

{𝟎}

and the image is

span (2 𝑥, 3 𝑥^{2}) =

span (𝑥, 𝑥^{2})

. (b)

𝑈^{'} \cap ker 𝐷 = span (1)

, and the image is

span (0, 1) = span (1)

. (c)

𝑈^{″} =

span (𝑥, 𝑥^{2}, 𝑥^{3})

Over $ℝ$ , $𝐷 (𝑎_{0} + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2} + 𝑎_{3} 𝑥^{3}) =$ $𝑎_{1} +$ $2 𝑎_{2} 𝑥 +$ $3 𝑎_{3} 𝑥^{2}$ is $𝟎$ exactly when $𝑎_{1} = 𝑎_{2} = 𝑎_{3} = 0$ , so $ker 𝐷 = span (1)$ .

(a) A polynomial $𝑎 𝑥^{2} + 𝑏 𝑥^{3}$ is constant only if $𝑎 = 𝑏 = 0$ , so $𝑈 \cap ker 𝐷 = {𝟎}$ , and $ker (𝐷 ↾_{𝑈}) = {𝟎}$ by Proposition 4.2.3(c). By Proposition 2.1.16(a), $im (𝐷 ↾_{𝑈}) =$ $span (𝐷 (𝑥^{2}), 𝐷 (𝑥^{3})) =$ $span (2 𝑥, 3 𝑥^{2}) =$ $span (𝑥, 𝑥^{2})$ .

(b) Here $𝑈^{'} \cap ker 𝐷 = span (1)$ , which is $ker (𝐷 ↾_{𝑈^{'}})$ , and $im (𝐷 ↾_{𝑈^{'}}) =$ $span (𝐷 (1), 𝐷 (𝑥)) =$ $span (𝟎, 1) =$ $span (1)$ .

(c) Let $𝑈^{″} =$ $span (𝑥, 𝑥^{2}, 𝑥^{3})$ . Its only constant is $𝟎$ , so $𝐷 ↾_{𝑈^{″}}$ is injective, and $im (𝐷 ↾_{𝑈^{″}}) =$ $span (1, 2 𝑥, 3 𝑥^{2}) =$ ${ℝ [𝑥]}_{\leq 2} =$ $im 𝐷$ . (So does $span (𝑥 + 1, 𝑥^{2}, 𝑥^{3})$ ; such a subspace is not unique.)

Restriction is a small idea that we will use constantly, so we name it.

Technique 4.2.5 (Restrict to a subspace). To study a linear map on part of its domain, restrict it. For a subspace $𝑈$ of $𝑉$ , the map $𝑇 ↾_{𝑈} : 𝑈 \to 𝑊$ is linear, its kernel is $𝑈 \cap ker 𝑇$ , and its image is the set of values of $𝑇$ on $𝑈$ (Proposition 4.2.3). Everything known about linear maps then applies to $𝑇 ↾_{𝑈}$ , which is often better behaved than $𝑇$ : it can be injective when $𝑇$ is not, and its domain is smaller. The most common entry point is the identity $im (𝑇 𝑆) =$ $im (𝑇 ↾_{im 𝑆})$ , which says that the composite $𝑇 𝑆$ sees $𝑇$ only on the subspace $im 𝑆$ .

Reach for it when a composite is involved, when a hypothesis concerns only part of $𝑉$ (an image, a kernel, a subspace that $𝑇$ maps into itself), or when $𝑇$ is injective on a subspace you care about. The canonical example is the proof of Theorem 4.2.7, which restricts $𝑇_{𝐺^{- 1}}$ to $im 𝑇_{𝐴_{𝑟}}$ . Later the same move bounds the rank of a product (Section 4.3) and turns an operator into a smaller operator on an invariant subspace (Section 7.2).

Used in 22 places and 3 practice exercises

Proposition 4.2.6, Theorem 4.2.7, Proposition 4.2.15, Proposition 4.2.26, Exercise 4.2.44, Exercise 4.2.52, Exercise 4.2.53, Proposition 4.3.1, Theorem 4.3.3, Proposition 4.3.5, Proposition 4.6.29, Exercise 4.6.52, Exercise 4.8.7, Exercise 4.8.10, Exercise 4.8.11, Problem 4.2, Problem 4.18, Corollary 6.6.22, Proposition 7.6.10, Proposition 7.6.12, Theorem 7.6.31, Notation 8.3.10; 3 practice exercises.

4.2.2Injective maps preserve dimension

An injective linear map loses nothing, so it should not lower dimension. The lecture proves this by pushing a basis forward, which we already did in Proposition 2.6.22.

Proposition 4.2.6 (Injective maps preserve dimension). Let

𝑇 \in L (𝑉, 𝑊)

(a)If $𝑉$ is finite-dimensional and $𝑇$ is injective, then $im 𝑇$ is finite-dimensional and $dim im 𝑇 = dim 𝑉$ . More precisely, for every basis $ℬ︀$ of $𝑉$ , the list $𝑇 (ℬ︀)$ is a basis of $im 𝑇$ .
(b)If $𝑈$ is a finite-dimensional subspace of $𝑉$ with $𝑈 \cap ker 𝑇 = {𝟎}$ , then $dim im (𝑇 ↾_{𝑈}) =$ $dim 𝑈$ .

Proof.routine

Uses. Proposition 2.6.22 (Testing injectivity and surjectivity on a basis), Proposition 4.2.3 (Properties of restriction), Definition 4.1.5 (Dimension)

Techniques. Restrict to a subspace (Technique 4.2.5)

Hint 1. Take a basis

ℬ︀

𝑉

. What does Proposition 2.6.22(d) say about

𝑇 (ℬ︀)

Hint 2. For (b), find an injective map to which (a) applies.

Sketch. (a) For injective

𝑇

, the list

𝑇 (ℬ︀)

spans

im 𝑇

and is independent (Proposition 2.6.22(d)), so it is a basis of

im 𝑇

with

dim 𝑉

entries. (b)

𝑇 ↾_{𝑈}

is injective by Proposition 4.2.3(c); apply (a) to it.

(a) Let $ℬ︀$ be a basis of $𝑉$ , of length $dim 𝑉$ . By Proposition 2.6.22(d), $𝑇 (ℬ︀)$ spans $im 𝑇$ , and it is a basis of $im 𝑇$ because $𝑇$ is injective. So $im 𝑇$ is finite-dimensional, and $dim im 𝑇$ is the length of $𝑇 (ℬ︀)$ , which is $dim 𝑉$ .

(b) By Proposition 4.2.3(c), $𝑇 ↾_{𝑈} \in L (𝑈, 𝑊)$ is injective. Applying (a) to it gives $dim im (𝑇 ↾_{𝑈}) =$ $dim 𝑈$ . □

Without injectivity, $𝑇 (ℬ︀)$ still spans $im 𝑇$ , so $im 𝑇$ is finite-dimensional with $dim im 𝑇 \leq dim 𝑉$ (Corollary 4.1.11(a)), and equality holds only if the spanning list $𝑇 (ℬ︀)$ is a basis, that is, only if $𝑇$ is injective.

4.2.3The image of a matrix

We now compute $dim im 𝑇_{𝐴}$ . The lecture’s strategy has three steps:

write $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ , where $𝐴_{𝑟} = rref (𝐴)$ and $𝐺$ is invertible;
show that the pivot columns of $𝐴_{𝑟}$ form a basis of $im 𝑇_{𝐴_{𝑟}}$ , which is easy because they are standard basis vectors;
slide this basis along $𝐺^{- 1}$ , which is injective, to get a basis of $im 𝑇_{𝐴}$ .

The last step lands on the pivot columns of $𝐴$ itself, because $𝐺^{- 1}$ times a column of $𝐴_{𝑟}$ is the corresponding column of $𝐴$ .

Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , let $𝑘 = rank 𝐴$ , and let $𝑝_{1} < \dots < 𝑝_{𝑘}$ be the pivot columns of $𝐴$ . Then $𝐚_{𝑝_{1}}, \dots, 𝐚_{𝑝_{𝑘}}$ is a basis of $im 𝑇_{𝐴}$ . In particular,

dim im 𝑇_{𝐴} = rank 𝐴 .

Proof (through the reduced form, by restriction).standard

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Proposition 3.3.8 (Properties of the output), Proposition 2.6.18 (The column space is spanned by the columns), Corollary 1.3.19 (Equal spans), Theorem 2.4.2 (The matrix of a composite), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 4.2.3 (Properties of restriction), Proposition 4.2.6 (Injective maps preserve dimension), Definition 2.4.1 (Matrix product)

Techniques. Restrict to a subspace (Technique 4.2.5), Reduce to RREF (Technique 3.3.22)

Hint 1. First solve the problem for

𝐴_{𝑟}

. Which columns of

𝐴_{𝑟}

are pivot columns, and in which rows can the other columns have nonzero entries?

Hint 2. Write

𝐴 = 𝐺^{- 1} 𝐴_{𝑟}

, so

𝑇_{𝐴} =

𝑇_{𝐺^{- 1}} \circ

𝑇_{𝐴_{𝑟}}

. By Proposition 4.2.3(b),

im 𝑇_{𝐴}

is the image of

𝑇_{𝐺^{- 1}}

restricted to

im 𝑇_{𝐴_{𝑟}}

Hint 3.

𝑇_{𝐺^{- 1}}

is injective, so it carries a basis of

im 𝑇_{𝐴_{𝑟}}

to a basis of

im 𝑇_{𝐴}

. Compute

𝐺^{- 1} 𝐞_{𝑠}

column by column from

𝐴 = 𝐺^{- 1} 𝐴_{𝑟}

Sketch. The pivot columns of

𝐴_{𝑟}

are

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

, and every column of

𝐴_{𝑟}

vanishes below row

𝑘

, so

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

is a basis of

im 𝑇_{𝐴_{𝑟}}

. With

𝐺 𝐴 = 𝐴_{𝑟}

𝑇_{𝐴} = 𝑇_{𝐺^{- 1}} 𝑇_{𝐴_{𝑟}}

, so

im 𝑇_{𝐴} =

im (𝑇_{𝐺^{- 1}} ↾_{im 𝑇_{𝐴_{𝑟}}})

. The injective map

𝑇_{𝐺^{- 1}}

sends the basis

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

to a basis of

im 𝑇_{𝐴}

, and

𝐺^{- 1} 𝐞_{𝑠} = 𝐺^{- 1}

(column

𝑝_{𝑠}

𝐴_{𝑟}

)

= 𝐚_{𝑝_{𝑠}}

Let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10), so that $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ .

The reduced matrix. By Lemma 3.3.16(b), the pivot columns of $𝐴_{𝑟}$ are $𝐞_{1}, \dots, 𝐞_{𝑘} \in 𝐹^{𝑚}$ , which are linearly independent. By Proposition 3.3.8, rows $𝑘 + 1, \dots, 𝑚$ of $𝐴_{𝑟}$ are zero, so every column of $𝐴_{𝑟}$ lies in $span (𝐞_{1}, \dots, 𝐞_{𝑘})$ . Since $𝐞_{1}, \dots, 𝐞_{𝑘}$ are themselves columns of $𝐴_{𝑟}$ , Corollary 1.3.19 and Proposition 2.6.18 give

im 𝑇_{𝐴_{𝑟}} = span (columns of 𝐴_{𝑟}) = span (𝐞_{1}, \dots, 𝐞_{𝑘}),

and $𝐞_{1}, \dots, 𝐞_{𝑘}$ is a basis of $im 𝑇_{𝐴_{𝑟}}$ .

Sliding by $𝐺^{- 1}$ . By Theorem 2.4.2, $𝑇_{𝐴} =$ $𝑇_{𝐺^{- 1} 𝐴_{𝑟}} =$ $𝑇_{𝐺^{- 1}} \circ$ $𝑇_{𝐴_{𝑟}}$ , so Proposition 4.2.3(b) gives

im 𝑇_{𝐴} = im (𝑇_{𝐺^{- 1}} ↾_{im 𝑇_{𝐴_{𝑟}}}) .

The map $𝑇_{𝐺^{- 1}}$ is injective, because $𝑇_{𝐺}$ is a left inverse of it: $𝑇_{𝐺} \circ$ $𝑇_{𝐺^{- 1}} =$ $𝑇_{𝐺 𝐺^{- 1}} =$ $𝑇_{𝐼_{𝑚}} =$ $id$ (Proposition 2.5.4). Its restriction to $im 𝑇_{𝐴_{𝑟}}$ is injective as well (Proposition 4.2.3(a)), so by Proposition 4.2.6(a) it sends the basis $𝐞_{1}, \dots, 𝐞_{𝑘}$ of $im 𝑇_{𝐴_{𝑟}}$ to a basis $𝐺^{- 1} 𝐞_{1},$ $\dots,$ $𝐺^{- 1} 𝐞_{𝑘}$ of $im 𝑇_{𝐴}$ . Finally, column $𝑝_{𝑠}$ of $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ is $𝐺^{- 1}$ times column $𝑝_{𝑠}$ of $𝐴_{𝑟}$ (Definition 2.4.1), that is,

𝐚_{𝑝_{𝑠}} = 𝐺^{- 1} 𝐞_{𝑠} (𝑠 = 1, \dots, 𝑘) .

So $𝐚_{𝑝_{1}}, \dots, 𝐚_{𝑝_{𝑘}}$ is a basis of $im 𝑇_{𝐴}$ , and $dim im 𝑇_{𝐴} =$ $𝑘 =$ $rank 𝐴$ . □

The second proof skips $𝐺$ and uses the description of pivot columns from Section 3.3.4, which never mentions the algorithm.

Proof (by sifting the columns).routine

Uses. Corollary 3.3.19 (Pivot columns, intrinsically), Corollary 1.5.13 (Independence, one entry at a time), Corollary 1.3.19 (Equal spans), Proposition 2.6.18 (The column space is spanned by the columns), Proposition 1.6.2 (Bases are independent spanning lists)

Hint 1. Corollary 3.3.19 describes the pivot columns of

𝐴

directly. Which of its two parts gives independence, and which gives spanning?

Hint 2. Independence:

𝐚_{𝑝_{𝑠}}

is not a combination of

𝐚_{1}, \dots, 𝐚_{𝑝_{𝑠} - 1}

, so in particular not of the earlier pivot columns. Use Corollary 1.5.13.

Hint 3. Spanning: every free column is a combination of pivot columns (Corollary 3.3.19(b)).

Sketch. By Corollary 3.3.19(a),

𝐚_{𝑝_{𝑠}} \notin

span (𝐚_{1}, \dots, 𝐚_{𝑝_{𝑠} - 1}) \supseteq

span (𝐚_{𝑝_{1}}, \dots, 𝐚_{𝑝_{𝑠 - 1}})

, so the pivot columns are independent by Corollary 1.5.13. By (b), every free column lies in their span, so their span contains all the columns and equals

im 𝑇_{𝐴}

Let $𝒫︀ =$ $𝐚_{𝑝_{1}},$ $\dots,$ $𝐚_{𝑝_{𝑘}}$ .

Independent. Let $1 \leq 𝑠 \leq 𝑘$ . By Corollary 3.3.19(a), $𝐚_{𝑝_{𝑠}}$ is not a linear combination of $𝐚_{1}, \dots, 𝐚_{𝑝_{𝑠} - 1}$ . Since $𝑝_{1},$ $\dots,$ $𝑝_{𝑠 - 1} <$ $𝑝_{𝑠}$ , it is in particular not a combination of $𝐚_{𝑝_{1}}, \dots, 𝐚_{𝑝_{𝑠 - 1}}$ . By Corollary 1.5.13, $𝒫︀$ is linearly independent.

Spanning. Each pivot column is an entry of $𝒫︀$ , and by Corollary 3.3.19(b) each free column is a linear combination of pivot columns. So every column of $𝐴$ lies in $span (𝒫︀)$ , and every entry of $𝒫︀$ is a column of $𝐴$ . By Corollary 1.3.19 and Proposition 2.6.18, $span (𝒫︀) =$ $span (𝐚_{1}, \dots, 𝐚_{𝑛}) =$ $im 𝑇_{𝐴}$ .

So $𝒫︀$ is a basis of $im 𝑇_{𝐴}$ (Proposition 1.6.2), of length $𝑘 = rank 𝐴$ . □

The first proof does the easy case $𝐴_{𝑟}$ and transports the answer along an injective map. The second is the sifting procedure of Section 1.6.3 applied to the columns of $𝐴$ : scanning left to right and keeping each column that is not a combination of the earlier ones keeps exactly the pivot columns. Both rest on one fact, that row operations do not change the linear relations among the columns (Corollary 3.2.17). The first proof uses it through $𝐺$ ; the second uses it through Corollary 3.3.19, which was proved from it.

The theorem names columns of $𝐴$ , not of $𝐴_{𝑟}$ , and the distinction matters.

Non-example 4.2.8 (The columns of

𝐴_{𝑟}

are the wrong vectors). Let

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

, so

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

. Then

im 𝑇_{𝐴_{𝑟}} =

span (𝐞_{1})

, while

im 𝑇_{𝐴} =

span ((1, 2))

, a different line. The pivot column

𝐞_{1}

𝐴_{𝑟}

does not even lie in

im 𝑇_{𝐴}

. Row operations change the column space. What they preserve is the linear relations among the columns, so

𝐴_{𝑟}

tells us which columns to take, and we must then take them from

𝐴

For the kernel, the free columns do the same job. Theorem 3.4.9 writes every vector of $ker 𝑇_{𝐴}$ as a combination of the basic solutions, one for each free column, and Remark 3.4.11 observed that they form a basis. So the reduced form gives bases of both subspaces at once.

Example 4.2.9 (Bases for the kernel and the image). Let

𝐴 = (\begin{matrix} 1 & 2 & 0 & 3 & 1 \\ 2 & 4 & 1 & 8 & 1 \\ - 1 & - 2 & 2 & 1 & - 3 \end{matrix}) \in ℚ^{3 \times 5}, 𝐴_{𝑟} = (\begin{matrix} 1 & 2 & 0 & 3 & 1 \\ 0 & 0 & 1 & 2 & - 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) .

The pivot columns are $1, 3$ and the free columns are $2, 4, 5$ , so $rank 𝐴 = 2$ .

Image. By Theorem 4.2.7, columns $1$ and $3$ of $𝐴$ form a basis of $im 𝑇_{𝐴}$ :

im 𝑇_{𝐴} = span ((1, 2, - 1), (0, 1, 2)),

a plane in $ℚ^{3}$ . (It does not contain the pivot column $𝐞_{1}$ of $𝐴_{𝑟}$ : $𝑎 (1, 2, - 1) +$ $𝑏 (0, 1, 2) =$ $(1, 0, 0)$ forces $𝑎 = 1$ , then $𝑏 = - 2$ , and then the third entry is $- 5$ .)

Kernel. Copying the free columns of $𝐴_{𝑟}$ into Definition 3.4.8, the basic solutions are

𝐬_{1} = (\begin{matrix} - 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}), 𝐬_{2} = (\begin{matrix} - 3 \\ 0 \\ - 2 \\ 1 \\ 0 \end{matrix}), 𝐬_{3} = (\begin{matrix} - 1 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix}),

and they form a basis of $ker 𝑇_{𝐴}$ . Each one records how a free column is built from pivot columns: $𝐴 𝐬_{2} = 𝟎$ says $𝐚_{4} = 3 𝐚_{1} + 2 𝐚_{3}$ , and $𝐴 𝐬_{3} = 𝟎$ says $𝐚_{5} = 𝐚_{1} - 𝐚_{3}$ .

So $dim im 𝑇_{𝐴} = 2$ and $dim ker 𝑇_{𝐴} = 3$ , one for each pivot column and one for each free column, and $2 + 3 = 5$ is the number of columns.

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

The reduction of Example 4.2.9. At the end the summary lists the pivot columns, whose columns in $𝐴$ form a basis of

im 𝑇_{𝐴}

, and the free columns, which index the basic solutions, a basis of

ker 𝑇_{𝐴}

. Use “Edit” to try your own matrix: the number of pivot columns plus the number of free columns is always the number of columns.

Exercise 4.2.10.routine Let $𝐴 =$ $(\begin{matrix} 1 & - 1 & 2 & 0 \\ 2 & - 2 & 5 & 1 \\ 0 & 0 & 1 & 1 \end{matrix}) \in$ $ℚ^{3 \times 4}$ .

(a)Find a basis of $im 𝑇_{𝐴}$ consisting of columns of $𝐴$ , and a basis of $ker 𝑇_{𝐴}$ .
(b)Is $(1, 0, 0)$ in $im 𝑇_{𝐴}$ ?

Solution.

Uses. Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Remark 3.4.11 (A basis of the kernel), Definition 3.4.8 (Basic solutions)

Hint 1. Row reduce. Subtract twice row

1

from row

2

first.

Hint 2. For (b), use the basis from (a) and compare entries, starting with the third.

Sketch.

𝐴_{𝑟} =

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

, with pivot columns

1, 3

. So

(1, 2, 0), (2, 5, 1)

is a basis of

im 𝑇_{𝐴}

, and the basic solutions

(1, 1, 0, 0),

(2, 0, - 1, 1)

are a basis of

ker 𝑇_{𝐴}

. (b) No:

𝑎 (1, 2, 0) +

𝑏 (2, 5, 1)

has third entry

𝑏

, so

𝑏 = 0

, and then the second entry is

2 𝑎 = 2 \neq 0

(a) Adding $- 2$ times row $1$ to row $2$ gives rows $(1, - 1, 2, 0)$ , $(0, 0, 1, 1)$ , $(0, 0, 1, 1)$ . Adding $- 1$ times row $2$ to row $3$ and $- 2$ times row $2$ to row $1$ gives

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

The pivot columns are $1$ and $3$ , so by Theorem 4.2.7 the columns $(1, 2, 0)$ and $(2, 5, 1)$ of $𝐴$ form a basis of $im 𝑇_{𝐴}$ . The free columns are $2$ and $4$ , and the basic solutions are $𝐬_{1} = (1, 1, 0, 0)$ and $𝐬_{2} = (2, 0, - 1, 1)$ , a basis of $ker 𝑇_{𝐴}$ (Remark 3.4.11). Check: $𝐚_{1} + 𝐚_{2} = 𝟎$ and $2 𝐚_{1} -$ $𝐚_{3} +$ $𝐚_{4} =$ $(2 - 2 + 0, 4 - 5 + 1, 0 - 1 + 1) =$ $𝟎$ .

(b) No. If $𝑎 (1, 2, 0) +$ $𝑏 (2, 5, 1) =$ $(1, 0, 0)$ , the third entry gives $𝑏 = 0$ , the first then gives $𝑎 = 1$ , and the second entry is $2 \neq 0$ . So $(1, 0, 0) \notin im 𝑇_{𝐴}$ , although it is a pivot column of $𝐴_{𝑟}$ .

4.2.4Rank–nullity

Intuition (Lost plus reached). Take $𝐴 = (\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix})$ . Both columns lie on the line $𝑦 = 𝑥$ , so $𝑇_{𝐴}$ flattens the plane onto that line: $im 𝑇_{𝐴} =$ $span ((1, 1))$ , of dimension $1$ . The vectors it sends to $𝟎$ are those with $𝑥 + 2 𝑦 = 0$ , so $ker 𝑇_{𝐴} =$ $span ((2, - 1))$ , also of dimension $1$ . One dimension of $ℝ^{2}$ is lost and the other survives, and $1 + 1 = 2$ .

There is more to see. Any line $ℓ$ through $𝟎$ other than $ker 𝑇_{𝐴}$ meets the kernel only in $𝟎$ , so $𝑇_{𝐴} ↾_{ℓ}$ is injective, and it maps $ℓ$ onto the image line. So the plane consists of the directions $𝑇_{𝐴}$ kills, together with a line that $𝑇_{𝐴}$ carries faithfully onto $im 𝑇_{𝐴}$ . In general, $𝑉$ is made of $ker 𝑇$ together with further directions on which $𝑇$ is injective; those are carried to independent directions that fill out $im 𝑇$ , and counting gives $dim 𝑉 =$ $dim ker 𝑇 +$ $dim im 𝑇$ . For a matrix the two kinds of direction have names: free variables and pivot variables.

The map of

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

squashes the whole plane onto its image, the line

𝑦 = 𝑥

, and sends its kernel, the line

𝑥 + 2 𝑦 = 0

, to

𝟎

. In the interactive version, drag the columns

𝐴 𝐞_{1}

and

𝐴 𝐞_{2}

. While they are independent the image is the whole plane and the kernel is

{𝟎}

; when they line up, the image drops to a line and a line of kernel appears (and if both are

𝟎

, the image is

{𝟎}

and the kernel is the plane), so the two dimensions always add up to

2

Theorem 4.2.11 (Rank–nullity).

(a)Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . Then
$dim ker 𝑇_{𝐴} + rank 𝐴 = 𝑛 .$
(b)Let $𝑉$ be finite-dimensional and let $𝑇 \in L (𝑉, 𝑊)$ . Then $im 𝑇$ is finite-dimensional, and
$dim ker 𝑇 + dim im 𝑇 = dim 𝑉 .$

In (a), $𝑛$ is the number of columns, the dimension of the domain $𝐹^{𝑛}$ ; the number of rows plays no role. In (b), only $𝑉$ is assumed finite-dimensional, and $𝑊$ may be any vector space. The first proof is the lecture’s: it counts pivots for matrices and transfers the count to arbitrary maps with coordinates.

Proof (by counting pivots).standard

Uses. Proposition 3.5.2 (First properties of rank), Remark 3.4.11 (A basis of the kernel), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Proposition 2.1.16 (Linear maps preserve spans and linear relations), Definition 1.6.23 (Finite-dimensional), Proposition 2.6.20 (Kernel and image in coordinates), Proposition 1.6.19 (Coordinates respect linear combinations), Proposition 1.6.16 (The coordinate map is a bijection), Proposition 4.2.3 (Properties of restriction), Proposition 4.2.6 (Injective maps preserve dimension), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Reduce to RREF (Technique 3.3.22), Translate between maps and matrices (Technique 2.3.27)

Hint 1. For (a): the free columns index a basis of

ker 𝑇_{𝐴}

, and the pivot columns of

𝐴

form a basis of

im 𝑇_{𝐴}

. How many of each are there?

Hint 2. For (b), choose bases and pass to a matrix of

𝑇

. A matrix needs a finite-dimensional target. Why may you replace

𝑊

im 𝑇

, and why is

im 𝑇

finite-dimensional?

Hint 3. The coordinate maps are injective and linear, and by Proposition 2.6.20 they carry

ker 𝑇

onto

ker 𝑇_{𝐴}

and

im 𝑇

onto

im 𝑇_{𝐴}

. What do injective linear maps do to dimension?

Sketch. (a) The

𝑛 - rank 𝐴

basic solutions form a basis of

ker 𝑇_{𝐴}

(Remark 3.4.11), and

dim im 𝑇_{𝐴} = rank 𝐴

(Theorem 4.2.7). (b)

im 𝑇

is spanned by

𝑇 (ℬ︀)

for a basis

ℬ︀

𝑉

, so it is finite-dimensional, say of dimension

𝑟

. The cases

dim 𝑉 = 0

and

𝑟 = 0

are immediate. Otherwise regard

𝑇

as a surjective map

𝑇^{'} : 𝑉 \to im 𝑇

and let

𝐴 =

{[𝑇^{'}]}_{𝒞︀ ℬ︀} \in

𝐹^{𝑟 \times 𝑛}

. Then

𝑇_{𝐴}

is surjective, so

rank 𝐴 = 𝑟

, and the coordinate map restricted to

ker 𝑇

is an injective linear map onto

ker 𝑇_{𝐴}

, so

dim ker 𝑇 =

dim ker 𝑇_{𝐴} =

𝑛 -

𝑟

by (a).

(a) Let $𝑘 = rank 𝐴$ . By Proposition 3.5.2(b), $𝐴$ has exactly $𝑛 - 𝑘$ free columns, and by Remark 3.4.11 the basic solutions, one for each free column, form a basis of $ker 𝑇_{𝐴}$ . So $dim ker 𝑇_{𝐴} = 𝑛 - 𝑘$ , and $dim ker 𝑇_{𝐴} +$ $rank 𝐴 =$ $(𝑛 - 𝑘) +$ $𝑘 =$ $𝑛$ . (By Theorem 4.2.7, the $𝑘$ here is also $dim im 𝑇_{𝐴}$ : the pivot columns count the image, and the free columns count the kernel.)

(b) Let $𝑛 = dim 𝑉$ and let $ℬ︀$ be a basis of $𝑉$ . By Proposition 2.1.16(a), $𝑇 (ℬ︀)$ spans $im 𝑇$ , so $im 𝑇$ is finite-dimensional (Definition 1.6.23). Let $𝑟 = dim im 𝑇$ . If $𝑛 = 0$ , then $𝑉 = {𝟎}$ and both sides are $0$ ; if $𝑟 = 0$ , then $𝑇 = 0$ and $ker 𝑇 = 𝑉$ . So assume $𝑛, 𝑟 \geq 1$ , and let $𝒞︀$ be a basis of $im 𝑇$ . The function

𝑇^{'} : 𝑉 \to im 𝑇, 𝑇^{'} (𝐯) = 𝑇 (𝐯),

is $𝑇$ with its target shrunk to $im 𝑇$ . It is linear, it is surjective, and $ker 𝑇^{'} = ker 𝑇$ . Let $𝐴 =$ ${[𝑇^{'}]}_{𝒞︀ ℬ︀} \in$ $𝐹^{𝑟 \times 𝑛}$ .

Since $𝑇^{'}$ is surjective, so is $𝑇_{𝐴}$ , by Proposition 2.6.20(c). So $im 𝑇_{𝐴} = 𝐹^{𝑟}$ and $rank 𝐴 = 𝑟$ by Theorem 4.2.7. By the same proposition, the coordinate map $𝐯 \mapsto {[𝐯]}_{ℬ︀}$ sends $ker 𝑇^{'}$ onto $ker 𝑇_{𝐴}$ . That map is linear and injective (Proposition 1.6.19, Proposition 1.6.16), so its restriction to the subspace $ker 𝑇$ is an injective linear map with image $ker 𝑇_{𝐴}$ (Proposition 4.2.3). Since $ker 𝑇$ is finite-dimensional (Proposition 4.1.21(a)), Proposition 4.2.6(a) gives $dim ker 𝑇 =$ $dim ker 𝑇_{𝐴}$ . By (a), $dim ker 𝑇_{𝐴} = 𝑛 - 𝑟$ . Hence

dim ker 𝑇 + dim im 𝑇 = (𝑛 - 𝑟) + 𝑟 = 𝑛 = dim 𝑉 .

□

The second proof is the one in LADR. It never chooses coordinates, and it explains the formula rather than verifying it: it finds the directions of the intuition above inside $𝑉$ .

Proof (by extending a basis of the kernel).standard

Uses. Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.1.16 (Extending to a basis), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.6.2 (Bases are independent spanning lists), Definition 2.6.5 (Kernel), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Extend a basis of a subspace (Technique 4.1.18)

Hint 1. Start from a basis

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

ker 𝑇

and extend it to a basis

𝐮_{1},

\dots,

𝐮_{𝑘},

𝐯_{1},

\dots,

𝐯_{𝑟}

𝑉

. Which vectors should form a basis of

im 𝑇

Hint 2.

𝑇 (𝐯_{1}),

\dots,

𝑇 (𝐯_{𝑟})

span

im 𝑇

: apply

𝑇

to an arbitrary vector, written in the basis, and watch the

𝐮_{𝑖}

disappear.

Hint 3. For independence: if

\sum_{𝑗} 𝑏_{𝑗} 𝑇 (𝐯_{𝑗}) =

𝟎

, then

\sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗} \in ker 𝑇

, so it is a combination of the

𝐮_{𝑖}

. Now use the independence of the whole basis of

𝑉

Sketch.

ker 𝑇

has a basis

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

(Proposition 4.1.21(a)), which extends to a basis

𝐮_{1},

\dots,

𝐮_{𝑘},

𝐯_{1},

\dots,

𝐯_{𝑟}

𝑉

. Since

𝑇

kills the

𝐮_{𝑖}

, the vectors

𝑇 (𝐯_{1}),

\dots,

𝑇 (𝐯_{𝑟})

span

im 𝑇

. If

\sum_{𝑗} 𝑏_{𝑗} 𝑇 (𝐯_{𝑗}) =

𝟎

, then

\sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗} \in

ker 𝑇 =

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

, which gives a linear relation among basis vectors of

𝑉

, so all

𝑏_{𝑗} = 0

. Hence

dim im 𝑇 =

𝑟 =

dim 𝑉 -

dim ker 𝑇

. Part (a) is (b) for

𝑇_{𝐴}

, with Theorem 4.2.7.

We prove (b). Then (a) follows by applying (b) to $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ , since $dim im 𝑇_{𝐴} = rank 𝐴$ (Theorem 4.2.7).

By Proposition 4.1.21(a), the subspace $ker 𝑇$ of $𝑉$ is finite-dimensional; let $𝐮_{1}, \dots, 𝐮_{𝑘}$ be a basis of it. By Theorem 4.1.16, it extends to a basis

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

of $𝑉$ , where $𝑘 + 𝑟 = dim 𝑉$ . We claim that $𝑇 (𝐯_{1}),$ $\dots,$ $𝑇 (𝐯_{𝑟})$ is a basis of $im 𝑇$ . Then $im 𝑇$ is finite-dimensional and $dim im 𝑇 =$ $𝑟 =$ $dim 𝑉 -$ $dim ker 𝑇$ , as desired.

Spanning. Let $𝐰 \in im 𝑇$ , say $𝐰 = 𝑇 (𝐯)$ , and write $𝐯 =$ $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} +$ $\sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗}$ . Since $𝑇 (𝐮_{𝑖}) = 𝟎$ for every $𝑖$ ,

𝐰 = \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝑇 (𝐮_{𝑖}) + \sum_{𝑗 = 1}^{𝑟} 𝑏_{𝑗} 𝑇 (𝐯_{𝑗}) = \sum_{𝑗 = 1}^{𝑟} 𝑏_{𝑗} 𝑇 (𝐯_{𝑗}) .

So the vectors $𝑇 (𝐯_{𝑗})$ , which lie in $im 𝑇$ , span it.

Independent. Suppose $\sum_{𝑗} 𝑏_{𝑗} 𝑇 (𝐯_{𝑗}) =$ $𝟎$ . Then $𝑇 (\sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗}) =$ $𝟎$ , so $\sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗} \in ker 𝑇$ , and there are scalars $𝑎_{1}, \dots, 𝑎_{𝑘}$ with $\sum_{𝑗} 𝑏_{𝑗} 𝐯_{𝑗} =$ $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖}$ . Then

\sum_{𝑖 = 1}^{𝑘} (- 𝑎_{𝑖}) 𝐮_{𝑖} + \sum_{𝑗 = 1}^{𝑟} 𝑏_{𝑗} 𝐯_{𝑗} = 𝟎

is a linear relation among the vectors of a basis of $𝑉$ , so all its coefficients are $0$ (Theorem 1.5.5). In particular $𝑏_{1} = \dots = 𝑏_{𝑟} = 0$ . □

In the language of Section 4.2.1, the second proof sets $𝑈 =$ $span (𝐯_{1}, \dots, 𝐯_{𝑟})$ . Independence says that $𝑈 \cap ker 𝑇 = {𝟎}$ , so $𝑇 ↾_{𝑈}$ is injective, and spanning says that $im (𝑇 ↾_{𝑈}) = im 𝑇$ . So $im 𝑇$ is a faithful copy of $𝑈$ , and Proposition 4.2.6(b) gives $dim im 𝑇 = dim 𝑈 = 𝑟$ .

Remark 4.2.12 (A third proof). The second proof chose the vectors

𝐯_{𝑗}

, and different choices give different subspaces

𝑈

; only

dim 𝑈

is determined by

𝑇

. In the plane example of Intuition (Lost plus reached), every line other than

ker 𝑇_{𝐴}

is a possible

𝑈

. Section 4.6 removes the choice: it replaces

𝑈

by the quotient space

𝑉 / ker 𝑇

, built from

𝑉

and

ker 𝑇

alone, whose elements are the translates

𝐯 + ker 𝑇

. The map

𝑇

induces an isomorphism

𝑉 / ker 𝑇 \to im 𝑇

(Theorem 4.6.34), and

dim 𝑉 / ker 𝑇 =

dim 𝑉 -

dim ker 𝑇

, which is rank–nullity once more. Quotients are not part of the course.

Intuition (Comparing the proofs). The pivot-counting proof is a computation. Row reduction sorts the columns of $𝐴$ into pivot columns and free columns; the free ones index a basis of the kernel, and the pivot ones are a basis of the image. For matrices, the theorem is then the observation that every column is one or the other. The proof produces explicit bases, which is what we want in examples. Its weakness is that it only sees matrices: for an abstract $𝑇$ we had to choose bases, and the real content of (b) moved into the transfer step, which says that coordinates do not change the dimensions of kernels and images.

The basis-extension proof never mentions matrices and works for every $𝑇$ whose domain is finite-dimensional. It shows why the formula holds: $𝑉$ is built from $ker 𝑇$ and a subspace $𝑈$ on which $𝑇$ is injective, and $𝑇$ carries $𝑈$ onto $im 𝑇$ without loss. Its price is a choice of $𝑈$ , which the quotient proof removes. When computing, count pivots. When proving something about an abstract map, extend a basis of the kernel.

The bases in the second proof are adapted to $𝑇$ . If $𝑊$ is finite-dimensional, extend the independent list $𝑇 (𝐯_{1}),$ $\dots,$ $𝑇 (𝐯_{𝑟})$ to a basis of $𝑊$ . In the bases $𝐯_{1},$ $\dots,$ $𝐯_{𝑟},$ $𝐮_{1},$ $\dots,$ $𝐮_{𝑘}$ of $𝑉$ and this basis of $𝑊$ , the matrix of $𝑇$ is the rank normal form $𝑁_{𝑟}$ of Theorem 3.5.27. This is Corollary 3.5.29 for abstract maps, and Section 4.5 returns to it.

Exercise 4.2.13.routine Let $𝑇 : 𝐹^{3} \to 𝐹^{3}$ , $𝑇 (𝑥_{1}, 𝑥_{2}, 𝑥_{3}) =$ $(𝑥_{1} - 𝑥_{2}, 𝑥_{2} - 𝑥_{3}, 𝑥_{3} - 𝑥_{1})$ .

(a)Find $ker 𝑇$ .
(b)Show that $im 𝑇 =$ ${𝐲 \in 𝐹^{3} | 𝑦_{1} + 𝑦_{2} + 𝑦_{3} = 0}$ , without solving $𝑇 (𝐱) = 𝐲$ .

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Proposition 1.6.2 (Bases are independent spanning lists)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. For (a), set each entry of

𝑇 (𝐱)

0

Hint 2. For (b), show one containment directly, and compare dimensions using rank–nullity.

Sketch. (a)

𝑇 (𝐱) = 𝟎

iff

𝑥_{1} = 𝑥_{2} = 𝑥_{3}

, so

ker 𝑇 =

span ((1, 1, 1))

. (b) The entries of

𝑇 (𝐱)

sum to

0

, so

im 𝑇 \subseteq

𝑃 =

{𝑦_{1} + 𝑦_{2} + 𝑦_{3} = 0}

. By rank–nullity

dim im 𝑇 = 3 - 1 = 2

, and

𝑃

has the basis

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

, so

dim 𝑃 = 2

and

im 𝑇 = 𝑃

(a) $𝑇 (𝐱) = 𝟎$ means $𝑥_{1} = 𝑥_{2}$ , $𝑥_{2} = 𝑥_{3}$ , and $𝑥_{3} = 𝑥_{1}$ , that is, $𝑥_{1} = 𝑥_{2} = 𝑥_{3}$ . So $ker 𝑇 =$ $span ((1, 1, 1))$ , which has dimension $1$ .

(b) Let $𝑃 =$ ${𝐲 \in 𝐹^{3} | 𝑦_{1} + 𝑦_{2} + 𝑦_{3} = 0}$ . The entries of $𝑇 (𝐱)$ add up to $(𝑥_{1} - 𝑥_{2}) +$ $(𝑥_{2} - 𝑥_{3}) +$ $(𝑥_{3} - 𝑥_{1}) =$ $0$ , so $im 𝑇 \subseteq 𝑃$ . By Theorem 4.2.11 and (a), $dim im 𝑇 = 3 - 1 = 2$ . On the other hand, every $𝐲 \in 𝑃$ satisfies

𝐲 = 𝑦_{1} (1, - 1, 0) + (𝑦_{1} + 𝑦_{2}) (0, 1, - 1),

since the third entry of the right side is $- 𝑦_{1} - 𝑦_{2} = 𝑦_{3}$ . The two vectors lie in $𝑃$ and are independent (look at the first entries, then the second), so they form a basis of $𝑃$ and $dim 𝑃 = 2$ . By Proposition 4.1.21(b), applied in $𝑃$ , $im 𝑇 = 𝑃$ . Every step is valid over every field.

4.2.5The rank of a linear map

Rank–nullity suggests measuring a linear map by the dimensions of its kernel and image. Remark 3.5.17 promised an intrinsic definition of rank; here it is.

Definition 4.2.14 (Rank and nullity of a linear map). Let $𝑇 \in L (𝑉, 𝑊)$ . If $im 𝑇$ is finite-dimensional, the rank of $𝑇$ is

rank 𝑇 = dim im 𝑇 .

If $ker 𝑇$ is finite-dimensional, the nullity of $𝑇$ is $nullity 𝑇 =$ $dim ker 𝑇$ .

When $𝑉$ is finite-dimensional both are defined (Theorem 4.2.11, Proposition 4.1.21), and rank–nullity reads

rank 𝑇 + nullity 𝑇 = dim 𝑉,

which is where the theorem’s name comes from. For a matrix, $rank 𝑇_{𝐴} =$ $dim im 𝑇_{𝐴} =$ $rank 𝐴$ by Theorem 4.2.7, so the two meanings of “rank” agree, and we use $rank 𝐴$ and $rank 𝑇_{𝐴}$ interchangeably. Likewise the nullity of $𝐴$ is $nullity 𝐴 =$ $dim ker 𝑇_{𝐴} =$ $𝑛 -$ $rank 𝐴$ .

For a map between finite-dimensional spaces, we can also compute the rank of any of its matrices. The lecture’s observation is that the answer does not depend on which matrix we pick.

Proposition 4.2.15 (Rank through any matrix). Let $𝑉$ and $𝑊$ be nonzero finite-dimensional spaces, with bases $ℬ︀$ and $𝒞︀$ , let $𝑇 \in L (𝑉, 𝑊)$ , and let $𝐴 = {[𝑇]}_{𝒞︀ ℬ︀}$ . Then

rank 𝐴 = rank 𝑇 and nullity 𝐴 = nullity 𝑇 .

In particular, $rank {[𝑇]}_{𝒞︀ ℬ︀}$ does not depend on the choice of $ℬ︀$ and $𝒞︀$ .

Proof.routine

Uses. Proposition 2.6.20 (Kernel and image in coordinates), Proposition 1.6.19 (Coordinates respect linear combinations), Proposition 1.6.16 (The coordinate map is a bijection), Proposition 4.2.3 (Properties of restriction), Proposition 4.2.6 (Injective maps preserve dimension), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Techniques. Translate between maps and matrices (Technique 2.3.27), Restrict to a subspace (Technique 4.2.5)

Hint 1. Under

𝒞︀

-coordinates, which subspace of

𝐹^{𝑚}

corresponds to

im 𝑇

? See Proposition 2.6.20.

Hint 2. The coordinate map of

𝑊

, restricted to

im 𝑇

, is linear and injective. What does that do to dimension?

Sketch. By Proposition 2.6.20,

𝐰 \mapsto {[𝐰]}_{𝒞︀}

maps

im 𝑇

onto

im 𝑇_{𝐴}

, and it is the restriction of an injective linear map, so

dim im 𝑇 =

dim im 𝑇_{𝐴} =

rank 𝐴

(Proposition 4.2.6, Theorem 4.2.7). The same argument with

ℬ︀

-coordinates matches

ker 𝑇

with

ker 𝑇_{𝐴}

By Proposition 2.6.20, the coordinate map $𝐰 \mapsto {[𝐰]}_{𝒞︀}$ sends $im 𝑇$ onto $im 𝑇_{𝐴}$ . It is linear and injective on all of $𝑊$ (Proposition 1.6.19, Proposition 1.6.16), so its restriction to $im 𝑇$ is an injective linear map with image $im 𝑇_{𝐴}$ (Proposition 4.2.3). The space $im 𝑇$ is finite-dimensional (Theorem 4.2.11), so Proposition 4.2.6(a) and Theorem 4.2.7 give

rank 𝑇 = dim im 𝑇 = dim im 𝑇_{𝐴} = rank 𝐴 .

In the same way, $𝐯 \mapsto {[𝐯]}_{ℬ︀}$ restricts to an injective linear map from $ker 𝑇$ onto $ker 𝑇_{𝐴}$ , so $nullity 𝑇 =$ $dim ker 𝑇_{𝐴} =$ $nullity 𝐴$ . □

This settles Remark 3.5.17. Once the change-of-basis formula of Section 4.5 expresses two matrices of $𝑇$ through each other by invertible factors, the proposition also shows that such factors do not change the rank; Section 4.3 proves that directly.

Example 4.2.16 (One map, two matrices). Let $ℓ = span (𝐮)$ with $𝐮 =$ $(𝑐, 𝑠) =$ $(cos 𝜃, sin 𝜃)$ , and let ${Pr}_{ℓ}$ be the orthogonal projection onto $ℓ$ , so ${Pr}_{ℓ} (𝑥, 𝑦) =$ $(𝑥 𝑐 + 𝑦 𝑠) 𝐮$ (Example 2.6.7(d)). In the standard basis,

{[{Pr}_{ℓ}]}_{ℰ︀ ℰ︀} = (\begin{matrix} 𝑐^{2} & 𝑐 𝑠 \\ 𝑐 𝑠 & 𝑠^{2} \end{matrix}),

whose columns $𝑐 𝐮$ and $𝑠 𝐮$ are multiples of the nonzero vector $𝐮$ , not both $𝟎$ ; so its rank is $1$ . Let $𝐮^{⟂} = (- 𝑠, 𝑐)$ . By Example 2.6.7(d), every vector of $ℝ^{2}$ is a combination of $𝐮$ and $𝐮^{⟂}$ , so $ℬ︀ = 𝐮, 𝐮^{⟂}$ is a basis (Corollary 4.1.11(b)). In this basis ${Pr}_{ℓ} (𝐮) = 𝐮$ and ${Pr}_{ℓ} (𝐮^{⟂}) = 𝟎$ , so

{[{Pr}_{ℓ}]}_{ℬ︀ ℬ︀} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) .

The two matrices look different, but both have rank $1 = dim ℓ = rank {Pr}_{ℓ}$ .

Exercise 4.2.17.routine Let

𝑇 : {𝐹 [𝑥]}_{\leq 2} \to 𝐹^{3}

𝑇 (𝑝) =

(𝑝 (0), 𝑝 (1), 𝑝 (2))

. Using the matrix of

𝑇

in the bases

1, 𝑥, 𝑥^{2}

and

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

, find

rank 𝑇

and

nullity 𝑇

for

𝐹 = ℚ

and for

𝐹 = 𝔽_{2}

. For

𝐹 = 𝔽_{2}

, find a nonzero

𝑝 \in ker 𝑇

Solution.

Uses. Proposition 4.2.15 (Rank through any matrix), Definition 2.3.1 (Matrix of a linear map), Theorem 4.2.11 (Rank–nullity)

Hint 1. The columns of the matrix are

𝑇 (1)

𝑇 (𝑥)

𝑇 (𝑥^{2})

Hint 2. Over

𝔽_{2}

, the entry

2

0

and so is

4

Sketch. The matrix is

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

. Over

ℚ

it reduces to

𝐼_{3}

, so

rank 𝑇 = 3

and

nullity 𝑇 = 0

. Over

𝔽_{2}

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

has rank

2

, so

nullity 𝑇 = 1

, and

ker 𝑇_{𝐴} =

span ((0, 1, 1))

gives

𝑝 = 𝑥 + 𝑥^{2}

The columns of $𝐴 = [𝑇]$ are $𝑇 (1) = (1, 1, 1)$ , $𝑇 (𝑥) = (0, 1, 2)$ , and $𝑇 (𝑥^{2}) = (0, 1, 4)$ :

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

Over $ℚ$ , subtracting row $1$ from rows $2$ and $3$ gives rows $(0, 1, 1)$ and $(0, 2, 4)$ , and subtracting twice the new row $2$ from row $3$ leaves $(0, 0, 2)$ . There are three pivots, so $rank 𝐴 = 3$ . By Proposition 4.2.15, $rank 𝑇 = 3$ , and $nullity 𝑇 = 3 - 3 = 0$ by Theorem 4.2.11.

Over $𝔽_{2}$ , $2 = 4 = 0$ , so $𝐴 = (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{matrix})$ . Rows $1$ and $3$ agree, and subtracting row $1$ from rows $2$ and $3$ gives $𝐴_{𝑟} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix})$ . So $rank 𝑇 = 2$ and $nullity 𝑇 = 1$ . The basic solution is $(0, 1, 1)$ , which is $[𝑥 + 𝑥^{2}]$ ; indeed $𝑥 + 𝑥^{2}$ takes the values $0$ , $1 + 1 = 0$ , and $0$ at $0$ , $1$ , and $2 = 0$ . Over $𝔽_{2}$ , a nonzero polynomial can vanish at every point of the field.

4.2.6Consequences

Rank–nullity turns statements about vectors into statements about numbers. This subsection collects the consequences that the course uses.

Injective, surjective, bijective

For a map between finite sets of the same size, injective and surjective are equivalent. Dimension plays the role of size.

Corollary 4.2.18 (Injective if and only if surjective). Let

𝑉

and

𝑊

be finite-dimensional with

dim 𝑉 = dim 𝑊

, and let

𝑇 \in L (𝑉, 𝑊)

. The following are equivalent.

(i) $𝑇$ is injective.
(ii) $𝑇$ is surjective.
(iii) $𝑇$ is bijective.

In particular, for

𝑉

finite-dimensional, an operator

𝑇 \in L (𝑉)

is injective if and only if it is surjective.

Proof.routine

Uses. Theorem 4.2.11 (Rank–nullity), Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Proposition 4.1.21 (Dimensions of subspaces), Definition 2.6.3 (Bijective)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. Translate injectivity and surjectivity into statements about

dim ker 𝑇

and

dim im 𝑇

Hint 2.

im 𝑇

is a subspace of

𝑊

. When is a subspace of

𝑊

equal to

𝑊

Sketch. Let

𝑛 = dim 𝑉 = dim 𝑊

𝑇

is injective iff

dim ker 𝑇 = 0

, iff

dim im 𝑇 = 𝑛

by rank–nullity, iff

im 𝑇 = 𝑊

by Proposition 4.1.21(b). Bijective means both.

Let

𝑛 = dim 𝑉 = dim 𝑊

. By Theorem 2.6.11,

𝑇

is injective if and only if

ker 𝑇 = {𝟎}

, that is,

dim ker 𝑇 = 0

. By Theorem 4.2.11 this holds if and only if

dim im 𝑇 = 𝑛

. Since

im 𝑇

is a subspace of

𝑊

and

dim 𝑊 = 𝑛

, Proposition 4.1.21(b) says that

dim im 𝑇 = 𝑛

if and only if

im 𝑇 = 𝑊

, that is,

𝑇

is surjective. So (i)

\Leftrightarrow

(ii), and (iii) is (i) and (ii) together (Definition 2.6.3). □

So for maps between spaces of the same finite dimension, uniqueness gives existence, which extends Technique 3.4.21 from square matrices to linear maps: to show that $𝑇 (𝐯) = 𝐰$ is solvable for every $𝐰$ , it suffices to show that $𝑇 (𝐯) = 𝟎$ only for $𝐯 = 𝟎$ .

Example 4.2.19 (Uniqueness gives existence, for polynomials). Let

𝑇 : {ℝ [𝑥]}_{\leq 𝑛} \to

{ℝ [𝑥]}_{\leq 𝑛}

𝑇 (𝑝) = 𝑝 + 𝑝^{'}

. If

𝑝 \neq 𝟎

has degree

𝑑

with leading coefficient

𝑎_{𝑑}

, then

𝑝^{'}

has degree less than

𝑑

, so the coefficient of

𝑥^{𝑑}

𝑝 + 𝑝^{'}

𝑎_{𝑑} \neq 0

. Hence

ker 𝑇 = {𝟎}

, and

𝑇

is surjective by Corollary 4.2.18: for every

𝑞 \in {ℝ [𝑥]}_{\leq 𝑛}

, the equation

𝑝 + 𝑝^{'} = 𝑞

has a solution

𝑝 \in {ℝ [𝑥]}_{\leq 𝑛}

, and only one. For instance, for

𝑞 = 𝑥^{2}

, trying

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

gives

𝑝 +

𝑝^{'} =

𝑥^{2} +

(𝑏 + 2) 𝑥 +

(𝑏 + 𝑐)

, so

𝑏 = - 2

𝑐 = 2

, and

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

. We knew a solution existed before we looked for it.

The finite dimension is essential. On $𝐹 [𝑥]$ , multiplication by $𝑥$ is injective but not surjective, and in characteristic $0$ differentiation is surjective but not injective (Example 2.6.4(e)).

Remark 4.2.20 (One-sided inverses of operators). Let

𝑉

be finite-dimensional and

𝑆, 𝑇 \in L (𝑉)

with

𝑆 𝑇 = {id}_{𝑉}

. Then

𝑇

is injective (Proposition 2.5.4), hence bijective by Corollary 4.2.18, and its inverse is linear (Proposition 2.7.7). So

𝑆 =

𝑆 (𝑇 𝑇^{- 1}) =

(𝑆 𝑇) 𝑇^{- 1} =

𝑇^{- 1}

, and

𝑇 𝑆 = {id}_{𝑉}

as well. A one-sided inverse of an operator on a finite-dimensional space is two-sided. This is Theorem 3.5.23 for operators, and the same argument works for

𝑇 \in L (𝑉, 𝑊)

and

𝑆 \in L (𝑊, 𝑉)

when

dim 𝑉 = dim 𝑊 < \infty

Dimension obstructions

Corollary 4.2.21 (Dimension obstructions). Let

𝑉

and

𝑊

be finite-dimensional, and let

𝑇 \in L (𝑉, 𝑊)

(a) $rank 𝑇 \leq$ $min (dim 𝑉, dim 𝑊)$ , and $dim ker 𝑇 \geq$ $dim 𝑉 -$ $dim 𝑊$ .
(b)If $𝑇$ is injective, then $dim 𝑉 \leq dim 𝑊$ . So if $dim 𝑉 > dim 𝑊$ , no linear map $𝑉 \to 𝑊$ is injective.
(c)If $𝑇$ is surjective, then $dim 𝑉 \geq dim 𝑊$ . So if $dim 𝑉 < dim 𝑊$ , no linear map $𝑉 \to 𝑊$ is surjective.

Proof.routine

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Theorem 2.6.11 (Injectivity is decided at $𝟎$ )

Techniques. Dimension counting (Technique 4.2.24)

Hint 1.

im 𝑇

is a subspace of

𝑊

, and rank–nullity gives

rank 𝑇 =

dim 𝑉 -

dim ker 𝑇

Hint 2. For (b) and (c), put

dim ker 𝑇 = 0

, respectively

rank 𝑇 = dim 𝑊

, into (a).

Sketch. (a)

rank 𝑇 \leq dim 𝑊

since

im 𝑇 \subseteq 𝑊

, and

rank 𝑇 =

dim 𝑉 -

dim ker 𝑇 \leq

dim 𝑉

; rearranging

rank 𝑇 \leq dim 𝑊

gives the bound on

dim ker 𝑇

. (b) Injective means

dim ker 𝑇 = 0

, so

dim 𝑉 =

rank 𝑇 \leq

dim 𝑊

. (c) Surjective means

rank 𝑇 = dim 𝑊

, so

dim 𝑊 \leq dim 𝑉

(a) Since $im 𝑇$ is a subspace of $𝑊$ , $rank 𝑇 \leq dim 𝑊$ (Proposition 4.1.21(a)). By Theorem 4.2.11, $rank 𝑇 =$ $dim 𝑉 -$ $dim ker 𝑇 \leq$ $dim 𝑉$ . Rearranging $dim 𝑉 -$ $dim ker 𝑇 =$ $rank 𝑇 \leq$ $dim 𝑊$ gives $dim ker 𝑇 \geq$ $dim 𝑉 -$ $dim 𝑊$ .

(b) If $𝑇$ is injective, then $dim ker 𝑇 = 0$ (Theorem 2.6.11), so $dim 𝑉 =$ $rank 𝑇 \leq$ $dim 𝑊$ by rank–nullity and (a).

(c) If $𝑇$ is surjective, then $rank 𝑇 = dim 𝑊$ , and $rank 𝑇 \leq dim 𝑉$ by (a). □

For $𝑇_{𝐴}$ with $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , (b) and (c) are the “moreover” parts of Theorem 3.5.12 and Theorem 3.5.13: an injective $𝑇_{𝐴}$ has $𝑛 \leq 𝑚$ , and a surjective one has $𝑛 \geq 𝑚$ . Now they hold for all linear maps. Part (b) is the precise sense in which a bigger space cannot be fitted into a smaller one. As sets, $ℝ^{2}$ and $ℝ$ are in bijection, but no injective map $ℝ^{2} \to ℝ$ is linear.

Exercise 4.2.22.routine For each item, give an example or show that none exists.

(a)An injective linear map $𝐹^{2 \times 3} \to {𝐹 [𝑥]}_{\leq 4}$ .
(b)A surjective linear map ${𝐹 [𝑥]}_{\leq 3} \to 𝐹^{2 \times 2}$ .
(c)A linear map $𝑇 : ℝ^{5} \to ℝ^{2}$ with $ker 𝑇 =$ $span (𝐞_{1}, 𝐞_{2})$ .
(d)A linear map $𝑇 : ℝ^{4} \to ℝ^{3}$ with $ker 𝑇 = span (𝐞_{1})$ .

Solution.

Uses. Corollary 4.2.21 (Dimension obstructions), Example 4.1.7 (Dimensions of the standard spaces)

Hint 1. Compute the dimensions involved first:

dim 𝐹^{2 \times 3} = 6

dim {𝐹 [𝑥]}_{\leq 4} = 5

dim {𝐹 [𝑥]}_{\leq 3} =

4 =

dim 𝐹^{2 \times 2}

Hint 2. In (c), how small can

dim ker 𝑇

be?

Sketch. (a) None:

6 > 5

. (b)

𝑎_{0} +

𝑎_{1} 𝑥 +

𝑎_{2} 𝑥^{2} +

𝑎_{3} 𝑥^{3} \mapsto

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

. (c) None:

dim ker 𝑇 \geq 5 - 2 = 3

. (d)

𝑇 (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}) =

(𝑥_{2}, 𝑥_{3}, 𝑥_{4})

(a) None. By Example 4.1.7, $dim 𝐹^{2 \times 3} =$ $6 >$ $5 =$ $dim {𝐹 [𝑥]}_{\leq 4}$ , so no linear map between them is injective (Corollary 4.2.21(b)).

(b) $𝑇 (𝑎_{0} + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2} + 𝑎_{3} 𝑥^{3}) =$ $(\begin{matrix} 𝑎_{0} & 𝑎_{1} \\ 𝑎_{2} & 𝑎_{3} \end{matrix})$ is linear (coefficients are added and scaled entrywise) and surjective, indeed bijective.

(c) None. By Corollary 4.2.21(a), every linear map $ℝ^{5} \to ℝ^{2}$ has $dim ker 𝑇 \geq 5 - 2 = 3$ , while $dim span (𝐞_{1}, 𝐞_{2}) =$ $2$ .

(d) $𝑇 (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}) =$ $(𝑥_{2}, 𝑥_{3}, 𝑥_{4})$ is linear, and $𝑇 (𝐱) = 𝟎$ if and only if $𝑥_{2} = 𝑥_{3} = 𝑥_{4} = 0$ , so $ker 𝑇 = span (𝐞_{1})$ . (Rank–nullity allows it: $1 + 3 = 4$ .)

Linear systems, revisited

Rank–nullity gives a second view of Corollary 3.4.19, and it says how many parameters a description of a solution set needs.

Corollary 4.2.23 (Dimension of solution sets). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

(a) $dim ker 𝑇_{𝐴} =$ $𝑛 -$ $rank 𝐴 \geq$ $𝑛 -$ $𝑚$ . In particular, if $𝑛 > 𝑚$ , then $𝐴 𝐱 = 𝟎$ has a nontrivial solution.
(b)Suppose $𝐴 𝐱 = 𝐲$ has a solution $𝐱_{0}$ , and that its solution set is $𝐱_{0} +$ $span (𝐮_{1}, \dots, 𝐮_{𝑟})$ for some $𝐮_{1}, \dots, 𝐮_{𝑟} \in 𝐹^{𝑛}$ . Then $𝑟 \geq 𝑛 - rank 𝐴$ , with equality if and only if $𝐮_{1}, \dots, 𝐮_{𝑟}$ is linearly independent.
(c)Conversely, if $𝐮_{1},$ $\dots,$ $𝐮_{𝑟} \in$ $ker 𝑇_{𝐴}$ are linearly independent and $𝑟 = 𝑛 - rank 𝐴$ , then the solution set of $𝐴 𝐱 = 𝐲$ is $𝐱_{0} +$ $span (𝐮_{1}, \dots, 𝐮_{𝑟})$ for every solution $𝐱_{0}$ .

Proof.routine

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 3.5.2 (First properties of rank), Proposition 3.1.19 (Solution sets are translates of the kernel), Corollary 4.1.11 (Spanning lists are long), Theorem 4.1.10 (Independent lists are short), Proposition 1.6.2 (Bases are independent spanning lists)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. (a) is rank–nullity for

𝑇_{𝐴}

, with

rank 𝐴 \leq 𝑚

Hint 2. For (b), the solution set is also

𝐱_{0} + ker 𝑇_{𝐴}

(Proposition 3.1.19). Deduce

span (𝐮_{1}, \dots, 𝐮_{𝑟}) =

ker 𝑇_{𝐴}

, and compare the length of a spanning list with the dimension.

Sketch. (a)

dim ker 𝑇_{𝐴} =

𝑛 -

rank 𝐴

and

rank 𝐴 \leq 𝑚

. (b) The solution set is

𝐱_{0} + ker 𝑇_{𝐴}

, so

span (𝐮_{𝑖}) =

ker 𝑇_{𝐴}

. A spanning list of a space of dimension

𝑛 - rank 𝐴

has at least that many entries, with equality iff it is a basis, iff it is independent. (c) An independent list of length

dim ker 𝑇_{𝐴}

ker 𝑇_{𝐴}

is a basis of it.

(a) By Theorem 4.2.11(a), $dim ker 𝑇_{𝐴} =$ $𝑛 -$ $rank 𝐴$ , and $rank 𝐴 \leq 𝑚$ (Proposition 3.5.2(a)). If $𝑛 > 𝑚$ , then $dim ker 𝑇_{𝐴} \geq$ $𝑛 -$ $𝑚 \geq$ $1$ , so $ker 𝑇_{𝐴}$ contains a nonzero vector.

(b) By Proposition 3.1.19, the solution set is $𝐱_{0} + ker 𝑇_{𝐴}$ . For $𝐯 \in 𝐹^{𝑛}$ , the vector $𝐱_{0} + 𝐯$ is a solution if and only if $𝐯 \in ker 𝑇_{𝐴}$ , and also if and only if $𝐯 \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑟})$ . So $span (𝐮_{1}, \dots, 𝐮_{𝑟}) =$ $ker 𝑇_{𝐴}$ , a space of dimension $𝑑 = 𝑛 - rank 𝐴$ . A list spanning it has length $𝑟 \geq 𝑑$ (Corollary 4.1.11(a)). If $𝑟 = 𝑑$ , the list is a basis (Corollary 4.1.11(b)), hence independent. If the list is independent, it is a basis of $ker 𝑇_{𝐴}$ (Proposition 1.6.2), so $𝑟 = 𝑑$ .

(c) An independent list in $ker 𝑇_{𝐴}$ of length $dim ker 𝑇_{𝐴}$ is a basis of $ker 𝑇_{𝐴}$ (Theorem 4.1.10(b)), so its span is $ker 𝑇_{𝐴}$ , and the solution set is $𝐱_{0} + ker 𝑇_{𝐴}$ by Proposition 3.1.19. □

Part (a) is Corollary 3.4.19(a) from the other side. There, more columns than pivots forced a free variable. Here, the image has room for at most $𝑚$ of the $𝑛$ dimensions of $𝐹^{𝑛}$ , so the kernel must absorb at least $𝑛 - 𝑚$ of them. Part (b) says that the number of parameters in a description of the solutions is at least $𝑛 - rank 𝐴$ , however the description was found, and part (c) is the quick completeness test promised in Remark 3.4.12: $𝑛 - rank 𝐴$ independent solutions of the homogeneous system always span its solution space. Over a field with $𝑞$ elements, a consistent system has $𝑞^{𝑛 - rank 𝐴}$ solutions (Corollary 3.4.14(b)).

Dimension counting

Rank–nullity and the bounds of Section 4.1 prove that certain vectors exist without exhibiting them. That is worth a name.

Technique 4.2.24 (Dimension counting). To show that a subspace is nonzero, that two subspaces are equal, or that a linear map is injective or surjective, compute dimensions instead of vectors. The tools are rank–nullity, which ties $dim ker 𝑇$ to $dim im 𝑇$ ; Proposition 4.1.21(b), which turns one containment and equal dimensions into equality; and Theorem 4.1.10, which makes long lists dependent. A typical argument computes whichever of $dim ker 𝑇$ and $dim im 𝑇$ is easier and reads off the other. Often the image is easy because it obviously contains a basis of the target, or the kernel is easy because a structural reason (degrees, a top coefficient) forces it to be small.

Reach for it when a direct computation would mean solving equations you would rather not solve, or when you need a nonzero vector with some properties (in an intersection, in a kernel) and only its existence matters. The canonical example is that two $3$ -dimensional subspaces of $ℝ^{5}$ meet in a nonzero vector (Proposition 4.2.26, Example 4.2.27). Later the same counting gives the rank inequalities (Section 4.3), the dimension formula for sums (Section 4.4), the bounds on eigenspaces (Section 7.4), and the min–max principles (Section 12.3).

Used in 78 places and 11 practice exercises

Exercise 4.2.13, Corollary 4.2.18, Corollary 4.2.21, Corollary 4.2.23, Proposition 4.2.26, Exercise 4.2.39, Exercise 4.2.40, Exercise 4.2.42, Exercise 4.2.46, Exercise 4.2.47, Exercise 4.2.49, Exercise 4.2.50, Exercise 4.2.51, Exercise 4.2.52, Proposition 4.3.1, Theorem 4.3.3, Proposition 4.3.5, Proposition 4.3.20, Proposition 4.3.23, Exercise 4.3.30, Exercise 4.3.31, Exercise 4.3.42, Theorem 4.4.13, Theorem 4.4.19, Proposition 4.4.21, Exercise 4.4.23, Theorem 4.4.27, Exercise 4.4.34, Exercise 4.4.40, Exercise 4.4.45, Exercise 4.4.46, Exercise 4.4.48, Exercise 4.4.49, Exercise 4.4.50, Theorem 4.5.6, Exercise 4.5.41, Theorem 4.6.5, Corollary 4.6.10, Proposition 4.6.11, Theorem 4.6.27, Exercise 4.6.38, Exercise 4.6.47, Exercise 4.6.48, Exercise 4.6.54, Theorem 4.7.8, Exercise 4.7.52, Exercise 4.8.4, Exercise 4.8.6, Exercise 4.8.7, Exercise 4.8.8, Exercise 4.8.9, Problem 4.1, Problem 4.5, Problem 4.6, Problem 4.8, Problem 4.9, Problem 4.11, Problem 4.16, Problem 4.17, Corollary 6.4.25, Theorem 6.4.26, Exercise 6.5.45, Corollary 6.6.22, Exercise 6.6.43, Problem 6.10, Theorem 7.1.14, Exercise 7.1.57, Exercise 7.2.45, Exercise 7.2.46, Exercise 7.2.50, Theorem 7.4.16, Theorem 7.4.30, Proposition 7.5.8, Proposition 7.6.12, Exercise 7.7.9, Problem 7.2, Problem 7.3, Problem 7.12; 11 practice exercises.

The simplest instance: one nonzero linear condition cuts the dimension by exactly one.

Example 4.2.25 (Kernels of linear functionals). Let $𝑉$ be finite-dimensional, and let $𝑓 : 𝑉 \to 𝐹$ be linear and not the zero map. Then $im 𝑓$ is a nonzero subspace of $𝐹$ , so $im 𝑓 = 𝐹$ (Proposition 4.1.21(b), as $dim 𝐹 = 1$ ), and by rank–nullity

dim ker 𝑓 = dim 𝑉 - 1 .

For instance:

(a)For $𝐚 \in 𝐹^{𝑛}$ with $𝐚 \neq 𝟎$ , the solutions of $𝑎_{1} 𝑥_{1} +$ $\dots +$ $𝑎_{𝑛} 𝑥_{𝑛} =$ $0$ form a subspace of $𝐹^{𝑛}$ of dimension $𝑛 - 1$ .
(b)The trace-zero matrices form a subspace of $𝐹^{𝑛 \times 𝑛}$ of dimension $𝑛^{2} - 1$ , since $tr : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ is linear (Proposition 2.4.27) and $tr 𝑈_{11} = 1$ .
(c)For $𝑐 \in 𝐹$ , the polynomials $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ with $𝑝 (𝑐) = 0$ form a subspace of dimension $𝑛$ , since evaluation at $𝑐$ is linear (Example 2.1.9) and sends $1$ to $1$ .

In Section 4.1, (b) and (c) needed an explicit basis or a squeeze (Exercise 4.1.43, Exercise 4.1.24). Here we only had to check that the functional is not zero.

The next proposition is the canonical example of the technique. In $ℝ^{3}$ , two planes through $𝟎$ always share a line, since $2 + 2 > 3$ . In $ℝ^{4}$ they need not: $span (𝐞_{1}, 𝐞_{2}) \cap$ $span (𝐞_{3}, 𝐞_{4}) =$ ${𝟎}$ . The count behind this: $𝑈$ and $𝑊$ together supply $dim 𝑈 + dim 𝑊$ independent directions, and $𝑉$ has room for only $dim 𝑉$ of them, so the excess must be shared.

Proposition 4.2.26 (Subspaces that must meet). Let $𝑉$ be finite-dimensional, and let $𝑈$ and $𝑊$ be subspaces of $𝑉$ . Then

dim (𝑈 \cap 𝑊) \geq dim 𝑈 + dim 𝑊 - dim 𝑉 .

In particular, if $dim 𝑈 + dim 𝑊 > dim 𝑉$ , then $𝑈 \cap 𝑊 \neq {𝟎}$ .

To make the count precise, we build a linear map whose kernel records $𝑈 \cap 𝑊$ . The first proof uses both subspaces symmetrically.

Proof (with a difference map).standard

Uses. Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.2.11 (Rank–nullity), Corollary 4.2.21 (Dimension obstructions), Theorem 1.5.5 (Independence is decided at zero), Proposition 4.2.6 (Injective maps preserve dimension), Theorem 2.6.11 (Injectivity is decided at $𝟎$ )

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. Take bases

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

𝑈

and

𝐰_{1}, \dots, 𝐰_{𝑙}

𝑊

, and consider

𝐿 : 𝐹^{𝑘 + 𝑙} \to 𝑉

𝐿 (𝐚, 𝐛) =

\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} -

\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗}

. How large is

ker 𝐿

Hint 2. An element of

ker 𝐿

says that

\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} =

\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗}

, a vector of

𝑈 \cap 𝑊

. Show that

(𝐚, 𝐛) \mapsto

\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖}

is injective on

ker 𝐿

Sketch. With

𝐿

as in the hint, rank–nullity gives

dim ker 𝐿 =

𝑘 +

𝑙 -

rank 𝐿 \geq

𝑘 +

𝑙 -

𝑛

. The linear map

𝜑 : ker 𝐿 \to 𝑉

(𝐚, 𝐛) \mapsto

\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖}

, takes values in

𝑈 \cap 𝑊

and is injective: if

\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} = 𝟎

, then

𝐚 = 𝟎

, and then

\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗} = 𝟎

gives

𝐛 = 𝟎

. So

dim (𝑈 \cap 𝑊) \geq

dim ker 𝐿 \geq

𝑘 +

𝑙 -

𝑛

Let $𝑛 = dim 𝑉$ . By Proposition 4.1.21(a), $𝑈$ and $𝑊$ are finite-dimensional; let $𝐮_{1}, \dots, 𝐮_{𝑘}$ and $𝐰_{1}, \dots, 𝐰_{𝑙}$ be bases. Write elements of $𝐹^{𝑘 + 𝑙}$ as $(𝐚, 𝐛)$ with $𝐚 \in 𝐹^{𝑘}$ and $𝐛 \in 𝐹^{𝑙}$ , and define

𝐿 : 𝐹^{𝑘 + 𝑙} \to 𝑉, 𝐿 (𝐚, 𝐛) = 𝑎_{1} 𝐮_{1} + \dots + 𝑎_{𝑘} 𝐮_{𝑘} - 𝑏_{1} 𝐰_{1} - \dots - 𝑏_{𝑙} 𝐰_{𝑙} .

It is linear, since each coordinate enters linearly. By Theorem 4.2.11 and Corollary 4.2.21(a),

dim ker 𝐿 = (𝑘 + 𝑙) - rank 𝐿 \geq 𝑘 + 𝑙 - 𝑛 .

Define $𝜑 : ker 𝐿 \to 𝑉$ by $𝜑 (𝐚, 𝐛) =$ $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖}$ ; it is linear. If $(𝐚, 𝐛) \in ker 𝐿$ , then $𝜑 (𝐚, 𝐛) =$ $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} =$ $\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗}$ lies in $𝑈$ and in $𝑊$ , so $im 𝜑 \subseteq 𝑈 \cap 𝑊$ . And $𝜑$ is injective: if $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} = 𝟎$ , then $𝐚 = 𝟎$ by independence of the $𝐮_{𝑖}$ (Theorem 1.5.5), so $\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗} =$ $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} =$ $𝟎$ and $𝐛 = 𝟎$ likewise. By Proposition 4.2.6(a) and Proposition 4.1.21(a),

dim (𝑈 \cap 𝑊) \geq dim im 𝜑 = dim ker 𝐿 \geq 𝑘 + 𝑙 - 𝑛,

as desired. □

The second proof describes $𝑊$ by linear equations and restricts them to $𝑈$ .

Proof (by restricting a map that kills $𝑊$ ).standard

Uses. Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.1.16 (Extending to a basis), Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 4.2.3 (Properties of restriction), Theorem 4.2.11 (Rank–nullity), Corollary 4.2.21 (Dimension obstructions)

Techniques. Restrict to a subspace (Technique 4.2.5), Extend a basis of a subspace (Technique 4.1.18), Dimension counting (Technique 4.2.24)

Hint 1. Find a linear map

𝐿 : 𝑉 \to 𝐹^{𝑛 - 𝑙}

, where

𝑙 = dim 𝑊

and

𝑛 = dim 𝑉

, with

ker 𝐿 = 𝑊

. Extending a basis of

𝑊

helps.

Hint 2. Restrict

𝐿

𝑈

. What is

ker (𝐿 ↾_{𝑈})

, and how large can

im (𝐿 ↾_{𝑈})

be?

Sketch. Extend a basis

𝐰_{1}, \dots, 𝐰_{𝑙}

𝑊

to a basis

𝐰_{1},

\dots,

𝐰_{𝑙},

𝐯_{1},

\dots,

𝐯_{𝑛 - 𝑙}

𝑉

, and let

𝐿

send

𝐰_{𝑗} \mapsto 𝟎

and

𝐯_{𝑖} \mapsto 𝐞_{𝑖} \in 𝐹^{𝑛 - 𝑙}

. Then

ker 𝐿 = 𝑊

, so

ker (𝐿 ↾_{𝑈}) = 𝑈 \cap 𝑊

, and rank–nullity for

𝐿 ↾_{𝑈}

gives

dim 𝑈 =

dim (𝑈 \cap 𝑊) +

rank (𝐿 ↾_{𝑈}) \leq

dim (𝑈 \cap 𝑊) +

𝑛 -

𝑙

Let $𝑛 = dim 𝑉$ and $𝑙 = dim 𝑊$ . Let $𝐰_{1}, \dots, 𝐰_{𝑙}$ be a basis of $𝑊$ (Proposition 4.1.21(a)), and extend it to a basis $𝐰_{1},$ $\dots,$ $𝐰_{𝑙},$ $𝐯_{1},$ $\dots,$ $𝐯_{𝑛 - 𝑙}$ of $𝑉$ (Theorem 4.1.16). By Theorem 2.2.1 there is a linear map $𝐿 : 𝑉 \to 𝐹^{𝑛 - 𝑙}$ with $𝐿 (𝐰_{𝑗}) = 𝟎$ for all $𝑗$ and $𝐿 (𝐯_{𝑖}) = 𝐞_{𝑖}$ for all $𝑖$ . If $𝐯 =$ $\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗} +$ $\sum_{𝑖} 𝑐_{𝑖} 𝐯_{𝑖}$ , then $𝐿 (𝐯) =$ $(𝑐_{1}, \dots, 𝑐_{𝑛 - 𝑙})$ , which is $𝟎$ exactly when all $𝑐_{𝑖} = 0$ , that is, when $𝐯 \in 𝑊$ . So $ker 𝐿 = 𝑊$ .

By Proposition 4.2.3(c), $𝐿 ↾_{𝑈} : 𝑈 \to 𝐹^{𝑛 - 𝑙}$ is linear with kernel $𝑈 \cap 𝑊$ . By Theorem 4.2.11 and Corollary 4.2.21(a),

dim 𝑈 = dim (𝑈 \cap 𝑊) + rank (𝐿 ↾_{𝑈}) \leq dim (𝑈 \cap 𝑊) + (𝑛 - 𝑙) .

Rearranging gives $dim (𝑈 \cap 𝑊) \geq$ $dim 𝑈 +$ $dim 𝑊 -$ $dim 𝑉$ . □

The first proof gives more if we look closer. The image of $𝐿$ is $𝑈 + 𝑊$ , and $𝜑$ maps $ker 𝐿$ onto $𝑈 \cap 𝑊$ , so rank–nullity for $𝐿$ is an equation, $dim (𝑈 + 𝑊) +$ $dim (𝑈 \cap 𝑊) =$ $dim 𝑈 +$ $dim 𝑊$ ; that is the dimension formula of Section 4.4 (Theorem 4.4.19). The second proof is the one to remember in practice. The map $𝐿$ has $𝑛 - 𝑙$ coordinates, each a linear condition, and $𝑊$ is the set where all of them vanish. Restricted to $𝑈$ , each condition lowers the dimension by at most one. So a subspace of $𝑈$ cut out by $𝑠$ linear conditions has dimension at least $dim 𝑈 - 𝑠$ .

Example 4.2.27 (Two subspaces of

ℝ^{5}

(a)Two $3$ -dimensional subspaces of $ℝ^{5}$ meet in at least a line, since $3 + 3 - 5 = 1$ . The bound is attained by $span (𝐞_{1}, 𝐞_{2}, 𝐞_{3})$ and $span (𝐞_{3}, 𝐞_{4}, 𝐞_{5})$ , which meet in $span (𝐞_{3})$ , and the intersection can be larger (take $𝑈 = 𝑊$ ). In $ℝ^{6}$ , two $3$ -dimensional subspaces need not share a nonzero vector: $span (𝐞_{1}, 𝐞_{2}, 𝐞_{3}) \cap$ $span (𝐞_{4}, 𝐞_{5}, 𝐞_{6}) =$ ${𝟎}$ .
(b)The polynomials $𝑝 \in {ℝ [𝑥]}_{\leq 4}$ with $𝑝 (0) = 𝑝^{'} (0) = 0$ form a $3$ -dimensional subspace $𝑊$ , with basis $𝑥^{2}, 𝑥^{3}, 𝑥^{4}$ . So by Proposition 4.2.26, every $3$ -dimensional subspace $𝑈$ of the $5$ -dimensional space ${ℝ [𝑥]}_{\leq 4}$ contains a nonzero $𝑝$ with $𝑝 (0) = 𝑝^{'} (0) = 0$ . For $𝑈 =$ $span (1, 1 + 𝑥 + 𝑥^{2}, 𝑥 + 𝑥^{3})$ , writing $𝑝 =$ $𝑎 +$ $𝑏 (1 + 𝑥 + 𝑥^{2}) +$ $𝑐 (𝑥 + 𝑥^{3})$ , the conditions are $𝑎 + 𝑏 = 0$ and $𝑏 + 𝑐 = 0$ , solved by $(𝑎, 𝑏, 𝑐) =$ $(1, - 1, 1)$ :
$𝑝 = 1 - (1 + 𝑥 + 𝑥^{2}) + (𝑥 + 𝑥^{3}) = 𝑥^{3} - 𝑥^{2} .$

Dimension counting also proves existence statements about polynomials, sometimes with a formula as a by-product.

Example 4.2.28 (Sums of powers). Let $𝑛 \geq 1$ , and let $Δ : {ℚ [𝑥]}_{\leq 𝑛} \to$ ${ℚ [𝑥]}_{\leq 𝑛 - 1}$ be the linear map with

Δ (𝑥^{𝑗}) = {(𝑥 + 1)}^{𝑗} - 𝑥^{𝑗} = \sum_{𝑖 = 0}^{𝑗 - 1} (\binom{𝑗}{𝑖}) 𝑥^{𝑖} (0 \leq 𝑗 \leq 𝑛)

(Theorem 2.2.1). By the binomial theorem in $ℚ$ , $(Δ 𝑝) (𝑡) =$ $𝑝 (𝑡 + 1) -$ $𝑝 (𝑡)$ for every $𝑝$ and every $𝑡 \in ℚ$ .

Kernel. Constants are in $ker Δ$ . Conversely, if $Δ 𝑝 = 𝟎$ , then $𝑝 (𝑡 + 1) = 𝑝 (𝑡)$ for all $𝑡$ , so $𝑝 (0) =$ $𝑝 (1) =$ $\dots =$ $𝑝 (𝑛)$ . Then $𝑝$ and the constant polynomial $𝑝 (0)$ have the same values at the $𝑛 + 1$ distinct points $0, 1, \dots, 𝑛$ , so they are equal by the uniqueness in Theorem 3.4.24. Hence $ker Δ$ is the constants, and $dim ker Δ = 1$ .

Image. By rank–nullity, $rank Δ =$ $(𝑛 + 1) -$ $1 =$ $𝑛 =$ $dim {ℚ [𝑥]}_{\leq 𝑛 - 1}$ , so $Δ$ is surjective (Proposition 4.1.21(b)). So for every $𝑞 \in {ℚ [𝑥]}_{\leq 𝑛 - 1}$ there is $𝑝 \in {ℚ [𝑥]}_{\leq 𝑛}$ with $𝑝 (𝑡 + 1) -$ $𝑝 (𝑡) =$ $𝑞 (𝑡)$ for all $𝑡$ , and the sum telescopes:

𝑞 (0) + 𝑞 (1) + \dots + 𝑞 (𝑁 - 1) = \sum_{𝑡 = 0}^{𝑁 - 1} (𝑝 (𝑡 + 1) - 𝑝 (𝑡)) = 𝑝 (𝑁) - 𝑝 (0) .

So for every nonzero polynomial $𝑞$ , the sum $\sum_{𝑡 = 0}^{𝑁 - 1} 𝑞 (𝑡)$ is a polynomial in $𝑁$ of degree at most $deg 𝑞 + 1$ .

For $𝑞 = 𝑥^{2}$ , some $𝑝 \in {ℚ [𝑥]}_{\leq 3}$ has $Δ 𝑝 = 𝑞$ , and subtracting its constant term (which lies in $ker Δ$ ) we may take $𝑝 =$ $𝑎 𝑥^{3} +$ $𝑏 𝑥^{2} +$ $𝑐 𝑥$ . Since $Δ (𝑥^{3}) = 3 𝑥^{2} + 3 𝑥 + 1$ , $Δ (𝑥^{2}) = 2 𝑥 + 1$ , and $Δ (𝑥) = 1$ ,

Δ 𝑝 = 3 𝑎 𝑥^{2} + (3 𝑎 + 2 𝑏) 𝑥 + (𝑎 + 𝑏 + 𝑐),

and $Δ 𝑝 = 𝑥^{2}$ gives $𝑎 = 1 / 3$ , $𝑏 = - 1 / 2$ , $𝑐 = 1 / 6$ , that is, $𝑝 =$ $𝑥 (𝑥 - 1) (2 𝑥 - 1) / 6$ . Hence

0^{2} + 1^{2} + \dots + {(𝑁 - 1)}^{2} = \frac{𝑁 (𝑁 - 1) (2 𝑁 - 1)}{6} .

The dimension count guaranteed in advance that this linear system for $𝑎, 𝑏, 𝑐$ had a solution.

Linear maps on spaces of matrices

Spaces of matrices are vector spaces of known dimension, so maps between them are natural targets for dimension counting.

Technique 4.2.29 (Study a linear map on a space of matrices). Many questions about matrices ask which $𝑋$ satisfy a linear condition, such as $𝐴 𝑋 = 𝑋 𝐴$ , $𝐴 𝑋 = 𝑋 𝐵$ , or $𝑋^{𝖳} = - 𝑋$ , or which matrices can be written in a given linear form, such as $𝐴 𝑋 - 𝑋 𝐴$ . Treat $𝑋 \mapsto (𝐴 𝑋 - 𝑋 𝐴)$ , or whatever the expression is, as a linear map on $𝐹^{𝑛 \times 𝑛}$ (or $𝐹^{𝑚 \times 𝑛}$ ), a space of dimension $𝑛^{2}$ (or $𝑚 𝑛$ ) by Example 4.1.7. The first kind of question asks for its kernel and the second for its image, and rank–nullity relates the two. So an easy description of the kernel gives the dimension of an image that is hard to describe, and with one easy containment the dimension often identifies the image completely.

Reach for it when a matrix equation is linear in the unknown matrix. The canonical example is Example 4.2.30. The trace argument that $𝐴 𝐵 - 𝐵 𝐴 \neq 𝐼_{𝑛}$ when $𝑛 \cdot 1 \neq 0$ in $𝐹$ (Technique 2.4.29) is an instance: the image of $𝑋 \mapsto 𝐴 𝑋 - 𝑋 𝐴$ lies in the trace-zero matrices. Later instances are Sylvester equations $𝐴 𝑋 - 𝑋 𝐵 = 𝐶$ (Section 10.3) and transposition as an operator with eigenvalues $\pm 1$ (Section 7.4).

Used in 10 places and 2 practice exercises

Exercise 4.2.41, Exercise 4.2.43, Exercise 4.5.48, Problem 4.4, Exercise 7.3.55, Exercise 7.4.41, Exercise 7.5.44, Exercise 7.5.45, Exercise 7.7.11, Problem 7.13; 2 practice exercises.

Example 4.2.30 (Commutators with a diagonal matrix). Let $𝐷 =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑛}) \in$ $𝐹^{𝑛 \times 𝑛}$ with distinct diagonal entries $𝑑_{1}, \dots, 𝑑_{𝑛}$ , and let ${ad}_{𝐷} : 𝐹^{𝑛 \times 𝑛} \to$ $𝐹^{𝑛 \times 𝑛}$ , ${ad}_{𝐷} (𝑋) =$ $𝐷 𝑋 -$ $𝑋 𝐷$ . It is linear (Proposition 2.4.14). Multiplying by $𝐷$ on the left scales row $𝑖$ by $𝑑_{𝑖}$ , and on the right scales column $𝑗$ by $𝑑_{𝑗}$ (Example 2.4.10), so

{(𝐷 𝑋 - 𝑋 𝐷)}_{𝑖 𝑗} = (𝑑_{𝑖} - 𝑑_{𝑗}) 𝑥_{𝑖 𝑗} .

Kernel. ${ad}_{𝐷} (𝑋) = 0$ means $(𝑑_{𝑖} - 𝑑_{𝑗}) 𝑥_{𝑖 𝑗} =$ $0$ for all $𝑖, 𝑗$ . For $𝑖 \neq 𝑗$ , $𝑑_{𝑖} - 𝑑_{𝑗} \neq 0$ , so $𝑥_{𝑖 𝑗} = 0$ . So $ker {ad}_{𝐷}$ is the space of diagonal matrices, of dimension $𝑛$ , and $rank {ad}_{𝐷} = 𝑛^{2} - 𝑛$ .

Image. Every $𝐷 𝑋 - 𝑋 𝐷$ has zero diagonal, since its $(𝑖, 𝑖)$ entry is $(𝑑_{𝑖} - 𝑑_{𝑖}) 𝑥_{𝑖 𝑖} =$ $0$ . The matrices with zero diagonal form a subspace $𝑍$ with basis $𝑈_{𝑖 𝑗}$ , $𝑖 \neq 𝑗$ , so $dim 𝑍 = 𝑛^{2} - 𝑛$ . Since $im {ad}_{𝐷} \subseteq 𝑍$ and the dimensions agree, $im {ad}_{𝐷} = 𝑍$ (Proposition 4.1.21(b)): every matrix with zero diagonal is $𝐷 𝑋 - 𝑋 𝐷$ for some $𝑋$ .

Here we could also have solved for $𝑋$ directly, $𝑥_{𝑖 𝑗} =$ $𝑐_{𝑖 𝑗} / (𝑑_{𝑖} - 𝑑_{𝑗})$ for $𝑖 \neq 𝑗$ . The count did not need the formula, which is what makes it useful when no formula is in sight.

4.2.7Application: error-correcting codes Beyond 21-242

Coding theory is not part of 21-242. This subsection uses only rank–nullity and arithmetic in $𝔽_{2}$ .

Suppose we send blocks of $4$ bits over a channel that occasionally flips a bit. Sending each bit three times and taking a majority vote corrects any single flipped bit, at the cost of $12$ bits per block. Hamming found a way to correct any single flipped bit in a block using $7$ bits. The construction is a kernel, and rank–nullity is what makes the numbers work.

We work in $𝔽_{2}^{𝑛}$ , where $- 𝐱 = 𝐱$ , so subtraction and addition agree.

Definition 4.2.31 (Linear codes). A linear code of length

𝑛

is a subspace

𝐶

𝔽_{2}^{𝑛}

, and its elements are codewords. If

dim 𝐶 = 𝑘

, we call

𝐶

[𝑛, 𝑘]

code. The weight

wt (𝐱)

𝐱 \in 𝔽_{2}^{𝑛}

is the number of nonzero entries of

𝐱

, and the distance between

𝐱

and

𝐲

𝑑 (𝐱, 𝐲) =

wt (𝐱 - 𝐲)

, the number of positions in which they differ. The minimum distance of

𝐶 \neq {𝟎}

is the smallest weight of a nonzero codeword.

Since $𝐜 - 𝐜^{'} \in 𝐶$ for codewords $𝐜, 𝐜^{'}$ , and $wt (𝐜) = 𝑑 (𝐜, 𝟎)$ , the minimum distance is also the smallest distance between two different codewords. The distance satisfies the triangle inequality $𝑑 (𝐱, 𝐳) \leq$ $𝑑 (𝐱, 𝐲) +$ $𝑑 (𝐲, 𝐳)$ : a position in which $𝐱$ and $𝐳$ differ is a position in which $𝐱$ differs from $𝐲$ or $𝐲$ differs from $𝐳$ .

A convenient way to specify a code is as a kernel. If $𝐻 \in 𝔽_{2}^{𝑟 \times 𝑛}$ , then $𝐶 = ker 𝑇_{𝐻}$ is a linear code of length $𝑛$ , the codewords are the vectors that pass the $𝑟$ parity checks given by the rows of $𝐻$ , and $𝐻$ is a parity-check matrix of $𝐶$ . By rank–nullity,

dim 𝐶 = 𝑛 - rank 𝐻, | 𝐶 | = 2^{𝑛 - rank 𝐻}

(Proposition 4.1.34).

Example 4.2.32 (The Hamming code). Let $𝐻 \in 𝔽_{2}^{3 \times 7}$ be the matrix whose $𝑗$ th column $𝐡_{𝑗}$ is the binary expansion of $𝑗$ , highest digit on top:

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

Columns $4, 2, 1$ are $𝐞_{1}, 𝐞_{2}, 𝐞_{3}$ , so the columns span $𝔽_{2}^{3}$ , and $rank 𝐻 =$ $dim im 𝑇_{𝐻} =$ $3$ (Proposition 2.6.18, Theorem 4.2.7). So the Hamming code $𝐶 = ker 𝑇_{𝐻}$ is a $[7, 4]$ code with $2^{4} = 16$ codewords.

Listing the rows of $𝐻$ from the bottom up already gives the reduced form,

𝐻_{𝑟} = (\begin{matrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}),

with pivot columns $1, 2, 4$ and free columns $3, 5, 6, 7$ . By Theorem 3.4.9, a codeword is determined by its free coordinates, which are arbitrary, and the others are

\begin{aligned} 𝑥_{1} & = 𝑥_{3} + 𝑥_{5} + 𝑥_{7}, \\ 𝑥_{2} & = 𝑥_{3} + 𝑥_{6} + 𝑥_{7}, \\ 𝑥_{4} & = 𝑥_{5} + 𝑥_{6} + 𝑥_{7} . \end{aligned}

So to encode a message $(𝑚_{1}, 𝑚_{2}, 𝑚_{3}, 𝑚_{4})$ , put it in positions $3, 5, 6, 7$ and fill in the parity bits in positions $1, 2, 4$ . The message $1011$ becomes the codeword $0110011$ .

(\begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix}) ⇝ (\begin{matrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}) over 𝔽_{2}

The parity-check matrix of the Hamming code over

𝔽_{2}

. The only row operation is the swap of rows

1

and

3

. The summary reports rank

3

, pivot columns

1, 2, 4

(the parity bits), and free columns

3, 5, 6, 7

(the message bits).

The columns of $𝐻$ are nonzero and pairwise distinct, and that is what makes the code correct errors.

Proposition 4.2.33 (Distinct columns give distance three). Let

𝐻 \in 𝔽_{2}^{𝑟 \times 𝑛}

have nonzero, pairwise distinct columns

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

, and let

𝐶 = ker 𝑇_{𝐻}

. Then every nonzero codeword has weight at least

3

Proof.routine

Uses. Definition 2.3.8 (Matrix–vector product), Definition 4.2.31 (Linear codes)

Hint 1. Over

𝔽_{2}

𝐻 𝐱

is the sum of the columns

𝐡_{𝑗}

at the positions where

𝐱

has a

1

Hint 2. Rule out codewords of weight

1

and

2

Sketch.

𝐻 𝐱 = \sum_{𝑥_{𝑗} = 1} 𝐡_{𝑗}

. A vector of weight

1

has

𝐻 𝐱 = 𝐡_{𝑗} \neq 𝟎

, and one of weight

2

has

𝐻 𝐱 = 𝐡_{𝑗} + 𝐡_{𝑘}

, which is

𝟎

only if

𝐡_{𝑗} = 𝐡_{𝑘}

By Definition 2.3.8,

𝐻 𝐱 = \sum_{𝑗} 𝑥_{𝑗} 𝐡_{𝑗}

, which over

𝔽_{2}

is the sum of the

𝐡_{𝑗}

with

𝑥_{𝑗} = 1

. If

wt (𝐱) = 1

, with its

1

in position

𝑗

, then

𝐻 𝐱 = 𝐡_{𝑗} \neq 𝟎

. If

wt (𝐱) = 2

, with

1

s in positions

𝑗 \neq 𝑘

, then

𝐻 𝐱 = 𝐡_{𝑗} + 𝐡_{𝑘}

, which is

𝟎

only if

𝐡_{𝑗} = - 𝐡_{𝑘} = 𝐡_{𝑘}

, and the columns are distinct. So no vector of weight

1

2

lies in

𝐶

. □

For the Hamming code the bound is attained: $𝐡_{1} +$ $𝐡_{2} +$ $𝐡_{3} =$ $(0, 0, 1) +$ $(0, 1, 0) +$ $(0, 1, 1) =$ $𝟎$ , so $1110000$ is a codeword of weight $3$ , and the minimum distance is $3$ .

Theorem 4.2.34 (Syndrome decoding). Let

𝐻

and

𝐶

be as in Proposition 4.2.33, let

𝐜 \in 𝐶

, and let

𝐫 = 𝐜 + 𝐞_{𝑗}

𝐜

with its

𝑗

th bit flipped.

(a)The syndrome $𝐻 𝐫$ equals $𝐡_{𝑗}$ . So $𝐻 𝐫$ determines $𝑗$ , and $𝐜 = 𝐫 + 𝐞_{𝑗}$ .
(b) $𝐜$ is the only codeword at distance at most $1$ from $𝐫$ .

For the Hamming code, the syndrome of a word with one flipped bit is the binary expansion of the position of the flip, and the syndrome of a codeword is

𝟎

Proof.routine

Uses. Proposition 4.2.33 (Distinct columns give distance three), Definition 4.2.31 (Linear codes), Definition 2.6.5 (Kernel)

Hint 1.

𝐻 𝐜 = 𝟎

and

𝐻 𝐞_{𝑗} = 𝐡_{𝑗}

Hint 2. For (b), use the triangle inequality and Proposition 4.2.33.

Sketch. (a)

𝐻 𝐫 =

𝐻 𝐜 +

𝐻 𝐞_{𝑗} =

𝐡_{𝑗}

; distinct columns determine

𝑗

;

𝐫 +

𝐞_{𝑗} =

𝐜 +

2 𝐞_{𝑗} =

𝐜

. (b) If

𝐜^{'} \in 𝐶

and

𝑑 (𝐫, 𝐜^{'}) \leq 1

, then

𝑑 (𝐜, 𝐜^{'}) \leq 2

, so

𝐜 - 𝐜^{'}

is a codeword of weight at most

2

, hence

𝟎

(a) Since $𝐜 \in ker 𝑇_{𝐻}$ , $𝐻 𝐫 =$ $𝐻 𝐜 +$ $𝐻 𝐞_{𝑗} =$ $𝟎 +$ $𝐡_{𝑗} =$ $𝐡_{𝑗}$ . The columns are distinct, so $𝐡_{𝑗}$ determines $𝑗$ . Over $𝔽_{2}$ , $𝐞_{𝑗} + 𝐞_{𝑗} = 𝟎$ , so $𝐫 + 𝐞_{𝑗} = 𝐜$ .

(b) $𝑑 (𝐫, 𝐜) =$ $wt (𝐞_{𝑗}) =$ $1$ . If $𝐜^{'} \in 𝐶$ and $𝑑 (𝐫, 𝐜^{'}) \leq 1$ , the triangle inequality gives $𝑑 (𝐜, 𝐜^{'}) \leq 2$ , so $𝐜 - 𝐜^{'}$ is a codeword of weight at most $2$ , and it is $𝟎$ by Proposition 4.2.33.

For the Hamming code, $𝐡_{𝑗}$ is the binary expansion of $𝑗$ by construction. □

For example, suppose $0110011$ is sent and $𝐫 = 0110111$ is received. Its syndrome is the sum of the columns at the $1$ s of $𝐫$ , which is $𝐡_{2} +$ $𝐡_{3} +$ $𝐡_{5} +$ $𝐡_{6} +$ $𝐡_{7} =$ $(0, 1, 0) +$ $(0, 1, 1) +$ $(1, 0, 1) +$ $(1, 1, 0) +$ $(1, 1, 1) =$ $(1, 0, 1)$ , binary for $5$ . Flipping bit $5$ recovers $0110011$ , and reading positions $3, 5, 6, 7$ recovers the message $1011$ .

The numbers fit exactly. The sets $𝐵 (𝐜) =$ ${𝐱 | 𝑑 (𝐱, 𝐜) \leq 1}$ for the $16$ codewords $𝐜$ are pairwise disjoint: if $𝐱 \in 𝐵 (𝐜) \cap 𝐵 (𝐜^{'})$ , then $𝑑 (𝐜, 𝐜^{'}) \leq 2$ by the triangle inequality, so $𝐜 = 𝐜^{'}$ by Proposition 4.2.33. Each $𝐵 (𝐜)$ has $1 + 7 = 8$ elements. Together they contain $16 \cdot 8 = 128 = 2^{7}$ vectors, all of $𝔽_{2}^{7}$ : every word of length $7$ is within distance $1$ of exactly one codeword. Codes with this property are called perfect. In terms of the syndrome map $𝑇_{𝐻} : 𝔽_{2}^{7} \to 𝔽_{2}^{3}$ , which is surjective, the $8$ possible syndromes correspond to “no error” and to the $7$ possible error positions, and the count $7 = 4 + 3$ is rank–nullity. The Hamming code transmits $4$ bits in $7$ , against $4$ in $12$ for the triple repetition code. Dual codes, which reverse the roles of the rows of $𝐻$ and the codewords, return in Section 12.4.

Exercises

Exercise 4.2.35.routine Let

𝐴 =

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

ℂ^{3 \times 4}

. Find bases of

ker 𝑇_{𝐴}

and of

im 𝑇_{𝐴}

, and check rank–nullity.

Solution.

Uses. Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Remark 3.4.11 (A basis of the kernel), Theorem 4.2.11 (Rank–nullity)

Hint 1. Clear the first column with

- 𝑖

times row

1

Hint 2. The third row becomes a multiple of the second.

Sketch.

𝐴_{𝑟} =

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

, pivot columns

1, 3

. So

(1, 𝑖, 0),

(0, 1, 1 + 𝑖)

is a basis of

im 𝑇_{𝐴}

, and the basic solutions

(- 𝑖, 1, 0, 0),

(- 1, 0, - 𝑖, 1)

form a basis of

ker 𝑇_{𝐴}

;

2 + 2 = 4

Adding $- 𝑖$ times row $1$ to row $2$ gives $(𝑖 - 𝑖, - 1 - 𝑖^{2}, 1 - 0, 2 𝑖 - 𝑖) =$ $(0, 0, 1, 𝑖)$ . Adding $- (1 + 𝑖)$ times this row to row $3$ gives $(0, 0, 0, - 1 + 𝑖 - (1 + 𝑖) 𝑖) =$ $(0, 0, 0, - 1 + 𝑖 - 𝑖 + 1) =$ $𝟎$ . So

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

with pivot columns $1, 3$ and free columns $2, 4$ . By Theorem 4.2.7, columns $1$ and $3$ of $𝐴$ , $(1, 𝑖, 0)$ and $(0, 1, 1 + 𝑖)$ , form a basis of $im 𝑇_{𝐴}$ . The basic solutions are $(- 𝑖, 1, 0, 0)$ and $(- 1, 0, - 𝑖, 1)$ , a basis of $ker 𝑇_{𝐴}$ (Remark 3.4.11). Check: $- 𝑖 𝐚_{1} +$ $𝐚_{2} =$ $(- 𝑖 + 𝑖, 1 - 1, 0) =$ $𝟎$ , and $- 𝐚_{1} - 𝑖 𝐚_{3} + 𝐚_{4} = 𝟎$ : the first entries give $- 1 + 0 + 1 = 0$ , the second $- 𝑖 - 𝑖 + 2 𝑖 = 0$ , and the third $0 -$ $𝑖 (1 + 𝑖) +$ $(- 1 + 𝑖) =$ $0$ . Rank–nullity: $2 + 2 = 4$ .

Exercise 4.2.36.routine Let

𝑀 =

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

, a matrix with integer entries. Find

rank 𝑀

and a basis of

ker 𝑇_{𝑀}

over

ℚ

and over

𝔽_{3}

. Explain why the rational kernel vector, read modulo

3

, lies in the kernel over

𝔽_{3}

, and why the converse fails.

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Remark 3.4.11 (A basis of the kernel), Corollary 3.3.19 (Pivot columns, intrinsically)

Hint 1. Over

ℚ

, swap rows

1

and

2

to get a pivot in position

(1, 1)

Hint 2. Over

𝔽_{3}

, reduce the entries first:

- 1 = 2

and

- 2 = 1

. Compare the first two columns.

Sketch. Over

ℚ

𝑀_{𝑟} =

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

: rank

3

, kernel spanned by

(- 2, 0, - 1, 1)

. Over

𝔽_{3}

𝑀_{𝑟} =

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

: rank

2

, kernel basis

(1, 1, 0, 0),

(1, 0, 2, 1)

. An integer relation among the columns stays a relation modulo

3

; but

𝐦_{2} - 2 𝐦_{1} = (0, 0, 6)

is zero only modulo

3

Over $ℚ$ . Swap rows $1$ and $2$ and scale the new row $1$ by $- 1$ , giving $(1, 2, - 2, 0)$ . Adding $2$ times it to row $3$ gives $(0, 6, - 1, - 1)$ . Swap this into row $2$ and scale by $1 / 6$ ; clearing column $2$ and then column $3$ (with the pivot row $(0, 0, 1, 1)$ ) gives

𝑀_{𝑟} = (\begin{matrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{matrix}) .

So $rank 𝑀 = 3$ , $dim ker 𝑇_{𝑀} = 4 - 3 = 1$ by Theorem 4.2.11, and the basic solution $(- 2, 0, - 1, 1)$ is a basis of $ker 𝑇_{𝑀}$ .

Over $𝔽_{3}$ . Reducing the entries, $𝑀 = (\begin{matrix} 0 & 0 & 1 & 1 \\ 2 & 1 & 2 & 0 \\ 1 & 2 & 0 & 2 \end{matrix})$ . Swap rows $1$ and $3$ ; adding $- 2$ times the new row $1$ to row $2$ gives $(0, - 3, 2, - 4) =$ $(0, 0, 2, 2)$ . Scaling by $2^{- 1} = 2$ gives $(0, 0, 1, 1)$ , and subtracting it from row $3$ leaves $𝟎$ :

𝑀_{𝑟} = (\begin{matrix} 1 & 2 & 0 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}) .

So $rank 𝑀 = 2$ and $dim ker 𝑇_{𝑀} = 2$ , with basic solutions $(- 2, 1, 0, 0) =$ $(1, 1, 0, 0)$ and $(- 2, 0, - 1, 1) =$ $(1, 0, 2, 1)$ .

If $𝐱$ has integer entries and $𝑀 𝐱 = 𝟎$ over $ℚ$ , then every entry of $𝑀 𝐱$ is the integer $0$ , so it is $0$ modulo $3$ as well. That is why $(- 2, 0, - 1, 1)$ , read in $𝔽_{3}$ , is the second basic solution. The converse fails because a combination of the columns can be a nonzero integer vector divisible by $3$ : $𝐦_{2} - 2 𝐦_{1} = (0, 0, 6)$ , so $(- 2, 1, 0, 0)$ is in the kernel over $𝔽_{3}$ but not over $ℚ$ . (By Corollary 3.3.19, column $2$ is free over $𝔽_{3}$ precisely because $𝐦_{2} = 2 𝐦_{1}$ there.)

Exercise 4.2.37.routine Let

𝐴 \in ℂ^{𝑚 \times 𝑛}

. Since real scalars are complex scalars,

𝑇_{𝐴} : ℂ^{𝑛} \to ℂ^{𝑚}

is also a linear map of vector spaces over

ℝ

. Show that its rank over

ℝ

2 rank 𝐴

and that

{dim}_{ℝ} ker 𝑇_{𝐴} =

2 {dim}_{ℂ} ker 𝑇_{𝐴}

Solution.

Uses. Example 4.1.7 (Dimensions of the standard spaces), Theorem 4.2.11 (Rank–nullity), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ )

Hint 1. The sets

ker 𝑇_{𝐴}

and

im 𝑇_{𝐴}

do not depend on which scalars we use. They are complex subspaces.

Hint 2. Example 4.1.7(c): a complex space of complex dimension

𝑑

has real dimension

2 𝑑

Sketch.

im 𝑇_{𝐴}

is a complex subspace of complex dimension

𝑟 = rank 𝐴

, so its real dimension is

2 𝑟

. Over

ℝ

ℂ^{𝑛}

has dimension

2 𝑛

, so rank–nullity gives

{dim}_{ℝ} ker 𝑇_{𝐴} =

2 𝑛 -

2 𝑟 =

2 (𝑛 - 𝑟) =

2 {dim}_{ℂ} ker 𝑇_{𝐴}

The set

im 𝑇_{𝐴} =

{𝐴 𝐱 | 𝐱 \in ℂ^{𝑛}}

is the same whether we regard

𝑇_{𝐴}

over

ℂ

or over

ℝ

, and it is a subspace over

ℂ

of dimension

𝑟 = rank 𝐴

(Theorem 4.2.7). By Example 4.1.7(c), its dimension over

ℝ

2 𝑟

. So the rank of

𝑇_{𝐴}

over

ℝ

2 𝑟

. The domain

ℂ^{𝑛}

has real dimension

2 𝑛

, so by Theorem 4.2.11 over

ℝ

{dim}_{ℝ} ker 𝑇_{𝐴} =

2 𝑛 -

2 𝑟

. Over

ℂ

{dim}_{ℂ} ker 𝑇_{𝐴} = 𝑛 - 𝑟

. Hence

{dim}_{ℝ} ker 𝑇_{𝐴} =

2 {dim}_{ℂ} ker 𝑇_{𝐴}

, which also follows from Example 4.1.7(c) applied to the complex subspace

ker 𝑇_{𝐴}

Exercise 4.2.38.routine Prove or disprove. All spaces are finite-dimensional.

(a)Every $𝑇 \in L (ℝ^{7}, ℝ^{4})$ has $dim ker 𝑇 \geq 3$ .
(b)If $𝑇 \in L (𝑉, 𝑊)$ is surjective and $dim 𝑉 = 5$ , then $dim 𝑊 \leq 5$ .
(c)There is an injective linear map $𝐹^{2 \times 3} \to {𝐹 [𝑥]}_{\leq 4}$ .
(d)If $𝑆, 𝑇 \in L (𝑉, 𝑊)$ have the same kernel, then they have the same image.
(e)If $𝑇 \in L (𝑉)$ satisfies $ker 𝑇 = im 𝑇$ , then $dim 𝑉$ is even.

Solution.

Uses. Corollary 4.2.21 (Dimension obstructions), Theorem 4.2.11 (Rank–nullity), Example 4.1.7 (Dimensions of the standard spaces)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Items (a), (b), (c), and (e) are about dimensions only. Use rank–nullity.

Hint 2. For (d), look for two maps

ℝ^{2} \to ℝ^{2}

that kill the same line but send the other directions to different lines.

Sketch. (a) True:

dim ker 𝑇 \geq 7 - 4

. (b) True:

dim 𝑊 = rank 𝑇 \leq 5

. (c) False:

6 > 5

. (d) False:

(𝑥, 𝑦) \mapsto (𝑥, 0)

and

(𝑥, 𝑦) \mapsto (0, 𝑥)

. (e) True:

dim 𝑉 = 2 dim ker 𝑇

(a) True, by Corollary 4.2.21(a): $dim ker 𝑇 \geq 7 - 4 = 3$ .

(b) True. $𝑊 = im 𝑇$ , so $dim 𝑊 =$ $rank 𝑇 =$ $5 -$ $dim ker 𝑇 \leq$ $5$ by Theorem 4.2.11.

(c) False. $dim 𝐹^{2 \times 3} =$ $6 >$ $5 =$ $dim {𝐹 [𝑥]}_{\leq 4}$ (Example 4.1.7), so no linear map between them is injective (Corollary 4.2.21(b)).

(d) False. Let $𝑆 (𝑥, 𝑦) = (𝑥, 0)$ and $𝑇 (𝑥, 𝑦) = (0, 𝑥)$ on $ℝ^{2}$ . Both have kernel $span (𝐞_{2})$ , but $im 𝑆 = span (𝐞_{1})$ and $im 𝑇 = span (𝐞_{2})$ . (They do have images of the same dimension, by rank–nullity.)

(e) True. By Theorem 4.2.11, $dim 𝑉 =$ $dim ker 𝑇 +$ $dim im 𝑇 =$ $2 dim ker 𝑇$ .

Exercise 4.2.39.routine Let

𝑇 : {𝐹 [𝑥]}_{\leq 3} \to 𝐹^{2}

𝑇 (𝑝) =

(𝑝 (1), 𝑝^{'} (1))

, where

𝑝^{'}

is the formal derivative. Show that

𝑇

is surjective, find

dim ker 𝑇

, and show that

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

is a basis of

ker 𝑇

, without solving

𝑇 (𝑝) = 𝟎

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 1.5.24 (Distinct degrees), Theorem 4.1.10 (Independent lists are short), Example 2.1.9 (Maps of polynomials)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. Find polynomials with

𝑇 (𝑝) = (1, 0)

and

𝑇 (𝑝) = (0, 1)

Hint 2. Rank–nullity gives

dim ker 𝑇

. Two independent vectors in a

2

-dimensional space are a basis.

Sketch.

𝑇 (1) = (1, 0)

and

𝑇 (𝑥 - 1) = (0, 1)

, so

𝑇

is surjective and

dim ker 𝑇 = 4 - 2 = 2

. Expanding,

{(𝑥 - 1)}^{2}

and

{(𝑥 - 1)}^{3}

vanish at

1

together with their derivatives, and they have distinct degrees, so they are an independent list of length

2

ker 𝑇

$𝑇$ is linear, as evaluation and the formal derivative are (Example 2.1.9). Since $𝑇 (1) = (1, 0)$ and $𝑇 (𝑥 - 1) = (0, 1)$ , the image contains a basis of $𝐹^{2}$ , so $𝑇$ is surjective, and $dim ker 𝑇 = 4 - 2 = 2$ by Theorem 4.2.11.

Now ${(𝑥 - 1)}^{2} = 𝑥^{2} - 2 𝑥 + 1$ has derivative $2 𝑥 - 2$ , and ${(𝑥 - 1)}^{3} =$ $𝑥^{3} -$ $3 𝑥^{2} +$ $3 𝑥 -$ $1$ has derivative $3 𝑥^{2} - 6 𝑥 + 3$ . Both polynomials and both derivatives vanish at $1$ , so both polynomials lie in $ker 𝑇$ . They are nonzero with degrees $2$ and $3$ , so they are independent (Proposition 1.5.24). An independent list of length $2 = dim ker 𝑇$ in $ker 𝑇$ is a basis of it (Theorem 4.1.10(b)). Every step is valid over every field.

Exercise 4.2.40.standard Let

𝑝

be a prime and

𝑛 \geq 1

, and let

𝐷

be the formal derivative on

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

. Find

nullity 𝐷

and

rank 𝐷

, and describe

im 𝐷

. Work out the case

𝑝 = 3

𝑛 = 7

Solution.

Uses. Example 2.1.9 (Maps of polynomials), Proposition 1.1.17 (No zero divisors), Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Proposition 1.6.7 (Standard bases)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1.

𝐷 (\sum_{𝑗} 𝑎_{𝑗} 𝑥^{𝑗}) =

\sum_{𝑗 \geq 1} 𝑗 𝑎_{𝑗} 𝑥^{𝑗 - 1}

. When is

𝑗 𝑎_{𝑗} = 0

𝔽_{𝑝}

Hint 2. Which monomials can be values of

𝐷

? Count them and compare with

rank 𝐷

Sketch.

𝑗 𝑎_{𝑗} = 0

iff

𝑝 ∣ 𝑗

𝑎_{𝑗} = 0

, so

ker 𝐷 =

span (𝑥^{𝑗} | 𝑝 ∣ 𝑗)

, of dimension

⌊ 𝑛 / 𝑝 ⌋ + 1

, and

rank 𝐷 = 𝑛 - ⌊ 𝑛 / 𝑝 ⌋

. Every value of

𝐷

is a combination of the

𝑥^{𝑗 - 1}

with

1 \leq 𝑗 \leq 𝑛

and

𝑝 ∤ 𝑗

; there are

𝑛 - ⌊ 𝑛 / 𝑝 ⌋

of these, so they span

im 𝐷

. For

𝑝 = 3

𝑛 = 7

ker 𝐷 =

span (1, 𝑥^{3}, 𝑥^{6})

im 𝐷 =

span (1, 𝑥, 𝑥^{3}, 𝑥^{4}, 𝑥^{6})

For $𝑓 =$ $\sum_{𝑗 = 0}^{𝑛} 𝑎_{𝑗} 𝑥^{𝑗}$ , $𝐷 (𝑓) =$ $\sum_{𝑗 = 1}^{𝑛} 𝑗 𝑎_{𝑗} 𝑥^{𝑗 - 1}$ , where $𝑗 𝑎_{𝑗}$ means $(𝑗 \cdot 1) 𝑎_{𝑗}$ in $𝔽_{𝑝}$ . So $𝐷 (𝑓) = 𝟎$ if and only if $𝑗 𝑎_{𝑗} = 0$ for $1 \leq 𝑗 \leq 𝑛$ . If $𝑝 ∣ 𝑗$ , then $𝑗 \cdot 1 = 0$ and this holds for every $𝑎_{𝑗}$ ; if $𝑝 ∤ 𝑗$ , then $𝑗 \cdot 1 \neq 0$ and it forces $𝑎_{𝑗} = 0$ (Proposition 1.1.17). Hence

ker 𝐷 = span (𝑥^{𝑗} | 0 \leq 𝑗 \leq 𝑛, 𝑝 ∣ 𝑗) = span (1, 𝑥^{𝑝}, 𝑥^{2 𝑝}, \dots, 𝑥^{⌊ 𝑛 / 𝑝 ⌋ 𝑝}),

and these monomials are independent, being part of the standard basis (Proposition 1.6.7). So $nullity 𝐷 =$ $⌊ 𝑛 / 𝑝 ⌋ + 1$ , and by Theorem 4.2.11, $rank 𝐷 =$ $(𝑛 + 1) -$ $(⌊ 𝑛 / 𝑝 ⌋ + 1) =$ $𝑛 -$ $⌊ 𝑛 / 𝑝 ⌋$ .

Let $𝐽 =$ ${𝑗 | 1 \leq 𝑗 \leq 𝑛, 𝑝 ∤ 𝑗}$ , which has $𝑛 - ⌊ 𝑛 / 𝑝 ⌋$ elements, and $𝑆 =$ $span (𝑥^{𝑗 - 1} | 𝑗 \in 𝐽)$ , of dimension $| 𝐽 |$ . Every value $𝐷 (𝑝) =$ $\sum_{𝑗 \in 𝐽} 𝑗 𝑎_{𝑗} 𝑥^{𝑗 - 1}$ lies in $𝑆$ , so $im 𝐷 \subseteq 𝑆$ , and both have dimension $𝑛 - ⌊ 𝑛 / 𝑝 ⌋$ . By Proposition 4.1.21(b), $im 𝐷 = 𝑆$ : the image is spanned by the monomials $𝑥^{𝑖}$ with $0 \leq 𝑖 \leq 𝑛 - 1$ and $𝑖 + 1$ not divisible by $𝑝$ .

For $𝑝 = 3$ and $𝑛 = 7$ : $ker 𝐷 =$ $span (1, 𝑥^{3}, 𝑥^{6})$ , $nullity 𝐷 = 3$ , $rank 𝐷 = 5$ , and $𝐽 = {1, 2, 4, 5, 7}$ , so $im 𝐷 =$ $span (1, 𝑥, 𝑥^{3}, 𝑥^{4}, 𝑥^{6})$ . The monomials $𝑥^{2}$ and $𝑥^{5}$ are not derivatives, because the only candidates $𝑥^{3}$ and $𝑥^{6}$ have derivative $0$ .

Exercise 4.2.41.standard Let $𝑛 \geq 1$ and $𝑇 : 𝐹^{𝑛 \times 𝑛} \to$ $𝐹^{𝑛 \times 𝑛}$ , $𝑇 (𝑋) = 𝑋 - 𝑋^{𝖳}$ .

(a)Show that $ker 𝑇$ is the space of symmetric matrices and that $rank 𝑇 = 𝑛 (𝑛 - 1) / 2$ .
(b)If $1 + 1 \neq 0$ in $𝐹$ , show that $im 𝑇$ is the space of skew-symmetric matrices.
(c)If $1 + 1 = 0$ in $𝐹$ , show that $im 𝑇$ is the space of symmetric matrices with zero diagonal. In particular, over $𝔽_{2}$ the image is a proper subspace of the symmetric matrices, although every value of $𝑇$ is symmetric.

Solution.

Uses. Definition 2.4.21 (Transpose), Exercise 4.1.46, Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces)

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

Hint 1.

𝑇

is linear because transposition is. The dimensions of the symmetric and skew-symmetric matrices are in Exercise 4.1.46.

Hint 2. Show

im 𝑇 \subseteq

(the claimed space) directly, then compare dimensions.

Hint 3. For (c), what is the

(𝑖, 𝑖)

entry of

𝑋 - 𝑋^{𝖳}

Sketch. (a)

𝑇 (𝑋) = 0

iff

𝑋 = 𝑋^{𝖳}

; symmetric matrices have dimension

𝑛 (𝑛 + 1) / 2

, so

rank 𝑇 =

𝑛^{2} -

𝑛 (𝑛 + 1) / 2 =

𝑛 (𝑛 - 1) / 2

. (b)

{(𝑋 - 𝑋^{𝖳})}^{𝖳} =

- (𝑋 - 𝑋^{𝖳})

, so

im 𝑇

lies in the skew-symmetric matrices, which have dimension

𝑛 (𝑛 - 1) / 2

when

1 + 1 \neq 0

. (c) Values of

𝑇

are symmetric (as

- 1 = 1

) with zero diagonal; that space has basis

𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}

𝑖 < 𝑗

, so dimension

𝑛 (𝑛 - 1) / 2

Since ${(𝑎 𝑋 + 𝑌)}^{𝖳} =$ $𝑎 𝑋^{𝖳} +$ $𝑌^{𝖳}$ entry by entry (Definition 2.4.21), $𝑇$ is linear.

(a) $𝑇 (𝑋) = 0$ if and only if $𝑋 = 𝑋^{𝖳}$ , so $ker 𝑇$ is the space $𝑆$ of symmetric matrices, and $dim 𝑆 = 𝑛 (𝑛 + 1) / 2$ by Exercise 4.1.46(a). By Theorem 4.2.11, $rank 𝑇 =$ $𝑛^{2} -$ $𝑛 (𝑛 + 1) / 2 =$ $𝑛 (𝑛 - 1) / 2$ .

(b) Since ${(𝑋^{𝖳})}^{𝖳} = 𝑋$ , we have ${(𝑋 - 𝑋^{𝖳})}^{𝖳} =$ $𝑋^{𝖳} -$ $𝑋 =$ $- (𝑋 - 𝑋^{𝖳})$ , so every value of $𝑇$ is skew-symmetric: $im 𝑇 \subseteq 𝐾$ . If $1 + 1 \neq 0$ , then $dim 𝐾 =$ $𝑛 (𝑛 - 1) / 2 =$ $rank 𝑇$ (Exercise 4.1.46(b)), so $im 𝑇 = 𝐾$ by Proposition 4.1.21(b).

(c) Suppose $1 + 1 = 0$ , so $- 1 = 1$ . By the computation in (b), every value of $𝑇$ satisfies $𝑌^{𝖳} = - 𝑌 = 𝑌$ , so it is symmetric, and its $(𝑖, 𝑖)$ entry is $𝑥_{𝑖 𝑖} - 𝑥_{𝑖 𝑖} = 0$ . So $im 𝑇 \subseteq 𝑍$ , the symmetric matrices with zero diagonal. A matrix in $𝑍$ equals $\sum_{𝑖 < 𝑗} 𝑦_{𝑖 𝑗} (𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖})$ , and these $𝑛 (𝑛 - 1) / 2$ matrices are independent (the $(𝑖, 𝑗)$ entry of a combination, for $𝑖 < 𝑗$ , is the coefficient of $𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}$ ). So $dim 𝑍 =$ $𝑛 (𝑛 - 1) / 2 =$ $rank 𝑇$ , and $im 𝑇 = 𝑍$ . Since $𝑈_{11}$ is symmetric but not in $𝑍$ , the image is a proper subspace of the symmetric matrices.

Exercise 4.2.42.standard Let $𝑛 \geq 1$ , and let $𝑍_{𝑛} \subseteq 𝐹^{𝑛 \times 𝑛}$ be the set of matrices all of whose row sums and column sums are $0$ .

(a)Show that $dim 𝑍_{𝑛} = {(𝑛 - 1)}^{2}$ . (Consider the map $Φ : 𝐹^{𝑛 \times 𝑛} \to 𝐹^{2 𝑛}$ sending $𝑋$ to its $𝑛$ row sums followed by its $𝑛$ column sums.)
(b)Show that the matrices $𝑈_{𝑖 𝑗} -$ $𝑈_{𝑖 𝑛} -$ $𝑈_{𝑛 𝑗} +$ $𝑈_{𝑛 𝑛}$ , for $1 \leq 𝑖, 𝑗 \leq 𝑛 - 1$ , form a basis of $𝑍_{𝑛}$ .

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Example 4.2.25 (Kernels of linear functionals), Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.1.10 (Independent lists are short), Lemma 2.4.24 (Matrix units)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. Every value

(𝐫, 𝐜)

Φ

satisfies

\sum_{𝑖} 𝑟_{𝑖} = \sum_{𝑗} 𝑐_{𝑗}

. Why? These vectors form the kernel of a nonzero linear functional on

𝐹^{2 𝑛}

Hint 2. To see that every such

(𝐫, 𝐜)

is a value, try

𝑋 =

\sum_{𝑖} 𝑟_{𝑖} 𝑈_{𝑖 1} +

\sum_{𝑗} 𝑐_{𝑗} 𝑈_{1 𝑗} -

𝑠 𝑈_{11}

with

𝑠 = \sum_{𝑖} 𝑟_{𝑖}

Hint 3. For (b), there are

{(𝑛 - 1)}^{2}

matrices; check that they lie in

𝑍_{𝑛}

and are independent.

Sketch. (a)

𝑍_{𝑛} = ker Φ

. Values of

Φ

lie in

𝐻 =

{(𝐫, 𝐜) | \sum 𝑟_{𝑖} = \sum 𝑐_{𝑗}}

, of dimension

2 𝑛 - 1

, and the matrix in the hint shows every element of

𝐻

is a value. So

rank Φ = 2 𝑛 - 1

and

dim 𝑍_{𝑛} = 𝑛^{2} - 2 𝑛 + 1

. (b) Each listed matrix has row and column sums

0

, and the

(𝑖, 𝑗)

entry of a combination, for

𝑖, 𝑗 < 𝑛

, is the coefficient of the

(𝑖, 𝑗)

th matrix; an independent list of length

dim 𝑍_{𝑛}

is a basis.

(a) $Φ$ is linear, since row and column sums are, and $𝑍_{𝑛} = ker Φ$ . Let $𝐻 =$ ${(𝐫, 𝐜) \in 𝐹^{2 𝑛} | 𝑟_{1} + \dots + 𝑟_{𝑛} = 𝑐_{1} + \dots + 𝑐_{𝑛}}$ . Every value of $Φ$ lies in $𝐻$ , since both sums equal the sum of all entries of $𝑋$ . $𝐻$ is the kernel of the linear functional $(𝐫, 𝐜) \mapsto$ $\sum_{𝑖} 𝑟_{𝑖} -$ $\sum_{𝑗} 𝑐_{𝑗}$ , which is not zero (it sends $𝐞_{1}$ to $1$ ), so $dim 𝐻 = 2 𝑛 - 1$ (Example 4.2.25).

Conversely, let $(𝐫, 𝐜) \in 𝐻$ with $𝑠 =$ $\sum_{𝑖} 𝑟_{𝑖} =$ $\sum_{𝑗} 𝑐_{𝑗}$ , and let

𝑋 = \sum_{𝑖 = 1}^{𝑛} 𝑟_{𝑖} 𝑈_{𝑖 1} + \sum_{𝑗 = 1}^{𝑛} 𝑐_{𝑗} 𝑈_{1 𝑗} - 𝑠 𝑈_{11} .

For $𝑖 \geq 2$ , the only entry of row $𝑖$ of $𝑋$ that can be nonzero is $𝑟_{𝑖}$ ; row $1$ has sum $𝑟_{1} +$ $\sum_{𝑗} 𝑐_{𝑗} -$ $𝑠 =$ $𝑟_{1}$ . For $𝑗 \geq 2$ , the only entry of column $𝑗$ that can be nonzero is $𝑐_{𝑗}$ ; column $1$ has sum $\sum_{𝑖} 𝑟_{𝑖} +$ $𝑐_{1} -$ $𝑠 =$ $𝑐_{1}$ . So $Φ (𝑋) = (𝐫, 𝐜)$ , and $im Φ = 𝐻$ . By Theorem 4.2.11,

dim 𝑍_{𝑛} = 𝑛^{2} - (2 𝑛 - 1) = {(𝑛 - 1)}^{2} .

(b) Let $𝑉_{𝑖 𝑗} =$ $𝑈_{𝑖 𝑗} -$ $𝑈_{𝑖 𝑛} -$ $𝑈_{𝑛 𝑗} +$ $𝑈_{𝑛 𝑛}$ for $𝑖, 𝑗 \leq 𝑛 - 1$ . Row $𝑖$ and row $𝑛$ of $𝑉_{𝑖 𝑗}$ contain one $1$ and one $- 1$ , and so do columns $𝑗$ and $𝑛$ ; all other rows and columns are zero. So $𝑉_{𝑖 𝑗} \in 𝑍_{𝑛}$ . In a combination $\sum_{𝑖, 𝑗 < 𝑛} 𝑐_{𝑖 𝑗} 𝑉_{𝑖 𝑗}$ , the only term with a nonzero $(𝑖, 𝑗)$ entry for $𝑖, 𝑗 < 𝑛$ is $𝑐_{𝑖 𝑗} 𝑉_{𝑖 𝑗}$ , so the combination is $0$ only if all $𝑐_{𝑖 𝑗} = 0$ . These ${(𝑛 - 1)}^{2}$ independent matrices form a basis of $𝑍_{𝑛}$ by (a) and Theorem 4.1.10(b).

Exercise 4.2.43.standard Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

𝑝 \geq 1

, and let

𝐿_{𝐴} : 𝐹^{𝑛 \times 𝑝} \to

𝐹^{𝑚 \times 𝑝}

𝐿_{𝐴} (𝑋) = 𝐴 𝑋

. Show that

rank 𝐿_{𝐴} =

𝑝 \cdot

rank 𝐴

Solution.

Uses. Definition 2.4.1 (Matrix product), Theorem 4.2.11 (Rank–nullity), Proposition 2.4.14 (Algebra of matrices), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.6.2 (Bases are independent spanning lists)

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

Hint 1. Column

𝑗

𝐴 𝑋

𝐴

times column

𝑗

𝑋

. So when is

𝐴 𝑋 = 0

Hint 2. If

𝐤_{1}, \dots, 𝐤_{𝑑}

is a basis of

ker 𝑇_{𝐴}

, let

𝐾_{𝑖 𝑗}

be the

𝑛 \times 𝑝

matrix whose column

𝑗

𝐤_{𝑖}

and whose other columns are

𝟎

. Show these

𝑑 𝑝

matrices form a basis of

ker 𝐿_{𝐴}

Sketch.

𝐴 𝑋 = 0

iff every column of

𝑋

lies in

ker 𝑇_{𝐴}

. With a basis

𝐤_{1}, \dots, 𝐤_{𝑑}

ker 𝑇_{𝐴}

𝑑 = 𝑛 - rank 𝐴

, the matrices

𝐾_{𝑖 𝑗}

(column

𝑗

equal to

𝐤_{𝑖}

, others zero) form a basis of

ker 𝐿_{𝐴}

: expand each column, and compare columns for independence. So

dim ker 𝐿_{𝐴} =

𝑝 (𝑛 - rank 𝐴)

, and rank–nullity gives

rank 𝐿_{𝐴} =

𝑛 𝑝 -

𝑝 (𝑛 - rank 𝐴) =

𝑝 rank 𝐴

$𝐿_{𝐴}$ is linear by Proposition 2.4.14. By Definition 2.4.1, column $𝑗$ of $𝐴 𝑋$ is $𝐴 𝐱_{𝑗}$ , where $𝐱_{𝑗}$ is column $𝑗$ of $𝑋$ . So $𝐴 𝑋 = 0$ if and only if $𝐱_{𝑗} \in ker 𝑇_{𝐴}$ for every $𝑗$ .

Let $𝑑 =$ $dim ker 𝑇_{𝐴} =$ $𝑛 -$ $rank 𝐴$ (Theorem 4.2.11) and let $𝐤_{1}, \dots, 𝐤_{𝑑}$ be a basis of $ker 𝑇_{𝐴}$ . For $1 \leq 𝑖 \leq 𝑑$ and $1 \leq 𝑗 \leq 𝑝$ , let $𝐾_{𝑖 𝑗} \in 𝐹^{𝑛 \times 𝑝}$ have column $𝑗$ equal to $𝐤_{𝑖}$ and all other columns zero. Each $𝐾_{𝑖 𝑗}$ lies in $ker 𝐿_{𝐴}$ . If $𝑋 \in ker 𝐿_{𝐴}$ , write $𝐱_{𝑗} =$ $\sum_{𝑖} 𝑐_{𝑖 𝑗} 𝐤_{𝑖}$ ; then $𝑋$ and $\sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝐾_{𝑖 𝑗}$ have the same column $𝑗$ for every $𝑗$ , so they are equal, and the $𝐾_{𝑖 𝑗}$ span $ker 𝐿_{𝐴}$ . If $\sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝐾_{𝑖 𝑗} =$ $0$ , then column $𝑗$ gives $\sum_{𝑖} 𝑐_{𝑖 𝑗} 𝐤_{𝑖} = 𝟎$ , so $𝑐_{𝑖 𝑗} = 0$ for all $𝑖$ (Theorem 1.5.5). So the $𝐾_{𝑖 𝑗}$ form a basis of $ker 𝐿_{𝐴}$ , and $dim ker 𝐿_{𝐴} = 𝑑 𝑝$ . By Theorem 4.2.11,

rank 𝐿_{𝐴} = 𝑛 𝑝 - 𝑝 (𝑛 - rank 𝐴) = 𝑝 \cdot rank 𝐴 .

Exercise 4.2.44.standard Let $𝑇 \in L (𝑉, 𝑊)$ .

(a)Let $𝑈$ be a finite-dimensional subspace of $𝑉$ . Show that $dim im (𝑇 ↾_{𝑈}) =$ $dim 𝑈 -$ $dim (𝑈 \cap ker 𝑇)$ .
(b)Let $𝑉$ be finite-dimensional. Show that there is a subspace $𝑈$ of $𝑉$ with $𝑈 \cap ker 𝑇 = {𝟎}$ and $im (𝑇 ↾_{𝑈}) = im 𝑇$ , and that every such $𝑈$ has $dim 𝑈 = rank 𝑇$ .
(c)For $𝑇 : ℝ^{3} \to ℝ^{2}$ , $𝑇 (𝑥, 𝑦, 𝑧) =$ $(𝑥 + 𝑦, 𝑦 + 𝑧)$ , give two different subspaces $𝑈$ as in (b).

Solution.

Uses. Proposition 4.2.3 (Properties of restriction), Theorem 4.2.11 (Rank–nullity), Proposition 2.1.16 (Linear maps preserve spans and linear relations), Theorem 1.5.5 (Independence is decided at zero)

Techniques. Restrict to a subspace (Technique 4.2.5)

Hint 1. (a) is rank–nullity for

𝑇 ↾_{𝑈}

Hint 2. (b) Take a basis

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

im 𝑇

, pick

𝐯_{𝑖}

with

𝑇 (𝐯_{𝑖}) = 𝐰_{𝑖}

, and let

𝑈 =

span (𝐯_{1}, \dots, 𝐯_{𝑟})

Sketch. (a)

ker (𝑇 ↾_{𝑈}) =

𝑈 \cap

ker 𝑇

; apply rank–nullity to

𝑇 ↾_{𝑈}

. (b) With

𝑈

as in the hint,

im (𝑇 ↾_{𝑈}) =

span (𝐰_{𝑖}) =

im 𝑇

, and

\sum 𝑐_{𝑖} 𝐯_{𝑖} \in ker 𝑇

gives

\sum 𝑐_{𝑖} 𝐰_{𝑖} = 𝟎

, so all

𝑐_{𝑖} = 0

. For any such

𝑈

, (a) gives

dim 𝑈 = rank 𝑇

. (c)

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

and

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

(a) By Proposition 4.2.3(c), $𝑇 ↾_{𝑈} \in L (𝑈, 𝑊)$ has kernel $𝑈 \cap ker 𝑇$ . By Theorem 4.2.11 applied to it, $dim 𝑈 =$ $dim (𝑈 \cap ker 𝑇) +$ $dim im (𝑇 ↾_{𝑈})$ .

(b) By Theorem 4.2.11, $im 𝑇$ is finite-dimensional; let $𝐰_{1}, \dots, 𝐰_{𝑟}$ be a basis, $𝑟 = rank 𝑇$ , and choose $𝐯_{𝑖} \in 𝑉$ with $𝑇 (𝐯_{𝑖}) = 𝐰_{𝑖}$ . Let $𝑈 =$ $span (𝐯_{1}, \dots, 𝐯_{𝑟})$ . By Proposition 2.1.16(a), $im (𝑇 ↾_{𝑈}) =$ $span (𝐰_{1}, \dots, 𝐰_{𝑟}) =$ $im 𝑇$ . If $𝐮 =$ $\sum_{𝑖} 𝑐_{𝑖} 𝐯_{𝑖} \in$ $ker 𝑇$ , then $𝟎 =$ $𝑇 (𝐮) =$ $\sum_{𝑖} 𝑐_{𝑖} 𝐰_{𝑖}$ , so all $𝑐_{𝑖} = 0$ (Theorem 1.5.5) and $𝐮 = 𝟎$ . So $𝑈 \cap ker 𝑇 = {𝟎}$ .

If $𝑈$ is any subspace with these two properties, it is finite-dimensional because $𝑉$ is, and (a) gives $dim 𝑈 =$ $dim im 𝑇 +$ $0 =$ $rank 𝑇$ .

(c) $𝑇 (𝑥, 𝑦, 𝑧) = 𝟎$ means $𝑥 = - 𝑦$ and $𝑧 = - 𝑦$ , so $ker 𝑇 =$ $span ((1, - 1, 1))$ , and $rank 𝑇 = 2$ , so $im 𝑇 = ℝ^{2}$ . For $𝑈 = span (𝐞_{1}, 𝐞_{3})$ : $𝑇 (𝐞_{1}) = (1, 0)$ and $𝑇 (𝐞_{3}) = (0, 1)$ span $ℝ^{2}$ , and a vector $(𝑎, 0, 𝑐)$ is a multiple $𝑡 (1, - 1, 1)$ only if $𝑡 = 0$ . For $𝑈 = span (𝐞_{1}, 𝐞_{2})$ : $𝑇 (𝐞_{1}) = (1, 0)$ and $𝑇 (𝐞_{2}) = (1, 1)$ span $ℝ^{2}$ , and $(𝑎, 𝑏, 0) =$ $𝑡 (1, - 1, 1)$ forces $𝑡 = 0$ . So $𝑈$ is not determined by $𝑇$ ; only its dimension is.

Exercise 4.2.45.standard Find the error in the following argument, show that its claim is false, and repair it.

Claim. Let $𝑉$ be finite-dimensional, $𝑇 \in L (𝑉, 𝑊)$ , and let $𝐯_{1}, \dots, 𝐯_{𝑛}$ be a basis of $𝑉$ such that $𝑇 (𝐯_{𝑘 + 1}),$ $\dots,$ $𝑇 (𝐯_{𝑛})$ is a basis of $im 𝑇$ . Then $𝐯_{1}, \dots, 𝐯_{𝑘}$ is a basis of $ker 𝑇$ .

Proof. By rank–nullity, $dim ker 𝑇 =$ $𝑛 -$ $(𝑛 - 𝑘) =$ $𝑘$ . The list $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly independent, as a sublist of a basis, and it has length $𝑘 = dim ker 𝑇$ . By Theorem 4.1.10(b), it is a basis of $ker 𝑇$ .

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Theorem 4.1.10 (Independent lists are short), Corollary 1.5.17 (Sublists), Corollary 4.1.11 (Spanning lists are long)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Theorem 4.1.10(b) applies to independent lists in

ker 𝑇

. Is each

𝐯_{𝑖}

with

𝑖 \leq 𝑘

ker 𝑇

Hint 2. Try

𝑇 (𝑥, 𝑦) = 𝑥

ℝ^{2}

with the basis

(1, 1), (1, 0)

Hint 3. To repair, subtract from each

𝐯_{𝑖}

(

𝑖 \leq 𝑘

) a combination of

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

with the same image under

𝑇

Sketch. The proof never checks that

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

lie in

ker 𝑇

. Counterexample:

𝑇 (𝑥, 𝑦) = 𝑥

𝐯_{1} = (1, 1)

𝐯_{2} = (1, 0)

;

𝑇 (𝐯_{2}) = 1

is a basis of

im 𝑇 = ℝ

, but

𝐯_{1} \notin ker 𝑇

. Repair: write

𝑇 (𝐯_{𝑖}) =

\sum_{𝑗 > 𝑘} 𝑐_{𝑖 𝑗} 𝑇 (𝐯_{𝑗})

and set

𝐯_{𝑖^{'}} =

𝐯_{𝑖} -

\sum_{𝑗 > 𝑘} 𝑐_{𝑖 𝑗} 𝐯_{𝑗}

; then

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

is a basis of

ker 𝑇

The error. Theorem 4.1.10(b), applied in the vector space $ker 𝑇$ , needs an independent list of vectors of $ker 𝑇$ . The proof never shows that $𝐯_{1}, \dots, 𝐯_{𝑘}$ lie in $ker 𝑇$ , and they need not.

Counterexample. Let $𝑇 : ℝ^{2} \to ℝ$ , $𝑇 (𝑥, 𝑦) = 𝑥$ , with the basis $𝐯_{1} = (1, 1)$ , $𝐯_{2} = (1, 0)$ of $ℝ^{2}$ and $𝑘 = 1$ . Then $𝑇 (𝐯_{2}) = 1$ is a basis of $im 𝑇 = ℝ$ , but $𝑇 (𝐯_{1}) = 1 \neq 0$ , so $𝐯_{1}$ is not in $ker 𝑇 = span (𝐞_{2})$ .

Repair. The claim holds if we also assume $𝐯_{1}, \dots, 𝐯_{𝑘} \in ker 𝑇$ ; then the proof above is correct. Without that assumption we can modify the $𝐯_{𝑖}$ . For $𝑖 \leq 𝑘$ , $𝑇 (𝐯_{𝑖}) \in im 𝑇$ , so $𝑇 (𝐯_{𝑖}) =$ $\sum_{𝑗 > 𝑘} 𝑐_{𝑖 𝑗} 𝑇 (𝐯_{𝑗})$ for some scalars $𝑐_{𝑖 𝑗}$ . Let $𝐯_{𝑖^{'}} =$ $𝐯_{𝑖} -$ $\sum_{𝑗 > 𝑘} 𝑐_{𝑖 𝑗} 𝐯_{𝑗}$ . Then $𝑇 (𝐯_{𝑖^{'}}) = 𝟎$ , and the list $𝐯_{1^{'}},$ $\dots,$ $𝐯_{𝑘^{'}},$ $𝐯_{𝑘 + 1},$ $\dots,$ $𝐯_{𝑛}$ spans $𝑉$ (each $𝐯_{𝑖}$ is recovered by adding back a combination of the later vectors) and has length $𝑛$ , so it is a basis (Corollary 4.1.11(b)). Its sublist $𝐯_{1^{'}}, \dots, 𝐯_{𝑘^{'}}$ is independent (Corollary 1.5.17), lies in $ker 𝑇$ , and has length $𝑘 = dim ker 𝑇$ , so it is a basis of $ker 𝑇$ . In the counterexample, $𝐯_{1^{'}} =$ $(1, 1) -$ $(1, 0) =$ $(0, 1)$ .

Exercise 4.2.46.standard Let

𝑛 \geq 1

and

0 \leq 𝑘 \leq 𝑛

. Show that there is

𝑇 \in L (𝐹^{𝑛})

with

𝑇^{2} = 0

and

rank 𝑇 = 𝑘

if and only if

2 𝑘 \leq 𝑛

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces), Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 2.1.16 (Linear maps preserve spans and linear relations)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1.

𝑇^{2} = 0

says that

𝑇

kills every value of

𝑇

. Compare

im 𝑇

and

ker 𝑇

Hint 2. For the construction, send

𝐞_{𝑘 + 𝑖} \mapsto 𝐞_{𝑖}

for

1 \leq 𝑖 \leq 𝑘

and every other standard basis vector to

𝟎

Sketch.

𝑇^{2} = 0

iff

im 𝑇 \subseteq ker 𝑇

, which forces

𝑘 \leq 𝑛 - 𝑘

. Conversely, if

2 𝑘 \leq 𝑛

, the map with

𝑇 (𝐞_{𝑘 + 𝑖}) = 𝐞_{𝑖}

(

𝑖 \leq 𝑘

) and

𝑇 (𝐞_{𝑗}) = 𝟎

otherwise has image

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

, which it kills.

Only if. If $𝑇^{2} = 0$ , then $𝑇 (𝑇 (𝐯)) = 𝟎$ for all $𝐯$ , so $im 𝑇 \subseteq ker 𝑇$ . By Proposition 4.1.21(a) and Theorem 4.2.11, $𝑘 =$ $dim im 𝑇 \leq$ $dim ker 𝑇 =$ $𝑛 -$ $𝑘$ , so $2 𝑘 \leq 𝑛$ .

If. Suppose $2 𝑘 \leq 𝑛$ . By Theorem 2.2.1 there is $𝑇 \in L (𝐹^{𝑛})$ with $𝑇 (𝐞_{𝑘 + 𝑖}) = 𝐞_{𝑖}$ for $1 \leq 𝑖 \leq 𝑘$ (these indices are at most $2 𝑘 \leq 𝑛$ ) and $𝑇 (𝐞_{𝑗}) = 𝟎$ for every other $𝑗$ . By Proposition 2.1.16(a), $im 𝑇 =$ $span (𝐞_{1}, \dots, 𝐞_{𝑘})$ , so $rank 𝑇 = 𝑘$ . For $𝑖 \leq 𝑘$ , the index $𝑖$ is not of the form $𝑘 + 𝑖^{'}$ with $𝑖^{'} \geq 1$ , so $𝑇 (𝐞_{𝑖}) = 𝟎$ . Hence $𝑇^{2} (𝐞_{𝑗}) =$ $𝑇 (𝑇 (𝐞_{𝑗})) =$ $𝟎$ for every $𝑗$ , since $𝑇 (𝐞_{𝑗})$ is $𝟎$ or some $𝐞_{𝑖}$ with $𝑖 \leq 𝑘$ . A linear map that kills a basis is $0$ , so $𝑇^{2} = 0$ .

Exercise 4.2.47.standard Let $𝐹$ be any field, and let $𝑇 : {𝐹 [𝑥]}_{\leq 3} \to 𝐹^{4}$ , $𝑇 (𝑝) =$ $(𝑝 (0), 𝑝^{'} (0), 𝑝 (1), 𝑝^{'} (1))$ .

(a)Show that $𝑇$ is bijective. So for any prescribed values and slopes at $0$ and $1$ there is exactly one polynomial of degree at most $3$ with them.
(b)Find the $𝑝$ with $𝑝 (0) =$ $𝑝^{'} (0) =$ $𝑝^{'} (1) =$ $0$ and $𝑝 (1) = 1$ .

Solution.

Uses. Corollary 4.2.18 (Injective if and only if surjective), Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Example 2.1.9 (Maps of polynomials)

Techniques. Uniqueness gives existence (Technique 3.4.21), Dimension counting (Technique 4.2.24)

Hint 1. Both spaces have dimension

4

, so it suffices to show

ker 𝑇 = {𝟎}

Hint 2. Write

𝑝 =

𝑎_{0} +

𝑎_{1} 𝑥 +

𝑎_{2} 𝑥^{2} +

𝑎_{3} 𝑥^{3}

and compute the four entries of

𝑇 (𝑝)

Sketch.

𝑇 (𝑝) =

(𝑎_{0}, 𝑎_{1}, 𝑎_{0} + 𝑎_{1} + 𝑎_{2} + 𝑎_{3}, 𝑎_{1} + 2 𝑎_{2} + 3 𝑎_{3})

. If this is

𝟎

, then

𝑎_{0} = 𝑎_{1} = 0

𝑎_{2} + 𝑎_{3} = 0

, and

2 𝑎_{2} + 3 𝑎_{3} = 0

; subtracting twice the third equation from the fourth gives

𝑎_{3} = 0

, then

𝑎_{2} = 0

. So

𝑇

is injective, hence bijective. (b) Solving

𝑎_{2} + 𝑎_{3} = 1

2 𝑎_{2} + 3 𝑎_{3} = 0

gives

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

(a) $𝑇$ is linear since evaluation and the formal derivative are (Example 2.1.9). For $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2} +$ $𝑎_{3} 𝑥^{3}$ , $𝑝^{'} =$ $𝑎_{1} +$ $2 𝑎_{2} 𝑥 +$ $3 𝑎_{3} 𝑥^{2}$ , so

𝑇 (𝑝) = (𝑎_{0}, 𝑎_{1}, 𝑎_{0} + 𝑎_{1} + 𝑎_{2} + 𝑎_{3}, 𝑎_{1} + 2 𝑎_{2} + 3 𝑎_{3}) .

If $𝑇 (𝑝) = 𝟎$ , then $𝑎_{0} = 𝑎_{1} = 0$ , $𝑎_{2} + 𝑎_{3} = 0$ , and $2 𝑎_{2} + 3 𝑎_{3} = 0$ . Subtracting twice the third equation from the fourth gives $𝑎_{3} = 0$ , and then $𝑎_{2} = 0$ . So $ker 𝑇 = {𝟎}$ , and $𝑇$ is injective (Theorem 2.6.11). Both spaces have dimension $4$ , so $𝑇$ is bijective by Corollary 4.2.18. No step divided by anything, so this holds over every field.

(b) We need $𝑎_{0} = 𝑎_{1} = 0$ , $𝑎_{2} + 𝑎_{3} = 1$ , and $2 𝑎_{2} + 3 𝑎_{3} = 0$ . Subtracting twice the first of the last two from the second gives $𝑎_{3} = - 2$ , so $𝑎_{2} = 3$ , and $𝑝 = 3 𝑥^{2} - 2 𝑥^{3}$ . Check: $𝑝 (1) = 1$ , $𝑝^{'} = 6 𝑥 - 6 𝑥^{2}$ vanishes at $0$ and $1$ .

Exercise 4.2.48.standard With

Δ

as in Example 4.2.28, find

𝑝 \in {ℚ [𝑥]}_{\leq 4}

with

Δ 𝑝 = 𝑥^{3}

, and deduce that

1^{3} +

2^{3} +

\dots +

𝑁^{3} =

{(𝑁 (𝑁 + 1) / 2)}^{2}

Solution.

Uses. Example 4.2.28 (Sums of powers)

Hint 1. By Example 4.2.28 such a

𝑝

exists. Try

𝑝 =

𝑎 𝑥^{4} +

𝑏 𝑥^{3} +

𝑐 𝑥^{2} +

𝑑 𝑥

, and compute

Δ (𝑥^{4}) =

4 𝑥^{3} +

6 𝑥^{2} +

4 𝑥 +

1

Hint 2. Telescoping gives

\sum_{𝑡 = 0}^{𝑁 - 1} 𝑡^{3} =

𝑝 (𝑁) -

𝑝 (0)

. Then replace

𝑁

𝑁 + 1

Sketch.

Δ 𝑝 =

4 𝑎 𝑥^{3} +

(6 𝑎 + 3 𝑏) 𝑥^{2} +

(4 𝑎 + 3 𝑏 + 2 𝑐) 𝑥 +

(𝑎 + 𝑏 + 𝑐 + 𝑑)

, so

𝑎 = 1 / 4

𝑏 = - 1 / 2

𝑐 = 1 / 4

𝑑 = 0

, and

𝑝 = {(𝑥 (𝑥 - 1) / 2)}^{2}

. Then

\sum_{𝑡 = 0}^{𝑁 - 1} 𝑡^{3} =

{(𝑁 (𝑁 - 1) / 2)}^{2}

; replace

𝑁

𝑁 + 1

Using $Δ (𝑥^{4}) =$ $4 𝑥^{3} +$ $6 𝑥^{2} +$ $4 𝑥 +$ $1$ , $Δ (𝑥^{3}) = 3 𝑥^{2} + 3 𝑥 + 1$ , $Δ (𝑥^{2}) = 2 𝑥 + 1$ , and $Δ (𝑥) = 1$ , for $𝑝 =$ $𝑎 𝑥^{4} +$ $𝑏 𝑥^{3} +$ $𝑐 𝑥^{2} +$ $𝑑 𝑥$ (a constant term may be dropped, since constants lie in $ker Δ$ ) we get

Δ 𝑝 = 4 𝑎 𝑥^{3} + (6 𝑎 + 3 𝑏) 𝑥^{2} + (4 𝑎 + 3 𝑏 + 2 𝑐) 𝑥 + (𝑎 + 𝑏 + 𝑐 + 𝑑) .

Setting this equal to $𝑥^{3}$ : $𝑎 = 1 / 4$ ; $6 𝑎 + 3 𝑏 = 0$ gives $𝑏 = - 1 / 2$ ; $4 𝑎 + 3 𝑏 + 2 𝑐 = 0$ gives $𝑐 = 1 / 4$ ; and $𝑎 + 𝑏 + 𝑐 + 𝑑 = 0$ gives $𝑑 = 0$ . So

𝑝 = \frac{1}{4} 𝑥^{4} - \frac{1}{2} 𝑥^{3} + \frac{1}{4} 𝑥^{2} = \frac{1}{4} 𝑥^{2} {(𝑥 - 1)}^{2} = {(\frac{𝑥 (𝑥 - 1)}{2})}^{2} .

By the telescoping identity of Example 4.2.28, $0^{3} +$ $1^{3} +$ $\dots +$ ${(𝑁 - 1)}^{3} =$ $𝑝 (𝑁) -$ $𝑝 (0) =$ ${(𝑁 (𝑁 - 1) / 2)}^{2}$ for every $𝑁 \geq 1$ . Applying this with $𝑁 + 1$ in place of $𝑁$ gives $1^{3} +$ $\dots +$ $𝑁^{3} =$ ${(𝑁 (𝑁 + 1) / 2)}^{2}$ .

Exercise 4.2.49.standard Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ .

(a)Let $𝑈_{1}, \dots, 𝑈_{𝑘}$ be subspaces of $𝑉$ . Show that
$dim (𝑈_{1} \cap \dots \cap 𝑈_{𝑘}) \geq dim 𝑈_{1} + \dots + dim 𝑈_{𝑘} - (𝑘 - 1) 𝑛 .$
(b)Let $𝑛 \geq 2$ . Deduce that any $𝑛 - 1$ subspaces of $𝑉$ of dimension $𝑛 - 1$ have a nonzero vector in common.
(c)Show that $𝑛$ subspaces of dimension $𝑛 - 1$ need not have one.

Solution.

Uses. Proposition 4.2.26 (Subspaces that must meet), Proposition 1.4.16 (Intersections of subspaces), Example 4.2.25 (Kernels of linear functionals)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. Induct on

𝑘

, using Proposition 4.2.26 for the intersection of

𝑈_{1} \cap \dots \cap 𝑈_{𝑘}

with

𝑈_{𝑘 + 1}

Hint 2. For (c), in

𝐹^{𝑛}

, use the coordinate hyperplanes

𝑥_{𝑖} = 0

Sketch. (a) For

𝑘 = 1

it is trivial; if

𝑋 = 𝑈_{1} \cap \dots \cap 𝑈_{𝑘}

satisfies the bound, then

dim (𝑋 \cap 𝑈_{𝑘 + 1}) \geq

dim 𝑋 +

dim 𝑈_{𝑘 + 1} -

𝑛

, which is the bound for

𝑘 + 1

. (b) The bound is

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

(𝑛 - 2) 𝑛 =

1

. (c)

𝑈_{𝑖} =

{𝐱 \in 𝐹^{𝑛} | 𝑥_{𝑖} = 0}

has dimension

𝑛 - 1

, and their intersection is

{𝟎}

(a) By induction on $𝑘$ . For $𝑘 = 1$ the claim is $dim 𝑈_{1} \geq dim 𝑈_{1}$ . Suppose it holds for $𝑘$ , and let $𝑋 = 𝑈_{1} \cap \dots \cap 𝑈_{𝑘}$ , a subspace (Proposition 1.4.16). By Proposition 4.2.26 and the inductive hypothesis,

dim (𝑋 \cap 𝑈_{𝑘 + 1}) \geq dim 𝑋 + dim 𝑈_{𝑘 + 1} - 𝑛 \geq \sum_{𝑖 = 1}^{𝑘 + 1} dim 𝑈_{𝑖} - (𝑘 - 1) 𝑛 - 𝑛,

which is the claim for $𝑘 + 1$ .

(b) With $𝑘 = 𝑛 - 1$ subspaces of dimension $𝑛 - 1$ , the bound is $(𝑛 - 1) (𝑛 - 1) -$ $(𝑛 - 2) 𝑛 =$ $𝑛^{2} -$ $2 𝑛 +$ $1 -$ $𝑛^{2} +$ $2 𝑛 =$ $1$ . So the intersection has dimension at least $1$ and contains a nonzero vector.

(c) Choose a basis and identify $𝑉$ with $𝐹^{𝑛}$ by coordinates. The subspace $𝑈_{𝑖} =$ ${𝐱 \in 𝐹^{𝑛} | 𝑥_{𝑖} = 0}$ is the kernel of the nonzero functional $𝐱 \mapsto 𝑥_{𝑖}$ , so it has dimension $𝑛 - 1$ (Example 4.2.25). A vector in all $𝑛$ of them has every coordinate $0$ , so $𝑈_{1} \cap \dots \cap 𝑈_{𝑛} = {𝟎}$ .

Exercise 4.2.50.standard Let

𝑉

be finite-dimensional and

𝑇 \in L (𝑉)

. Show that the following are equivalent:

(i) $ker 𝑇 \cap im 𝑇 = {𝟎}$ ;
(ii) $ker 𝑇^{2} = ker 𝑇$ ;
(iii) $rank 𝑇^{2} = rank 𝑇$ ;
(iv) $im 𝑇^{2} = im 𝑇$ ;
(v) $ker 𝑇 + im 𝑇 = 𝑉$ .

Show by an example on an infinite-dimensional space that (i) and (iv) are not equivalent in general.

Solution.

Uses. Exercise 2.6.39, Proposition 2.6.15 (Kernels and images of composites), Theorem 4.2.11 (Rank–nullity), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24), Proving TFAE (Technique 2.7.1)

Hint 1. Exercise 2.6.39(c) already gives (i)

\Leftrightarrow

(ii) and (iv)

\Leftrightarrow

(v), with no dimension needed.

Hint 2.

ker 𝑇 \subseteq ker 𝑇^{2}

and

im 𝑇^{2} \subseteq im 𝑇

always. Containment plus equal dimension gives equality.

Hint 3. For the example, try differentiation on

ℝ [𝑥]

Sketch. (i)

\Leftrightarrow

(ii) and (iv)

\Leftrightarrow

(v) are Exercise 2.6.39(c). Since

ker 𝑇 \subseteq ker 𝑇^{2}

, (ii) holds iff the dimensions agree, iff

rank 𝑇^{2} = rank 𝑇

by rank–nullity for

𝑇

and

𝑇^{2}

. Since

im 𝑇^{2} \subseteq im 𝑇

, (iv) holds iff the ranks agree. On

ℝ [𝑥]

𝐷

is surjective, so

im 𝐷^{2} = im 𝐷

, but

ker 𝐷 \cap im 𝐷

is the constants.

By Exercise 2.6.39(c), (i) $\Leftrightarrow$ (ii) and (iv) $\Leftrightarrow$ (v). It remains to connect (ii), (iii), and (iv).

(ii) $\Leftrightarrow$ (iii). By Proposition 2.6.15(a), $ker 𝑇 \subseteq ker 𝑇^{2}$ . By Proposition 4.1.21(b), applied in $ker 𝑇^{2}$ , they are equal if and only if $dim ker 𝑇 =$ $dim ker 𝑇^{2}$ . By Theorem 4.2.11 for $𝑇$ and for $𝑇^{2}$ , $dim ker 𝑇 =$ $dim 𝑉 -$ $rank 𝑇$ and $dim ker 𝑇^{2} =$ $dim 𝑉 -$ $rank 𝑇^{2}$ . So (ii) holds if and only if $rank 𝑇 = rank 𝑇^{2}$ .

(iii) $\Leftrightarrow$ (iv). By Proposition 2.6.15(b), $im 𝑇^{2} \subseteq im 𝑇$ , so by Proposition 4.1.21(b) they are equal if and only if $rank 𝑇^{2} = rank 𝑇$ .

Infinite dimensions. Let $𝐷$ be differentiation on $ℝ [𝑥]$ . Every polynomial is a derivative, so $im 𝐷 = ℝ [𝑥]$ and $im 𝐷^{2} =$ $𝐷 (im 𝐷) =$ $im 𝐷$ , which is (iv). But $ker 𝐷$ is the constants, which lie in $im 𝐷$ , so $ker 𝐷 \cap im 𝐷 \neq {𝟎}$ and (i) fails. The dimension count in (ii) $\Leftrightarrow$ (iii) $\Leftrightarrow$ (iv) has nothing to count here.

Exercise 4.2.51.hard Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ , and let $𝑇 \in L (𝑉)$ .

(a)Show that $ker 𝑇^{𝑘} = ker 𝑇^{𝑘 + 1}$ for some $𝑘$ with $0 \leq 𝑘 \leq 𝑛$ .
(b)Show that if $ker 𝑇^{𝑘} = ker 𝑇^{𝑘 + 1}$ , then $ker 𝑇^{𝑚} = ker 𝑇^{𝑘}$ for every $𝑚 \geq 𝑘$ . Deduce that $ker 𝑇^{2 𝑛} = ker 𝑇^{𝑛}$ .
(c)Deduce that $ker 𝑇^{𝑛} \cap$ $im 𝑇^{𝑛} =$ ${𝟎}$ and $dim ker 𝑇^{𝑛} +$ $dim im 𝑇^{𝑛} =$ $𝑛$ . In particular, for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , $ker 𝑇_{𝐴^{𝑛}} \cap$ $im 𝑇_{𝐴^{𝑛}} =$ ${𝟎}$ .

Solution.

Uses. Proposition 2.6.15 (Kernels and images of composites), Proposition 4.1.21 (Dimensions of subspaces), Exercise 2.6.39, Theorem 4.2.11 (Rank–nullity), Theorem 2.4.2 (The matrix of a composite)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9), Dimension counting (Technique 4.2.24)

Hint 1.

ker 𝑇^{0} \subseteq ker 𝑇^{1} \subseteq \dots

. If every inclusion up to

ker 𝑇^{𝑛 + 1}

were strict, how large would

dim ker 𝑇^{𝑛 + 1}

be?

Hint 2. For (b), if

𝑇^{𝑚 + 2} 𝐯 = 𝟎

, then

𝑇 𝐯 \in ker 𝑇^{𝑚 + 1}

. Induct on

𝑚

Hint 3. For (c), apply Exercise 2.6.39(c) to

𝑆 = 𝑇^{𝑛}

Sketch. (a) A strict inclusion of subspaces raises the dimension by at least

1

, so if all inclusions

ker 𝑇^{𝑘} \subseteq ker 𝑇^{𝑘 + 1}

for

𝑘 = 0, \dots, 𝑛

were strict,

dim ker 𝑇^{𝑛 + 1} \geq 𝑛 + 1

. (b) If

ker 𝑇^{𝑚 + 1} = ker 𝑇^{𝑚}

and

𝑇^{𝑚 + 2} 𝐯 = 𝟎

, then

𝑇 𝐯 \in

ker 𝑇^{𝑚 + 1} =

ker 𝑇^{𝑚}

, so

𝐯 \in ker 𝑇^{𝑚 + 1}

; induct. Since

𝑘 \leq 𝑛 \leq 2 𝑛

ker 𝑇^{𝑛} =

ker 𝑇^{𝑘} =

ker 𝑇^{2 𝑛}

. (c) With

𝑆 = 𝑇^{𝑛}

ker 𝑆^{2} = ker 𝑆

, so

ker 𝑆 \cap im 𝑆 = {𝟎}

; rank–nullity gives the dimensions.

For all $𝑗 \geq 0$ , $ker 𝑇^{𝑗} \subseteq ker 𝑇^{𝑗 + 1}$ , since $𝑇^{𝑗 + 1} = 𝑇 \circ 𝑇^{𝑗}$ (Proposition 2.6.15(a)).

(a) Suppose, to the contrary, that $ker 𝑇^{𝑘} \neq ker 𝑇^{𝑘 + 1}$ for every $𝑘 = 0, 1, \dots, 𝑛$ . A proper subspace has strictly smaller dimension (Proposition 4.1.21(b)), so $dim ker 𝑇^{𝑘 + 1} \geq$ $dim ker 𝑇^{𝑘} +$ $1$ for each such $𝑘$ , and since $dim ker 𝑇^{0} =$ $dim ker {id}_{𝑉} =$ $0$ , induction gives $dim ker 𝑇^{𝑛 + 1} \geq 𝑛 + 1$ . This contradicts $dim ker 𝑇^{𝑛 + 1} \leq 𝑛$ (Proposition 4.1.21(a)).

(b) We show by induction on $𝑚 \geq 𝑘$ that $ker 𝑇^{𝑚 + 1} = ker 𝑇^{𝑚}$ ; the case $𝑚 = 𝑘$ is the hypothesis. Suppose $ker 𝑇^{𝑚 + 1} = ker 𝑇^{𝑚}$ , and let $𝐯 \in ker 𝑇^{𝑚 + 2}$ . Then $𝑇^{𝑚 + 1} (𝑇 𝐯) = 𝟎$ , so $𝑇 𝐯 \in$ $ker 𝑇^{𝑚 + 1} =$ $ker 𝑇^{𝑚}$ , that is, $𝑇^{𝑚 + 1} 𝐯 = 𝟎$ . So $ker 𝑇^{𝑚 + 2} \subseteq$ $ker 𝑇^{𝑚 + 1}$ , and the other containment always holds. Chaining the equalities, $ker 𝑇^{𝑚} = ker 𝑇^{𝑘}$ for all $𝑚 \geq 𝑘$ . With $𝑘 \leq 𝑛$ from (a), $ker 𝑇^{𝑛} =$ $ker 𝑇^{𝑘} =$ $ker 𝑇^{2 𝑛}$ .

(c) Let $𝑆 = 𝑇^{𝑛}$ . By (b), $ker 𝑆^{2} =$ $ker 𝑇^{2 𝑛} =$ $ker 𝑇^{𝑛} =$ $ker 𝑆$ , so $ker 𝑆 \cap im 𝑆 = {𝟎}$ by Exercise 2.6.39(c). By Theorem 4.2.11, $dim ker 𝑆 +$ $dim im 𝑆 =$ $𝑛$ . For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , apply this to $𝑇 = 𝑇_{𝐴}$ , using ${(𝑇_{𝐴})}^{𝑛} = 𝑇_{𝐴^{𝑛}}$ (Theorem 2.4.2).

With the direct sums of Section 4.4, (c) says $𝑉 = ker 𝑇^{𝑛} \oplus im 𝑇^{𝑛}$ . This is Fitting’s decomposition, the starting point of Section 10.1.

Exercise 4.2.52.hard Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ , let $𝑇 \in L (𝑉)$ , and for $𝑘 \geq 1$ let $𝑑_{𝑘} =$ $dim ker 𝑇^{𝑘} -$ $dim ker 𝑇^{𝑘 - 1}$ .

(a)Show that $𝑑_{𝑘} =$ $dim (im 𝑇^{𝑘 - 1} \cap ker 𝑇)$ . (Restrict $𝑇^{𝑘 - 1}$ to $ker 𝑇^{𝑘}$ .)
(b)Deduce that $𝑑_{1} \geq 𝑑_{2} \geq 𝑑_{3} \geq \dots$ .
(c)Suppose $𝑇^{𝑚} = 0$ for some $𝑚 \geq 1$ . Show that $dim ker 𝑇 \geq 𝑛 / 𝑚$ , so that $rank 𝑇 \leq$ $(𝑚 - 1) 𝑛 / 𝑚$ .

Solution.

Uses. Proposition 4.2.3 (Properties of restriction), Theorem 4.2.11 (Rank–nullity), Proposition 2.6.15 (Kernels and images of composites), Proposition 4.1.21 (Dimensions of subspaces)

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

Hint 1. Let

𝑆 = 𝑇^{𝑘 - 1} ↾_{ker 𝑇^{𝑘}}

. Its kernel is

ker 𝑇^{𝑘 - 1}

. Show that its image is

im 𝑇^{𝑘 - 1} \cap ker 𝑇

Hint 2. For (b),

im 𝑇^{𝑘} \subseteq im 𝑇^{𝑘 - 1}

Hint 3. For (c),

𝑛 =

dim ker 𝑇^{𝑚} =

𝑑_{1} +

\dots +

𝑑_{𝑚}

Sketch. (a)

𝑆 = 𝑇^{𝑘 - 1} ↾_{ker 𝑇^{𝑘}}

has kernel

ker 𝑇^{𝑘} \cap

ker 𝑇^{𝑘 - 1} =

ker 𝑇^{𝑘 - 1}

and image

im 𝑇^{𝑘 - 1} \cap ker 𝑇

(a vector

𝑇^{𝑘 - 1} 𝐯

lies in

ker 𝑇

iff

𝐯 \in ker 𝑇^{𝑘}

). Rank–nullity for

𝑆

is the claim. (b) The subspaces

im 𝑇^{𝑘 - 1} \cap ker 𝑇

shrink as

𝑘

grows. (c)

𝑛 =

𝑑_{1} +

\dots +

𝑑_{𝑚} \leq

𝑚 𝑑_{1} =

𝑚 dim ker 𝑇

(a) Let $𝑆 =$ $𝑇^{𝑘 - 1} ↾_{ker 𝑇^{𝑘}} : ker 𝑇^{𝑘} \to$ $𝑉$ , which is linear (Proposition 4.2.3(c)). Its kernel is $ker 𝑇^{𝑘} \cap$ $ker 𝑇^{𝑘 - 1} =$ $ker 𝑇^{𝑘 - 1}$ , since $ker 𝑇^{𝑘 - 1} \subseteq ker 𝑇^{𝑘}$ . Its image is $im 𝑇^{𝑘 - 1} \cap ker 𝑇$ : if $𝐯 \in ker 𝑇^{𝑘}$ , then $𝑇^{𝑘 - 1} 𝐯 \in im 𝑇^{𝑘 - 1}$ and $𝑇 (𝑇^{𝑘 - 1} 𝐯) =$ $𝑇^{𝑘} 𝐯 =$ $𝟎$ ; conversely, if $𝐰 = 𝑇^{𝑘 - 1} 𝐯$ lies in $ker 𝑇$ , then $𝑇^{𝑘} 𝐯 = 𝑇 𝐰 = 𝟎$ , so $𝐯 \in ker 𝑇^{𝑘}$ and $𝐰 = 𝑆 (𝐯)$ . By Theorem 4.2.11 for $𝑆$ ,

dim ker 𝑇^{𝑘} = dim ker 𝑇^{𝑘 - 1} + dim (im 𝑇^{𝑘 - 1} \cap ker 𝑇) .

(b) Since $𝑇^{𝑘} = 𝑇^{𝑘 - 1} \circ 𝑇$ , $im 𝑇^{𝑘} \subseteq im 𝑇^{𝑘 - 1}$ (Proposition 2.6.15(b)). So $im 𝑇^{𝑘} \cap$ $ker 𝑇 \subseteq$ $im 𝑇^{𝑘 - 1} \cap$ $ker 𝑇$ , and $𝑑_{𝑘 + 1} \leq 𝑑_{𝑘}$ by (a) and Proposition 4.1.21(a).

(c) If $𝑇^{𝑚} = 0$ , then $ker 𝑇^{𝑚} = 𝑉$ , and $ker 𝑇^{0} = {𝟎}$ , so the sum telescopes:

𝑛 = dim ker 𝑇^{𝑚} - dim ker 𝑇^{0} = 𝑑_{1} + 𝑑_{2} + \dots + 𝑑_{𝑚} \leq 𝑚 𝑑_{1} = 𝑚 dim ker 𝑇,

using (b). Hence $dim ker 𝑇 \geq 𝑛 / 𝑚$ , and $rank 𝑇 =$ $𝑛 -$ $dim ker 𝑇 \leq$ $𝑛 -$ $𝑛 / 𝑚 =$ $(𝑚 - 1) 𝑛 / 𝑚$ .

For $𝑚 = 2$ this is the bound $rank 𝑇 \leq 𝑛 / 2$ of Exercise 4.2.46. For the shift $𝑁$ on $𝐹^{4}$ of Section 4.1.7, $𝑑_{1} = 𝑑_{2} = 𝑑_{3} = 𝑑_{4} = 1$ ; how the $𝑑_{𝑘}$ can decrease is what Section 10.3 classifies.

Exercise 4.2.53.hard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ .

(a)Show that $𝐱 \mapsto 𝐵 𝐱$ maps $ker 𝑇_{𝐼_{𝑚} - 𝐴 𝐵}$ injectively into $ker 𝑇_{𝐼_{𝑛} - 𝐵 𝐴}$ .
(b)Deduce that $dim ker (𝐼_{𝑚} - 𝐴 𝐵) =$ $dim ker (𝐼_{𝑛} - 𝐵 𝐴)$ .
(c)Deduce that $𝐼_{𝑚} - 𝐴 𝐵$ is invertible if and only if $𝐼_{𝑛} - 𝐵 𝐴$ is.

Solution.

Uses. Proposition 4.2.3 (Properties of restriction), Proposition 4.2.6 (Injective maps preserve dimension), Proposition 4.1.21 (Dimensions of subspaces), Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.14 (Third Fundamental Theorem, completed), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ ), Proposition 2.4.14 (Algebra of matrices)

Techniques. Restrict to a subspace (Technique 4.2.5)

Hint 1. If

(𝐼_{𝑚} - 𝐴 𝐵) 𝐱 = 𝟎

, then

𝐱 = 𝐴 𝐵 𝐱

. Compute

(𝐼_{𝑛} - 𝐵 𝐴) (𝐵 𝐱)

Hint 2. If also

𝐵 𝐱 = 𝟎

, what is

𝐱

Hint 3. For (b), swap the roles of

𝐴

and

𝐵

Sketch. If

𝐱 = 𝐴 𝐵 𝐱

, then

(𝐼_{𝑛} - 𝐵 𝐴) 𝐵 𝐱 =

𝐵 𝐱 -

𝐵 (𝐴 𝐵 𝐱) =

𝟎

, and

𝐵 𝐱 = 𝟎

forces

𝐱 = 𝐴 (𝐵 𝐱) = 𝟎

. So

𝑇_{𝐵} ↾_{ker (𝐼_{𝑚} - 𝐴 𝐵)}

is injective into

ker (𝐼_{𝑛} - 𝐵 𝐴)

, giving

\leq

; by symmetry, equality. A square matrix is invertible iff its kernel is

{𝟎}

(a) Let $𝐱 \in ker 𝑇_{𝐼_{𝑚} - 𝐴 𝐵}$ , so $𝐱 = 𝐴 𝐵 𝐱$ . Then

(𝐼_{𝑛} - 𝐵 𝐴) (𝐵 𝐱) = 𝐵 𝐱 - 𝐵 (𝐴 𝐵 𝐱) = 𝐵 𝐱 - 𝐵 𝐱 = 𝟎,

so $𝐵 𝐱 \in$ $ker 𝑇_{𝐼_{𝑛} - 𝐵 𝐴}$ . If $𝐵 𝐱 = 𝟎$ , then $𝐱 = 𝐴 (𝐵 𝐱) = 𝟎$ . So the restriction of $𝑇_{𝐵}$ to $ker 𝑇_{𝐼_{𝑚} - 𝐴 𝐵}$ is linear with kernel ${𝟎}$ (Proposition 4.2.3(c)), hence injective, with image inside $ker 𝑇_{𝐼_{𝑛} - 𝐵 𝐴}$ .

(b) By (a) and Proposition 4.2.6(b), $dim ker (𝐼_{𝑚} - 𝐴 𝐵) =$ $dim im (𝑇_{𝐵} ↾_{ker (𝐼_{𝑚} - 𝐴 𝐵)}) \leq$ $dim ker (𝐼_{𝑛} - 𝐵 𝐴)$ , using Proposition 4.1.21(a). Applying (a) with the roles of $𝐴$ and $𝐵$ exchanged (and $𝑚$ , $𝑛$ exchanged) gives the reverse inequality.

(c) For a square matrix $𝐶 \in 𝐹^{𝑘 \times 𝑘}$ , $ker 𝑇_{𝐶} = {𝟎}$ if and only if $rank 𝐶 = 𝑘$ (Theorem 3.5.12), if and only if $𝑇_{𝐶}$ is invertible (Theorem 3.5.14), if and only if $𝐶$ is invertible (Remark 3.5.7). By (b), $ker (𝐼_{𝑚} - 𝐴 𝐵) =$ ${𝟎}$ if and only if $ker (𝐼_{𝑛} - 𝐵 𝐴) =$ ${𝟎}$ .

Replacing $𝐴$ by $𝜆^{- 1} 𝐴$ for a scalar $𝜆 \neq 0$ shows $dim ker (𝜆 𝐼_{𝑚} - 𝐴 𝐵) =$ $dim ker (𝜆 𝐼_{𝑛} - 𝐵 𝐴)$ : in the language of Section 7.2, $𝐴 𝐵$ and $𝐵 𝐴$ have the same nonzero eigenvalues, with eigenspaces of the same dimensions, even when $𝑚 \neq 𝑛$ .

Exercise 4.2.54.hard Let $𝑆$ be a subspace of $𝐹^{𝑛 \times 𝑛}$ in which every nonzero matrix is invertible.

(a)Show that $dim 𝑆 \leq 𝑛$ .
(b)Show that $𝑆 =$ ${(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix}) | 𝑎, 𝑏 \in ℝ}$ is such a subspace of $ℝ^{2 \times 2}$ with $dim 𝑆 = 2$ .
(c)Find such a subspace of $𝔽_{2}^{2 \times 2}$ of dimension $2$ .

Solution.

Uses. Corollary 4.2.21 (Dimension obstructions), Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Definition 2.5.12 (Invertible)

Hint 1. Find an injective linear map from

𝑆

into

𝐹^{𝑛}

. What does a nonzero invertible matrix do to

𝐞_{1}

Hint 2. For (b), multiply

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

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

Hint 3. For (c), you need a matrix

𝑀

such that

𝑀

and

𝐼_{2} + 𝑀

are both invertible. Recall Exercise 1.1.56.

Sketch. (a)

𝑋 \mapsto 𝑋 𝐞_{1}

is linear

𝑆 \to 𝐹^{𝑛}

, and injective: if

𝑋 𝐞_{1} = 𝟎

with

𝑋 \neq 0

, then

𝑋

is invertible and

𝐞_{1} = 𝑋^{- 1} 𝟎 = 𝟎

. So

dim 𝑆 \leq 𝑛

. (b)

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

(𝑎^{2} + 𝑏^{2}) 𝐼_{2}

. (c)

span (𝐼_{2}, 𝑀)

with

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

𝑀 (𝑀 + 𝐼_{2}) = 𝐼_{2}

(a) The map $𝜑 : 𝑆 \to 𝐹^{𝑛}$ , $𝜑 (𝑋) = 𝑋 𝐞_{1}$ , is linear. If $𝜑 (𝑋) = 𝟎$ and $𝑋 \neq 0$ , then $𝑋$ is invertible, so $𝐞_{1} =$ $𝑋^{- 1} (𝑋 𝐞_{1}) =$ $𝟎$ , which is false. So $ker 𝜑 = {0}$ , $𝜑$ is injective (Theorem 2.6.11), and $dim 𝑆 \leq 𝑛$ by Corollary 4.2.21(b).

(b) $𝑆 = span (𝐼_{2}, 𝐽)$ with $𝐽 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ , and $𝐼_{2}, 𝐽$ are independent, so $dim 𝑆 = 2$ . For $(𝑎, 𝑏) \neq (0, 0)$ ,

(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix}) (\begin{matrix} 𝑎 & 𝑏 \\ - 𝑏 & 𝑎 \end{matrix}) = (\begin{matrix} 𝑎^{2} + 𝑏^{2} & 0 \\ 0 & 𝑎^{2} + 𝑏^{2} \end{matrix}),

and the product in the other order is the same, so $(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})$ has inverse ${(𝑎^{2} + 𝑏^{2})}^{- 1} (\begin{matrix} 𝑎 & 𝑏 \\ - 𝑏 & 𝑎 \end{matrix})$ , since $𝑎^{2} + 𝑏^{2} > 0$ . (This is $ℂ$ in disguise.)

(c) Let $𝑀 = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}) \in 𝔽_{2}^{2 \times 2}$ and $𝑆 =$ $span (𝐼_{2}, 𝑀) =$ ${0, 𝐼_{2}, 𝑀, 𝐼_{2} + 𝑀}$ . Over $𝔽_{2}$ , $𝑀^{2} =$ $(\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}) =$ $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) =$ $𝐼_{2} +$ $𝑀$ , so $𝑀 (𝑀 + 𝐼_{2}) =$ $𝑀^{2} +$ $𝑀 =$ $𝐼_{2} +$ $𝑀 +$ $𝑀 =$ $𝐼_{2}$ , and likewise $(𝑀 + 𝐼_{2}) 𝑀 = 𝐼_{2}$ . So $𝑀$ and $𝐼_{2} + 𝑀$ are invertible, as is $𝐼_{2}$ , and $𝐼_{2}, 𝑀$ are independent, so $dim 𝑆 = 2$ . (The four matrices multiply like the field $𝔽_{4}$ of Exercise 1.1.56, with $𝑀$ as $𝛼$ .)

Exercise 4.2.55.challenge For $𝐱, 𝐲 \in 𝔽_{2}^{𝑛}$ , let $𝐱 \cdot$ $𝐲 =$ $𝑥_{1} 𝑦_{1} +$ $\dots +$ $𝑥_{𝑛} 𝑦_{𝑛} \in$ $𝔽_{2}$ .

(a)Let $𝐶$ be a subspace of $𝔽_{2}^{𝑛}$ with $dim 𝐶 = 𝑘$ , and let $𝐶^{⟂} =$ ${𝐲 \in 𝔽_{2}^{𝑛} | 𝐜 \cdot 𝐲 = 0 for all 𝐜 \in 𝐶}$ . Show that $𝐶^{⟂}$ is a subspace of dimension $𝑛 - 𝑘$ .
(b)(Eventown.) A town has $𝑛$ residents, who form clubs. Every club has an even number of members, every two clubs have an even number of members in common, and no two clubs have exactly the same members. Show that there are at most $2^{⌊ 𝑛 / 2 ⌋}$ clubs, and that this many is possible.

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Proposition 4.1.19 (Extending linear maps and separating vectors), Theorem 1.5.5 (Independence is decided at zero), Proposition 4.1.34 (Size of a vector space over a finite field)

Hint 1. For (a), with a basis

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

𝐶

, consider

𝜑 : 𝔽_{2}^{𝑛} \to 𝔽_{2}^{𝑘}

𝐲 \mapsto

(𝐛_{1} \cdot 𝐲, \dots, 𝐛_{𝑘} \cdot 𝐲)

. Its kernel is

𝐶^{⟂}

. Why is it surjective?

Hint 2. If

𝜑

were not surjective, a nonzero linear functional on

𝔽_{2}^{𝑘}

would vanish on

im 𝜑

(Proposition 4.1.19(b)). Turn that into a linear relation among the

𝐛_{𝑖}

Hint 3. For (b), let

𝐶

be the span of the indicator vectors of the clubs. Show

𝐶 \subseteq 𝐶^{⟂}

and count.

Sketch. (a)

ker 𝜑 = 𝐶^{⟂}

by bilinearity. If

im 𝜑 \neq 𝔽_{2}^{𝑘}

, some nonzero

𝑓 (𝐳) = \sum 𝑎_{𝑖} 𝑧_{𝑖}

vanishes on

im 𝜑

, so

(\sum 𝑎_{𝑖} 𝐛_{𝑖}) \cdot 𝐲 = 0

for all

𝐲

; taking

𝐲 = 𝐞_{𝑗}

gives

\sum 𝑎_{𝑖} 𝐛_{𝑖} = 𝟎

, contradicting independence. So

dim 𝐶^{⟂} = 𝑛 - 𝑘

. (b) Indicator vectors satisfy

𝐯_{𝐴} \cdot

𝐯_{𝐵} =

| 𝐴 \cap

𝐵 | =

0

𝔽_{2}

, so their span

𝐶

satisfies

𝐶 \subseteq 𝐶^{⟂}

, whence

dim 𝐶 \leq 𝑛 - dim 𝐶

and

| 𝐶 | \leq 2^{⌊ 𝑛 / 2 ⌋}

. Unions of the pairs

{1, 2}, {3, 4}, \dots

attain the bound.

The product is linear in each argument: $(𝑎 𝐱 + 𝐱^{'}) \cdot$ $𝐲 =$ $𝑎 (𝐱 \cdot 𝐲) +$ $𝐱^{'} \cdot$ $𝐲$ , and symmetrically, directly from the formula.

(a) Let $𝐛_{1}, \dots, 𝐛_{𝑘}$ be a basis of $𝐶$ and define $𝜑 : 𝔽_{2}^{𝑛} \to 𝔽_{2}^{𝑘}$ by $𝜑 (𝐲) =$ $(𝐛_{1} \cdot 𝐲, \dots, 𝐛_{𝑘} \cdot 𝐲)$ , which is linear. If $𝐲 \in 𝐶^{⟂}$ , then $𝜑 (𝐲) = 𝟎$ . Conversely, if $𝜑 (𝐲) = 𝟎$ and $𝐜 = \sum_{𝑖} 𝑎_{𝑖} 𝐛_{𝑖} \in 𝐶$ , then $𝐜 \cdot$ $𝐲 =$ $\sum_{𝑖} 𝑎_{𝑖} (𝐛_{𝑖} \cdot 𝐲) =$ $0$ . So $𝐶^{⟂} = ker 𝜑$ , a subspace.

We show that $𝜑$ is surjective. If not, $im 𝜑$ is a subspace of $𝔽_{2}^{𝑘}$ missing some vector $𝐳_{0}$ , and by Proposition 4.1.19(b) there is a linear $𝑓 : 𝔽_{2}^{𝑘} \to 𝔽_{2}$ with $𝑓 (𝐳_{0}) = 1$ and $𝑓 = 0$ on $im 𝜑$ . Writing $𝑎_{𝑖} = 𝑓 (𝐞_{𝑖})$ , we have $𝑓 (𝐳) =$ $\sum_{𝑖} 𝑎_{𝑖} 𝑧_{𝑖}$ , and not all $𝑎_{𝑖}$ are $0$ since $𝑓 \neq 0$ . For every $𝐲$ ,

0 = 𝑓 (𝜑 (𝐲)) = \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} (𝐛_{𝑖} \cdot 𝐲) = (\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐛_{𝑖}) \cdot 𝐲 .

Taking $𝐲 = 𝐞_{𝑗}$ shows that the $𝑗$ th entry of $\sum_{𝑖} 𝑎_{𝑖} 𝐛_{𝑖}$ is $0$ , for every $𝑗$ . So $\sum_{𝑖} 𝑎_{𝑖} 𝐛_{𝑖} = 𝟎$ with not all $𝑎_{𝑖} = 0$ , contradicting the independence of the $𝐛_{𝑖}$ (Theorem 1.5.5). Hence $rank 𝜑 = 𝑘$ , and by Theorem 4.2.11, $dim 𝐶^{⟂} = 𝑛 - 𝑘$ .

(b) Number the residents $1, \dots, 𝑛$ , and for a club $𝐴 \subseteq {1, \dots, 𝑛}$ let $𝐯_{𝐴} \in 𝔽_{2}^{𝑛}$ have $1$ in the positions of the members and $0$ elsewhere. Then $𝐯_{𝐴} \cdot 𝐯_{𝐵}$ counts the common members modulo $2$ , so it is $0$ for any two clubs $𝐴, 𝐵$ , including $𝐴 = 𝐵$ (each club has an even number of members). Let $𝐶$ be the span of all the $𝐯_{𝐴}$ . By linearity in each argument, $𝐜 \cdot 𝐜^{'} = 0$ for all $𝐜, 𝐜^{'} \in 𝐶$ , so $𝐶 \subseteq 𝐶^{⟂}$ . With $𝑘 = dim 𝐶$ , (a) gives $𝑘 \leq 𝑛 - 𝑘$ , so $𝑘 \leq 𝑛 / 2$ , and as $𝑘$ is an integer, $𝑘 \leq ⌊ 𝑛 / 2 ⌋$ . Different clubs have different vectors $𝐯_{𝐴}$ , all in $𝐶$ , so the number of clubs is at most $| 𝐶 | = 2^{𝑘} \leq 2^{⌊ 𝑛 / 2 ⌋}$ (Proposition 4.1.34).

For the construction, let $𝑚 = ⌊ 𝑛 / 2 ⌋$ and take as clubs all unions of some of the pairs ${1, 2},$ ${3, 4},$ $\dots,$ ${2 𝑚 - 1, 2 𝑚}$ , including the empty union. There are $2^{𝑚}$ of them, each a union of pairs, so of even size, and the intersection of two of them is the union of their common pairs, also of even size.

Exercise 4.2.56.standardBeyond 21-242 Let $𝑟 \geq 2$ , $𝑛 = 2^{𝑟} - 1$ , and let $𝐻_{𝑟} \in 𝔽_{2}^{𝑟 \times 𝑛}$ be a matrix whose columns are the $𝑛$ nonzero vectors of $𝔽_{2}^{𝑟}$ , in some order. Let $𝐶_{𝑟} = ker 𝑇_{𝐻_{𝑟}}$ , the Hamming code of length $𝑛$ .

(a)Show that $𝐶_{𝑟}$ is an $[𝑛, 𝑛 - 𝑟]$ code.
(b)Show that its minimum distance is $3$ .
(c)Show that every $𝐱 \in 𝔽_{2}^{𝑛}$ is within distance $1$ of exactly one codeword.

Solution.

Uses. Theorem 4.2.11 (Rank–nullity), Corollary 2.6.24 (The columns decide), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Proposition 4.2.33 (Distinct columns give distance three), Theorem 4.2.34 (Syndrome decoding)

Hint 1. (a) The columns include

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

Hint 2. (b) Proposition 4.2.33 gives at least

3

. For a codeword of weight

3

, use three columns adding up to

𝟎

, such as

𝐞_{1}, 𝐞_{2}, 𝐞_{1} + 𝐞_{2}

Hint 3. (c) If

𝐻_{𝑟} 𝐱 \neq 𝟎

, the syndrome is one of the columns.

Sketch. (a)

𝑇_{𝐻_{𝑟}}

is surjective, so

rank 𝐻_{𝑟} = 𝑟

and

dim 𝐶_{𝑟} = 𝑛 - 𝑟

. (b) Distinct nonzero columns give weight

\geq 3

; the positions of

𝐞_{1}

𝐞_{2}

𝐞_{1} + 𝐞_{2}

give a codeword of weight

3

. (c) If

𝐻_{𝑟} 𝐱 = 𝐡_{𝑗}

, then

𝐱 + 𝐞_{𝑗} \in 𝐶_{𝑟}

; if

𝐻_{𝑟} 𝐱 = 𝟎

𝐱 \in 𝐶_{𝑟}

. Two codewords within distance

1

𝐱

are within distance

2

of each other, hence equal.

(a) The vectors $𝐞_{1}, \dots, 𝐞_{𝑟}$ are among the columns, so the columns span $𝔽_{2}^{𝑟}$ , $𝑇_{𝐻_{𝑟}}$ is surjective (Corollary 2.6.24), and $rank 𝐻_{𝑟} =$ $dim im 𝑇_{𝐻_{𝑟}} =$ $𝑟$ (Theorem 4.2.7). By Theorem 4.2.11, $dim 𝐶_{𝑟} = 𝑛 - 𝑟$ .

(b) The columns are nonzero and pairwise distinct, so every nonzero codeword has weight at least $3$ (Proposition 4.2.33). Since $𝑟 \geq 2$ , the vectors $𝐞_{1}$ , $𝐞_{2}$ , and $𝐞_{1} + 𝐞_{2}$ are three different columns, in positions $𝑖, 𝑗, 𝑙$ say, and their sum is $𝟎$ . So the vector with $1$ s in positions $𝑖, 𝑗, 𝑙$ is a codeword of weight $3$ .

(c) Existence. If $𝐻_{𝑟} 𝐱 = 𝟎$ , then $𝐱$ is a codeword. Otherwise $𝐻_{𝑟} 𝐱$ is a nonzero vector of $𝔽_{2}^{𝑟}$ , hence equal to some column $𝐡_{𝑗}$ , and $𝐻_{𝑟} (𝐱 + 𝐞_{𝑗}) =$ $𝐡_{𝑗} +$ $𝐡_{𝑗} =$ $𝟎$ . So $𝐱 + 𝐞_{𝑗}$ is a codeword at distance $1$ from $𝐱$ .

Uniqueness. If $𝐜, 𝐜^{'} \in 𝐶_{𝑟}$ are both within distance $1$ of $𝐱$ , then $𝑑 (𝐜, 𝐜^{'}) \leq 2$ by the triangle inequality, so $𝐜 - 𝐜^{'}$ is a codeword of weight at most $2$ , and it is $𝟎$ by (b).

So $𝐶_{𝑟}$ is perfect: $2^{𝑛 - 𝑟}$ codewords, each with $𝑛 + 1 = 2^{𝑟}$ words within distance $1$ , account for all $2^{𝑛}$ words.

Exercise 4.2.57.routineBeyond 21-242 Use the Hamming code of Example 4.2.32.

(a)Encode the message $0110$ .
(b)Decode the received words $1000110$ and $1101011$ , assuming each has at most one flipped bit.
(c)The codeword $0000000$ is sent, and bits $1$ and $2$ are flipped. What does syndrome decoding return?

Solution.

Uses. Example 4.2.32 (The Hamming code), Theorem 4.2.34 (Syndrome decoding)

Hint 1. Put the message in positions

3, 5, 6, 7

and compute

𝑥_{1} = 𝑥_{3} + 𝑥_{5} + 𝑥_{7}

𝑥_{2} = 𝑥_{3} + 𝑥_{6} + 𝑥_{7}

𝑥_{4} = 𝑥_{5} + 𝑥_{6} + 𝑥_{7}

Hint 2. The syndrome is the sum of the columns

𝐡_{𝑗}

at the

1

s of the received word; read it as a binary number.

Sketch. (a)

1100110

. (b)

1000110

has syndrome

(0, 1, 0) = 2

, so it decodes to

1100110

and the message

0110

;

1101011

has syndrome

(1, 1, 0) = 6

, so it decodes to

1101001

and the message

0001

. (c) Syndrome

𝐡_{1} + 𝐡_{2} = (0, 1, 1) = 3

, so the decoder flips bit

3

and returns

1110000

, the wrong codeword.

(a) With $(𝑥_{3}, 𝑥_{5}, 𝑥_{6}, 𝑥_{7}) =$ $(0, 1, 1, 0)$ : $𝑥_{1} = 0 + 1 + 0 = 1$ , $𝑥_{2} = 0 + 1 + 0 = 1$ , $𝑥_{4} = 1 + 1 + 0 = 0$ . The codeword is $1100110$ .

(b) The word $1000110$ has $1$ s in positions $1, 5, 6$ , so its syndrome is $𝐡_{1} +$ $𝐡_{5} +$ $𝐡_{6} =$ $(0, 0, 1) +$ $(1, 0, 1) +$ $(1, 1, 0) =$ $(0, 1, 0)$ , binary for $2$ . By Theorem 4.2.34, flipping bit $2$ gives the codeword $1100110$ , and the message is $0110$ . The word $1101011$ has $1$ s in positions $1, 2, 4, 6, 7$ , with syndrome $(0, 0, 1) +$ $(0, 1, 0) +$ $(1, 0, 0) +$ $(1, 1, 0) +$ $(1, 1, 1) =$ $(1, 1, 0)$ , binary for $6$ . Flipping bit $6$ gives $1101001$ , and the message (positions $3, 5, 6, 7$ ) is $0001$ .

(c) The received word $1100000$ has syndrome $𝐡_{1} + 𝐡_{2} = (0, 1, 1)$ , binary for $3$ , so the decoder flips bit $3$ and returns $1110000$ . That is a codeword (Section 4.2.7), but not the one sent. The code corrects one error; two errors can be mistaken for one error at a third position, since the minimum distance is only $3$ .

More practice

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