4.1 Dimension · Matrix Theory

The standard bases of $𝐹^{𝑛}$ , $𝐹^{𝑚 \times 𝑛}$ , and ${𝐹 [𝑥]}_{\leq 𝑛}$ have $𝑛$ , $𝑚 𝑛$ , and $𝑛 + 1$ entries. Each of these spaces has many other bases (Section 1.6), and this section begins by showing that all of them have the same length. That length is the dimension of the space. We prove it twice: with the matrix machinery of Section 3.5, as the lecture does, and with the exchange lemma, which works inside $𝑉$ and says more, namely that an independent list is never longer than a spanning list.

Dimension then turns many questions into counting. A list of the right length is a basis as soon as it is independent or spanning, every independent list extends to a basis, and a subspace is no bigger than the space around it. The counting has consequences well beyond bases. When a chain $𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots$ ends in $𝟎$ , its nonzero vectors are independent, so an operator on an $𝑛$ -dimensional space that is eventually $0$ is already $0$ after $𝑛$ steps. Any $𝑛^{2} + 1$ matrices of size $𝑛 \times 𝑛$ satisfy a linear relation, so every square matrix satisfies a polynomial equation. And over a field with $𝑞$ elements, a space of dimension $𝑛$ has exactly $𝑞^{𝑛}$ vectors.

Throughout, $𝑉$ is a vector space over a field $𝐹$ .

4.1.1Bases of $𝐹^{𝑚}$

Intuition (Why the number of vectors should be fixed). A basis

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

𝑉

names every vector by its coordinates

{[𝐯]}_{ℬ︀} \in 𝐹^{𝑛}

, and the coordinate map

𝑉 \to 𝐹^{𝑛}

is a bijection that respects linear combinations (Proposition 1.6.16, Proposition 1.6.19). So a basis of length

𝑛

makes

𝑉

a copy of

𝐹^{𝑛}

with the vectors renamed. If

𝑉

also had a basis of length

𝑚

, it would be a copy of

𝐹^{𝑚}

as well, and translating from one set of names to the other would give a bijection

𝐹^{𝑚} \to 𝐹^{𝑛}

that respects linear combinations, that is, an invertible linear map. Every linear map

𝐹^{𝑚} \to 𝐹^{𝑛}

𝑇_{𝐴}

for a matrix

𝐴 \in 𝐹^{𝑛 \times 𝑚}

(Proposition 2.3.17), and invertible matrices are square (Corollary 3.5.15). So

𝑚 = 𝑛

. The lecture runs this argument in the simplest case,

𝑉 = 𝐹^{𝑚}

, where no translation is needed.

Theorem 4.1.1 (Bases of

𝐹^{𝑚}

). Every basis of

𝐹^{𝑚}

has exactly

𝑚

vectors.

Proof (via the Third Fundamental Theorem).routine

Uses. Theorem 3.5.14 (Third Fundamental Theorem, completed), Definition 1.6.1 (Basis)

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Put the vectors of a basis

ℬ︀

𝐹^{𝑚}

into a matrix as its columns. What is its size?

Hint 2. Condition (III) of Theorem 3.5.14 is a statement about the columns of a matrix. What does the “moreover” part of that theorem conclude?

Sketch. If

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

is a basis of

𝐹^{𝑚}

, the

𝑚 \times 𝑛

matrix with columns

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

satisfies condition (III) of Theorem 3.5.14, so

𝑚 = 𝑛

by the “moreover” part.

Let $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ be a basis of $𝐹^{𝑚}$ , and let

𝐴 = (\begin{matrix} 𝐯_{1} & \dots & 𝐯_{𝑛} \end{matrix}) \in 𝐹^{𝑚 \times 𝑛}

be the matrix whose columns are $𝐯_{1}, \dots, 𝐯_{𝑛}$ . Its columns form a basis of $𝐹^{𝑚}$ , which is condition (III) of Theorem 3.5.14. By the “moreover” part of that theorem, $𝑚 = 𝑛$ . □

The proof is two lines because the work was done in Section 3.5. The “moreover” part of Theorem 3.5.14 comes from the inequality $rank 𝐴 \leq min (𝑚, 𝑛)$ , which holds because the pivots of $rref (𝐴)$ occupy distinct rows and distinct columns (Proposition 3.5.2). So the theorem is really a count of pivots. To prove the corresponding statement in an arbitrary vector space without first choosing coordinates, we need a count that happens inside $𝑉$ . That count is the exchange lemma.

4.1.2The exchange lemma

Intuition (Trading spanning vectors for independent ones). Let

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

be independent and let

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

span

𝑉

. Since the

𝐰_{𝑖}

span,

𝐮_{1}

is a linear combination of them, and since

𝐮_{1} \neq 𝟎

, some

𝐰_{𝑖}

appears with a nonzero coefficient. Solving for that

𝐰_{𝑖}

shows that it lies in the span of

𝐮_{1}

and the other

𝐰

’s, so we can trade it for

𝐮_{1}

and still have a spanning list of length

𝑛

. This is the exchange of Exercise 1.3.34 and Exercise 1.5.33. Now trade a second

𝐰

for

𝐮_{2}

, and so on. The independence of the

𝐮

’s guarantees that each trade removes a

𝐰

, and never one of the

𝐮

’s brought in earlier. If there were more

𝐮

’s than

𝐰

’s, we would run out of

𝐰

’s to trade.

Lemma 4.1.2 (Exchange lemma). Let $𝐮_{1}, \dots, 𝐮_{𝑚}$ be a linearly independent list in $𝑉$ , and let $𝐰_{1}, \dots, 𝐰_{𝑛}$ be a list that spans $𝑉$ . Then $𝑚 \leq 𝑛$ . More precisely, the $𝐰_{𝑖}$ can be renumbered so that

𝐮_{1}, \dots, 𝐮_{𝑚}, 𝐰_{𝑚 + 1}, \dots, 𝐰_{𝑛}

spans $𝑉$ .

In words: an independent list is never longer than a spanning list, and the independent list can replace an equal number of entries of the spanning list without losing the span. The result is often called the Steinitz exchange lemma. The first proof makes the trades of the intuition one at a time, and an induction keeps track of them.

Proof (by exchange).standard

Uses. Lemma 1.5.10 (Linear dependence lemma), Corollary 1.5.13 (Independence, one entry at a time), Corollary 1.5.17 (Sublists), Proposition 1.5.18 (Operations that preserve independence), Corollary 1.3.20 (Operations that preserve the span)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. Prove by induction on

𝑘 = 0, 1, \dots, 𝑚

𝑘 \leq 𝑛

, and after renumbering the

𝐰_{𝑖}

, the list

𝐮_{1},

\dots,

𝐮_{𝑘},

𝐰_{𝑘 + 1},

\dots,

𝐰_{𝑛}

spans

𝑉

Hint 2. In the inductive step, insert

𝐮_{𝑘 + 1}

right after

𝐮_{𝑘}

. Why is the longer list dependent, and what does Lemma 1.5.10 then let you delete?

Hint 3. The deleted entry is in the span of the entries before it. It cannot be one of

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

, which come first and form an independent list (Corollary 1.5.13). So it is a

𝐰

, and in particular some

𝐰

was still there.

Sketch. Induct on

𝑘

. Suppose

{ℬ︀}_{𝑘} =

𝐮_{1},

\dots,

𝐮_{𝑘},

𝐰_{𝑘 + 1},

\dots,

𝐰_{𝑛}

spans

𝑉

. Inserting

𝐮_{𝑘 + 1} \in span ({ℬ︀}_{𝑘})

after

𝐮_{𝑘}

gives a dependent list that still spans. By Lemma 1.5.10, some entry lies in the span of the entries before it, and deleting it keeps the span. It is not among the independent

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

at the front, so it is some

𝐰_{𝑖}

with

𝑖 > 𝑘

. Hence

𝑘 + 1 \leq 𝑛

, and after renumbering, deleting it gives

{ℬ︀}_{𝑘 + 1}

. At

𝑘 = 𝑚

we get

𝑚 \leq 𝑛

We prove by induction on $𝑘 \in {0, 1, \dots, 𝑚}$ the statement

$𝑃 (𝑘)$ : $𝑘 \leq 𝑛$ , and the $𝐰_{𝑖}$ can be renumbered so that ${ℬ︀}_{𝑘} =$ $𝐮_{1},$ $\dots,$ $𝐮_{𝑘},$ $𝐰_{𝑘 + 1},$ $\dots,$ $𝐰_{𝑛}$ spans $𝑉$ .

For $𝑘 = 𝑚$ this is the lemma.

Base case. $𝑃 (0)$ says that $0 \leq 𝑛$ and that $𝐰_{1}, \dots, 𝐰_{𝑛}$ spans $𝑉$ , which is the hypothesis.

Inductive step. Let $0 \leq 𝑘 < 𝑚$ and assume $𝑃 (𝑘)$ , with the $𝐰_{𝑖}$ numbered so that ${ℬ︀}_{𝑘}$ spans $𝑉$ . Let

ℒ︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}, 𝐮_{𝑘 + 1}, 𝐰_{𝑘 + 1}, \dots, 𝐰_{𝑛}

be ${ℬ︀}_{𝑘}$ with $𝐮_{𝑘 + 1}$ inserted after $𝐮_{𝑘}$ . The list $ℒ︀$ spans $𝑉$ , since it contains every entry of ${ℬ︀}_{𝑘}$ (Corollary 1.3.20). It is linearly dependent: $𝐮_{𝑘 + 1} \in$ $𝑉 =$ $span ({ℬ︀}_{𝑘})$ , so the reordering ${ℬ︀}_{𝑘}, 𝐮_{𝑘 + 1}$ of $ℒ︀$ is dependent by Corollary 1.5.13, and reordering does not affect independence (Proposition 1.5.18(a)).

By Lemma 1.5.10, some entry of $ℒ︀$ lies in the span of the entries before it, and deleting that entry does not change the span. The first $𝑘 + 1$ entries of $ℒ︀$ form the list $𝐮_{1}, \dots, 𝐮_{𝑘 + 1}$ , which is independent as a sublist of an independent list (Corollary 1.5.17). By Corollary 1.5.13, none of them lies in the span of the entries before it. So the entry in question is $𝐰_{𝑖}$ for some $𝑖$ with $𝑘 + 1 \leq 𝑖 \leq 𝑛$ . In particular $𝑘 + 1 \leq 𝑛$ . Renumber $𝐰_{𝑘 + 1}, \dots, 𝐰_{𝑛}$ so that this entry becomes $𝐰_{𝑘 + 1}$ . Deleting it from $ℒ︀$ leaves

{ℬ︀}_{𝑘 + 1} = 𝐮_{1}, \dots, 𝐮_{𝑘 + 1}, 𝐰_{𝑘 + 2}, \dots, 𝐰_{𝑛},

whose span is $span (ℒ︀) = 𝑉$ . This is $𝑃 (𝑘 + 1)$ . □

Each step of the induction removes a $𝐰$ that is still present, so the steps assign to each $𝐮$ a different $𝐰$ , and $𝑚 \leq 𝑛$ is the pigeonhole principle. The second proof replaces the trades by a single linear system. It shows that $𝑚 \leq 𝑛$ , but not the renumbering statement.

Proof (via a homogeneous system).standard

Uses. Definition 1.3.12 (Spanning list), Corollary 3.4.19 (More unknowns than equations), Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 2.3.11 (Entries of $𝐴 𝐱$ )

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Write each

𝐮_{𝑗}

as a linear combination of

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

, and collect the coefficients into a matrix

𝐴

. What is its size?

Hint 2. Suppose

𝑚 > 𝑛

. Then the system

𝐴 𝐱 = 𝟎

has more unknowns than equations. Turn a nonzero solution into a linear relation among the

𝐮_{𝑗}

Sketch. Write

𝐮_{𝑗} =

\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝐰_{𝑖}

and let

𝐴 =

(𝑎_{𝑖 𝑗}) \in

𝐹^{𝑛 \times 𝑚}

. If

𝑚 > 𝑛

, some

𝐱 \neq 𝟎

has

𝐴 𝐱 = 𝟎

(Corollary 3.4.19). Regrouping,

\sum_{𝑗} 𝑥_{𝑗} 𝐮_{𝑗} =

\sum_{𝑖} {(𝐴 𝐱)}_{𝑖} 𝐰_{𝑖} =

𝟎

, a nontrivial relation among the independent

𝐮_{𝑗}

Suppose, to the contrary, that $𝑚 > 𝑛$ . Since $𝐰_{1}, \dots, 𝐰_{𝑛}$ spans $𝑉$ , for each $𝑗$ there are scalars $𝑎_{1 𝑗}, \dots, 𝑎_{𝑛 𝑗}$ with

𝐮_{𝑗} = 𝑎_{1 𝑗} 𝐰_{1} + \dots + 𝑎_{𝑛 𝑗} 𝐰_{𝑛} .

Let $𝐴 =$ $(𝑎_{𝑖 𝑗}) \in$ $𝐹^{𝑛 \times 𝑚}$ . It has more columns than rows, so by Corollary 3.4.19(a) there is $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑚}) \neq$ $𝟎$ with $𝐴 𝐱 = 𝟎$ . Regrouping the double sum by repeated use of Lemma 1.3.9,

\sum_{𝑗 = 1}^{𝑚} 𝑥_{𝑗} 𝐮_{𝑗} = \sum_{𝑗 = 1}^{𝑚} 𝑥_{𝑗} \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝑗} 𝐰_{𝑖} = \sum_{𝑖 = 1}^{𝑛} (\sum_{𝑗 = 1}^{𝑚} 𝑎_{𝑖 𝑗} 𝑥_{𝑗}) 𝐰_{𝑖} = \sum_{𝑖 = 1}^{𝑛} {(𝐴 𝐱)}_{𝑖} 𝐰_{𝑖} = 𝟎,

where ${(𝐴 𝐱)}_{𝑖} =$ $\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑥_{𝑗}$ is the $𝑖$ -th entry of $𝐴 𝐱$ (Proposition 2.3.11). Since some $𝑥_{𝑗} \neq 0$ , this is a nontrivial linear relation of $𝐮_{1}, \dots, 𝐮_{𝑚}$ , contradicting their independence (Theorem 1.5.5). So $𝑚 \leq 𝑛$ . □

Example 4.1.3 (The exchange, step by step). In $ℝ^{3}$ , let $𝐮_{1} = (1, 1, 0)$ and $𝐮_{2} = (0, 1, 1)$ , which are independent since neither is a multiple of the other, and let $𝐰_{1},$ $𝐰_{2},$ $𝐰_{3} =$ $𝐞_{1},$ $𝐞_{2},$ $𝐞_{3}$ .

Step 1. Insert $𝐮_{1}$ at the front: $𝐮_{1}, 𝐞_{1}, 𝐞_{2}, 𝐞_{3}$ . The relation $𝐮_{1} - 𝐞_{1} - 𝐞_{2} = 𝟎$ shows that $𝐞_{2} \in span (𝐮_{1}, 𝐞_{1})$ , and $𝐞_{2}$ is the first entry with this property, since $𝐞_{1} \notin span (𝐮_{1})$ . Delete it: $𝐮_{1}, 𝐞_{1}, 𝐞_{3}$ spans $ℝ^{3}$ .

Step 2. Insert $𝐮_{2}$ : $𝐮_{1}, 𝐮_{2}, 𝐞_{1}, 𝐞_{3}$ . Now $𝐮_{2} = 𝐮_{1} - 𝐞_{1} + 𝐞_{3}$ , so $𝐞_{3} \in$ $span (𝐮_{1}, 𝐮_{2}, 𝐞_{1})$ . Here $𝐞_{3}$ is the only entry in the span of the earlier ones: $𝐮_{1}$ and $𝐮_{2}$ cannot be, and $𝐞_{1} =$ $(1, 0, 0) \notin$ $span (𝐮_{1}, 𝐮_{2})$ , whose vectors $𝑎 (1, 1, 0) +$ $𝑏 (0, 1, 1) =$ $(𝑎, 𝑎 + 𝑏, 𝑏)$ have middle coordinate equal to the sum of the others. Delete $𝐞_{3}$ : the list $𝐮_{1}, 𝐮_{2}, 𝐞_{1}$ spans $ℝ^{3}$ .

Two independent vectors pushed out two of the three standard basis vectors, and the one that survived, $𝐞_{1}$ , was enough to complete $𝐮_{1}, 𝐮_{2}$ to a spanning list of $ℝ^{3}$ . (So would $𝐞_{2}$ or $𝐞_{3}$ have been; the exchange simply found one.)

With the lemma, the theorem on $𝐹^{𝑚}$ has a proof that uses nothing but the standard basis.

Proof of Theorem 4.1.1 (via the exchange lemma).routine

Uses. Lemma 4.1.2 (Exchange lemma), Proposition 1.6.7 (Standard bases), Proposition 1.6.2 (Bases are independent spanning lists)

Hint 1. Compare a basis

ℬ︀

𝐹^{𝑚}

of length

𝑛

with the standard basis

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

. Both lists are independent and both span.

Hint 2. Apply Lemma 4.1.2 twice, with the roles of the two lists swapped.

Sketch.

ℬ︀

is independent and

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

spans

𝐹^{𝑚}

, so

𝑛 \leq 𝑚

. The standard basis is independent and

ℬ︀

spans, so

𝑚 \leq 𝑛

Let

ℬ︀

be a basis of

𝐹^{𝑚}

of length

𝑛

. The standard basis

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

is a basis of

𝐹^{𝑚}

(Proposition 1.6.7). By Proposition 1.6.2 both lists are independent and both span

𝐹^{𝑚}

. Applying Lemma 4.1.2 to the independent list

ℬ︀

and the spanning list

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

gives

𝑛 \leq 𝑚

. Applying it to the independent list

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

and the spanning list

ℬ︀

gives

𝑚 \leq 𝑛

. Hence

𝑛 = 𝑚

. □

Intuition (Matrix machinery versus pure exchange). Both proofs of Theorem 4.1.1 are counting arguments, and they count different things. The first counts pivots: $rank 𝐴 \leq min (𝑚, 𝑛)$ because each pivot of $rref (𝐴)$ has a row and a column to itself. Behind it stands all of Gauss–Jordan elimination, and in return the proof is a computation: row reduce, and the pivots show which columns are independent and whether they span. The second counts trades: each $𝐮$ pushes out a $𝐰$ that has not been pushed out before. It never mentions matrices or coordinates, and the only tool it uses is the linear dependence lemma. That is why it works verbatim in ${𝐹 [𝑥]}_{\leq 𝑛}$ , in spaces of functions, and in subspaces cut out by equations, where there is no matrix to reduce until a basis has been chosen. The price is that it is not a computation. It asserts that some $𝐰$ can be removed, and finding one means testing membership in spans, which in practice is again a row reduction.

The second proof of the exchange lemma sits between the two. It uses coordinates, but only with respect to a spanning list, which need not be a basis, and the single fact about linear systems that it needs is that a homogeneous system with more unknowns than equations has a nonzero solution.

4.1.3Dimension

The theorem on $𝐹^{𝑚}$ extends to every finite-dimensional space, again in two ways. The lecture transports the question to $𝐹^{𝑚}$ by coordinates. The exchange lemma answers it in $𝑉$ directly.

Theorem 4.1.4 (All bases have the same length). Let

𝑉

be finite-dimensional. Any two bases of

𝑉

have the same length.

Proof (via coordinates).routine

Uses. Proposition 1.6.20 (Coordinates translate questions about $𝑉$ into $𝐹^{𝑛}$ ), Theorem 4.1.1 (Bases of $𝐹^{𝑚}$ )

Hint 1. Take bases

ℬ︀

of length

𝑚

and

𝒞︀

of length

𝑛

. Use

ℬ︀

-coordinates to move the list

𝒞︀

into

𝐹^{𝑚}

Hint 2. By Proposition 1.6.20(c), the coordinate vectors of a basis of

𝑉

form a basis of

𝐹^{𝑚}

. How long is every basis of

𝐹^{𝑚}

Sketch. If

ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑚}

and

𝒞︀ = 𝐰_{1}, \dots, 𝐰_{𝑛}

are bases, then

{[𝐰_{1}]}_{ℬ︀},

\dots,

{[𝐰_{𝑛}]}_{ℬ︀}

is a basis of

𝐹^{𝑚}

by Proposition 1.6.20(c), so

𝑛 = 𝑚

by Theorem 4.1.1.

Let

ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑚}

and

𝒞︀ = 𝐰_{1}, \dots, 𝐰_{𝑛}

be bases of

𝑉

. Since

𝒞︀

is a basis of

𝑉

, Proposition 1.6.20(c), applied with the basis

ℬ︀

, shows that

{[𝐰_{1}]}_{ℬ︀},

\dots,

{[𝐰_{𝑛}]}_{ℬ︀}

is a basis of

𝐹^{𝑚}

. It has

𝑛

vectors, so

𝑛 = 𝑚

by Theorem 4.1.1. □

Proof (via the exchange lemma).routine

Uses. Lemma 4.1.2 (Exchange lemma), Proposition 1.6.2 (Bases are independent spanning lists)

Hint 1. A basis is both independent and spanning.

Hint 2. Apply Lemma 4.1.2 with

ℬ︀

as the independent list and

𝒞︀

as the spanning list, and then the other way around.

Sketch.

ℬ︀

is independent and

𝒞︀

spans, so

𝑚 \leq 𝑛

; symmetrically

𝑛 \leq 𝑚

Let

ℬ︀

and

𝒞︀

be bases of

𝑉

of lengths

𝑚

and

𝑛

. By Proposition 1.6.2,

ℬ︀

is independent and

𝒞︀

spans

𝑉

, so

𝑚 \leq 𝑛

by Lemma 4.1.2. Exchanging the roles of

ℬ︀

and

𝒞︀

gives

𝑛 \leq 𝑚

. □

The first proof reduces the question about $𝑉$ to the same question about $𝐹^{𝑚}$ , and the dictionary of Proposition 1.6.20 guarantees that nothing is lost in translation. The second proof needs no dictionary. Both are worth knowing: transporting a problem to $𝐹^{𝑛}$ by coordinates is how most computations in abstract spaces are done, and arguing inside $𝑉$ is how most proofs about them are written.

By Corollary 1.6.24 a finite-dimensional space has a basis, and by Theorem 4.1.4 all of its bases have the same length. So the following definition makes sense.

Definition 4.1.5 (Dimension). Let

𝑉

be a finite-dimensional vector space. The dimension of

𝑉

, written

dim 𝑉

, is the length of any basis of

𝑉

. If

dim 𝑉 = 𝑛

, we say that

𝑉

is $𝑛$ -dimensional. If

𝑉

is infinite-dimensional, we write

dim 𝑉 = \infty

The symbol $\infty$ is shorthand and not a number we compute with. It lets us write statements such as “ $dim 𝑉 < \infty$ ” for “ $𝑉$ is finite-dimensional”. Since ${𝟎}$ has the basis $()$ and every other space has a nonzero vector, which no basis of length $0$ can represent, $dim 𝑉 = 0$ exactly when $𝑉 = {𝟎}$ .

Remark 4.1.6 (The field is part of the data). Whether a list is a basis depends on which scalars are allowed (Example 1.6.5), so the dimension depends on the field. When the field matters we write

{dim}_{𝐹} 𝑉

. For example,

{dim}_{ℂ} ℂ = 1

, with basis

1

, while

{dim}_{ℝ} ℂ = 2

, with basis

1, 𝑖

. The set and the addition are the same; only the scalars differ.

Example 4.1.7 (Dimensions of the standard spaces).

(a)By Proposition 1.6.7, $dim 𝐹^{𝑛} = 𝑛$ , $dim 𝐹^{𝑚 \times 𝑛} = 𝑚 𝑛$ , and $dim {𝐹 [𝑥]}_{\leq 𝑛} = 𝑛 + 1$ .
(b)The plane $𝑃 =$ ${(𝑥, 𝑦, 𝑧) \in ℝ^{3} | 𝑥 + 𝑦 + 𝑧 = 0}$ has the basis $(1, 0, - 1), (0, 1, - 1)$ (Example 1.6.3(b)), so $dim 𝑃 = 2$ .
(c)If $𝑉$ is a vector space over $ℂ$ with ${dim}_{ℂ} 𝑉 = 𝑛$ and basis $𝐯_{1}, \dots, 𝐯_{𝑛}$ , then $𝐯_{1},$ $𝑖 𝐯_{1},$ $\dots,$ $𝐯_{𝑛},$ $𝑖 𝐯_{𝑛}$ is a basis of $𝑉$ over $ℝ$ . It is independent over $ℝ$ by Exercise 1.5.37, and it spans $𝑉$ over $ℝ$ , since every $𝐯 \in 𝑉$ is $\sum_{𝑗} (𝑎_{𝑗} + 𝑏_{𝑗} 𝑖) 𝐯_{𝑗} =$ $\sum_{𝑗} (𝑎_{𝑗} 𝐯_{𝑗} + 𝑏_{𝑗} (𝑖 𝐯_{𝑗}))$ with $𝑎_{𝑗}, 𝑏_{𝑗} \in ℝ$ . So ${dim}_{ℝ} 𝑉 = 2 𝑛$ ; for instance ${dim}_{ℝ} ℂ^{𝑛} = 2 𝑛$ .
(d) $𝐹 [𝑥]$ is infinite-dimensional (Proposition 1.6.25), and so is $ℝ$ over $ℚ$ (Exercise 1.3.45). In both cases $dim = \infty$ . For $𝐹 [𝑥]$ the set ${1, 𝑥, 𝑥^{2}, \dots}$ is a basis in the infinite sense of Aside (Bases of infinite-dimensional spaces). For $ℝ$ over $ℚ$ every such basis is uncountable, and none can be described explicitly; their existence rests on the axiom of choice (Section 15.1).
(e)Linear maps $𝐹^{𝑛} \to 𝐹^{𝑚}$ correspond to matrices in $𝐹^{𝑚 \times 𝑛}$ (Theorem 2.3.20), and the correspondence respects sums and scalar multiples (Proposition 2.4.12). We will see in Section 4.5 that this makes $dim L (𝑉, 𝑊) =$ $(dim 𝑉) (dim 𝑊)$ for all finite-dimensional $𝑉$ and $𝑊$ .

Non-example 4.1.8 (What the dimension does not count).

(a)Every vector of the plane $𝑃$ in (b) above has three coordinates, but $dim 𝑃 = 2$ . The dimension counts the vectors in a basis of $𝑃$ , not the coordinates used to write down its elements.
(b)The list $(1, 0), (0, 1), (1, 1)$ spans $ℝ^{2}$ but $dim ℝ^{2} = 2$ . A spanning list can be longer than the dimension, and Corollary 4.1.11 below shows that it can never be shorter.
(c) $ℂ$ and $ℝ^{2}$ can be identified as sets with the same addition (Example 1.6.5), yet ${dim}_{ℂ} ℂ = 1$ and ${dim}_{ℝ} ℝ^{2} = 2$ . Without the field, “the dimension of $ℂ$ ” is ambiguous.

Exercise 4.1.9.routine Find a basis and the dimension of

𝑈 =

{(𝑎, 𝑏, 𝑎 + 𝑏, 𝑎 - 𝑏) | 𝑎, 𝑏 \in 𝐹} \subseteq

𝐹^{4}

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Theorem 1.5.5 (Independence is decided at zero), Definition 4.1.5 (Dimension)

Hint 1. Split

(𝑎, 𝑏, 𝑎 + 𝑏, 𝑎 - 𝑏)

into a part with

𝑎

and a part with

𝑏

Hint 2. Check that the two vectors you get are independent by looking at their first two coordinates.

Sketch.

(𝑎, 𝑏, 𝑎 + 𝑏, 𝑎 - 𝑏) =

𝑎 (1, 0, 1, 1) +

𝑏 (0, 1, 1, - 1)

, so these two vectors span

𝑈

. A relation

𝑎 (1, 0, 1, 1) +

𝑏 (0, 1, 1, - 1) =

𝟎

has first two coordinates

𝑎

and

𝑏

, so it is trivial. Hence

dim 𝑈 = 2

For all $𝑎, 𝑏 \in 𝐹$ ,

(𝑎, 𝑏, 𝑎 + 𝑏, 𝑎 - 𝑏) = 𝑎 (1, 0, 1, 1) + 𝑏 (0, 1, 1, - 1),

so $(1, 0, 1, 1),$ $(0, 1, 1, - 1)$ lies in $𝑈$ and spans it. If $𝑎 (1, 0, 1, 1) +$ $𝑏 (0, 1, 1, - 1) =$ $𝟎$ , then the first two coordinates give $𝑎 = 0$ and $𝑏 = 0$ , so the list is independent (Theorem 1.5.5). It is a basis of $𝑈$ by Proposition 1.6.2, and $dim 𝑈 = 2$ . This holds over every field, $𝔽_{2}$ included, where $𝑎 - 𝑏 = 𝑎 + 𝑏$ .

4.1.4Lists of the right length

Once $dim 𝑉$ is known, the length of a list already says a good deal about it. The lecture proves the next theorem with coordinates and the First and Third Fundamental Theorems. The exchange lemma gives a second proof.

Theorem 4.1.10 (Independent lists are short). Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ , and let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a linearly independent list in $𝑉$ .

(a) $𝑘 \leq 𝑛$ .
(b)If $𝑘 = 𝑛$ , then $ℒ︀$ is a basis of $𝑉$ .

Proof (via coordinates and the Fundamental Theorems).routine

Uses. Proposition 1.6.20 (Coordinates translate questions about $𝑉$ into $𝐹^{𝑛}$ ), Corollary 3.5.16 (Lists of vectors in $𝐹^{𝑚}$ ), Definition 4.1.5 (Dimension)

Hint 1. Fix a basis

ℬ︀

𝑉

, of length

𝑛

, and pass to the coordinate vectors

{[𝐯_{1}]}_{ℬ︀},

\dots,

{[𝐯_{𝑘}]}_{ℬ︀} \in

𝐹^{𝑛}

. Are they independent?

Hint 2. Corollary 3.5.16 describes independent and spanning lists in

𝐹^{𝑛}

. Apply (a) of it, and for

𝑘 = 𝑛

apply (c), then translate back with Proposition 1.6.20.

Sketch. With a basis

ℬ︀

of length

𝑛

, the coordinate vectors

{[𝐯_{𝑖}]}_{ℬ︀}

form an independent list of length

𝑘

𝐹^{𝑛}

(Proposition 1.6.20(a)), so

𝑘 \leq 𝑛

by Corollary 3.5.16(a). If

𝑘 = 𝑛

, they form a basis of

𝐹^{𝑛}

by Corollary 3.5.16(c), so

ℒ︀

is a basis of

𝑉

by Proposition 1.6.20(c).

Fix a basis $ℬ︀$ of $𝑉$ ; it has length $𝑛$ (Definition 4.1.5). By Proposition 1.6.20(a), the list ${[𝐯_{1}]}_{ℬ︀},$ $\dots,$ ${[𝐯_{𝑘}]}_{ℬ︀}$ is linearly independent in $𝐹^{𝑛}$ .

(a) By Corollary 3.5.16(a), applied to the $𝑛 \times 𝑘$ matrix with these columns, $𝑘 \leq 𝑛$ .

(b) If $𝑘 = 𝑛$ , then by Corollary 3.5.16(c) the independent list ${[𝐯_{1}]}_{ℬ︀},$ $\dots,$ ${[𝐯_{𝑛}]}_{ℬ︀}$ is a basis of $𝐹^{𝑛}$ . By Proposition 1.6.20(c), $ℒ︀$ is a basis of $𝑉$ . □

Proof (via the exchange lemma).routine

Uses. Lemma 4.1.2 (Exchange lemma), Proposition 1.5.14 (Appending a vector), Proposition 1.6.2 (Bases are independent spanning lists), Definition 4.1.5 (Dimension)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. For (a), a basis of

𝑉

is a spanning list of length

𝑛

Hint 2. For (b), suppose

ℒ︀

does not span

𝑉

. Append a vector outside its span and count.

Sketch. (a) A basis of

𝑉

spans and has length

𝑛

, so

𝑘 \leq 𝑛

by Lemma 4.1.2. (b) If an independent

ℒ︀

of length

𝑛

did not span, appending

𝐰 \notin span (ℒ︀)

would give an independent list of length

𝑛 + 1

(Proposition 1.5.14), contradicting (a).

(a) A basis of $𝑉$ spans $𝑉$ and has length $𝑛$ , so $𝑘 \leq 𝑛$ by Lemma 4.1.2.

(b) Suppose $𝑘 = 𝑛$ . If $ℒ︀$ did not span $𝑉$ , there would be some $𝐰 \in 𝑉$ with $𝐰 \notin span (ℒ︀)$ , and $ℒ︀, 𝐰$ would be an independent list of length $𝑛 + 1$ by Proposition 1.5.14, contradicting (a). So $ℒ︀$ spans $𝑉$ , and being independent, it is a basis (Proposition 1.6.2). □

The contrapositive of (a) is used constantly: in an $𝑛$ -dimensional space, every list of more than $𝑛$ vectors is linearly dependent. For instance, any four vectors in $ℝ^{3}$ are dependent, which is what the span explorer of Section 1.5.3 showed for three vectors in $ℝ^{2}$ . Spanning lists satisfy the mirror-image statements.

Corollary 4.1.11 (Spanning lists are long). Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ , and let $𝒮︀$ be a list of length $𝑙$ that spans $𝑉$ .

(a) $𝑙 \geq 𝑛$ .
(b)If $𝑙 = 𝑛$ , then $𝒮︀$ is a basis of $𝑉$ .

Proof.routine

Uses. Theorem 1.6.10 (Every spanning list contains a basis), Theorem 4.1.4 (All bases have the same length), Definition 4.1.5 (Dimension)

Hint 1. Every spanning list contains a basis as a sublist (Theorem 1.6.10). How long is that basis?

Hint 2. For (b), a sublist with as many entries as the whole list is the whole list.

Sketch.

𝒮︀

has a sublist that is a basis, of length

𝑛

(Theorem 4.1.4), so

𝑛 \leq 𝑙

. If

𝑙 = 𝑛

, that sublist has all

𝑙

entries, so it is

𝒮︀

By Theorem 1.6.10, some sublist ${𝒮︀}^{'}$ of $𝒮︀$ is a basis of $𝑉$ , and by Theorem 4.1.4 it has length $𝑛$ .

(a) A sublist is obtained by deleting entries, so $𝑛 = | {𝒮︀}^{'} | \leq 𝑙$ .

(b) If $𝑙 = 𝑛$ , then ${𝒮︀}^{'}$ is obtained from $𝒮︀$ by deleting $𝑙 - 𝑛 = 0$ entries, so ${𝒮︀}^{'} = 𝒮︀$ , and $𝒮︀$ is a basis. □

Part (a) also follows from Lemma 4.1.2, applied to a basis of $𝑉$ and $𝒮︀$ . Together, the two results say that for a list of length exactly $dim 𝑉$ , being independent, spanning, and being a basis are the same condition. So to check that a list of the right length is a basis, check whichever of the two properties is easier, and the other comes for free. In $𝐹^{𝑚}$ this is Corollary 3.5.16(c), now available in every finite-dimensional space.

Example 4.1.12 (Two bases for the price of one property).

(a)Let $𝑐 \in 𝐹$ and $𝑛 \geq 0$ . The polynomials $1,$ $𝑥 -$ $𝑐,$ ${(𝑥 - 𝑐)}^{2},$ $\dots,$ ${(𝑥 - 𝑐)}^{𝑛}$ are nonzero with distinct degrees $0, 1, \dots, 𝑛$ , so they are independent (Proposition 1.5.24). There are $𝑛 + 1 = dim {𝐹 [𝑥]}_{\leq 𝑛}$ of them, so they form a basis of ${𝐹 [𝑥]}_{\leq 𝑛}$ by Theorem 4.1.10(b). We never had to show that every polynomial of degree at most $𝑛$ is a combination of powers of $𝑥 - 𝑐$ . The coordinates of $𝑝$ in this basis are the coefficients of its expansion in powers of $𝑥 - 𝑐$ , which over $ℝ$ are the Taylor coefficients at $𝑐$ ; Exercise 1.6.18 computed them for $𝑛 = 2$ and $𝑐 = 1$ .
(b)In $ℂ^{2 \times 2}$ , consider
$𝐼_{2} = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}), 𝑋 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), 𝑌 = (\begin{matrix} 0 & - 𝑖 \\ 𝑖 & 0 \end{matrix}), 𝑍 = (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}) .$
If $𝑎 𝐼_{2} +$ $𝑏 𝑋 +$ $𝑐 𝑌 +$ $𝑑 𝑍 =$ $0$ , then
$(\begin{matrix} 𝑎 + 𝑑 & 𝑏 - 𝑖 𝑐 \\ 𝑏 + 𝑖 𝑐 & 𝑎 - 𝑑 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) .$
Adding and subtracting the diagonal entries gives $2 𝑎 = 2 𝑑 = 0$ , and the off-diagonal entries give $2 𝑏 = 0$ and $2 𝑖 𝑐 = 0$ . So $𝑎 = 𝑏 = 𝑐 = 𝑑 = 0$ , the list is independent, and since $dim ℂ^{2 \times 2} = 4$ it is a basis. (These are the Pauli matrices of quantum mechanics.)

Intuition (Halving the work, and where the halving comes from). For a list of length

dim 𝑉

, independence and spanning are equivalent. In

𝐹^{𝑛}

this was the square case of the Fundamental Theorems: for a square matrix, “pivot in every column” and “pivot in every row” both say that there are

𝑛

pivots. In general it is the exchange lemma: an independent list that did not span could be lengthened, and a spanning list that was dependent could be shortened, and either would produce a list whose length is on the wrong side of

dim 𝑉

. The count only works when the length is exactly right. A list of length less than

dim 𝑉

is never spanning, one of length more is never independent, and these are the shape constraints of Corollary 3.5.16(a) and (b) in disguise.

Dimension also gives a convenient test for infinite dimension. It is the test promised after Proposition 1.6.25.

Corollary 4.1.13 (Detecting infinite dimension). A vector space

𝑉

is infinite-dimensional if and only if for every

𝑘 \geq 0

it contains a linearly independent list of length

𝑘

Proof.routine

Uses. Theorem 4.1.10 (Independent lists are short), Proposition 1.5.14 (Appending a vector), Definition 1.6.23 (Finite-dimensional), Proposition 1.5.15 (Short lists, zeros, and repeats)

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. For (

\Leftarrow

), if

𝑉

were finite-dimensional with

dim 𝑉 = 𝑛

, which length of independent list would be impossible?

Hint 2. For (

\Rightarrow

), build the lists by induction on

𝑘

. If

𝑉

is infinite-dimensional, can an independent list span it?

Sketch. (

\Leftarrow

) If

dim 𝑉 = 𝑛

, an independent list of length

𝑛 + 1

contradicts Theorem 4.1.10(a). (

\Rightarrow

) Induct on

𝑘

, starting from

()

. An independent list

ℒ︀

of length

𝑘

does not span

𝑉

, since no list does, so appending some

𝐰 \notin span (ℒ︀)

gives an independent list of length

𝑘 + 1

(Proposition 1.5.14).

( $\Leftarrow$ ) We prove the contrapositive. If $𝑉$ is finite-dimensional, say $dim 𝑉 = 𝑛$ , then by Theorem 4.1.10(a) there is no independent list of length $𝑛 + 1$ in $𝑉$ .

( $\Rightarrow$ ) Suppose $𝑉$ is infinite-dimensional. We show by induction on $𝑘$ that $𝑉$ contains an independent list of length $𝑘$ . For $𝑘 = 0$ take $()$ (Proposition 1.5.15(a)). If $ℒ︀$ is independent of length $𝑘$ , then $ℒ︀$ does not span $𝑉$ , because no list spans $𝑉$ (Definition 1.6.23). So there is $𝐰 \in 𝑉$ with $𝐰 \notin span (ℒ︀)$ , and $ℒ︀, 𝐰$ is independent of length $𝑘 + 1$ by Proposition 1.5.14. □

Example 4.1.14 (Function spaces are infinite-dimensional). Let

𝐼 \subseteq ℝ

be an infinite set, for instance

ℝ

[0, 1]

. For each

𝑘

, the functions

1, 𝑡, 𝑡^{2}, \dots, 𝑡^{𝑘}

𝐼

are linearly independent in

ℝ^{𝐼}

: if

𝑎_{0} +

𝑎_{1} 𝑡 +

\dots +

𝑎_{𝑘} 𝑡^{𝑘} =

0

for every

𝑡 \in 𝐼

, then the polynomial

𝑎_{0} +

𝑎_{1} 𝑥 +

\dots +

𝑎_{𝑘} 𝑥^{𝑘}

has infinitely many roots, so it is the zero polynomial (Proposition 7.1.22), and all

𝑎_{𝑖} = 0

. By Corollary 4.1.13,

ℝ^{𝐼}

is infinite-dimensional. These functions are continuous, so the subspace

𝐶 [0, 1]

ℝ^{[0, 1]}

is infinite-dimensional as well.

Exercise 4.1.15.routine Show that

1 +

𝑥,

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

𝑥^{2} +

𝑥^{3},

𝑥^{3}

is a basis of

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

for every field

𝐹

Solution.

Uses. Theorem 4.1.10 (Independent lists are short), Example 4.1.7 (Dimensions of the standard spaces), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. The list has

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

entries, so it suffices to check independence.

Hint 2. The degrees are

1, 2, 3, 3

, so Proposition 1.5.24 does not apply directly. Write out a relation and compare coefficients, starting from the constant and

𝑥

coefficients.

Sketch. Length

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

, so independence suffices. In

𝑎 (1 + 𝑥) +

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

𝑐 (𝑥^{2} + 𝑥^{3}) +

𝑑 𝑥^{3} =

0

, the constant term gives

𝑎 + 𝑏 = 0

, the

𝑥

term

𝑎 + 2 𝑏 = 0

, so

𝑏 = 0 = 𝑎

; then

𝑥^{2}

gives

𝑐 = 0

and

𝑥^{3}

gives

𝑑 = 0

Since $dim {𝐹 [𝑥]}_{\leq 3} = 4$ (Example 4.1.7), by Theorem 4.1.10(b) it suffices to show that the four polynomials are independent. Suppose

𝑎 (1 + 𝑥) + 𝑏 (1 + 2 𝑥 + 𝑥^{2}) + 𝑐 (𝑥^{2} + 𝑥^{3}) + 𝑑 𝑥^{3} = 0 .

Comparing coefficients of $1$ , $𝑥$ , $𝑥^{2}$ , and $𝑥^{3}$ gives

𝑎 + 𝑏 = 0, 𝑎 + 2 𝑏 = 0, 𝑏 + 𝑐 = 0, 𝑐 + 𝑑 = 0 .

Subtracting the first equation from the second gives $𝑏 = 0$ , and then $𝑎 = 0$ , $𝑐 = 0$ , and $𝑑 = 0$ . So the only relation is trivial (Theorem 1.5.5), and the list is a basis. Every step was valid over every field.

4.1.5Extending to a basis

A spanning list can be thinned to a basis (Theorem 1.6.10). Remark 1.6.26 described the opposite process: grow an independent list by appending vectors outside its span. It warned that growing need not stop, as in $𝐹 [𝑥]$ . In a finite-dimensional space it does stop, because Theorem 4.1.10 caps the length of an independent list. This is the lecture’s corollary, and the homework step of appending one vector (Proposition 1.5.14) is what drives it. We also record which vectors can be appended.

Theorem 4.1.16 (Extending to a basis). Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ , and let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ be a linearly independent list in $𝑉$ . Then $ℒ︀$ extends to a basis of $𝑉$ : there are vectors $𝐰_{1}, \dots, 𝐰_{𝑛 - 𝑘} \in 𝑉$ such that

𝐯_{1}, \dots, 𝐯_{𝑘}, 𝐰_{1}, \dots, 𝐰_{𝑛 - 𝑘}

is a basis of $𝑉$ . Moreover, if $𝒮︀$ is any list that spans $𝑉$ , the $𝐰_{𝑗}$ can be chosen among the entries of $𝒮︀$ .

Proof.standard

Uses. Theorem 4.1.10 (Independent lists are short), Proposition 1.5.14 (Appending a vector), Proposition 1.4.14 (The span is the smallest subspace containing a list), Theorem 4.1.4 (All bases have the same length), Definition 4.1.5 (Dimension)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. By Theorem 4.1.10,

𝑘 \leq 𝑛

, and if

𝑘 = 𝑛

there is nothing to do. Induct on

𝑛 - 𝑘

Hint 2. If

𝑘 < 𝑛

, then

ℒ︀

does not span

𝑉

. Why must some entry of

𝒮︀

lie outside

span (ℒ︀)

Hint 3. Append that entry. The new list is independent (Proposition 1.5.14) and one entry longer, so the inductive hypothesis applies to it.

Sketch. By Theorem 4.1.10,

𝑘 \leq 𝑛

; induct on

𝑑 = 𝑛 - 𝑘

. If

𝑑 = 0

ℒ︀

is already a basis. If

𝑑 > 0

ℒ︀

is not a basis (wrong length), so it does not span. If every entry of

𝒮︀

were in

span (ℒ︀)

, then

𝑉 =

span (𝒮︀) \subseteq

span (ℒ︀)

; so some entry

𝐬

𝒮︀

is not. Then

ℒ︀, 𝐬

is independent of length

𝑘 + 1

, and the inductive hypothesis extends it by entries of

𝒮︀

Fix a spanning list $𝒮︀$ of $𝑉$ ; one exists because $𝑉$ is finite-dimensional. By Theorem 4.1.10(a), every independent list in $𝑉$ has length at most $𝑛$ . We prove by induction on $𝑑 \geq 0$ that every independent list of length $𝑛 - 𝑑$ extends to a basis of $𝑉$ by appending $𝑑$ entries of $𝒮︀$ . Taking $𝒮︀$ to be any spanning list proves the theorem, including the “moreover”.

Base case. If $𝑑 = 0$ , then $ℒ︀$ is independent of length $𝑛$ , so it is a basis by Theorem 4.1.10(b), and we append nothing.

Inductive step. Let $𝑑 \geq 1$ , assume the claim for $𝑑 - 1$ , and let $ℒ︀$ be independent of length $𝑘 = 𝑛 - 𝑑 < 𝑛$ . Then $ℒ︀$ is not a basis of $𝑉$ , since every basis has length $𝑛$ (Theorem 4.1.4), so $ℒ︀$ does not span $𝑉$ . If every entry of $𝒮︀$ were in $span (ℒ︀)$ , then, since $span (ℒ︀)$ is a subspace, $𝑉 =$ $span (𝒮︀) \subseteq$ $span (ℒ︀)$ by Proposition 1.4.14(b), which is false. So some entry $𝐬$ of $𝒮︀$ lies outside $span (ℒ︀)$ . By Proposition 1.5.14, $ℒ︀, 𝐬$ is independent, of length $𝑘 + 1 = 𝑛 - (𝑑 - 1)$ . By the inductive hypothesis, it extends to a basis of $𝑉$ by appending $𝑑 - 1$ entries of $𝒮︀$ . Together with $𝐬$ , these are $𝑑$ entries of $𝒮︀$ appended to $ℒ︀$ , as desired. □

The lecture remarks that its argument “may be formalized as an induction on $𝑑 - 𝑘$ ”, where its $𝑑$ is the dimension; our $𝑑 = 𝑛 - 𝑘$ is that quantity. Unwound, the proof says: test the entries of $𝒮︀$ one at a time and append each one that is not in the span of the list built so far. The list stays independent, and the process stops because its length cannot exceed $𝑛$ . Finite dimension enters exactly there, in the cap on the length. In $𝐹 [𝑥]$ there is no spanning list to draw from, and appending vectors outside the span can go on forever (Remark 1.6.26). In infinite dimensions, an extension to a basis in the sense of Aside (Bases of infinite-dimensional spaces) needs Zorn’s lemma (Section 15.1).

Unwound in this way, the procedure is the sifting of Section 1.6.3 applied to the list $ℒ︀, 𝒮︀$ . Since $ℒ︀$ is independent, no entry of $ℒ︀$ lies in the span of the entries before it (Corollary 1.5.13), so sifting keeps all of $ℒ︀$ , and it keeps exactly the entries of $𝒮︀$ not already accounted for. In $𝐹^{𝑛}$ , with $𝒮︀ = 𝐞_{1}, \dots, 𝐞_{𝑛}$ , sifting is row reduction: by Corollary 3.3.19, the pivot columns of a matrix are exactly the columns that are not combinations of the columns before them.

Example 4.1.17 (Extending by row reduction). Extend $𝐯_{1} = (1, 1, 0, 0)$ and $𝐯_{2} = (1, 1, 1, 1)$ to a basis of $ℚ^{4}$ . Row reduce the matrix with columns $𝐯_{1},$ $𝐯_{2},$ $𝐞_{1},$ $𝐞_{2},$ $𝐞_{3},$ $𝐞_{4}$ :

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

The pivot columns are $1, 2, 3, 5$ . So $𝐯_{1}, 𝐯_{2}, 𝐞_{1}, 𝐞_{3}$ is a basis of $ℚ^{4}$ . The free columns explain the rejections: column $4$ of the reduced matrix says $𝐞_{2} = 𝐯_{1} - 𝐞_{1}$ , and column $6$ says $𝐞_{4} = - 𝐯_{1} + 𝐯_{2} - 𝐞_{3}$ (Corollary 3.3.19(b)).

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

The reduction of Example 4.1.17. The first two columns are

𝐯_{1}, 𝐯_{2}

and the last four are

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

. The pivot columns are the columns that survive sifting. Use “Edit” to put your own independent vectors in the first columns, or switch to

𝔽_{𝑝}

; as long as those vectors are independent over the chosen field, they always end up as pivot columns.

Extension is most useful when the independent list is a basis of a subspace. Then the extended basis is adapted to the subspace: its first vectors describe the subspace, and the remaining ones describe “the rest” of $𝑉$ , on which we are free to do as we like.

Technique 4.1.18 (Extend a basis of a subspace). To study a subspace $𝑈$ of a finite-dimensional space $𝑉$ , choose a basis $𝐮_{1}, \dots, 𝐮_{𝑘}$ of $𝑈$ and extend it to a basis $𝐮_{1},$ $\dots,$ $𝐮_{𝑘},$ $𝐰_{1},$ $\dots,$ $𝐰_{𝑟}$ of $𝑉$ (Theorem 4.1.16). The new vectors are independent of $𝑈$ in a strong sense: a combination of them lies in $𝑈$ only if it is $𝟎$ . Since a linear map may be prescribed freely on a basis (Theorem 2.2.1), the extension lets us define maps that do one thing on $𝑈$ and anything we like on the $𝐰_{𝑗}$ . Since the extended list is a basis, it also lets us count: $dim 𝑉 - dim 𝑈$ is the number $𝑟$ of new vectors.

Reach for it when you need a linear map with prescribed behavior on a subspace, when you need to compare a subspace with the whole space, or when you want coordinates in which a subspace looks like the span of the first few standard basis vectors. The canonical example is Proposition 4.1.19. Later the same move proves rank–nullity (Section 4.2), produces complements and the dimension formula for sums (Section 4.4), and starts the proof of triangularization (Section 7.5).

Used in 15 places and 5 practice exercises

Proposition 4.1.19, Theorem 4.2.11, Proposition 4.2.26, Proposition 4.4.16, Proposition 4.4.18, Theorem 4.4.19, Exercise 4.4.38, Exercise 4.4.42, Exercise 4.4.50, Corollary 4.5.22, Theorem 4.6.27, Problem 4.1, Problem 4.13, Problem 7.11, Proposition 8.4.19; 5 practice exercises.

Proposition 4.1.19 (Extending linear maps and separating vectors). Let $𝑉$ be finite-dimensional, and let $𝑈$ be a subspace of $𝑉$ .

(a)For every vector space $𝑊$ and every linear map $𝑆 : 𝑈 \to 𝑊$ , there is a linear map $𝑇 : 𝑉 \to 𝑊$ with $𝑇 (𝐮) = 𝑆 (𝐮)$ for all $𝐮 \in 𝑈$ .
(b)For every $𝐯 \in 𝑉$ with $𝐯 \notin 𝑈$ , there is a linear map $𝑓 : 𝑉 \to 𝐹$ with $𝑓 (𝐮) = 0$ for all $𝐮 \in 𝑈$ and $𝑓 (𝐯) = 1$ .

The proof uses that $𝑈$ has a basis. That every subspace of a finite-dimensional space is finite-dimensional is Proposition 4.1.21(a) below, whose proof does not use this proposition.

Proof.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 1.5.14 (Appending a vector)

Techniques. Extend a basis of a subspace (Technique 4.1.18), Construct a map by choosing it on a basis (Technique 2.2.4)

Hint 1. Take a basis

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

𝑈

and extend it to a basis of

𝑉

. A linear map on

𝑉

can be prescribed freely on this basis.

Hint 2. For (a), send

𝐮_{𝑖}

𝑆 (𝐮_{𝑖})

and the new basis vectors to

𝟎

. Why do

𝑇

and

𝑆

then agree on all of

𝑈

Hint 3. For (b), first extend

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

, which is independent because

𝐯 \notin 𝑈

Sketch. Take a basis

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

𝑈

. (a) Extend it to a basis

𝐮_{1},

\dots,

𝐮_{𝑘},

𝐰_{1},

\dots,

𝐰_{𝑟}

𝑉

and let

𝑇

send

𝐮_{𝑖} \mapsto 𝑆 (𝐮_{𝑖})

𝐰_{𝑗} \mapsto 𝟎

(Theorem 2.2.1). Then

𝑇 (\sum 𝑐_{𝑖} 𝐮_{𝑖}) =

\sum 𝑐_{𝑖} 𝑆 (𝐮_{𝑖}) =

𝑆 (\sum 𝑐_{𝑖} 𝐮_{𝑖})

. (b)

𝐯 \notin

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

, so

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

is independent; extend it to a basis and let

𝑓

1

𝐯

and

0

on every other basis vector.

By Proposition 4.1.21(a), $𝑈$ is finite-dimensional; let $𝐮_{1}, \dots, 𝐮_{𝑘}$ be a basis of $𝑈$ . It is an independent list in $𝑉$ .

(a) By Theorem 4.1.16 there are $𝐰_{1}, \dots, 𝐰_{𝑟}$ such that $𝐮_{1},$ $\dots,$ $𝐮_{𝑘},$ $𝐰_{1},$ $\dots,$ $𝐰_{𝑟}$ is a basis of $𝑉$ . By Theorem 2.2.1 there is a linear map $𝑇 : 𝑉 \to 𝑊$ with $𝑇 (𝐮_{𝑖}) = 𝑆 (𝐮_{𝑖})$ for all $𝑖$ and $𝑇 (𝐰_{𝑗}) = 𝟎$ for all $𝑗$ . Let $𝐮 \in 𝑈$ , and write $𝐮 =$ $𝑐_{1} 𝐮_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐮_{𝑘}$ . Since $𝑇$ and $𝑆$ are both linear,

𝑇 (𝐮) = \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝑇 (𝐮_{𝑖}) = \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝑆 (𝐮_{𝑖}) = 𝑆 (𝐮),

as desired.

(b) Since $𝑈 =$ $span (𝐮_{1}, \dots, 𝐮_{𝑘})$ and $𝐯 \notin 𝑈$ , the list $𝐮_{1}, \dots, 𝐮_{𝑘}, 𝐯$ is independent by Proposition 1.5.14. By Theorem 4.1.16 it extends to a basis $𝐮_{1},$ $\dots,$ $𝐮_{𝑘},$ $𝐯,$ $𝐰_{1},$ $\dots,$ $𝐰_{𝑟}$ of $𝑉$ . By Theorem 2.2.1 there is a linear map $𝑓 : 𝑉 \to 𝐹$ with $𝑓 (𝐯) = 1$ and with value $0$ on every other vector of this basis. For $𝐮 = \sum_{𝑖} 𝑐_{𝑖} 𝐮_{𝑖} \in 𝑈$ , linearity gives $𝑓 (𝐮) =$ $\sum_{𝑖} 𝑐_{𝑖} 𝑓 (𝐮_{𝑖}) =$ $0$ . □

Part (b) says that a vector outside a subspace can always be told apart from the subspace by a linear function. It is the starting point of duality (Section 13.1). Neither part is automatic in infinite dimensions without Zorn’s lemma, which is needed even to extend a basis of $𝑈$ (Section 15.1).

Exercise 4.1.20.routine Extend

(1, 2, 1)

to a basis of

𝐹^{3}

by appending standard basis vectors, (a) for

𝐹 = ℚ

, and (b) for

𝐹 = 𝔽_{3}

. Which standard basis vectors are appended?

Solution.

Uses. Theorem 4.1.16 (Extending to a basis), Proposition 1.5.14 (Appending a vector), Proposition 1.5.15 (Short lists, zeros, and repeats)

Hint 1. Sift the list

(1, 2, 1),

𝐞_{1},

𝐞_{2},

𝐞_{3}

: keep each entry that is not in the span of the entries kept before it.

Hint 2.

𝐞_{1}

is never a multiple of

(1, 2, 1)

. For the third vector, describe

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

and test

𝐞_{2}

Sketch. In both cases

𝐞_{1}

is kept.

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

{(𝑎 + 𝑏, 2 𝑎, 𝑎)}

, whose vectors have second coordinate

2

times the third;

𝐞_{2}

fails this, so it is kept, and

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

is a basis in both cases, by length.

We follow the proof of Theorem 4.1.16 with

𝒮︀ = 𝐞_{1}, 𝐞_{2}, 𝐞_{3}

. The vector

𝐞_{1}

is not a multiple of

(1, 2, 1)

, since a multiple

𝑡 (1, 2, 1)

with third coordinate

0

has

𝑡 = 0

. So

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

is independent (Proposition 1.5.15(d)). Its span consists of the vectors

𝑎 (1, 2, 1) +

𝑏 𝐞_{1} =

(𝑎 + 𝑏, 2 𝑎, 𝑎)

, whose second coordinate is

2

times the third. The vector

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

fails this test, since

1 \neq 2 \cdot 0

in every field. So

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

is independent (Proposition 1.5.14), and as it has length

3 = dim 𝐹^{3}

, it is a basis. The same vectors are appended in (a) and (b): the computation used only that

1 \neq 0

4.1.6Dimensions of subspaces

Every subspace of $𝐹^{3}$ ought to have dimension $0$ , $1$ , $2$ , or $3$ . Proving that a subspace $𝑈$ of a finite-dimensional space has dimension at most $dim 𝑉$ looks like a direct application of Theorem 4.1.10, but there is a gap: the theorem applies to a basis of $𝑈$ , and we do not yet know that $𝑈$ has one. A basis of $𝑉$ is no help, since none of its vectors need lie in $𝑈$ . (In $ℝ^{2}$ , the line $span ((1, 1))$ contains neither $𝐞_{1}$ nor $𝐞_{2}$ .) The lecture closes the gap by growing an independent list inside $𝑈$ . The bound on independent lists in $𝑉$ forces the growth to stop, and it can only stop at a basis of $𝑈$ .

Proposition 4.1.21 (Dimensions of subspaces). Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛$ , and let $𝑈$ be a subspace of $𝑉$ .

(a) $𝑈$ is finite-dimensional, and $dim 𝑈 \leq 𝑛$ .
(b) $dim 𝑈 = 𝑛$ if and only if $𝑈 = 𝑉$ .

Proof.standard

Uses. Theorem 4.1.10 (Independent lists are short), Proposition 1.5.14 (Appending a vector), Proposition 1.6.2 (Bases are independent spanning lists), Proposition 1.4.14 (The span is the smallest subspace containing a list), Definition 1.4.1 (Subspace)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. An independent list in

𝑈

is also an independent list in

𝑉

, so it has length at most

𝑛

. Choose an independent list in

𝑈

that is as long as possible.

Hint 2. If that list did not span

𝑈

, what could you append to it?

Hint 3. For (b), a basis of

𝑈

of length

𝑛

is an independent list of length

𝑛

𝑉

. Apply Theorem 4.1.10(b).

Sketch. Independent lists in

𝑈

are independent in

𝑉

, so they have length at most

𝑛

. Take one,

ℒ︀

, of maximal length. If some

𝐮 \in 𝑈

were outside

span (ℒ︀)

, then

ℒ︀, 𝐮

would be a longer independent list in

𝑈

. So

ℒ︀

spans

𝑈

and is a basis of

𝑈

of length at most

𝑛

. For (b), if

dim 𝑈 = 𝑛

, a basis of

𝑈

is independent of length

𝑛

𝑉

, hence a basis of

𝑉

, so

𝑉 = span (ℒ︀) \subseteq 𝑈

A linear relation among vectors of $𝑈$ is computed with the operations of $𝑉$ (Definition 1.4.1), so a list in $𝑈$ is independent in $𝑈$ if and only if it is independent in $𝑉$ .

(a) By Theorem 4.1.10(a), every independent list in $𝑈$ has length at most $𝑛$ . The empty list is independent, so the lengths of the independent lists in $𝑈$ form a nonempty set of integers between $0$ and $𝑛$ . Choose an independent list $ℒ︀$ in $𝑈$ whose length $𝑘$ is as large as possible. Suppose, to the contrary, that some $𝐮 \in 𝑈$ is not in $span (ℒ︀)$ . Then $ℒ︀, 𝐮$ is an independent list in $𝑈$ (Proposition 1.5.14) of length $𝑘 + 1$ , contradicting the choice of $ℒ︀$ . So $ℒ︀$ spans $𝑈$ , and it is a basis of $𝑈$ (Proposition 1.6.2). Hence $𝑈$ is finite-dimensional, and $dim 𝑈 = 𝑘 \leq 𝑛$ .

(b) If $𝑈 = 𝑉$ , then $dim 𝑈 = 𝑛$ . Conversely, suppose $dim 𝑈 = 𝑛$ , and let $ℒ︀$ be a basis of $𝑈$ . It is an independent list in $𝑉$ of length $𝑛$ , so it is a basis of $𝑉$ by Theorem 4.1.10(b). Since $𝑈$ is a subspace containing the entries of $ℒ︀$ , Proposition 1.4.14 gives $𝑉 = span (ℒ︀) \subseteq 𝑈$ . Hence $𝑈 = 𝑉$ . □

The lecture’s proof is the same argument told as a process: grow an independent list in $𝑈$ , one vector at a time, and observe that the process cannot reach length $𝑛 + 1$ . Choosing a longest list in advance replaces the process by an extremal choice (Technique 1.5.9), and then there is no need to say “and so on”.

Since every subspace is a vector space in its own right, (b) can be applied with $𝑊$ in place of $𝑉$ : if $𝑈 \subseteq 𝑊$ are subspaces of a finite-dimensional space and $dim 𝑈 = dim 𝑊$ , then $𝑈 = 𝑊$ . This is how equality of subspaces is usually proved in practice. Show one containment, and compare dimensions. Equivalently, a proper subspace has strictly smaller dimension, so a subspace can be pinned down by squeezing its dimension between two bounds.

Example 4.1.22 (Squeezing a dimension). Let $𝑈 =$ ${𝐴 \in 𝐹^{2 \times 2} | tr 𝐴 = 0}$ , the trace-zero matrices of Example 1.4.11. The matrices

𝑈_{12}, 𝑈_{21}, 𝑈_{11} - 𝑈_{22}

lie in $𝑈$ and are independent, since $𝑎 𝑈_{12} +$ $𝑏 𝑈_{21} +$ $𝑐 (𝑈_{11} - 𝑈_{22}) =$ $(\begin{matrix} 𝑐 & 𝑎 \\ 𝑏 & - 𝑐 \end{matrix})$ is $0$ only if $𝑎 = 𝑏 = 𝑐 = 0$ . So $dim 𝑈 \geq 3$ , by Theorem 4.1.10(a) applied in $𝑈$ . On the other hand $𝑈_{11} \notin 𝑈$ , so $𝑈 \neq 𝐹^{2 \times 2}$ and $dim 𝑈 < 4$ by Proposition 4.1.21(b). Hence $dim 𝑈 = 3$ , and by Theorem 4.1.10(b) the three matrices form a basis of $𝑈$ . We never checked that they span. The same squeeze shows that the trace-zero matrices in $𝐹^{𝑛 \times 𝑛}$ have dimension $𝑛^{2} - 1$ (Exercise 4.1.43).

Example 4.1.23 (The subspaces of $𝐹^{3}$ ). Let $𝑈$ be a subspace of $𝐹^{3}$ . By Proposition 4.1.21, $dim 𝑈 \in {0, 1, 2, 3}$ , and $𝑈$ has a basis of that length:

$dim 𝑈 = 0$ : $𝑈 = {𝟎}$ ;
$dim 𝑈 = 1$ : $𝑈 = span (𝐯)$ for some $𝐯 \neq 𝟎$ , a line through $𝟎$ ;
$dim 𝑈 = 2$ : $𝑈 = span (𝐯, 𝐰)$ for some independent $𝐯, 𝐰$ , a plane through $𝟎$ ;
$dim 𝑈 = 3$ : $𝑈 = 𝐹^{3}$ , by Proposition 4.1.21(b).

Over $ℝ$ these are the subspaces of $ℝ^{3}$ that Section 1.4 anticipated: the origin, the lines and the planes through it, and $ℝ^{3}$ . The proof of Theorem 1.4.25 for $𝐹^{2}$ worked by cases on how many independent directions $𝑈$ contains. Dimension is that count, and it settles $𝐹^{𝑛}$ for every $𝑛$ at once.

Exercise 4.1.24.routine Let

𝑈 =

{𝑝 \in {ℝ [𝑥]}_{\leq 3} | 𝑝 (2) = 0}

. Find

dim 𝑈

and a basis of

𝑈

, by a squeeze.

Solution.

Uses. Proposition 1.5.24 (Distinct degrees), Theorem 4.1.10 (Independent lists are short), Proposition 4.1.21 (Dimensions of subspaces)

Hint 1. Find three independent polynomials in

𝑈

; powers of

𝑥 - 2

are natural.

Hint 2. Find one polynomial of degree at most

3

that is not in

𝑈

, and use Proposition 4.1.21(b).

Sketch.

𝑥 - 2

{(𝑥 - 2)}^{2}

{(𝑥 - 2)}^{3}

lie in

𝑈

and have distinct degrees, so

dim 𝑈 \geq 3

. The constant

1

is not in

𝑈

, so

dim 𝑈 < 4

. Hence

dim 𝑈 = 3

, and the three polynomials form a basis.

The polynomials

𝑥 - 2

{(𝑥 - 2)}^{2}

{(𝑥 - 2)}^{3}

vanish at

2

, so they lie in

𝑈

, and they are independent by Proposition 1.5.24. So

dim 𝑈 \geq 3

by Theorem 4.1.10(a), applied in

𝑈

. The constant polynomial

1

does not vanish at

2

, so

𝑈 \neq {ℝ [𝑥]}_{\leq 3}

, and

dim 𝑈 < 4

by Proposition 4.1.21(b). Hence

dim 𝑈 = 3

, and the three polynomials, an independent list of length

dim 𝑈

𝑈

, form a basis of

𝑈

by Theorem 4.1.10(b).

4.1.7Nilpotent chains

Some operators become $0$ after finitely many applications. On $𝐹^{4}$ , the shift

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

moves every entry one place up and pushes a $0$ in at the bottom, so $𝑁^{4} = 0$ . Following one vector,

𝐞_{4} \overset{𝑁}{⟶} 𝐞_{3} \overset{𝑁}{⟶} 𝐞_{2} \overset{𝑁}{⟶} 𝐞_{1} \overset{𝑁}{⟶} 𝟎,

so $𝑁^{3} \neq 0$ but $𝑁^{4} = 0$ . Over $ℝ$ , differentiation on ${ℝ [𝑥]}_{\leq 3}$ behaves the same way:

𝑥^{3} \overset{𝐷}{⟶} 3 𝑥^{2} \overset{𝐷}{⟶} 6 𝑥 \overset{𝐷}{⟶} 6 \overset{𝐷}{⟶} 𝟎 .

An operator $𝑇 \in L (𝑉)$ with $𝑇^{𝑚} = 0$ for some $𝑚 \geq 1$ is called nilpotent; Chapter 10 studies these operators in depth (Section 10.1). In both examples the chain of images ends at $𝟎$ after exactly $dim 𝑉$ steps, and the vectors in the chain form a basis. That is no accident. The vectors in such a chain are always independent, and the reason is a move worth naming.

Technique 4.1.25 (Apply an operator to a relation to kill terms). To show that $𝐯_{1}, \dots, 𝐯_{𝑘}$ is independent, take a relation $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ and apply a linear map $𝐿$ that sends all but a few of the $𝐯_{𝑖}$ to $𝟎$ . Since $𝐿 (𝟎) = 𝟎$ , the result is a shorter relation, ideally a single term $𝑎_{𝑗} 𝐿 (𝐯_{𝑗}) = 𝟎$ with $𝐿 (𝐯_{𝑗}) \neq 𝟎$ , which forces $𝑎_{𝑗} = 0$ . Then repeat with another map, or on the shorter relation that remains.

Reach for it when the vectors come with an operator that acts on them in simple and distinguishable ways: a power of $𝑇$ along a chain $𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots$ ; differentiation or a shift on exponentials and geometric sequences (Example 1.5.27, Exercise 1.5.44); evaluation at a point for functions that vanish at all but one point; a dot product with one of the vectors when they are mutually orthogonal (Exercise 1.5.46). The canonical example is Proposition 4.1.26. The same move shows that eigenvectors for distinct eigenvalues are independent (Section 7.2), and it organizes the Jordan chains of Section 10.3.

Used in 25 places and 1 practice exercise

Example 1.5.27, Exercise 1.5.47, Proposition 4.1.26, Corollary 4.1.27, Exercise 4.1.45, Exercise 4.1.51, Exercise 4.1.60, Proposition 4.4.29, Exercise 4.5.50, Proposition 4.6.28, Exercise 4.8.5, Exercise 4.8.8, Exercise 4.8.14, Problem 4.3, Problem 4.5, Problem 4.8, Theorem 7.2.21, Proposition 7.2.37, Exercise 7.2.51, Exercise 7.7.9, Problem 7.1, Problem 7.3, Problem 7.4, Problem 7.12, Problem 7.15; 1 practice exercise.

Proposition 4.1.26 (Nilpotent chains are independent). Let $𝑇 \in L (𝑉)$ , let $𝐯 \in 𝑉$ , and let $𝑘 \geq 0$ be such that

𝑇^{𝑘} 𝐯 \neq 𝟎 and 𝑇^{𝑘 + 1} 𝐯 = 𝟎 .

Then $𝐯,$ $𝑇 𝐯,$ $𝑇^{2} 𝐯,$ $\dots,$ $𝑇^{𝑘} 𝐯$ is linearly independent.

Intuition. The chain

𝐯 \mapsto

𝑇 𝐯 \mapsto

\dots \mapsto

𝑇^{𝑘} 𝐯 \mapsto

𝟎

has a last nonzero vector. Applying

𝑇^{𝑘}

to the chain kills every vector except the first, which it sends to that last nonzero vector

𝑇^{𝑘} 𝐯

. So applying

𝑇^{𝑘}

to a relation isolates the coefficient of

𝐯

. Once that coefficient is known to be

0

, applying

𝑇^{𝑘 - 1}

isolates the next one, and so on down the chain.

Proof.standard

Uses. Theorem 1.5.5 (Independence is decided at zero), Notation 2.1.18, Proposition 2.1.4 (Linear maps preserve $𝟎$ and negatives), Proposition 1.2.35 (Zero products)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. Take a relation

𝑎_{0} 𝐯 +

𝑎_{1} 𝑇 𝐯 +

\dots +

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

𝟎

and apply

𝑇^{𝑘}

. Which terms survive?

Hint 2.

𝑇^{𝑘} (𝑇^{𝑗} 𝐯) =

𝑇^{𝑘 + 𝑗} 𝐯

, and this is

𝟎

for

𝑗 \geq 1

, since

𝑇^{𝑘 + 𝑗} 𝐯 =

𝑇^{𝑗 - 1} (𝑇^{𝑘 + 1} 𝐯)

. So only

𝑎_{0} 𝑇^{𝑘} 𝐯

is left.

Hint 3. Prove

𝑎_{𝑖} = 0

by induction on

𝑖

: if

𝑎_{0} = \dots = 𝑎_{𝑖 - 1} = 0

, apply

𝑇^{𝑘 - 𝑖}

to the relation.

Sketch. Let

\sum_{𝑗 = 0}^{𝑘} 𝑎_{𝑗} 𝑇^{𝑗} 𝐯 =

𝟎

. Since

𝑇^{𝑙} 𝐯 = 𝟎

for all

𝑙 \geq 𝑘 + 1

, applying

𝑇^{𝑘}

leaves

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

, so

𝑎_{0} = 0

. If

𝑎_{0} = \dots = 𝑎_{𝑖 - 1} = 0

, applying

𝑇^{𝑘 - 𝑖}

\sum_{𝑗 \geq 𝑖} 𝑎_{𝑗} 𝑇^{𝑗} 𝐯 =

𝟎

leaves

𝑎_{𝑖} 𝑇^{𝑘} 𝐯 = 𝟎

, so

𝑎_{𝑖} = 0

First, $𝑇^{𝑙} 𝐯 = 𝟎$ for every $𝑙 \geq 𝑘 + 1$ , because $𝑇^{𝑙} 𝐯 =$ $𝑇^{𝑙 - 𝑘 - 1} (𝑇^{𝑘 + 1} 𝐯) =$ $𝑇^{𝑙 - 𝑘 - 1} (𝟎) =$ $𝟎$ (Notation 2.1.18, Proposition 2.1.4). Suppose that

𝑎_{0} 𝐯 + 𝑎_{1} 𝑇 𝐯 + \dots + 𝑎_{𝑘} 𝑇^{𝑘} 𝐯 = 𝟎 .

(4.1.1)

We show by induction on $𝑖 \in {0, 1, \dots, 𝑘}$ that $𝑎_{𝑖} = 0$ . Let $𝑖$ be given and assume that $𝑎_{𝑗} = 0$ for all $𝑗 < 𝑖$ , which is no assumption when $𝑖 = 0$ . Then (4.1.1) reads $\sum_{𝑗 = 𝑖}^{𝑘} 𝑎_{𝑗} 𝑇^{𝑗} 𝐯 =$ $𝟎$ . Apply the linear map $𝑇^{𝑘 - 𝑖}$ to both sides:

𝟎 = \sum_{𝑗 = 𝑖}^{𝑘} 𝑎_{𝑗} 𝑇^{𝑘 - 𝑖 + 𝑗} 𝐯 = 𝑎_{𝑖} 𝑇^{𝑘} 𝐯 + \sum_{𝑗 = 𝑖 + 1}^{𝑘} 𝑎_{𝑗} 𝑇^{𝑘 + (𝑗 - 𝑖)} 𝐯 = 𝑎_{𝑖} 𝑇^{𝑘} 𝐯,

since every exponent $𝑘 + (𝑗 - 𝑖)$ in the last sum is at least $𝑘 + 1$ . As $𝑇^{𝑘} 𝐯 \neq 𝟎$ , Proposition 1.2.35 gives $𝑎_{𝑖} = 0$ . By induction all $𝑎_{𝑖} = 0$ , so the list is independent by Theorem 1.5.5. □

Table 4.1.1. The proof of Proposition 4.1.26 for

𝑘 = 3

. Each row applies a power of

𝑇

to the relation

𝑎_{0} 𝐯 +

𝑎_{1} 𝑇 𝐯 +

𝑎_{2} 𝑇^{2} 𝐯 +

𝑎_{3} 𝑇^{3} 𝐯 =

𝟎

. Terms pushed past

𝑇^{3} 𝐯

become

𝟎

; a dot marks a term whose coefficient is already known to be

0

. Exactly one term survives in each row, and it is a multiple of

𝑇^{3} 𝐯 \neq 𝟎

The proposition did not assume that $𝑉$ is finite-dimensional. Combined with the bound on independent lists, it bounds how long an operator on a finite-dimensional space can take to reach $0$ . The striking part is that the bound depends only on $dim 𝑉$ : nothing about the particular operator enters.

Corollary 4.1.27 (A nilpotent operator dies within

dim 𝑉

steps). Let

𝑉

be finite-dimensional with

dim 𝑉 = 𝑛

, and let

𝑇 \in L (𝑉)

with

𝑇^{𝑚} = 0

for some

𝑚 \geq 1

. Then

𝑇^{𝑛} = 0

. Similarly, if

𝐴 \in 𝐹^{𝑛 \times 𝑛}

and

𝐴^{𝑚} = 0

for some

𝑚 \geq 1

, then

𝐴^{𝑛} = 0

Proof.standard

Uses. Proposition 4.1.26 (Nilpotent chains are independent), Theorem 4.1.10 (Independent lists are short), Theorem 2.4.2 (The matrix of a composite), Definition 2.3.15 (The linear map of a matrix)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. Fix

𝐯 \neq 𝟎

. Since

𝑇^{𝑚} 𝐯 = 𝟎

, there is a largest

𝑘

with

𝑇^{𝑘} 𝐯 \neq 𝟎

. What does Proposition 4.1.26 say about

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

Hint 2. That list has

𝑘 + 1

entries in an

𝑛

-dimensional space, so

𝑘 + 1 \leq 𝑛

. Now compute

𝑇^{𝑛} 𝐯

Sketch. For

𝐯 \neq 𝟎

, let

𝑘

be the largest integer with

𝑇^{𝑘} 𝐯 \neq 𝟎

; it exists, and

𝑘 < 𝑚

, because

𝑇^{0} 𝐯 = 𝐯 \neq 𝟎

and

𝑇^{𝑚} 𝐯 = 𝟎

. By Proposition 4.1.26 the chain

𝐯, \dots, 𝑇^{𝑘} 𝐯

is independent, so

𝑘 + 1 \leq 𝑛

. Hence

𝑇^{𝑛} 𝐯 =

𝑇^{𝑛 - 𝑘 - 1} (𝑇^{𝑘 + 1} 𝐯) =

𝟎

. For matrices, apply this to

𝑇_{𝐴}

Let $𝐯 \in 𝑉$ . If $𝐯 = 𝟎$ , then $𝑇^{𝑛} 𝐯 = 𝟎$ . Suppose $𝐯 \neq 𝟎$ . The set of integers $𝑗 \geq 0$ with $𝑇^{𝑗} 𝐯 \neq 𝟎$ contains $0$ , as $𝑇^{0} 𝐯 = 𝐯$ , and contains no $𝑗 \geq 𝑚$ , as $𝑇^{𝑗} 𝐯 =$ $𝑇^{𝑗 - 𝑚} (𝑇^{𝑚} 𝐯) =$ $𝟎$ for those. Let $𝑘$ be its largest element. Then $𝑇^{𝑘} 𝐯 \neq 𝟎$ and $𝑇^{𝑘 + 1} 𝐯 = 𝟎$ , so by Proposition 4.1.26 the list $𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑘} 𝐯$ is independent. It has $𝑘 + 1$ entries, so $𝑘 + 1 \leq 𝑛$ by Theorem 4.1.10(a). Therefore

𝑇^{𝑛} 𝐯 = 𝑇^{𝑛 - 𝑘 - 1} (𝑇^{𝑘 + 1} 𝐯) = 𝑇^{𝑛 - 𝑘 - 1} (𝟎) = 𝟎 .

This holds for every $𝐯$ , so $𝑇^{𝑛} = 0$ .

For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , the linear map $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑛}$ satisfies ${(𝑇_{𝐴})}^{𝑗} = 𝑇_{𝐴^{𝑗}}$ for all $𝑗 \geq 1$ , by Theorem 2.4.2 and induction on $𝑗$ . So ${(𝑇_{𝐴})}^{𝑚} = 𝑇_{𝐴^{𝑚}} = 0$ , and by the first part $𝑇_{𝐴^{𝑛}} = {(𝑇_{𝐴})}^{𝑛} = 0$ . The columns of $𝐴^{𝑛}$ are the vectors $𝐴^{𝑛} 𝐞_{𝑗} =$ $𝑇_{𝐴^{𝑛}} (𝐞_{𝑗}) =$ $𝟎$ , so $𝐴^{𝑛} = 0$ . □

The exponent $𝑛$ cannot be lowered in general: the shift $𝑁$ on $𝐹^{4}$ above has $𝑁^{3} \neq 0$ . And the corollary rules out operators that take longer. For instance, there is no $𝐴 \in ℝ^{3 \times 3}$ with $𝐴^{3} \neq 0$ but $𝐴^{4} = 0$ , however cleverly its entries are chosen. In the plane, the corollary says that a nilpotent $2 \times 2$ matrix satisfies $𝐴^{2} = 0$ .

The map of

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

(called

𝐴

in the interactive version) flattens the plane onto the line

ℓ

through

(1, 1)

, and it sends

ℓ

itself to

𝟎

, since

𝑁 (1, 1) = 𝟎

. So

𝑁^{2} = 0

. For any

𝐯

off

ℓ

, such as

𝐞_{1}

, the chain

𝐯, 𝑁 𝐯

ends at

𝟎

; by Proposition 4.1.26 it is independent, and having length

2 = dim ℝ^{2}

, it is a basis (Theorem 4.1.10(b)). In the interactive version, move the columns: a nonzero

2 \times 2

matrix is nilpotent exactly when it flattens the plane onto a line and sends that line to

𝟎

Over a field in which some integer is $0$ , the derivative dies much sooner than in characteristic $0$ , sooner than $dim 𝑉$ steps.

Example 4.1.28 (Differentiation over $𝔽_{𝑝}$ ). Let $𝑝$ be a prime and let $𝐷$ be the formal derivative on $𝔽_{𝑝} [𝑥]$ (Example 2.1.9). Then $𝐷^{𝑝} (𝑥^{𝑗}) =$ $𝑗 (𝑗 - 1) \dots (𝑗 - 𝑝 + 1) 𝑥^{𝑗 - 𝑝}$ for $𝑗 \geq 𝑝$ , and the product of the $𝑝$ consecutive integers $𝑗, 𝑗 - 1, \dots, 𝑗 - 𝑝 + 1$ is divisible by $𝑝$ , so it is $0$ in $𝔽_{𝑝}$ . For $𝑗 < 𝑝$ , $𝐷^{𝑝} (𝑥^{𝑗}) = 0$ already. So $𝐷^{𝑝} = 0$ on all of $𝔽_{𝑝} [𝑥]$ , an infinite-dimensional space.

For $𝑝 = 2$ , on $𝔽_{2} {[𝑥]}_{\leq 3}$ the chains are

𝑥^{3} \overset{𝐷}{⟶} 𝑥^{2} \overset{𝐷}{⟶} 𝟎, 𝑥 \overset{𝐷}{⟶} 1 \overset{𝐷}{⟶} 𝟎,

since $𝐷 (𝑥^{3}) = 3 𝑥^{2} = 𝑥^{2}$ and $𝐷 (𝑥^{2}) = 2 𝑥 = 0$ . Here $𝐷^{2} = 0$ although $dim 𝔽_{2} {[𝑥]}_{\leq 3} = 4$ . The basis $𝑥^{3}, 𝑥^{2}, 𝑥, 1$ splits into two chains of length $2$ instead of one chain of length $4$ . How a nilpotent operator splits a space into chains is the subject of Section 10.3.

Exercise 4.1.29.routine For which

𝑛

is there a matrix

𝐴 \in 𝐹^{𝑛 \times 𝑛}

with

𝐴^{4} \neq 0

and

𝐴^{5} = 0

? For each such

𝑛

, give one.

Solution.

Uses. Corollary 4.1.27 (A nilpotent operator dies within $dim 𝑉$ steps)

Hint 1. If

𝑛 \leq 4

, what does Corollary 4.1.27 say about

𝐴^{𝑛}

, and hence about

𝐴^{4}

Hint 2. For

𝑛 \geq 5

, generalize the shift: send

𝐞_{5} \mapsto 𝐞_{4} \mapsto \dots \mapsto 𝐞_{1} \mapsto 𝟎

and kill the remaining standard basis vectors.

Sketch. If

𝑛 \leq 4

, then

𝐴^{5} = 0

gives

𝐴^{𝑛} = 0

, so

𝐴^{4} = 𝐴^{4 - 𝑛} 𝐴^{𝑛} = 0

. For

𝑛 \geq 5

, take

𝐴 =

𝑈_{12} +

𝑈_{23} +

𝑈_{34} +

𝑈_{45}

, with

𝐴 𝐞_{𝑗 + 1} = 𝐞_{𝑗}

for

𝑗 \leq 4

and

𝐴 𝐞_{𝑗} = 𝟎

otherwise; then

𝐴^{4} 𝐞_{5} = 𝐞_{1}

and

𝐴^{5} = 0

Suppose $𝑛 \leq 4$ and $𝐴^{5} = 0$ . By Corollary 4.1.27, $𝐴^{𝑛} = 0$ , so $𝐴^{4} = 𝐴^{4 - 𝑛} 𝐴^{𝑛} = 0$ . So no such $𝐴$ exists for $𝑛 \leq 4$ .

For $𝑛 \geq 5$ , let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ have $1$ in positions $(1, 2),$ $(2, 3),$ $(3, 4),$ $(4, 5)$ and $0$ elsewhere. Then $𝐴 𝐞_{1} = 𝟎$ , $𝐴 𝐞_{𝑗} = 𝐞_{𝑗 - 1}$ for $2 \leq 𝑗 \leq 5$ , and $𝐴 𝐞_{𝑗} = 𝟎$ for $𝑗 \geq 6$ . Hence $𝐴^{4} 𝐞_{5} = 𝐞_{1} \neq 𝟎$ , so $𝐴^{4} \neq 0$ . And $𝐴^{5} 𝐞_{𝑗} = 𝟎$ for every $𝑗$ : for $𝑗 \leq 5$ the vector $𝐞_{𝑗}$ reaches $𝟎$ after $𝑗 \leq 5$ steps, and for $𝑗 \geq 6$ after one. Since $𝐴^{5}$ kills a basis, $𝐴^{5} = 0$ . So the answer is: exactly for $𝑛 \geq 5$ .

4.1.8Too many vectors

Theorem 4.1.10 also works in the other direction. To prove that some linear relation exists, without being able to write one down, it is enough to produce more vectors than the dimension of a space that contains them.

Technique 4.1.30 (Too many vectors force a dependence). If a list of more than $𝑛$ vectors lies in a space of dimension at most $𝑛$ , it is linearly dependent (Theorem 4.1.10(a)), so it has a nontrivial linear relation. The relation is the output: it is a statement about the vectors that we did not have to guess. Natural sources of many vectors in a space of known dimension are powers $𝐼, 𝐴, 𝐴^{2}, \dots$ of a matrix, iterates $𝐯, 𝑇 𝐯, 𝑇^{2} 𝐯, \dots$ of a vector, and powers $1, 𝛼, 𝛼^{2}, \dots$ of a number inside a space spanned by a few known quantities. Often the relation is then refined, for instance by choosing one with the smallest index of a nonzero coefficient (Technique 1.5.9).

Reach for it when you need an identity or an equation of a given shape and have no formula for it, but can count. The canonical example is Proposition 4.1.31. The iterates $𝐯, 𝑇 𝐯, \dots, 𝑇^{𝑛} 𝐯$ give eigenvalues without determinants in Section 7.3; the powers of $𝑇$ lead to the minimal polynomial (Section 7.6); and the powers of a number lead to algebraic numbers (Section 14.2).

Used in 12 places and 3 practice exercises

Exercise 2.5.49, Proposition 4.1.31, Exercise 4.1.33, Exercise 4.1.56, Exercise 4.1.57, Exercise 4.1.60, Exercise 4.8.4, Exercise 4.8.9, Problem 4.15, Proposition 7.2.35, Theorem 7.3.27, Proposition 7.6.4; 3 practice exercises.

Proposition 4.1.31 (Every square matrix satisfies a polynomial).

(a)Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝑛 \geq 1$ . There are $𝑐_{0},$ $𝑐_{1},$ $\dots,$ $𝑐_{𝑛^{2}} \in$ $𝐹$ , not all $0$ , with
$𝑐_{0} 𝐼_{𝑛} + 𝑐_{1} 𝐴 + 𝑐_{2} 𝐴^{2} + \dots + 𝑐_{𝑛^{2}} 𝐴^{𝑛^{2}} = 0 .$
(b)Let $𝑉$ be finite-dimensional with $dim 𝑉 = 𝑛 \geq 1$ , and let $𝑇 \in L (𝑉)$ . There are $𝑐_{0}, \dots, 𝑐_{𝑛^{2}} \in 𝐹$ , not all $0$ , with $𝑐_{0} {id}_{𝑉} +$ $𝑐_{1} 𝑇 +$ $\dots +$ $𝑐_{𝑛^{2}} 𝑇^{𝑛^{2}} =$ $0$ .

Proof.routine

Uses. Example 4.1.7 (Dimensions of the standard spaces), Theorem 4.1.10 (Independent lists are short), Theorem 1.5.5 (Independence is decided at zero), Notation 2.4.16 (Powers of a matrix), Theorem 2.3.20 (Linear maps correspond to matrices)

Techniques. Too many vectors force a dependence (Technique 4.1.30), Translate between maps and matrices (Technique 2.3.27)

Hint 1. Count the matrices

𝐼_{𝑛},

𝐴,

𝐴^{2},

\dots,

𝐴^{𝑛^{2}}

, and recall

dim 𝐹^{𝑛 \times 𝑛}

Hint 2. For (b), apply (a) to

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

for a basis

ℬ︀

𝑉

, and use

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

(Notation 2.4.16).

Sketch. The list

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

has

𝑛^{2} + 1

entries in

𝐹^{𝑛 \times 𝑛}

, which has dimension

𝑛^{2}

, so it is dependent, and a nontrivial relation is the claim. For (b), take the relation for

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

; by Notation 2.4.16 it says

{[\sum 𝑐_{𝑗} 𝑇^{𝑗}]}_{ℬ︀ ℬ︀} =

0 =

{[0]}_{ℬ︀ ℬ︀}

, and a map is determined by its matrix.

(a) The list $𝐼_{𝑛},$ $𝐴,$ $𝐴^{2},$ $\dots,$ $𝐴^{𝑛^{2}}$ has $𝑛^{2} + 1$ entries, and it lies in $𝐹^{𝑛 \times 𝑛}$ , which has dimension $𝑛^{2}$ (Example 4.1.7). By Theorem 4.1.10(a) it is linearly dependent, so by Theorem 1.5.5 it has a nontrivial linear relation. That relation is the claim.

(b) Fix a basis $ℬ︀$ of $𝑉$ and let $𝐴 =$ ${[𝑇]}_{ℬ︀ ℬ︀} \in$ $𝐹^{𝑛 \times 𝑛}$ . Take $𝑐_{0}, \dots, 𝑐_{𝑛^{2}}$ , not all $0$ , as in (a). By Notation 2.4.16,

{[𝑐_{0} {id}_{𝑉} + 𝑐_{1} 𝑇 + \dots + 𝑐_{𝑛^{2}} 𝑇^{𝑛^{2}}]}_{ℬ︀ ℬ︀} = 𝑐_{0} 𝐼_{𝑛} + 𝑐_{1} 𝐴 + \dots + 𝑐_{𝑛^{2}} 𝐴^{𝑛^{2}} = 0 = {[0]}_{ℬ︀ ℬ︀} .

By Theorem 2.3.20, a linear map $𝑉 \to 𝑉$ is determined by its matrix with respect to $ℬ︀$ , so $𝑐_{0} {id}_{𝑉} +$ $𝑐_{1} 𝑇 +$ $\dots +$ $𝑐_{𝑛^{2}} 𝑇^{𝑛^{2}} =$ $0$ . □

In the language of polynomials, $𝐴$ is a root of the nonzero polynomial $𝑐_{0} +$ $𝑐_{1} 𝑥 +$ $\dots +$ $𝑐_{𝑛^{2}} 𝑥^{𝑛^{2}}$ . Evaluating polynomials at matrices and operators is made formal in Section 7.1 and Section 7.2, and Section 7.6 studies the polynomial of smallest degree that $𝐴$ satisfies. The bound $𝑛^{2}$ is far from the truth: the Cayley–Hamilton theorem (Theorem 7.6.20) gives a nonzero polynomial of degree $𝑛$ . For now, the point is that the existence of some polynomial costs nothing beyond counting.

Example 4.1.32 ( $\sqrt{2} + \sqrt{3}$ is a root of a rational polynomial). Regard $ℝ$ as a vector space over $ℚ$ (Example 1.2.20), and let $𝛼 = \sqrt{2} + \sqrt{3}$ . Expanding,

𝛼^{2} = 5 + 2 \sqrt{6}, 𝛼^{3} = 11 \sqrt{2} + 9 \sqrt{3}, 𝛼^{4} = 49 + 20 \sqrt{6} .

So $1, 𝛼, 𝛼^{2}, 𝛼^{3}, 𝛼^{4}$ all lie in $𝑊 = {span}_{ℚ} (1, \sqrt{2}, \sqrt{3}, \sqrt{6})$ , which has dimension at most $4$ by Corollary 4.1.11(a). Five vectors in a space of dimension at most $4$ are dependent: there are rationals $𝑐_{0}, \dots, 𝑐_{4}$ , not all $0$ , with $𝑐_{0} +$ $𝑐_{1} 𝛼 +$ $\dots +$ $𝑐_{4} 𝛼^{4} =$ $0$ . Before computing anything, we know that $𝛼$ is a root of a nonzero polynomial with rational coefficients and degree at most $4$ .

To find one, note that the even powers lie in ${span}_{ℚ} (1, \sqrt{6})$ , and look for $𝛼^{4} + 𝑎 𝛼^{2} + 𝑏 = 0$ :

49 + 20 \sqrt{6} + 𝑎 (5 + 2 \sqrt{6}) + 𝑏 = (49 + 5 𝑎 + 𝑏) + (20 + 2 𝑎) \sqrt{6} .

Taking $𝑎 = - 10$ and $𝑏 = 1$ makes both brackets $0$ , so $𝛼^{4} - 10 𝛼^{2} + 1 = 0$ . Making the brackets $0$ is sufficient whether or not $1, \sqrt{6}$ is independent over $ℚ$ . (It is: $𝑎^{'} + 𝑏^{'} \sqrt{6} = 0$ with $𝑏^{'} \neq 0$ would make $\sqrt{6}$ rational.)

Exercise 4.1.33.routine Let

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

. By Proposition 4.1.31,

𝐼_{2}, 𝐴, \dots, 𝐴^{4}

satisfy a nontrivial relation. Find a nontrivial relation among

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

alone, and use it to compute

𝐴^{10}

Solution.

Uses. Proposition 4.1.31 (Every square matrix satisfies a polynomial)

Techniques. Too many vectors force a dependence (Technique 4.1.30)

Hint 1. Compute

𝐴^{2}

and compare it with

𝐴

and

𝐼_{2}

Hint 2. From

𝐴^{2} = 2 𝐴 - 𝐼_{2}

, show by induction that

𝐴^{𝑘} =

𝑘 𝐴 -

(𝑘 - 1) 𝐼_{2}

Sketch.

𝐴^{2} =

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

2 𝐴 -

𝐼_{2}

, so

𝐴^{2} - 2 𝐴 + 𝐼_{2} = 0

. Induction gives

𝐴^{𝑘} =

𝑘 𝐴 -

(𝑘 - 1) 𝐼_{2} =

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

, so

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

We have $𝐴^{2} =$ $(\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}) =$ $2 𝐴 -$ $𝐼_{2}$ , so $𝐴^{2} - 2 𝐴 + 𝐼_{2} = 0$ is a nontrivial relation. We show $𝐴^{𝑘} =$ $𝑘 𝐴 -$ $(𝑘 - 1) 𝐼_{2}$ for $𝑘 \geq 1$ by induction. For $𝑘 = 1$ it reads $𝐴 = 𝐴$ . If it holds for $𝑘$ , then

𝐴^{𝑘 + 1} = 𝐴 (𝑘 𝐴 - (𝑘 - 1) 𝐼_{2}) = 𝑘 𝐴^{2} - (𝑘 - 1) 𝐴 = 𝑘 (2 𝐴 - 𝐼_{2}) - (𝑘 - 1) 𝐴 = (𝑘 + 1) 𝐴 - 𝑘 𝐼_{2} .

Hence $𝐴^{10} =$ $10 𝐴 -$ $9 𝐼_{2} =$ $(\begin{matrix} 1 & 10 \\ 0 & 1 \end{matrix})$ .

4.1.9Dimension over a finite field

Over a finite field, dimension counts elements. In Exercise 1.5.43 and Exercise 1.6.38 we counted spans and bases in $𝐹^{𝑛}$ by hand; with dimension available, the counts hold in every finite-dimensional space and come with a short proof.

Proposition 4.1.34 (Size of a vector space over a finite field). Let $𝐹$ be a finite field with $𝑞$ elements, and let $𝑉$ be a vector space over $𝐹$ . Then $𝑉$ is finite-dimensional if and only if $𝑉$ is a finite set, and in that case

| 𝑉 | = 𝑞^{dim 𝑉} .

Proof.routine

Uses. Proposition 1.6.16 (The coordinate map is a bijection), Definition 1.6.23 (Finite-dimensional), Definition 1.2.4 (The space $𝐹^{𝑛}$ ), Definition 4.1.5 (Dimension)

Hint 1. If

𝑉

is a finite set, find a spanning list directly.

Hint 2. If

dim 𝑉 = 𝑛

, the coordinate map of a basis is a bijection

𝑉 \to 𝐹^{𝑛}

. How many elements does

𝐹^{𝑛}

have?

Sketch. A finite

𝑉

is spanned by the list of all its elements. Conversely, a basis of length

𝑛 = dim 𝑉

gives a bijection

𝑉 \to 𝐹^{𝑛}

(Proposition 1.6.16), and

𝐹^{𝑛}

has

𝑞^{𝑛}

elements, one for each choice of

𝑛

entries.

𝑉

is finite, the list of all elements of

𝑉

spans

𝑉

, so

𝑉

is finite-dimensional. Conversely, suppose

dim 𝑉 = 𝑛

, and let

ℬ︀

be a basis of

𝑉

. By Proposition 1.6.16,

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

is a bijection

𝑉 \to 𝐹^{𝑛}

. An element of

𝐹^{𝑛}

is a list of

𝑛

entries, each chosen from

𝑞

elements, so

| 𝐹^{𝑛} | = 𝑞^{𝑛}

. Hence

𝑉

is finite and

| 𝑉 | = 𝑞^{𝑛}

. □

So every subspace of $𝔽_{𝑝}^{𝑛}$ has a power of $𝑝$ as its number of elements, and a subspace with $𝑝^{𝑘}$ elements has dimension $𝑘$ . For instance, no subspace of $𝔽_{3}^{5}$ has $30$ elements, and a subspace of $𝔽_{2}^{7}$ with $16$ elements is $4$ -dimensional.

Corollary 4.1.35 (Counting independent lists and bases). Let $𝐹$ be a finite field with $𝑞$ elements, and let $𝑉$ be a vector space over $𝐹$ with $dim 𝑉 = 𝑛$ . For $0 \leq 𝑘 \leq 𝑛$ , the number of linearly independent lists of length $𝑘$ in $𝑉$ is

𝑁_{𝑞} (𝑛, 𝑘) = (𝑞^{𝑛} - 1) (𝑞^{𝑛} - 𝑞) (𝑞^{𝑛} - 𝑞^{2}) \dots (𝑞^{𝑛} - 𝑞^{𝑘 - 1}) .

In particular $𝑉$ has exactly $𝑁_{𝑞} (𝑛, 𝑛)$ bases.

Proof.standard

Uses. Proposition 4.1.34 (Size of a vector space over a finite field), Proposition 1.5.14 (Appending a vector), Corollary 1.5.17 (Sublists), Proposition 1.6.2 (Bases are independent spanning lists), Theorem 4.1.10 (Independent lists are short), Theorem 4.1.4 (All bases have the same length)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. An independent list of length

𝑘 + 1

is an independent list

ℒ︀

of length

𝑘

followed by a vector outside

span (ℒ︀)

. How many vectors does

span (ℒ︀)

have?

Hint 2.

ℒ︀

is a basis of

span (ℒ︀)

, so

| span (ℒ︀) | = 𝑞^{𝑘}

by Proposition 4.1.34. Induct on

𝑘

. For bases, use Theorem 4.1.10(b).

Sketch. By Corollary 1.5.17 and Proposition 1.5.14, the independent lists of length

𝑘 + 1

are the lists

ℒ︀, 𝐰

with

ℒ︀

independent of length

𝑘

and

𝐰 \notin span (ℒ︀)

. Since

ℒ︀

is a basis of

span (ℒ︀)

, that span has

𝑞^{𝑘}

elements, leaving

𝑞^{𝑛} - 𝑞^{𝑘}

choices of

𝐰

. Induction on

𝑘

gives the product. The bases are exactly the independent lists of length

𝑛

Let $𝐼_{𝑘}$ be the number of independent lists of length $𝑘$ in $𝑉$ . We show $𝐼_{𝑘} = 𝑁_{𝑞} (𝑛, 𝑘)$ by induction on $𝑘$ . For $𝑘 = 0$ , the only list of length $0$ is $()$ , which is independent, and $𝑁_{𝑞} (𝑛, 0) = 1$ is the empty product.

Let $0 \leq 𝑘 < 𝑛$ . A list $ℒ︀, 𝐰$ of length $𝑘 + 1$ is independent if and only if $ℒ︀$ is independent and $𝐰 \notin span (ℒ︀)$ : if it is independent, so is its sublist $ℒ︀$ (Corollary 1.5.17), and then $𝐰 \notin span (ℒ︀)$ by Proposition 1.5.14; the converse is Proposition 1.5.14. For an independent $ℒ︀$ of length $𝑘$ , the subspace $span (ℒ︀)$ has $ℒ︀$ as a basis (Proposition 1.6.2), so it has dimension $𝑘$ and $𝑞^{𝑘}$ elements by Proposition 4.1.34. That leaves $𝑞^{𝑛} - 𝑞^{𝑘}$ choices of $𝐰$ for each of the $𝐼_{𝑘}$ choices of $ℒ︀$ . So

𝐼_{𝑘 + 1} = 𝐼_{𝑘} (𝑞^{𝑛} - 𝑞^{𝑘}) = 𝑁_{𝑞} (𝑛, 𝑘) (𝑞^{𝑛} - 𝑞^{𝑘}) = 𝑁_{𝑞} (𝑛, 𝑘 + 1) .

Every basis of $𝑉$ has length $𝑛$ (Theorem 4.1.4) and is independent, and every independent list of length $𝑛$ is a basis (Theorem 4.1.10(b)). So the bases of $𝑉$ are the independent lists of length $𝑛$ , and there are $𝑁_{𝑞} (𝑛, 𝑛)$ of them. □

By Theorem 3.5.14, a matrix in $𝐹^{𝑛 \times 𝑛}$ is invertible if and only if its columns form a basis of $𝐹^{𝑛}$ , and the columns determine the matrix. So there are exactly $𝑁_{𝑞} (𝑛, 𝑛)$ invertible $𝑛 \times 𝑛$ matrices over a field with $𝑞$ elements. Over $𝔽_{2}$ this gives $3 \cdot 2 = 6$ invertible $2 \times 2$ matrices and $7 \cdot 6 \cdot 4 = 168$ invertible $3 \times 3$ matrices.

Counting subspaces Beyond 21-242

Counting subspaces over finite fields is standard combinatorics, but it is not part of 21-242.

How many $𝑘$ -dimensional subspaces does $𝔽_{2}^{3}$ have? Each such subspace has many bases, and each independent list spans exactly one subspace. Counting the pairs (subspace, basis) in two ways answers the question, and the move is worth a name.

Technique 4.1.36 (Double counting). To count a set $𝑋$ that is hard to list, find a second set $𝑃$ of pairs $(𝑥, 𝑦)$ with $𝑥 \in 𝑋$ that is easy to count in another way. If every $𝑥 \in 𝑋$ occurs in the same number $𝑑$ of pairs, then $| 𝑃 | = | 𝑋 | \cdot 𝑑$ , and $| 𝑋 | = | 𝑃 | / 𝑑$ . Its cousin, the pigeonhole principle, compares two sets through a one-to-one assignment: the proof by exchange of Lemma 4.1.2 assigns to each $𝐮$ a different $𝐰$ , which is why $𝑚 \leq 𝑛$ .

Reach for it when the objects to be counted are hard to enumerate but each one is described by many easy-to-count objects, such as subspaces by their bases. The canonical example is Proposition 4.1.37. Counting over finite fields returns in Section 14.3.

Used in 7 places and 1 practice exercise

Proposition 4.1.37, Exercise 4.1.54, Exercise 4.4.52, Exercise 4.7.63, Problem 4.10, Problem 4.14, Exercise 7.3.52; 1 practice exercise.

Proposition 4.1.37 (Counting subspaces). Let $𝐹$ be a finite field with $𝑞$ elements, let $dim 𝑉 = 𝑛$ , and let $0 \leq 𝑘 \leq 𝑛$ . With $𝑁_{𝑞}$ as in Corollary 4.1.35, the number of $𝑘$ -dimensional subspaces of $𝑉$ is

𝑁_{𝑞} \frac{𝑛, 𝑘}{𝑁_{𝑞}} (𝑘, 𝑘) = \frac{(𝑞^{𝑛} - 1) (𝑞^{𝑛} - 𝑞) \dots (𝑞^{𝑛} - 𝑞^{𝑘 - 1})}{(𝑞^{𝑘} - 1) (𝑞^{𝑘} - 𝑞) \dots (𝑞^{𝑘} - 𝑞^{𝑘 - 1})} .

Proof.standard

Uses. Corollary 4.1.35 (Counting independent lists and bases), Theorem 1.6.10 (Every spanning list contains a basis), Definition 4.1.5 (Dimension)

Techniques. Double counting (Technique 4.1.36)

Hint 1. Count the pairs

(𝑈, ℒ︀)

, where

𝑈

is a

𝑘

-dimensional subspace of

𝑉

and

ℒ︀

is a basis of

𝑈

Hint 2. Counted by

𝑈

first: each

𝑈

has

𝑁_{𝑞} (𝑘, 𝑘)

bases. Counted by

ℒ︀

first: which lists

ℒ︀

occur, and in how many pairs?

Sketch. Let

𝑃

be the set of pairs

(𝑈, ℒ︀)

with

dim 𝑈 = 𝑘

and

ℒ︀

a basis of

𝑈

. Each

𝑘

-dimensional

𝑈

has

𝑁_{𝑞} (𝑘, 𝑘)

bases (Corollary 4.1.35 applied to

𝑈

), so

| 𝑃 | =

𝑠 \cdot

𝑁_{𝑞} (𝑘, 𝑘)

, where

𝑠

is the number of subspaces. Each independent list

ℒ︀

of length

𝑘

𝑉

occurs in exactly one pair, with

𝑈 = span (ℒ︀)

, so

| 𝑃 | = 𝑁_{𝑞} (𝑛, 𝑘)

Let $𝑠$ be the number of $𝑘$ -dimensional subspaces of $𝑉$ , and let $𝑃$ be the set of pairs $(𝑈, ℒ︀)$ in which $𝑈$ is a $𝑘$ -dimensional subspace of $𝑉$ and $ℒ︀$ is a basis of $𝑈$ . We count $𝑃$ in two ways.

By subspaces. A $𝑘$ -dimensional subspace $𝑈$ is a vector space over $𝐹$ of dimension $𝑘$ , so by Corollary 4.1.35 it has $𝑁_{𝑞} (𝑘, 𝑘)$ bases. Hence $| 𝑃 | =$ $𝑠 \cdot$ $𝑁_{𝑞} (𝑘, 𝑘)$ .

By lists. If $(𝑈, ℒ︀) \in 𝑃$ , then $ℒ︀$ is an independent list of length $𝑘$ in $𝑉$ , and $𝑈 = span (ℒ︀)$ is determined by $ℒ︀$ . Conversely, every independent list $ℒ︀$ of length $𝑘$ in $𝑉$ is a basis of the subspace $span (ℒ︀)$ (Theorem 1.6.10), which then has dimension $𝑘$ , so $(span (ℒ︀), ℒ︀) \in 𝑃$ . So the pairs in $𝑃$ correspond to the independent lists of length $𝑘$ in $𝑉$ , and $| 𝑃 | = 𝑁_{𝑞} (𝑛, 𝑘)$ by Corollary 4.1.35.

Comparing, $𝑠 \cdot$ $𝑁_{𝑞} (𝑘, 𝑘) =$ $𝑁_{𝑞} (𝑛, 𝑘)$ . Since $𝑁_{𝑞} (𝑘, 𝑘) \geq 1$ (a $𝑘$ -dimensional space has a basis), we may divide. □

Example 4.1.38 (The subspaces of $𝔽_{2}^{3}$ ). For $𝑞 = 2$ and $𝑛 = 3$ : the number of $1$ -dimensional subspaces is $𝑁_{2} (3, 1) / 𝑁_{2} (1, 1) =$ $7 / 1 =$ $7$ , one for each nonzero vector, since a line over $𝔽_{2}$ is ${𝟎, 𝐯}$ . The number of $2$ -dimensional subspaces is

𝑁_{2} \frac{3, 2}{𝑁_{2}} (2, 2) = \frac{7 \cdot 6}{3 \cdot 2} = 7 .

Each plane has $2^{2} = 4$ elements and contains $3$ of the $7$ lines. Taking the $7$ lines as points and the $7$ planes as lines, with “lies in” as incidence, gives the Fano plane of combinatorics.

Exercise 4.1.39.routine (a) Can a vector space over

𝔽_{5}

have exactly

100

elements? (b) How many elements does a

3

-dimensional subspace of

𝔽_{5}^{7}

have? (c) How many bases does

𝔽_{3}^{2}

have?

Solution.

Uses. Proposition 4.1.34 (Size of a vector space over a finite field), Corollary 4.1.35 (Counting independent lists and bases)

Hint 1. By Proposition 4.1.34, a finite vector space over

𝔽_{5}

has

5^{𝑛}

elements for some

𝑛

Hint 2. For (c), use

𝑁_{3} (2, 2) =

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

Sketch. (a) No:

100

is not a power of

5

. (b)

5^{3} = 125

. (c)

(9 - 1) (9 - 3) = 48

(a) No. A vector space over $𝔽_{5}$ with finitely many elements is finite-dimensional, so it has $5^{dim 𝑉}$ elements by Proposition 4.1.34, and $100 = 2^{2} \cdot 5^{2}$ is not a power of $5$ .

(b) A $3$ -dimensional subspace is a $3$ -dimensional vector space over $𝔽_{5}$ , so it has $5^{3} = 125$ elements.

(c) By Corollary 4.1.35, $𝔽_{3}^{2}$ has $𝑁_{3} (2, 2) =$ $(9 - 1) (9 - 3) =$ $48$ bases.

Exercises

Exercise 4.1.40.routine Find a basis and the dimension of each subspace.

(a) $𝑈_{1} =$ ${𝐱 \in 𝐹^{4} | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} + 𝑥_{4} = 0}$ .
(b) $𝑈_{2} =$ ${𝑝 \in {𝐹 [𝑥]}_{\leq 3} | 𝑝 (0) = 𝑝 (1) = 0}$ .
(c) $𝑈_{3}$ , the upper triangular matrices in $𝐹^{3 \times 3}$ , those with $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ .

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.5.24 (Distinct degrees), Corollary 1.5.17 (Sublists), Proposition 1.6.7 (Standard bases)

Hint 1. In each case solve the defining conditions for some of the coordinates and write a general element as a combination of fixed vectors with the remaining coordinates as coefficients.

Hint 2. In (a),

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

. In (b),

𝑝 (0)

is the constant term and

𝑝 (1)

is the sum of the coefficients. In (c), use matrix units.

Sketch. (a)

𝐱 =

𝑥_{1} (𝐞_{1} - 𝐞_{4}) +

𝑥_{2} (𝐞_{2} - 𝐞_{4}) +

𝑥_{3} (𝐞_{3} - 𝐞_{4})

; dimension

3

. (b)

𝑝 =

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

𝑎_{3} (𝑥^{3} - 𝑥)

; dimension

2

. (c) The six

𝑈_{𝑖 𝑗}

with

𝑖 \leq 𝑗

; dimension

6

(a) For $𝐱 \in 𝑈_{1}$ we have $𝑥_{4} = - 𝑥_{1} - 𝑥_{2} - 𝑥_{3}$ , so

𝐱 = 𝑥_{1} (𝐞_{1} - 𝐞_{4}) + 𝑥_{2} (𝐞_{2} - 𝐞_{4}) + 𝑥_{3} (𝐞_{3} - 𝐞_{4}) .

The three vectors $𝐞_{𝑖} - 𝐞_{4}$ lie in $𝑈_{1}$ , so they span $𝑈_{1}$ . A combination $\sum_{𝑖 = 1}^{3} 𝑐_{𝑖} (𝐞_{𝑖} - 𝐞_{4})$ has first three coordinates $𝑐_{1}, 𝑐_{2}, 𝑐_{3}$ , so it is $𝟎$ only if all $𝑐_{𝑖} = 0$ . So they form a basis (Proposition 1.6.2), and $dim 𝑈_{1} = 3$ .

(b) Let $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2} +$ $𝑎_{3} 𝑥^{3}$ . Then $𝑝 (0) = 𝑎_{0}$ and $𝑝 (1) =$ $𝑎_{0} +$ $𝑎_{1} +$ $𝑎_{2} +$ $𝑎_{3}$ , so $𝑝 \in 𝑈_{2}$ if and only if $𝑎_{0} = 0$ and $𝑎_{1} = - 𝑎_{2} - 𝑎_{3}$ , that is,

𝑝 = 𝑎_{2} (𝑥^{2} - 𝑥) + 𝑎_{3} (𝑥^{3} - 𝑥) .

So $𝑥^{2} - 𝑥, 𝑥^{3} - 𝑥$ spans $𝑈_{2}$ , and it is independent because its entries are nonzero with distinct degrees (Proposition 1.5.24). Hence $dim 𝑈_{2} = 2$ .

(c) An upper triangular $𝐴$ is $\sum_{𝑖 \leq 𝑗} 𝑎_{𝑖 𝑗} 𝑈_{𝑖 𝑗}$ , so the six matrix units $𝑈_{11},$ $𝑈_{12},$ $𝑈_{13},$ $𝑈_{22},$ $𝑈_{23},$ $𝑈_{33}$ span $𝑈_{3}$ . They are a sublist of the standard basis of $𝐹^{3 \times 3}$ (Proposition 1.6.7), hence independent (Corollary 1.5.17). So $dim 𝑈_{3} = 6$ .

Exercise 4.1.41.routine Let $𝑉$ be a vector space with $dim 𝑉 = 4$ . Prove or disprove each statement.

(a)Every list of $5$ vectors in $𝑉$ spans $𝑉$ .
(b)Every list of $3$ vectors in $𝑉$ is linearly independent.
(c)If $𝐯_{1}, \dots, 𝐯_{4}$ spans $𝑉$ , then it is linearly independent.
(d)If $𝑈$ and $𝑊$ are subspaces of $𝑉$ with $dim 𝑈 = dim 𝑊$ , then $𝑈 = 𝑊$ .
(e)If $𝑈 \subseteq 𝑊$ are subspaces of $𝑉$ with $dim 𝑈 = dim 𝑊$ , then $𝑈 = 𝑊$ .
(f) $ℝ^{2}$ is a $2$ -dimensional subspace of $ℝ^{3}$ .

Solution.

Uses. Corollary 4.1.11 (Spanning lists are long), Proposition 4.1.21 (Dimensions of subspaces), Proposition 1.5.15 (Short lists, zeros, and repeats), Definition 1.4.1 (Subspace)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Length alone can force a property only in one direction: a list longer than

dim 𝑉

cannot be independent, and a list shorter than

dim 𝑉

cannot span. It never forces a list to span or to be independent.

Hint 2. For (d), think of two different lines in a plane. For (e), apply Proposition 4.1.21(b) inside

𝑊

. For (f), what are the elements of

ℝ^{2}

Sketch. (a) False: five copies of

𝟎

. (b) False: three copies of

𝟎

. (c) True by Corollary 4.1.11(b). (d) False: two different

1

-dimensional subspaces. (e) True:

𝑈

is a subspace of the vector space

𝑊

of full dimension. (f) False:

ℝ^{2}

is not a subset of

ℝ^{3}

, though

{(𝑥, 𝑦, 0)}

is a

2

-dimensional subspace.

(a) False. The list $𝟎, 𝟎, 𝟎, 𝟎, 𝟎$ spans ${𝟎} \neq 𝑉$ .

(b) False. The list $𝟎, 𝟎, 𝟎$ is dependent (Proposition 1.5.15(c)).

(c) True. A spanning list of length $4 = dim 𝑉$ is a basis by Corollary 4.1.11(b), so it is independent.

(d) False. Let $𝐯_{1}, \dots, 𝐯_{4}$ be a basis of $𝑉$ . Then $span (𝐯_{1})$ and $span (𝐯_{2})$ are both $1$ -dimensional, and they differ, since $𝐯_{2} \notin span (𝐯_{1})$ by independence.

(e) True. $𝑊$ is a vector space with the operations of $𝑉$ , and $𝑈$ is a subspace of $𝑊$ : it is a subset closed under the same operations (Definition 1.4.1). Since $dim 𝑈 = dim 𝑊$ , Proposition 4.1.21(b), applied in $𝑊$ , gives $𝑈 = 𝑊$ .

(f) False. The elements of $ℝ^{2}$ are pairs and those of $ℝ^{3}$ are triples, so $ℝ^{2}$ is not a subset of $ℝ^{3}$ . The subset ${(𝑥, 𝑦, 0) | 𝑥, 𝑦 \in ℝ}$ is a $2$ -dimensional subspace of $ℝ^{3}$ , with basis $𝐞_{1}, 𝐞_{2}$ , and it is a copy of $ℝ^{2}$ in a sense made precise in Section 4.5.

Exercise 4.1.42.routine Let

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

and

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

. Extend

𝐯_{1}, 𝐯_{2}

to a basis of

𝐹^{4}

by sifting the list

𝐯_{1},

𝐯_{2},

𝐞_{1},

𝐞_{2},

𝐞_{3},

𝐞_{4}

, first for

𝐹 = ℚ

and then for

𝐹 = 𝔽_{3}

. Explain why the answers differ.

Solution.

Uses. Theorem 4.1.16 (Extending to a basis), Proposition 1.5.14 (Appending a vector), Theorem 4.1.10 (Independent lists are short)

Hint 1. The span of

𝐯_{1}, 𝐯_{2}

consists of the vectors

(𝑏, 0, 𝑎 + 2 𝑏, 2 𝑎 + 𝑏)

. Is

𝐞_{1}

of this form?

Hint 2. For

𝐞_{1}

you need

𝑏 = 1

𝑎 = - 2

, and

2 𝑎 + 𝑏 = 0

, that is,

- 3 = 0

. Which field allows this? Stop sifting as soon as you have

4

vectors.

Sketch.

𝐞_{1} \in span (𝐯_{1}, 𝐯_{2})

exactly when

3 = 0

; indeed

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

, which is

𝐞_{1}

𝔽_{3}^{4}

. Over

ℚ

sifting keeps

𝐞_{1}

and

𝐞_{2}

(all of

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

has second coordinate

0

). Over

𝔽_{3}

it deletes

𝐞_{1}

and keeps

𝐞_{2}

and

𝐞_{3}

The vectors $𝐯_{1}, 𝐯_{2}$ are independent over every field, since $𝑎 𝐯_{1} +$ $𝑏 𝐯_{2} =$ $(𝑏, 0, 𝑎 + 2 𝑏, 2 𝑎 + 𝑏)$ is $𝟎$ only if $𝑏 = 0$ and then $𝑎 = 0$ . Their span consists of the vectors $(𝑏, 0, 𝑎 + 2 𝑏, 2 𝑎 + 𝑏)$ .

Is $𝐞_{1}$ in the span? We need $𝑏 = 1$ , $𝑎 + 2 = 0$ , and $2 𝑎 + 1 = 0$ . The second gives $𝑎 = - 2$ , and then the third reads $- 3 = 0$ . Over $ℚ$ this is false, so $𝐞_{1}$ is kept. Over $𝔽_{3}$ it is true, and indeed $𝐯_{1} +$ $𝐯_{2} =$ $(1, 0, 3, 3) =$ $𝐞_{1}$ there, so $𝐞_{1}$ is deleted.

Over $ℚ$ . The vectors of $span (𝐯_{1}, 𝐯_{2}, 𝐞_{1})$ have second coordinate $0$ , so $𝐞_{2}$ is not among them and is kept. Now $𝐯_{1}, 𝐯_{2}, 𝐞_{1}, 𝐞_{2}$ is independent (Proposition 1.5.14) of length $4 = dim ℚ^{4}$ , so it is a basis (Theorem 4.1.10(b)), and $𝐞_{3}, 𝐞_{4}$ are deleted.

Over $𝔽_{3}$ . Again $𝐞_{2}$ is kept, because every vector of $span (𝐯_{1}, 𝐯_{2})$ has second coordinate $0$ . The span of $𝐯_{1}, 𝐯_{2}, 𝐞_{2}$ consists of the vectors $(𝑏, 𝑑, 𝑎 + 2 𝑏, 2 𝑎 + 𝑏)$ . For $𝐞_{3} = (0, 0, 1, 0)$ we would need $𝑏 = 0$ , $𝑎 = 1$ , and $2 𝑎 = 0$ , which is false in $𝔽_{3}$ . So $𝐞_{3}$ is kept, and $𝐯_{1}, 𝐯_{2}, 𝐞_{2}, 𝐞_{3}$ is a basis of $𝔽_{3}^{4}$ .

The answers differ because whether a vector lies in a span is a question about solving linear equations, and here the equations are solvable exactly when $3 = 0$ in $𝐹$ .

Exercise 4.1.43.routine Let

𝑛 \geq 1

. Show that the trace-zero matrices

𝑈 =

{𝐴 \in 𝐹^{𝑛 \times 𝑛} | tr 𝐴 = 0}

form a subspace of dimension

𝑛^{2} - 1

, and find a basis of

𝑈

Solution.

Uses. Example 1.4.11 (Matrices), Theorem 4.1.10 (Independent lists are short), Proposition 4.1.21 (Dimensions of subspaces), Proposition 1.6.7 (Standard bases)

Hint 1. Generalize Example 4.1.22. Which matrix units lie in

𝑈

, and which combinations of diagonal ones do?

Hint 2. Use

𝑈_{𝑖 𝑗}

for

𝑖 \neq 𝑗

and

𝑈_{𝑖 𝑖} - 𝑈_{𝑛 𝑛}

for

𝑖 < 𝑛

to get a lower bound, and

𝑈_{11} \notin 𝑈

for an upper bound.

Sketch. The

𝑛^{2} - 𝑛

matrices

𝑈_{𝑖 𝑗}

(

𝑖 \neq 𝑗

) and the

𝑛 - 1

matrices

𝑈_{𝑖 𝑖} - 𝑈_{𝑛 𝑛}

(

𝑖 < 𝑛

) lie in

𝑈

and are independent, since a combination of them has these coefficients as its off-diagonal and first

𝑛 - 1

diagonal entries. So

dim 𝑈 \geq 𝑛^{2} - 1

. Since

tr 𝑈_{11} = 1

𝑈 \neq 𝐹^{𝑛 \times 𝑛}

, so

dim 𝑈 < 𝑛^{2}

. Hence

dim 𝑈 = 𝑛^{2} - 1

and the list is a basis.

$𝑈$ is a subspace by Example 1.4.11. The $𝑛^{2} - 𝑛$ matrices $𝑈_{𝑖 𝑗}$ with $𝑖 \neq 𝑗$ have trace $0$ , and so do the $𝑛 - 1$ matrices $𝑈_{𝑖 𝑖} - 𝑈_{𝑛 𝑛}$ with $1 \leq 𝑖 < 𝑛$ . Consider a combination

𝐴 = \sum_{𝑖 \neq 𝑗} 𝑎_{𝑖 𝑗} 𝑈_{𝑖 𝑗} + \sum_{𝑖 = 1}^{𝑛 - 1} 𝑐_{𝑖} (𝑈_{𝑖 𝑖} - 𝑈_{𝑛 𝑛}) .

Its $(𝑖, 𝑗)$ entry is $𝑎_{𝑖 𝑗}$ for $𝑖 \neq 𝑗$ , its $(𝑖, 𝑖)$ entry is $𝑐_{𝑖}$ for $𝑖 < 𝑛$ , and its $(𝑛, 𝑛)$ entry is $- (𝑐_{1} + \dots + 𝑐_{𝑛 - 1})$ . If $𝐴 = 0$ , all $𝑎_{𝑖 𝑗}$ and $𝑐_{𝑖}$ are $0$ . So these $𝑛^{2} - 1$ matrices form an independent list in $𝑈$ , and $dim 𝑈 \geq 𝑛^{2} - 1$ by Theorem 4.1.10(a), applied in $𝑈$ . On the other hand, $tr 𝑈_{11} = 1 \neq 0$ , so $𝑈 \neq 𝐹^{𝑛 \times 𝑛}$ and $dim 𝑈 < 𝑛^{2}$ by Proposition 4.1.21(b). Hence $dim 𝑈 = 𝑛^{2} - 1$ , and the independent list above, of length $dim 𝑈$ , is a basis of $𝑈$ (Theorem 4.1.10(b)). For $𝑛 = 1$ the list is empty and $𝑈 = {0}$ .

Exercise 4.1.44.routine Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

with

𝐴^{𝑚} = 0

for some

𝑚 \geq 1

. Show that

𝐼_{𝑛} - 𝐴

is invertible with inverse

𝐼_{𝑛} +

𝐴 +

𝐴^{2} +

\dots +

𝐴^{𝑛 - 1}

, however large

𝑚

is.

Solution.

Uses. Corollary 4.1.27 (A nilpotent operator dies within $dim 𝑉$ steps), Proposition 2.4.14 (Algebra of matrices), Definition 2.5.12 (Invertible)

Hint 1. First replace

𝑚

𝑛

using Corollary 4.1.27.

Hint 2. Multiply out

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

; the sum telescopes.

Sketch. By Corollary 4.1.27,

𝐴^{𝑛} = 0

. Then

(𝐼_{𝑛} - 𝐴) (𝐼_{𝑛} + 𝐴 + \dots + 𝐴^{𝑛 - 1}) =

𝐼_{𝑛} -

𝐴^{𝑛} =

𝐼_{𝑛}

, and the product in the other order telescopes in the same way.

By Corollary 4.1.27, $𝐴^{𝑛} = 0$ . Let $𝐵 =$ $𝐼_{𝑛} +$ $𝐴 +$ $\dots +$ $𝐴^{𝑛 - 1}$ . By distributivity (Proposition 2.4.14),

(𝐼_{𝑛} - 𝐴) 𝐵 = (𝐼_{𝑛} + 𝐴 + \dots + 𝐴^{𝑛 - 1}) - (𝐴 + 𝐴^{2} + \dots + 𝐴^{𝑛}) = 𝐼_{𝑛} - 𝐴^{𝑛} = 𝐼_{𝑛},

and in the same way $𝐵 (𝐼_{𝑛} - 𝐴) =$ $𝐼_{𝑛} -$ $𝐴^{𝑛} =$ $𝐼_{𝑛}$ , since $𝐴$ commutes with its powers. So $𝐵$ is a two-sided inverse of $𝐼_{𝑛} - 𝐴$ (Definition 2.5.12). Exercise 2.5.39 gave the inverse $𝐼_{𝑛} + 𝐴 + \dots + 𝐴^{𝑚 - 1}$ ; the point here is that the terms from $𝐴^{𝑛}$ on are all $0$ , so at most $𝑛$ terms are needed.

Exercise 4.1.45.routine Let $𝑋$ be a set, and for $𝑥 \in 𝑋$ let $𝛿_{𝑥} \in 𝐹^{𝑋}$ be the function with $𝛿_{𝑥} (𝑥) = 1$ and $𝛿_{𝑥} (𝑦) = 0$ for $𝑦 \neq 𝑥$ .

(a)If $𝑋 = {𝑥_{1}, \dots, 𝑥_{𝑛}}$ has $𝑛$ elements, show that $𝛿_{𝑥_{1}}, \dots, 𝛿_{𝑥_{𝑛}}$ is a basis of $𝐹^{𝑋}$ , so $dim 𝐹^{𝑋} = 𝑛$ .
(b)If $𝑋$ is infinite, show that $𝐹^{𝑋}$ is infinite-dimensional.

Solution.

Uses. Definition 1.2.9 (Function spaces), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.6.2 (Bases are independent spanning lists), Corollary 4.1.13 (Detecting infinite dimension)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. To show that

𝛿_{𝑥_{1}}, \dots, 𝛿_{𝑥_{𝑘}}

is independent for distinct points, evaluate a relation at

𝑥_{𝑗}

. Which terms survive?

Hint 2. For spanning in (a), compare

𝑓

with

\sum_{𝑖} 𝑓 (𝑥_{𝑖}) 𝛿_{𝑥_{𝑖}}

at each point. For (b), use Corollary 4.1.13.

Sketch. For distinct

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

, evaluating

\sum 𝑎_{𝑖} 𝛿_{𝑥_{𝑖}} = 0

𝑥_{𝑗}

kills every term but the

𝑗

-th and gives

𝑎_{𝑗} = 0

. In (a),

𝑓 =

\sum_{𝑖} 𝑓 (𝑥_{𝑖}) 𝛿_{𝑥_{𝑖}}

because both sides agree at every

𝑥_{𝑗}

. In (b),

𝑋

has

𝑘

distinct points for every

𝑘

, so

𝐹^{𝑋}

has independent lists of every length.

Let $𝑥_{1}, \dots, 𝑥_{𝑘} \in 𝑋$ be distinct, and suppose $\sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝛿_{𝑥_{𝑖}} =$ $0$ , the zero function. Evaluating at $𝑥_{𝑗}$ , and using that $𝛿_{𝑥_{𝑖}} (𝑥_{𝑗})$ is $1$ for $𝑖 = 𝑗$ and $0$ for $𝑖 \neq 𝑗$ , gives $𝑎_{𝑗} = 0$ . So $𝛿_{𝑥_{1}}, \dots, 𝛿_{𝑥_{𝑘}}$ is independent (Theorem 1.5.5). Evaluation at $𝑥_{𝑗}$ is a linear map $𝐹^{𝑋} \to 𝐹$ that kills every $𝛿_{𝑥_{𝑖}}$ except $𝛿_{𝑥_{𝑗}}$ , which is the move of Technique 4.1.25.

(a) For $𝑓 \in 𝐹^{𝑋}$ , the function $𝑔 =$ $\sum_{𝑖 = 1}^{𝑛} 𝑓 (𝑥_{𝑖}) 𝛿_{𝑥_{𝑖}}$ satisfies $𝑔 (𝑥_{𝑗}) = 𝑓 (𝑥_{𝑗})$ for every $𝑗$ , so $𝑔 = 𝑓$ . So $𝛿_{𝑥_{1}}, \dots, 𝛿_{𝑥_{𝑛}}$ spans $𝐹^{𝑋}$ , and with the independence above it is a basis (Proposition 1.6.2). Hence $dim 𝐹^{𝑋} = 𝑛$ . For $𝑋 = {1, \dots, 𝑛}$ , these functions are the standard basis vectors of $𝐹^{𝑛}$ (Remark 1.2.11).

(b) If $𝑋$ is infinite, then for every $𝑘$ it contains $𝑘$ distinct points, and the corresponding $𝛿$ ’s form an independent list of length $𝑘$ . By Corollary 4.1.13, $𝐹^{𝑋}$ is infinite-dimensional.

Exercise 4.1.46.standard Let $𝑛 \geq 1$ . In $𝐹^{𝑛 \times 𝑛}$ , let $𝑆$ be the symmetric matrices ( $𝑎_{𝑖 𝑗} = 𝑎_{𝑗 𝑖}$ for all $𝑖, 𝑗$ ) and $𝐾$ the skew-symmetric matrices ( $𝑎_{𝑖 𝑗} = - 𝑎_{𝑗 𝑖}$ for all $𝑖, 𝑗$ ), as in Exercise 1.4.36.

(a)Show that $dim 𝑆 = 𝑛 (𝑛 + 1) / 2$ .
(b)Show that $dim 𝐾 = 𝑛 (𝑛 - 1) / 2$ if $1 + 1 \neq 0$ in $𝐹$ , and $dim 𝐾 = 𝑛 (𝑛 + 1) / 2$ if $1 + 1 = 0$ .

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.1.17 (No zero divisors)

Hint 1. A symmetric matrix is determined by its entries on and above the diagonal. Find one matrix in

𝑆

for each such position.

Hint 2. For

𝐾

, look at the diagonal:

𝑎_{𝑖 𝑖} = - 𝑎_{𝑖 𝑖}

means

(1 + 1) 𝑎_{𝑖 𝑖} = 0

. When

1 + 1 = 0

, compare the conditions defining

𝑆

and

𝐾

Sketch. (a) Basis

𝑈_{𝑖 𝑖}

(

1 \leq 𝑖 \leq 𝑛

) and

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

(

𝑖 < 𝑗

𝑛 + 𝑛 (𝑛 - 1) / 2

matrices. (b) If

1 + 1 \neq 0

, the diagonal of a skew-symmetric matrix is

0

, and

𝑈_{𝑖 𝑗} - 𝑈_{𝑗 𝑖}

(

𝑖 < 𝑗

) is a basis. If

1 + 1 = 0

, then

- 𝑎 = 𝑎

for all

𝑎

, so

𝐾 = 𝑆

(a) If $𝐴 \in 𝑆$ , then

𝐴 = \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝑖} 𝑈_{𝑖 𝑖} + \sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} (𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}),

since both sides have $(𝑖, 𝑗)$ entry $𝑎_{𝑖 𝑗}$ for $𝑖 \leq 𝑗$ , and $(𝑗, 𝑖)$ entry $𝑎_{𝑖 𝑗} = 𝑎_{𝑗 𝑖}$ for $𝑖 < 𝑗$ . The matrices $𝑈_{𝑖 𝑖}$ and $𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}$ ( $𝑖 < 𝑗$ ) are symmetric, so they span $𝑆$ . A combination $\sum_{𝑖} 𝑐_{𝑖 𝑖} 𝑈_{𝑖 𝑖} +$ $\sum_{𝑖 < 𝑗} 𝑐_{𝑖 𝑗} (𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖})$ has $(𝑖, 𝑗)$ entry $𝑐_{𝑖 𝑗}$ for $𝑖 \leq 𝑗$ , so it is $0$ only if all coefficients are $0$ . So these matrices form a basis of $𝑆$ , and

dim 𝑆 = 𝑛 + 𝑛 \frac{𝑛 - 1}{2} = 𝑛 \frac{𝑛 + 1}{2} .

(b) Suppose $1 + 1 \neq 0$ . For $𝐴 \in 𝐾$ , $𝑎_{𝑖 𝑖} = - 𝑎_{𝑖 𝑖}$ gives $(1 + 1) 𝑎_{𝑖 𝑖} = 0$ , so $𝑎_{𝑖 𝑖} = 0$ (Proposition 1.1.17). Then $𝐴 =$ $\sum_{𝑖 < 𝑗} 𝑎_{𝑖 𝑗} (𝑈_{𝑖 𝑗} - 𝑈_{𝑗 𝑖})$ , as both sides have $(𝑖, 𝑗)$ entry $𝑎_{𝑖 𝑗}$ and $(𝑗, 𝑖)$ entry $- 𝑎_{𝑖 𝑗} = 𝑎_{𝑗 𝑖}$ for $𝑖 < 𝑗$ , and zero diagonal. The matrices $𝑈_{𝑖 𝑗} - 𝑈_{𝑗 𝑖}$ lie in $𝐾$ and are independent, since a combination of them has $(𝑖, 𝑗)$ entry equal to the coefficient of $𝑈_{𝑖 𝑗} - 𝑈_{𝑗 𝑖}$ for $𝑖 < 𝑗$ . So $dim 𝐾 = 𝑛 (𝑛 - 1) / 2$ .

Suppose $1 + 1 = 0$ . Then $- 1 = 1$ , so $- 𝑎_{𝑗 𝑖} = 𝑎_{𝑗 𝑖}$ and the conditions defining $𝐾$ and $𝑆$ coincide. Hence $𝐾 = 𝑆$ and $dim 𝐾 = 𝑛 (𝑛 + 1) / 2$ by (a).

Exercise 4.1.47.standard A matrix $𝐴 \in ℂ^{𝑛 \times 𝑛}$ is Hermitian if $𝑎_{𝑗 𝑖} = 𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ , where $𝑧$ is the complex conjugate of $𝑧$ (Definition B.1.1). Let $𝐻$ be the set of Hermitian matrices.

(a)Show that $𝐻$ is a subspace of $ℂ^{𝑛 \times 𝑛}$ regarded as a vector space over $ℝ$ , but not a subspace of $ℂ^{𝑛 \times 𝑛}$ over $ℂ$ .
(b)Show that ${dim}_{ℝ} 𝐻 = 𝑛^{2}$ , while ${dim}_{ℝ} ℂ^{𝑛 \times 𝑛} = 2 𝑛^{2}$ .

Solution.

Uses. Definition B.1.1 (Complex conjugate), Theorem 1.4.3 (Subspace criterion), Proposition 1.6.2 (Bases are independent spanning lists), Example 4.1.7 (Dimensions of the standard spaces)

Hint 1. Conjugation satisfies

𝑧 + 𝑤 = 𝑧 + 𝑤

and

𝑡 𝑧 = 𝑡 𝑧

for real

𝑡

, but

𝑖 𝑧 = - 𝑖 𝑧

. What does

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

say about diagonal entries?

Hint 2. For (b), a Hermitian matrix is determined by

𝑛

real diagonal entries and the complex entries above the diagonal, each of which carries two real parameters. Find a matrix in

𝐻

for each real parameter.

Sketch. (a) The conditions are preserved by sums and real multiples because conjugation is additive and fixes reals;

𝐼_{𝑛} \in 𝐻

but

𝑖 𝐼_{𝑛} \notin 𝐻

. (b) Basis over

ℝ

𝑈_{𝑘 𝑘}

, and for

𝑘 < 𝑙

both

𝑈_{𝑘 𝑙} + 𝑈_{𝑙 𝑘}

and

𝑖 (𝑈_{𝑘 𝑙} - 𝑈_{𝑙 𝑘})

𝑛 +

2 \cdot

𝑛 (𝑛 - 1) / 2 =

𝑛^{2}

matrices. And

{dim}_{ℝ} ℂ^{𝑛 \times 𝑛} =

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

2 𝑛^{2}

(a) The zero matrix is Hermitian. If $𝐴, 𝐵 \in 𝐻$ and $𝑡 \in ℝ$ , then for all $𝑖, 𝑗$ ,

{(𝐴 + 𝑡 𝐵)}_{𝑗 𝑖} = 𝑎_{𝑗 𝑖} + 𝑡 𝑏_{𝑗 𝑖} = 𝑎_{𝑖 𝑗} + 𝑡 𝑏_{𝑖 𝑗} = 𝑎_{𝑖 𝑗} + 𝑡 𝑏_{𝑖 𝑗},

since conjugation is additive and $𝑡 = 𝑡$ for real $𝑡$ . So $𝐻$ is a subspace over $ℝ$ (Theorem 1.4.3). It is not a subspace over $ℂ$ : $𝐼_{𝑛} \in 𝐻$ , but $𝑖 𝐼_{𝑛}$ has diagonal entry $𝑖$ , while a Hermitian matrix has $𝑎_{11} = 𝑎_{11}$ , so $𝑎_{11}$ is real.

(b) For $𝑘 < 𝑙$ , let $𝑋_{𝑘 𝑙} =$ $𝑈_{𝑘 𝑙} +$ $𝑈_{𝑙 𝑘}$ and $𝑌_{𝑘 𝑙} =$ $𝑖 (𝑈_{𝑘 𝑙} - 𝑈_{𝑙 𝑘})$ . These are Hermitian: the $(𝑘, 𝑙)$ and $(𝑙, 𝑘)$ entries are $1, 1$ and $𝑖, - 𝑖$ , which are conjugate pairs, and the other entries are $0$ . So are the $𝑈_{𝑘 𝑘}$ . Let $𝐴 \in 𝐻$ . Its diagonal entries are real, and for $𝑘 < 𝑙$ write $𝑎_{𝑘 𝑙} =$ $𝑥_{𝑘 𝑙} +$ $𝑖 𝑦_{𝑘 𝑙}$ with $𝑥_{𝑘 𝑙}, 𝑦_{𝑘 𝑙} \in ℝ$ , so that $𝑎_{𝑙 𝑘} =$ $𝑥_{𝑘 𝑙} -$ $𝑖 𝑦_{𝑘 𝑙}$ . Then

𝐴 = \sum_{𝑘 = 1}^{𝑛} 𝑎_{𝑘 𝑘} 𝑈_{𝑘 𝑘} + \sum_{𝑘 < 𝑙} (𝑥_{𝑘 𝑙} 𝑋_{𝑘 𝑙} + 𝑦_{𝑘 𝑙} 𝑌_{𝑘 𝑙}),

since both sides have the same $(𝑘, 𝑘)$ , $(𝑘, 𝑙)$ , and $(𝑙, 𝑘)$ entries. So these matrices span $𝐻$ over $ℝ$ . If a real combination $\sum_{𝑘} 𝑟_{𝑘} 𝑈_{𝑘 𝑘} +$ $\sum_{𝑘 < 𝑙} (𝑠_{𝑘 𝑙} 𝑋_{𝑘 𝑙} + 𝑡_{𝑘 𝑙} 𝑌_{𝑘 𝑙})$ is $0$ , its $(𝑘, 𝑘)$ entries give $𝑟_{𝑘} = 0$ , and its $(𝑘, 𝑙)$ entry $𝑠_{𝑘 𝑙} + 𝑖 𝑡_{𝑘 𝑙} = 0$ gives $𝑠_{𝑘 𝑙} = 𝑡_{𝑘 𝑙} = 0$ , because $𝑠_{𝑘 𝑙}, 𝑡_{𝑘 𝑙}$ are real. So they form a basis of $𝐻$ over $ℝ$ , and

{dim}_{ℝ} 𝐻 = 𝑛 + 2 \cdot \frac{𝑛 (𝑛 - 1)}{2} = 𝑛^{2} .

Since ${dim}_{ℂ} ℂ^{𝑛 \times 𝑛} = 𝑛^{2}$ , Example 4.1.7(c) gives ${dim}_{ℝ} ℂ^{𝑛 \times 𝑛} = 2 𝑛^{2}$ . So the Hermitian matrices are a real subspace of exactly half the real dimension.

Exercise 4.1.48.standard Find the error in the following argument, and decide whether the claim is true.

Claim. Let $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ be a basis of $𝑉$ , and let $𝑈$ be a subspace of $𝑉$ . Then the entries of $ℬ︀$ that lie in $𝑈$ form a basis of $𝑈$ .

Proof. Let ${ℬ︀}^{'}$ be the sublist of entries of $ℬ︀$ that lie in $𝑈$ . It is independent, as a sublist of an independent list. Let $𝐮 \in 𝑈$ , and write $𝐮 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐯_{𝑛}$ . Since $𝐮 \in 𝑈$ and $𝑈$ is a subspace, each term $𝑎_{𝑖} 𝐯_{𝑖}$ lies in $𝑈$ . So $𝑎_{𝑖} = 0$ whenever $𝐯_{𝑖} \notin 𝑈$ , and $𝐮 \in span ({ℬ︀}^{'})$ . Hence ${ℬ︀}^{'}$ spans $𝑈$ .

Solution.

Uses. Proposition 4.1.21 (Dimensions of subspaces), Theorem 4.1.16 (Extending to a basis)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. If a sum lies in a subspace, must its terms?

Hint 2. Try

𝑉 = ℝ^{2}

with the standard basis and

𝑈 = span ((1, 1))

Sketch. The step “each term

𝑎_{𝑖} 𝐯_{𝑖}

lies in

𝑈

” is wrong: a sum can lie in a subspace without its terms doing so. The claim is false: in

ℝ^{2}

, no standard basis vector lies in

𝑈 = span ((1, 1))

, so

{ℬ︀}^{'} = ()

, which does not span

𝑈

. What is true is the reverse: a basis of

𝑈

extends to a basis of

𝑉

(Theorem 4.1.16).

The error is the sentence “each term $𝑎_{𝑖} 𝐯_{𝑖}$ lies in $𝑈$ ”. A subspace is closed under sums, but a sum lying in $𝑈$ says nothing about its terms. For instance $(1, 0) +$ $(0, 1) \in$ $span ((1, 1))$ , while neither term is.

The claim is false. Take $𝑉 = ℝ^{2}$ , $ℬ︀ = 𝐞_{1}, 𝐞_{2}$ , and $𝑈 = span ((1, 1))$ . Neither $𝐞_{1}$ nor $𝐞_{2}$ is a multiple of $(1, 1)$ , so ${ℬ︀}^{'} = ()$ , whose span ${𝟎}$ is not $𝑈$ . A basis of $𝑉$ need not have any vectors in a given subspace, which is why the proof of Proposition 4.1.21 had to build a basis of $𝑈$ from scratch. The correct relation goes the other way: a basis of $𝑈$ can be extended to a basis of $𝑉$ (Theorem 4.1.16), so some basis of $𝑉$ contains a basis of $𝑈$ .

Exercise 4.1.49.standard Let $𝐯_{1}, \dots, 𝐯_{𝑚}$ be linearly independent in $𝑉$ , with $𝑚 \geq 1$ , and let $𝐰 \in 𝑉$ .

(a)Show that $𝐯_{1} - 𝐰, \dots, 𝐯_{𝑚} - 𝐰$ is linearly dependent if and only if $𝐰 =$ $𝑡_{1} 𝐯_{1} +$ $\dots +$ $𝑡_{𝑚} 𝐯_{𝑚}$ for some scalars with $𝑡_{1} + \dots + 𝑡_{𝑚} = 1$ .
(b)Show that $dim span (𝐯_{1} - 𝐰, \dots, 𝐯_{𝑚} - 𝐰) \geq$ $𝑚 -$ $1$ in all cases.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Theorem 4.1.10 (Independent lists are short), Lemma 1.3.9 (Arithmetic of linear combinations)

Hint 1. Rewrite

\sum_{𝑖} 𝑎_{𝑖} (𝐯_{𝑖} - 𝐰) =

𝟎

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

(\sum_{𝑖} 𝑎_{𝑖}) 𝐰

. Split into the cases

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

and

\sum_{𝑖} 𝑎_{𝑖} \neq 0

Hint 2. For (b), the differences

(𝐯_{𝑖} - 𝐰) -

(𝐯_{𝑚} - 𝐰)

lie in the span. Are they independent?

Sketch. (a) A relation

\sum 𝑎_{𝑖} (𝐯_{𝑖} - 𝐰) = 𝟎

says

\sum 𝑎_{𝑖} 𝐯_{𝑖} = 𝑠 𝐰

with

𝑠 = \sum 𝑎_{𝑖}

. If

𝑠 = 0

the relation is trivial by independence of the

𝐯_{𝑖}

; so a nontrivial one has

𝑠 \neq 0

and gives

𝐰 = \sum (𝑎_{𝑖} / 𝑠) 𝐯_{𝑖}

. Conversely, coefficients

𝑡_{𝑖}

with sum

1

give the nontrivial relation

\sum 𝑡_{𝑖} (𝐯_{𝑖} - 𝐰) =

𝐰 -

𝐰 =

𝟎

. (b) The

𝑚 - 1

vectors

𝐯_{𝑖} - 𝐯_{𝑚}

(

𝑖 < 𝑚

) lie in the span and are independent.

(a) For scalars $𝑎_{1}, \dots, 𝑎_{𝑚}$ with $𝑠 = 𝑎_{1} + \dots + 𝑎_{𝑚}$ , Lemma 1.3.9 gives

\sum_{𝑖 = 1}^{𝑚} 𝑎_{𝑖} (𝐯_{𝑖} - 𝐰) = \sum_{𝑖 = 1}^{𝑚} 𝑎_{𝑖} 𝐯_{𝑖} - 𝑠 𝐰 .

( $\Rightarrow$ ) Suppose the $𝑎_{𝑖}$ form a nontrivial relation of the list, so $\sum_{𝑖} 𝑎_{𝑖} 𝐯_{𝑖} = 𝑠 𝐰$ . If $𝑠 = 0$ , then $\sum_{𝑖} 𝑎_{𝑖} 𝐯_{𝑖} = 𝟎$ , and independence forces every $𝑎_{𝑖} = 0$ , which is false. So $𝑠 \neq 0$ , and $𝐰 =$ $\sum_{𝑖} (𝑎_{𝑖} / 𝑠) 𝐯_{𝑖}$ , where the coefficients $𝑡_{𝑖} = 𝑎_{𝑖} / 𝑠$ satisfy $\sum_{𝑖} 𝑡_{𝑖} = 𝑠 / 𝑠 = 1$ .

( $\Leftarrow$ ) If $𝐰 = \sum_{𝑖} 𝑡_{𝑖} 𝐯_{𝑖}$ with $\sum_{𝑖} 𝑡_{𝑖} = 1$ , then $\sum_{𝑖} 𝑡_{𝑖} (𝐯_{𝑖} - 𝐰) =$ $𝐰 -$ $1 𝐰 =$ $𝟎$ , and not all $𝑡_{𝑖}$ are $0$ since they sum to $1$ . So the list is dependent.

(b) Let $𝑊 =$ $span (𝐯_{1} - 𝐰, \dots, 𝐯_{𝑚} - 𝐰)$ , which is finite-dimensional. If $𝑚 = 1$ there is nothing to prove. For $𝑚 \geq 2$ and $𝑖 < 𝑚$ , the vector $𝐯_{𝑖} -$ $𝐯_{𝑚} =$ $(𝐯_{𝑖} - 𝐰) -$ $(𝐯_{𝑚} - 𝐰)$ lies in $𝑊$ . These $𝑚 - 1$ vectors are independent: if $\sum_{𝑖 < 𝑚} 𝑐_{𝑖} (𝐯_{𝑖} - 𝐯_{𝑚}) =$ $𝟎$ , then $\sum_{𝑖 < 𝑚} 𝑐_{𝑖} 𝐯_{𝑖} -$ $(\sum_{𝑖 < 𝑚} 𝑐_{𝑖}) 𝐯_{𝑚} =$ $𝟎$ , and independence of $𝐯_{1}, \dots, 𝐯_{𝑚}$ gives $𝑐_{𝑖} = 0$ for all $𝑖 < 𝑚$ . By Theorem 4.1.10(a), applied in $𝑊$ , $dim 𝑊 \geq 𝑚 - 1$ .

Geometrically, (a) says the translated list is dependent exactly when $𝐰$ lies on the affine hull of the $𝐯_{𝑖}$ , the “flat” through them (Section 4.7).

Exercise 4.1.50.standard Let $dim 𝑉 = 𝑛$ .

(a)Show that if $𝑈_{0} ⊊ 𝑈_{1} ⊊ \dots ⊊ 𝑈_{𝑘}$ are subspaces of $𝑉$ , then $𝑘 \leq 𝑛$ .
(b)Show that such a chain with $𝑘 = 𝑛$ exists, and that in every such chain $dim 𝑈_{𝑖} = 𝑖$ for all $𝑖$ . In particular $𝑈_{0} = {𝟎}$ and $𝑈_{𝑛} = 𝑉$ .

Solution.

Uses. Proposition 4.1.21 (Dimensions of subspaces), Corollary 1.5.13 (Independence, one entry at a time), Definition 1.4.1 (Subspace)

Hint 1. Each

𝑈_{𝑖 - 1}

is a subspace of

𝑈_{𝑖}

and differs from it. What does Proposition 4.1.21(b), applied in

𝑈_{𝑖}

, say about their dimensions?

Hint 2. The dimensions form a strictly increasing sequence of integers between

0

and

𝑛

. For existence, use the spans of the first

𝑖

vectors of a basis.

Sketch.

𝑈_{𝑖 - 1}

is a proper subspace of

𝑈_{𝑖}

, so

dim 𝑈_{𝑖 - 1} <

dim 𝑈_{𝑖}

. Hence

dim 𝑈_{𝑖} \geq

dim 𝑈_{0} +

𝑖 \geq

𝑖

, and

𝑘 \leq dim 𝑈_{𝑘} \leq 𝑛

. For a basis

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

, the spans

𝑈_{𝑖} =

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

increase strictly. If

𝑘 = 𝑛

, then

𝑛 \geq

dim 𝑈_{𝑛} \geq

dim 𝑈_{0} +

𝑛

forces

dim 𝑈_{0} = 0

and equality throughout.

(a) For $1 \leq 𝑖 \leq 𝑘$ , $𝑈_{𝑖 - 1}$ is a subset of $𝑈_{𝑖}$ closed under the operations, so it is a subspace of $𝑈_{𝑖}$ (Definition 1.4.1), and $𝑈_{𝑖 - 1} \neq 𝑈_{𝑖}$ . By Proposition 4.1.21, applied in the finite-dimensional space $𝑈_{𝑖}$ , $dim 𝑈_{𝑖 - 1} <$ $dim 𝑈_{𝑖}$ . So the integers $dim 𝑈_{0} <$ $dim 𝑈_{1} <$ $\dots <$ $dim 𝑈_{𝑘}$ increase strictly, which gives $dim 𝑈_{𝑖} \geq$ $dim 𝑈_{0} +$ $𝑖 \geq$ $𝑖$ . In particular $𝑘 \leq dim 𝑈_{𝑘} \leq 𝑛$ , again by Proposition 4.1.21.

(b) Let $𝐛_{1}, \dots, 𝐛_{𝑛}$ be a basis of $𝑉$ and $𝑈_{𝑖} =$ $span (𝐛_{1}, \dots, 𝐛_{𝑖})$ for $0 \leq 𝑖 \leq 𝑛$ . Then $𝑈_{𝑖 - 1} \subseteq 𝑈_{𝑖}$ , and $𝑈_{𝑖 - 1} \neq 𝑈_{𝑖}$ because $𝐛_{𝑖} \notin 𝑈_{𝑖 - 1}$ (Corollary 1.5.13). So this is a chain with $𝑘 = 𝑛$ .

Now let $𝑈_{0} ⊊ \dots ⊊ 𝑈_{𝑛}$ be any chain with $𝑘 = 𝑛$ . By (a), $𝑛 \geq$ $dim 𝑈_{𝑛} \geq$ $dim 𝑈_{0} +$ $𝑛$ , so $dim 𝑈_{0} = 0$ , and then $𝑖 \leq$ $dim 𝑈_{𝑖} \leq$ $dim 𝑈_{𝑛} -$ $(𝑛 - 𝑖) \leq$ $𝑖$ for every $𝑖$ , using the strict increase once more. So $dim 𝑈_{𝑖} = 𝑖$ . In particular $𝑈_{0} = {𝟎}$ , and $𝑈_{𝑛} = 𝑉$ by Proposition 4.1.21(b).

Exercise 4.1.51.standard Let $𝑛 \geq 0$ and let $𝐹$ be a field in which $𝑛! = 1 \cdot 2 \dots 𝑛$ is nonzero, such as $ℚ$ , $ℝ$ , $ℂ$ , or $𝔽_{𝑝}$ with $𝑝 > 𝑛$ . Let $𝐷$ be the formal derivative on $𝐹 [𝑥]$ (Example 2.1.9).

(a)Let $𝑝 \in 𝐹 [𝑥]$ have degree $𝑛$ . Show that $𝑝,$ $𝐷 𝑝,$ $𝐷^{2} 𝑝,$ $\dots,$ $𝐷^{𝑛} 𝑝$ is a basis of ${𝐹 [𝑥]}_{\leq 𝑛}$ .
(b)Show that (a) fails for $𝐹 = 𝔽_{2}$ , $𝑛 = 2$ , and $𝑝 = 𝑥^{2}$ .

Solution.

Uses. Proposition 4.1.26 (Nilpotent chains are independent), Theorem 4.1.10 (Independent lists are short), Example 2.1.9 (Maps of polynomials), Proposition 1.1.17 (No zero divisors), Proposition 1.5.15 (Short lists, zeros, and repeats)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25)

Hint 1. Show that

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

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

for

𝑗 \leq 𝑘

, and

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

for

𝑗 > 𝑘

. What are

𝐷^{𝑛} 𝑝

and

𝐷^{𝑛 + 1} 𝑝

Hint 2.

𝐷^{𝑛} 𝑝

is the constant

𝑛! 𝑎_{𝑛}

, where

𝑎_{𝑛} \neq 0

is the leading coefficient. Apply Proposition 4.1.26 with

𝑇 = 𝐷

and

𝑘 = 𝑛

, then count.

Sketch. By induction on

𝑗

𝐷^{𝑗} 𝑥^{𝑘} =

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

for

𝑗 \leq 𝑘

, so

𝐷^{𝑛} 𝑝 = 𝑛! 𝑎_{𝑛} \neq 0

and

𝐷^{𝑛 + 1} 𝑝 = 0

. By Proposition 4.1.26 the

𝑛 + 1

polynomials

𝑝, \dots, 𝐷^{𝑛} 𝑝

are independent. They lie in

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

, which has dimension

𝑛 + 1

, so they form a basis. Over

𝔽_{2}

𝐷 (𝑥^{2}) = 2 𝑥 = 0

, and the list

𝑥^{2}, 0, 0

contains

𝟎

(a) By Example 2.1.9, $𝐷 (𝑥^{𝑘}) = 𝑘 𝑥^{𝑘 - 1}$ for $𝑘 \geq 1$ and $𝐷 (1) = 0$ . By induction on $𝑗$ , $𝐷^{𝑗} (𝑥^{𝑘}) =$ $𝑘 (𝑘 - 1) \dots (𝑘 - 𝑗 + 1) 𝑥^{𝑘 - 𝑗}$ for $0 \leq 𝑗 \leq 𝑘$ ; in particular $𝐷^{𝑘} (𝑥^{𝑘}) = 𝑘!$ is a constant, and hence $𝐷^{𝑗} (𝑥^{𝑘}) = 0$ for $𝑗 > 𝑘$ .

Write $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ with $𝑎_{𝑛} \neq 0$ . By linearity, $𝐷^{𝑛} 𝑝 =$ $\sum_{𝑘} 𝑎_{𝑘} 𝐷^{𝑛} (𝑥^{𝑘}) =$ $𝑛! 𝑎_{𝑛}$ , since the terms with $𝑘 < 𝑛$ vanish. This is nonzero, since $𝑛! \neq 0$ and $𝑎_{𝑛} \neq 0$ (Proposition 1.1.17). And $𝐷^{𝑛 + 1} 𝑝 =$ $𝐷 (𝑛! 𝑎_{𝑛}) =$ $0$ . By Proposition 4.1.26, applied to $𝑇 = 𝐷 \in L (𝐹 [𝑥])$ , $𝐯 = 𝑝$ , and $𝑘 = 𝑛$ , the list $𝑝, 𝐷 𝑝, \dots, 𝐷^{𝑛} 𝑝$ is independent. Each $𝐷^{𝑗} 𝑝$ has degree at most $𝑛$ , so the list lies in ${𝐹 [𝑥]}_{\leq 𝑛}$ . It has $𝑛 + 1 = dim {𝐹 [𝑥]}_{\leq 𝑛}$ entries, so it is a basis by Theorem 4.1.10(b).

(b) Over $𝔽_{2}$ , $𝐷 (𝑥^{2}) = 2 𝑥 = 0$ , so the list is $𝑥^{2}, 0, 0$ . It contains $𝟎$ , so it is dependent (Proposition 1.5.15(c)). Here $2! = 2 = 0$ , so the hypothesis fails, and the chain from $𝑥^{2}$ reaches $𝟎$ after one step instead of two.

Exercise 4.1.52.standard Let $dim 𝑉 = 𝑛 \geq 1$ , and let $𝑇 \in L (𝑉)$ satisfy $𝑇^{𝑛 - 1} \neq 0$ and $𝑇^{𝑛} = 0$ .

(a)Show that there is $𝐯 \in 𝑉$ such that $𝐯,$ $𝑇 𝐯,$ $\dots,$ $𝑇^{𝑛 - 1} 𝐯$ is a basis of $𝑉$ .
(b)Find the matrix of $𝑇$ with respect to the basis $ℬ︀ =$ $𝑇^{𝑛 - 1} 𝐯,$ $\dots,$ $𝑇 𝐯,$ $𝐯$ .

Solution.

Uses. Proposition 4.1.26 (Nilpotent chains are independent), Theorem 4.1.10 (Independent lists are short), Definition 2.3.1 (Matrix of a linear map), (1.6.1)

Hint 1. Since

𝑇^{𝑛 - 1} \neq 0

, some

𝐯

has

𝑇^{𝑛 - 1} 𝐯 \neq 𝟎

. What is

𝑇^{𝑛} 𝐯

Hint 2. For (b), write

𝐛_{𝑖} = 𝑇^{𝑛 - 𝑖} 𝐯

and compute

𝑇 𝐛_{𝑖}

in terms of the

𝐛

’s. The

𝑖

-th column of the matrix is

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

Sketch. (a) Choose

𝐯

with

𝑇^{𝑛 - 1} 𝐯 \neq 𝟎

; since

𝑇^{𝑛} 𝐯 = 𝟎

, the chain

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

is independent (Proposition 4.1.26) of length

𝑛

, hence a basis. (b) With

𝐛_{𝑖} = 𝑇^{𝑛 - 𝑖} 𝐯

𝑇 𝐛_{1} = 𝟎

and

𝑇 𝐛_{𝑖} = 𝐛_{𝑖 - 1}

for

𝑖 \geq 2

. So the matrix has

1

′s just above the diagonal and

0

′s elsewhere.

(a) Since $𝑇^{𝑛 - 1} \neq 0$ , there is $𝐯 \in 𝑉$ with $𝑇^{𝑛 - 1} 𝐯 \neq 𝟎$ , and $𝑇^{𝑛} 𝐯 = 𝟎$ . By Proposition 4.1.26 with $𝑘 = 𝑛 - 1$ , the list $𝐯,$ $𝑇 𝐯,$ $\dots,$ $𝑇^{𝑛 - 1} 𝐯$ is independent. It has $𝑛 = dim 𝑉$ entries, so it is a basis (Theorem 4.1.10(b)).

(b) The list $ℬ︀$ is a reordering of the basis in (a), so it is a basis. Write $𝐛_{𝑖} = 𝑇^{𝑛 - 𝑖} 𝐯$ for $1 \leq 𝑖 \leq 𝑛$ . Then $𝑇 𝐛_{1} = 𝑇^{𝑛} 𝐯 = 𝟎$ , and $𝑇 𝐛_{𝑖} =$ $𝑇^{𝑛 - 𝑖 + 1} 𝐯 =$ $𝐛_{𝑖 - 1}$ for $2 \leq 𝑖 \leq 𝑛$ . So ${[𝑇 𝐛_{1}]}_{ℬ︀} = 𝟎$ and, by (1.6.1), ${[𝑇 𝐛_{𝑖}]}_{ℬ︀} = 𝐞_{𝑖 - 1}$ for $𝑖 \geq 2$ . These are the columns of ${[𝑇]}_{ℬ︀ ℬ︀}$ (Definition 2.3.1), so

{[𝑇]}_{ℬ︀ ℬ︀} = (\begin{matrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \\ 0 & 0 & 0 & \dots & 0 \end{matrix}),

the matrix with $1$ in positions $(𝑖, 𝑖 + 1)$ and $0$ elsewhere. It is the matrix of the shift $𝑁$ from the start of Section 4.1.7, so every such $𝑇$ looks like the shift in a suitable basis. This is the simplest case of the Jordan form (Section 10.3).

Exercise 4.1.53.standard

(a)What fraction of the matrices in $𝔽_{2}^{3 \times 3}$ are invertible?
(b)Show that for every $𝑛 \geq 1$ , more than a quarter of the matrices in $𝔽_{2}^{𝑛 \times 𝑛}$ are invertible.

Solution.

Uses. Corollary 4.1.35 (Counting independent lists and bases), Theorem 3.5.14 (Third Fundamental Theorem, completed), Proposition 4.1.34 (Size of a vector space over a finite field)

Hint 1. A matrix is invertible exactly when its columns form a basis (Theorem 3.5.14), so there are

𝑁_{2} (𝑛, 𝑛)

invertible matrices out of

2^{𝑛^{2}}

Hint 2. Write the fraction as

\prod_{𝑗 = 1}^{𝑛} (1 - 2^{- 𝑗})

. Keep the factor

1 / 2

and bound the rest with

\prod (1 - 𝑎_{𝑗}) \geq 1 - \sum 𝑎_{𝑗}

for

0 \leq 𝑎_{𝑗} \leq 1

Sketch. (a)

168 / 512 = 21 / 64

. (b) The fraction is

\prod_{𝑖 = 0}^{𝑛 - 1} (2^{𝑛} - 2^{𝑖}) / 2^{𝑛} =

\prod_{𝑗 = 1}^{𝑛} (1 - 2^{- 𝑗})

. By induction,

\prod (1 - 𝑎_{𝑗}) \geq 1 - \sum 𝑎_{𝑗}

when all

𝑎_{𝑗} \in [0, 1]

, so

\prod_{𝑗 = 2}^{𝑛} (1 - 2^{- 𝑗}) \geq

1 -

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

1 / 2

, and the fraction exceeds

1 / 4

By Theorem 3.5.14, $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is invertible if and only if its columns form a basis of $𝐹^{𝑛}$ , and $𝐴$ is determined by its list of columns. So by Corollary 4.1.35 there are $𝑁_{2} (𝑛, 𝑛) =$ $\prod_{𝑖 = 0}^{𝑛 - 1} (2^{𝑛} - 2^{𝑖})$ invertible matrices in $𝔽_{2}^{𝑛 \times 𝑛}$ , out of $2^{𝑛^{2}}$ in all (Proposition 4.1.34).

(a) For $𝑛 = 3$ : $(8 - 1) (8 - 2) (8 - 4) =$ $168$ , out of $2^{9} = 512$ , so the fraction is $168 / 512 =$ $21 / 64 \approx$ $0.33$ .

(b) Dividing each of the $𝑛$ factors by $2^{𝑛}$ ,

𝑁_{2} \frac{𝑛, 𝑛}{2^{𝑛^{2}}} = \prod_{𝑖 = 0}^{𝑛 - 1} (1 - 2^{𝑖 - 𝑛}) = \prod_{𝑗 = 1}^{𝑛} (1 - 2^{- 𝑗}) .

First, if $𝑎_{2}, \dots, 𝑎_{𝑛} \in [0, 1]$ , then $\prod_{𝑗 = 2}^{𝑛} (1 - 𝑎_{𝑗}) \geq$ $1 -$ $\sum_{𝑗 = 2}^{𝑛} 𝑎_{𝑗}$ . This is clear for an empty product, and if $𝑃$ is the product of the first factors and $𝑆$ their sum, with $𝑃 \geq 1 - 𝑆$ , then, since $1 - 𝑎 \geq 0$ ,

𝑃 (1 - 𝑎) \geq (1 - 𝑆) (1 - 𝑎) = 1 - (𝑆 + 𝑎) + 𝑆 𝑎 \geq 1 - (𝑆 + 𝑎) .

With $𝑎_{𝑗} = 2^{- 𝑗}$ we get $\sum_{𝑗 = 2}^{𝑛} 2^{- 𝑗} =$ $1 / 2 -$ $2^{- 𝑛} <$ $1 / 2$ , so

\prod_{𝑗 = 1}^{𝑛} (1 - 2^{- 𝑗}) = \frac{1}{2} \prod_{𝑗 = 2}^{𝑛} (1 - 2^{- 𝑗}) \geq \frac{1}{2} (\frac{1}{2} + 2^{- 𝑛}) > \frac{1}{4} .

(As $𝑛 \to \infty$ the fraction decreases to about $0.289$ .)

Exercise 4.1.54.standardBeyond 21-242

(a)For $0 \leq 𝑘 \leq 4$ , find the number of $𝑘$ -dimensional subspaces of $𝔽_{2}^{4}$ .
(b)Let $𝐹$ have $𝑞$ elements and $dim 𝑉 = 𝑛$ . Show that $𝑉$ has as many $𝑘$ -dimensional subspaces as $(𝑛 - 𝑘)$ -dimensional ones.

Solution.

Uses. Proposition 4.1.37 (Counting subspaces), Corollary 4.1.35 (Counting independent lists and bases)

Techniques. Double counting (Technique 4.1.36)

Hint 1. Use Proposition 4.1.37 with

𝑞 = 2

𝑛 = 4

Hint 2. For (b), factor

𝑞^{𝑖}

out of each factor

𝑞^{𝑛} - 𝑞^{𝑖}

𝑁_{𝑞} (𝑛, 𝑘)

, and write the count as a ratio of products of factors

𝑞^{𝑗} - 1

Sketch. (a)

1, 15, 35, 15, 1

, so

67

subspaces in all. (b)

𝑁_{𝑞} (𝑛, 𝑘) =

𝑞^{𝑘 (𝑘 - 1) / 2} \prod_{𝑗 = 𝑛 - 𝑘 + 1}^{𝑛} (𝑞^{𝑗} - 1)

, so the count is

[𝑛]! / ([𝑘]! [𝑛 - 𝑘]!)

with

[𝑚]! =

\prod_{𝑗 = 1}^{𝑚} (𝑞^{𝑗} - 1)

, which is symmetric in

𝑘

and

𝑛 - 𝑘

(a) With $𝑞 = 2$ and $𝑛 = 4$ , Proposition 4.1.37 gives

𝑘 = 1 : \frac{15}{1} = 15, 𝑘 = 2 : \frac{15 \cdot 14}{3 \cdot 2} = 35, 𝑘 = 3 : \frac{15 \cdot 14 \cdot 12}{7 \cdot 6 \cdot 4} = 15,

and of course one subspace each of dimensions $0$ and $4$ . So $𝔽_{2}^{4}$ has $1 + 15 + 35 + 15 + 1 = 67$ subspaces.

(b) Factoring $𝑞^{𝑖}$ out of $𝑞^{𝑛} - 𝑞^{𝑖}$ ,

𝑁_{𝑞} (𝑛, 𝑘) = \prod_{𝑖 = 0}^{𝑘 - 1} 𝑞^{𝑖} (𝑞^{𝑛 - 𝑖} - 1) = 𝑞^{𝑘 (𝑘 - 1) / 2} \prod_{𝑗 = 𝑛 - 𝑘 + 1}^{𝑛} (𝑞^{𝑗} - 1) .

For $𝑛 = 𝑘$ this reads $𝑁_{𝑞} (𝑘, 𝑘) =$ $𝑞^{𝑘 (𝑘 - 1) / 2} \prod_{𝑗 = 1}^{𝑘} (𝑞^{𝑗} - 1)$ . Writing $[𝑚]! =$ $\prod_{𝑗 = 1}^{𝑚} (𝑞^{𝑗} - 1)$ , with $[0]! = 1$ , the number of $𝑘$ -dimensional subspaces is therefore

𝑁_{𝑞} \frac{𝑛, 𝑘}{𝑁_{𝑞}} (𝑘, 𝑘) = \frac{\prod_{𝑗 = 𝑛 - 𝑘 + 1}^{𝑛} (𝑞^{𝑗} - 1)}{[𝑘]!} = \frac{[𝑛]!}{[𝑘]! [𝑛 - 𝑘]!},

since $\prod_{𝑗 = 𝑛 - 𝑘 + 1}^{𝑛} (𝑞^{𝑗} - 1) =$ $[𝑛]! / [𝑛 - 𝑘]!$ . The last expression does not change when $𝑘$ is replaced by $𝑛 - 𝑘$ . (Duality explains the symmetry: sending $𝑈$ to the functionals that vanish on $𝑈$ matches the $𝑘$ -dimensional subspaces of $𝑉$ with the $(𝑛 - 𝑘)$ -dimensional subspaces of the dual space, which has the same dimension as $𝑉$ (Section 13.1).)

Exercise 4.1.55.hard Let $dim 𝑉 = 𝑛 \geq 1$ , and let $𝑁 \in L (𝑉)$ satisfy $𝑁^{𝑛 - 1} \neq 0$ and $𝑁^{𝑛} = 0$ . Show that $𝑆 \in L (𝑉)$ commutes with $𝑁$ , that is, $𝑆 𝑁 = 𝑁 𝑆$ , if and only if

𝑆 = 𝑐_{0} {id}_{𝑉} + 𝑐_{1} 𝑁 + \dots + 𝑐_{𝑛 - 1} 𝑁^{𝑛 - 1}

for some $𝑐_{0}, \dots, 𝑐_{𝑛 - 1} \in 𝐹$ .

Solution.

Uses. Exercise 4.1.52, Corollary 2.2.6 (Agreeing on a spanning list), Proposition 2.1.24 (Algebra of composition)

Techniques. Check it on a basis (Technique 2.2.7)

Hint 1. By Exercise 4.1.52 there is

𝐯

with

𝐯,

𝑁 𝐯,

\dots,

𝑁^{𝑛 - 1} 𝐯

a basis. Expand

𝑆 𝐯

in this basis.

Hint 2. If

𝑆 𝐯 = \sum 𝑐_{𝑖} 𝑁^{𝑖} 𝐯

, let

𝑃 = \sum 𝑐_{𝑖} 𝑁^{𝑖}

. Compare

𝑆

and

𝑃

on each basis vector

𝑁^{𝑗} 𝐯

, using that both commute with

𝑁^{𝑗}

Sketch. Polynomials in

𝑁

commute with

𝑁

. Conversely, take

𝐯

with

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

a basis, write

𝑆 𝐯 =

\sum_{𝑖} 𝑐_{𝑖} 𝑁^{𝑖} 𝐯

, and let

𝑃 = \sum_{𝑖} 𝑐_{𝑖} 𝑁^{𝑖}

. Since

𝑆

and

𝑃

commute with

𝑁^{𝑗}

𝑆 𝑁^{𝑗} 𝐯 =

𝑁^{𝑗} 𝑆 𝐯 =

𝑁^{𝑗} 𝑃 𝐯 =

𝑃 𝑁^{𝑗} 𝐯

. So

𝑆

and

𝑃

agree on a basis, and

𝑆 = 𝑃

( $\Leftarrow$ ) $𝑁$ commutes with each power $𝑁^{𝑖}$ , since $𝑁 𝑁^{𝑖} =$ $𝑁^{𝑖 + 1} =$ $𝑁^{𝑖} 𝑁$ . By the distributive laws of Proposition 2.1.24, $𝑁$ commutes with every combination $\sum_{𝑖} 𝑐_{𝑖} 𝑁^{𝑖}$ .

( $\Rightarrow$ ) Suppose $𝑆 𝑁 = 𝑁 𝑆$ . By induction on $𝑗$ , $𝑆 𝑁^{𝑗} = 𝑁^{𝑗} 𝑆$ for all $𝑗 \geq 0$ : if $𝑆 𝑁^{𝑗} = 𝑁^{𝑗} 𝑆$ , then $𝑆 𝑁^{𝑗 + 1} =$ $(𝑆 𝑁) 𝑁^{𝑗} =$ $𝑁 𝑆 𝑁^{𝑗} =$ $𝑁 𝑁^{𝑗} 𝑆 =$ $𝑁^{𝑗 + 1} 𝑆$ . By Exercise 4.1.52 there is $𝐯 \in 𝑉$ such that $𝐯,$ $𝑁 𝐯,$ $\dots,$ $𝑁^{𝑛 - 1} 𝐯$ is a basis of $𝑉$ . Expand $𝑆 𝐯$ in it:

𝑆 𝐯 = 𝑐_{0} 𝐯 + 𝑐_{1} 𝑁 𝐯 + \dots + 𝑐_{𝑛 - 1} 𝑁^{𝑛 - 1} 𝐯,

and let $𝑃 =$ $𝑐_{0} {id}_{𝑉} +$ $𝑐_{1} 𝑁 +$ $\dots +$ $𝑐_{𝑛 - 1} 𝑁^{𝑛 - 1}$ , so that $𝑆 𝐯 = 𝑃 𝐯$ . For each $𝑗$ , using that $𝑆$ and $𝑃$ both commute with $𝑁^{𝑗}$ ,

𝑆 (𝑁^{𝑗} 𝐯) = 𝑁^{𝑗} (𝑆 𝐯) = 𝑁^{𝑗} (𝑃 𝐯) = 𝑃 (𝑁^{𝑗} 𝐯) .

So $𝑆$ and $𝑃$ agree on every vector of a basis of $𝑉$ , and therefore $𝑆 = 𝑃$ (Corollary 2.2.6).

Without the hypothesis $𝑁^{𝑛 - 1} \neq 0$ the statement fails: for $𝑛 \geq 2$ and $𝑁 = 0$ , every $𝑆$ commutes with $𝑁$ , but the combinations of powers of $0$ are only the multiples of ${id}_{𝑉}$ .

Exercise 4.1.56.hard Let $𝑉$ be finite-dimensional, and let $𝑇 \in L (𝑉)$ be injective.

(a)Show that $𝑇$ is invertible, and that $𝑇^{- 1} =$ $𝑏_{0} {id}_{𝑉} +$ $𝑏_{1} 𝑇 +$ $\dots +$ $𝑏_{𝑑} 𝑇^{𝑑}$ for some $𝑑 \geq 0$ and scalars $𝑏_{0}, \dots, 𝑏_{𝑑}$ .
(b)Let $𝑀 \in L (𝐹 [𝑥])$ be multiplication by $𝑥$ (Example 2.1.9). Show that $𝑀$ is injective but not surjective. Which step of (a) fails for $𝑀$ ?

Solution.

Uses. Proposition 4.1.31 (Every square matrix satisfies a polynomial), Proposition 2.1.24 (Algebra of composition), Definition 2.6.1 (Injective), Definition 2.5.12 (Invertible)

Techniques. Too many vectors force a dependence (Technique 4.1.30), Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. By Proposition 4.1.31 there is a nontrivial relation

\sum_{𝑗 = 0}^{𝑁} 𝑐_{𝑗} 𝑇^{𝑗} = 0

. Let

𝑟

be the smallest index with

𝑐_{𝑟} \neq 0

and factor out

𝑇^{𝑟}

Hint 2.

𝑇^{𝑟}

is injective, so

𝑇^{𝑟} 𝑅 = 0

forces

𝑅 = 0

. Now

𝑅 = 𝑐_{𝑟} {id}_{𝑉} + 𝑇 𝑄

for a combination

𝑄

of powers of

𝑇

. Solve for

{id}_{𝑉}

Sketch. Take

\sum_{𝑗 = 𝑟}^{𝑁} 𝑐_{𝑗} 𝑇^{𝑗} =

0

with

𝑐_{𝑟} \neq 0

. Then

𝑇^{𝑟} 𝑅 = 0

with

𝑅 =

\sum_{𝑗 \geq 𝑟} 𝑐_{𝑗} 𝑇^{𝑗 - 𝑟}

, and

𝑇^{𝑟}

is injective, so

𝑅 = 0

. Writing

𝑅 = 𝑐_{𝑟} {id}_{𝑉} + 𝑇 𝑄

gives

𝑇 (- 𝑐_{𝑟}^{- 1} 𝑄) =

{id}_{𝑉}

, and

𝑄

commutes with

𝑇

, so

- 𝑐_{𝑟}^{- 1} 𝑄

is a two-sided inverse. For

𝑀

1 \notin im 𝑀

; the step that fails is the existence of a relation among

id, 𝑀, 𝑀^{2}, \dots

, since these are independent (

𝑀^{𝑗} (1) = 𝑥^{𝑗}

(a) If $𝑉 = {𝟎}$ , then $𝑇 = {id}_{𝑉}$ and $𝑇^{- 1} = {id}_{𝑉}$ . Otherwise $𝑛 = dim 𝑉 \geq 1$ , and by Proposition 4.1.31 there are $𝑐_{0}, \dots, 𝑐_{𝑁}$ ( $𝑁 = 𝑛^{2}$ ), not all $0$ , with $\sum_{𝑗 = 0}^{𝑁} 𝑐_{𝑗} 𝑇^{𝑗} = 0$ . Let $𝑟$ be the smallest index with $𝑐_{𝑟} \neq 0$ , and let

𝑅 = 𝑐_{𝑟} {id}_{𝑉} + 𝑐_{𝑟 + 1} 𝑇 + \dots + 𝑐_{𝑁} 𝑇^{𝑁 - 𝑟},

so that $\sum_{𝑗 = 𝑟}^{𝑁} 𝑐_{𝑗} 𝑇^{𝑗} =$ $𝑇^{𝑟} 𝑅$ by Proposition 2.1.24. Thus $𝑇^{𝑟} 𝑅 = 0$ . The map $𝑇^{𝑟}$ is injective, as a composite of injective maps. For every $𝐮 \in 𝑉$ , $𝑇^{𝑟} (𝑅 𝐮) =$ $𝟎 =$ $𝑇^{𝑟} (𝟎)$ , so $𝑅 𝐮 = 𝟎$ . Hence $𝑅 = 0$ . Let $𝑄 =$ $𝑐_{𝑟 + 1} {id}_{𝑉} +$ $𝑐_{𝑟 + 2} 𝑇 +$ $\dots +$ $𝑐_{𝑁} 𝑇^{𝑁 - 𝑟 - 1}$ (an empty sum is $0$ ), so that $𝑅 = 𝑐_{𝑟} {id}_{𝑉} + 𝑇 𝑄$ , and let $𝑆 = - 𝑐_{𝑟}^{- 1} 𝑄$ . Then $𝑅 = 0$ gives

𝑇 𝑆 = - 𝑐_{𝑟}^{- 1} 𝑇 𝑄 = - 𝑐_{𝑟}^{- 1} (𝑅 - 𝑐_{𝑟} {id}_{𝑉}) = {id}_{𝑉} .

Since $𝑆$ is a combination of powers of $𝑇$ , it commutes with $𝑇$ , so $𝑆 𝑇 = 𝑇 𝑆 = {id}_{𝑉}$ as well. So $𝑇$ is invertible (Definition 2.5.12), and $𝑇^{- 1} = 𝑆$ is a combination of ${id}_{𝑉},$ $𝑇,$ $\dots,$ $𝑇^{𝑁 - 𝑟 - 1}$ .

(b) If $𝑥 𝑝 = 0$ , then every coefficient of $𝑝$ , which is a coefficient of $𝑥 𝑝$ shifted by one place, is $0$ ; so $𝑀$ is injective. Every $𝑥 𝑝$ has constant coefficient $0$ , so $1 \notin im 𝑀$ , and $𝑀$ is not surjective. The argument of (a) fails at its first step: there is no nontrivial relation $\sum_{𝑗} 𝑐_{𝑗} 𝑀^{𝑗} = 0$ , because applying it to $1$ gives $\sum_{𝑗} 𝑐_{𝑗} 𝑥^{𝑗} = 0$ , which forces all $𝑐_{𝑗} = 0$ . The space $L (𝐹 [𝑥])$ is infinite-dimensional, and the powers of $𝑀$ never become too many.

In particular, an injective operator on a finite-dimensional space is surjective. Section 4.2 proves this again with dimension counting (Corollary 4.2.18).

Exercise 4.1.57.hard Let $𝐴_{1}, \dots, 𝐴_{𝑛 + 1}$ be nonempty subsets of ${1, \dots, 𝑛}$ . Show that there are disjoint nonempty sets $𝐼, 𝐽 \subseteq {1, \dots, 𝑛 + 1}$ with

⋃_{𝑖 \in 𝐼} 𝐴_{𝑖} = ⋃_{𝑗 \in 𝐽} 𝐴_{𝑗} .

Solution.

Uses. Theorem 4.1.10 (Independent lists are short), Theorem 1.5.5 (Independence is decided at zero), Example 4.1.7 (Dimensions of the standard spaces)

Techniques. Too many vectors force a dependence (Technique 4.1.30)

Hint 1. Encode

𝐴_{𝑖}

as the vector

𝐱_{𝑖} \in ℝ^{𝑛}

whose

𝑡

-th entry is

1

𝑡 \in 𝐴_{𝑖}

and

0

otherwise. There are

𝑛 + 1

of these.

Hint 2. Take a nontrivial relation and move the terms with negative coefficients to the other side. When is the

𝑡

-th entry of a combination of the

𝐱_{𝑖}

with positive coefficients positive?

Sketch. The

𝑛 + 1

indicator vectors in

ℝ^{𝑛}

are dependent. Split a nontrivial relation as

\sum_{𝑖 \in 𝐼} 𝑐_{𝑖} 𝐱_{𝑖} =

\sum_{𝑗 \in 𝐽} 𝑑_{𝑗} 𝐱_{𝑗}

with all

𝑐_{𝑖}, 𝑑_{𝑗} > 0

, where

𝐼

and

𝐽

are the indices with positive and negative coefficients. Both are nonempty, since a positive combination of nonzero vectors with entries

\geq 0

is nonzero. The

𝑡

-th entry of the left side is positive exactly when

𝑡 \in ⋃_{𝐼} 𝐴_{𝑖}

, and likewise on the right.

For each $𝑖$ , let $𝐱_{𝑖} \in ℝ^{𝑛}$ have $𝑡$ -th entry $1$ if $𝑡 \in 𝐴_{𝑖}$ and $0$ otherwise; $𝐱_{𝑖} \neq 𝟎$ since $𝐴_{𝑖} \neq \emptyset$ . These are $𝑛 + 1$ vectors in $ℝ^{𝑛}$ , and $dim ℝ^{𝑛} = 𝑛$ , so they are dependent (Theorem 4.1.10(a)): there are real $𝑎_{1}, \dots, 𝑎_{𝑛 + 1}$ , not all $0$ , with $\sum_{𝑖} 𝑎_{𝑖} 𝐱_{𝑖} = 𝟎$ . Let $𝐼 = {𝑖 | 𝑎_{𝑖} > 0}$ and $𝐽 = {𝑗 | 𝑎_{𝑗} < 0}$ , which are disjoint. Moving the negative terms across,

𝐲 = \sum_{𝑖 \in 𝐼} 𝑎_{𝑖} 𝐱_{𝑖} = \sum_{𝑗 \in 𝐽} (- 𝑎_{𝑗}) 𝐱_{𝑗},

where all coefficients now are positive.

Consider the $𝑡$ -th entry of $𝐲$ . On the left it is $\sum_{𝑖 \in 𝐼, 𝑡 \in 𝐴_{𝑖}} 𝑎_{𝑖}$ , a sum of positive numbers, which is positive if $𝑡 \in ⋃_{𝑖 \in 𝐼} 𝐴_{𝑖}$ and $0$ otherwise. On the right, in the same way, it is positive exactly when $𝑡 \in ⋃_{𝑗 \in 𝐽} 𝐴_{𝑗}$ . So the two unions are both equal to the set of $𝑡$ with $𝑦_{𝑡} > 0$ , and hence equal to each other.

It remains to see that $𝐼$ and $𝐽$ are nonempty. Not all $𝑎_{𝑖}$ are $0$ , so $𝐼 \cup 𝐽 \neq \emptyset$ ; say $𝐼 \neq \emptyset$ . Pick $𝑖_{0} \in 𝐼$ and $𝑡 \in 𝐴_{𝑖_{0}}$ . Then $𝑦_{𝑡} \geq 𝑎_{𝑖_{0}} > 0$ , so $𝐲 \neq 𝟎$ , and the right side, an empty sum if $𝐽 = \emptyset$ , would be $𝟎$ . So $𝐽 \neq \emptyset$ . The case $𝐽 \neq \emptyset$ is symmetric.

Exercise 4.1.58.hard Show that for every field

𝐹

and every

𝑛 \geq 1

, the space

𝐹^{𝑛 \times 𝑛}

has a basis consisting of invertible matrices. Write one down for

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

Solution.

Uses. Theorem 1.6.10 (Every spanning list contains a basis), Lemma 2.4.24 (Matrix units), Definition 3.2.2 (Elementary matrices), Proposition 3.2.10 (Inverses of elementary matrices), Proposition 2.5.17 (Algebra of inverses), Theorem 4.1.10 (Independent lists are short)

Hint 1. It is enough to show that the invertible matrices span

𝐹^{𝑛 \times 𝑛}

, since a spanning list contains a basis. Write each matrix unit as a difference of two invertible matrices.

Hint 2. For

𝑖 \neq 𝑗

𝑈_{𝑖 𝑗} =

(𝐼 + 𝑈_{𝑖 𝑗}) -

𝐼

. For

𝑈_{𝑖 𝑖}

, pick

𝑗 \neq 𝑖

and let

𝑃 = 𝐸_{𝑖 𝑗}

be the swap. Show

𝑃 +

𝑈_{𝑖 𝑖} =

𝑃 (𝐼 + 𝑈_{𝑗 𝑖})

Sketch. For

𝑛 = 1

take

(1)

. For

𝑛 \geq 2

: if

𝑖 \neq 𝑗

then

(𝐼 + 𝑈_{𝑖 𝑗}) (𝐼 - 𝑈_{𝑖 𝑗}) =

𝐼

because

𝑈_{𝑖 𝑗}^{2} = 0

, so

𝑈_{𝑖 𝑗} =

(𝐼 + 𝑈_{𝑖 𝑗}) -

𝐼

is a difference of invertibles. For

𝑈_{𝑖 𝑖}

, take

𝑗 \neq 𝑖

and the swap

𝑃 = 𝐸_{𝑖 𝑗}

; then

𝑃 𝑈_{𝑖 𝑖} = 𝑈_{𝑗 𝑖}

, so

𝑃 +

𝑈_{𝑖 𝑖} =

𝑃 (𝐼 + 𝑈_{𝑗 𝑖})

is invertible and

𝑈_{𝑖 𝑖} =

(𝑃 + 𝑈_{𝑖 𝑖}) -

𝑃

. So finitely many invertible matrices span, and a basis can be extracted from them. Over

𝔽_{2}

𝐼_{2}

𝐼_{2} + 𝑈_{12}

𝐼_{2} + 𝑈_{21}

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

For $𝑛 = 1$ , the matrix $(1)$ is an invertible basis of $𝐹^{1 \times 1}$ . Let $𝑛 \geq 2$ , and write $𝐼 = 𝐼_{𝑛}$ . By Lemma 2.4.24, $𝑈_{𝑖 𝑗} 𝑈_{𝑘 𝑙} =$ $𝑈_{𝑖 𝑙}$ if $𝑗 = 𝑘$ and $0$ otherwise.

Off-diagonal units. For $𝑖 \neq 𝑗$ , $𝑈_{𝑖 𝑗}^{2} = 0$ , so $(𝐼 + 𝑈_{𝑖 𝑗}) (𝐼 - 𝑈_{𝑖 𝑗}) =$ $𝐼 -$ $𝑈_{𝑖 𝑗}^{2} =$ $𝐼$ and likewise $(𝐼 - 𝑈_{𝑖 𝑗}) (𝐼 + 𝑈_{𝑖 𝑗}) =$ $𝐼$ . So $𝐼 + 𝑈_{𝑖 𝑗}$ is invertible, and $𝑈_{𝑖 𝑗} =$ $(𝐼 + 𝑈_{𝑖 𝑗}) -$ $𝐼$ .

Diagonal units. Fix $𝑖$ and choose $𝑗 \neq 𝑖$ . Let $𝑃 = 𝐸_{𝑖 𝑗}$ be the elementary matrix that swaps rows $𝑖$ and $𝑗$ (Definition 3.2.2); it is invertible with $𝑃^{- 1} = 𝑃$ (Proposition 3.2.10). Its $𝑖$ -th column is $𝐞_{𝑗}$ , so $𝑃 𝑈_{𝑖 𝑖} =$ $𝑃 𝐞_{𝑖} 𝐞_{𝑖}^{𝖳} =$ $𝐞_{𝑗} 𝐞_{𝑖}^{𝖳} =$ $𝑈_{𝑗 𝑖}$ . Hence

𝑃 (𝐼 + 𝑈_{𝑗 𝑖}) = 𝑃 + 𝑃 𝑈_{𝑗 𝑖} = 𝑃 + 𝑃 (𝑃 𝑈_{𝑖 𝑖}) = 𝑃 + 𝑈_{𝑖 𝑖} .

By the previous paragraph $𝐼 + 𝑈_{𝑗 𝑖}$ is invertible, so $𝑃 + 𝑈_{𝑖 𝑖}$ is a product of invertible matrices and is invertible (Proposition 2.5.17). And $𝑈_{𝑖 𝑖} =$ $(𝑃 + 𝑈_{𝑖 𝑖}) -$ $𝑃$ .

So every matrix unit is a combination of finitely many invertible matrices, and these invertible matrices span $𝐹^{𝑛 \times 𝑛}$ , since the matrix units do. By Theorem 1.6.10, some sublist of them is a basis.

For $𝔽_{2}^{2 \times 2}$ , take

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

Each is invertible: the first three are $𝐼_{2}$ and $𝐼_{2} + 𝑈_{12}$ , $𝐼_{2} + 𝑈_{21}$ , and the last is $𝐸_{12} + 𝑈_{11}$ . A combination $𝑎 𝐼_{2} +$ $𝑏 (𝐼_{2} + 𝑈_{12}) +$ $𝑐 (𝐼_{2} + 𝑈_{21}) +$ $𝑑 (𝐸_{12} + 𝑈_{11})$ has $(1, 1)$ entry $𝑎 + 𝑏 + 𝑐 + 𝑑$ and $(2, 2)$ entry $𝑎 + 𝑏 + 𝑐$ , so if it is $0$ then $𝑑 = 0$ ; its $(1, 2)$ and $(2, 1)$ entries are then $𝑏$ and $𝑐$ , so $𝑏 = 𝑐 = 0$ , and finally $𝑎 = 0$ . Four independent vectors in the $4$ -dimensional space $𝔽_{2}^{2 \times 2}$ form a basis (Theorem 4.1.10(b)).

Exercise 4.1.59.hard Let $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ and $𝒞︀ = 𝐜_{1}, \dots, 𝐜_{𝑛}$ be bases of $𝑉$ , and fix $𝑖$ . Show that there is an index $𝑗$ such that both of the following are bases of $𝑉$ :

(a) $ℬ︀$ with $𝐛_{𝑖}$ replaced by $𝐜_{𝑗}$ ;
(b) $𝒞︀$ with $𝐜_{𝑗}$ replaced by $𝐛_{𝑖}$ .

Solution.

Uses. Exercise 1.5.33, Proposition 1.6.19 (Coordinates respect linear combinations), Definition 1.6.14 (Coordinates)

Hint 1. By Exercise 1.5.33, replacing

𝐛_{𝑖}

𝐰

gives a basis exactly when the

𝑖

-th

ℬ︀

-coordinate of

𝐰

is nonzero. Express both conditions (a) and (b) by coordinates.

Hint 2. Let

𝛽_{𝑗}

be the

𝑗

-th

𝒞︀

-coordinate of

𝐛_{𝑖}

and

𝛾_{𝑗}

the

𝑖

-th

ℬ︀

-coordinate of

𝐜_{𝑗}

. Take the

𝑖

-th

ℬ︀

-coordinate of both sides of

𝐛_{𝑖} = \sum_{𝑗} 𝛽_{𝑗} 𝐜_{𝑗}

Sketch. By Exercise 1.5.33, (a) holds iff

𝛾_{𝑗} \neq 0

and (b) holds iff

𝛽_{𝑗} \neq 0

, where

𝐛_{𝑖} = \sum_{𝑗} 𝛽_{𝑗} 𝐜_{𝑗}

and

𝛾_{𝑗}

is the

𝑖

-th

ℬ︀

-coordinate of

𝐜_{𝑗}

. Taking

𝑖

-th

ℬ︀

-coordinates of

𝐛_{𝑖} = \sum_{𝑗} 𝛽_{𝑗} 𝐜_{𝑗}

gives

1 = \sum_{𝑗} 𝛽_{𝑗} 𝛾_{𝑗}

, so some

𝛽_{𝑗} 𝛾_{𝑗} \neq 0

For $𝐰 \in 𝑉$ , Exercise 1.5.33 says that replacing $𝐛_{𝑖}$ by $𝐰$ in the independent list $ℬ︀$ gives an independent list if and only if the coefficient of $𝐛_{𝑖}$ in $𝐰$ , that is, the $𝑖$ -th coordinate of ${[𝐰]}_{ℬ︀}$ , is nonzero, and that the span is then still $𝑉$ . So the new list is a basis exactly in that case. Let $𝛾_{𝑗}$ be the $𝑖$ -th coordinate of ${[𝐜_{𝑗}]}_{ℬ︀}$ . Then (a) holds for $𝑗$ if and only if $𝛾_{𝑗} \neq 0$ .

In the same way, with the roles of the bases exchanged, write ${[𝐛_{𝑖}]}_{𝒞︀} =$ $(𝛽_{1}, \dots, 𝛽_{𝑛})$ , that is, $𝐛_{𝑖} = \sum_{𝑗} 𝛽_{𝑗} 𝐜_{𝑗}$ . Then (b) holds for $𝑗$ if and only if $𝛽_{𝑗} \neq 0$ .

Take the $𝑖$ -th $ℬ︀$ -coordinate of both sides of $𝐛_{𝑖} = \sum_{𝑗} 𝛽_{𝑗} 𝐜_{𝑗}$ . On the left it is $1$ , since ${[𝐛_{𝑖}]}_{ℬ︀} = 𝐞_{𝑖}$ . On the right, by Proposition 1.6.19(c), it is $\sum_{𝑗} 𝛽_{𝑗} 𝛾_{𝑗}$ . So $\sum_{𝑗 = 1}^{𝑛} 𝛽_{𝑗} 𝛾_{𝑗} =$ $1 \neq$ $0$ , and some term $𝛽_{𝑗} 𝛾_{𝑗}$ is nonzero. For that $𝑗$ , both $𝛽_{𝑗} \neq 0$ and $𝛾_{𝑗} \neq 0$ , so (a) and (b) both hold.

Exercise 4.1.60.challenge Let

𝐹

be a field of characteristic

0

(Definition 1.1.28), such as

ℚ

ℝ

, or

ℂ

, and let

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

satisfy

𝐴 𝐵 - 𝐵 𝐴 = 𝐴

. Show that

𝐴^{𝑛} = 0

Solution.

Uses. Corollary 4.1.27 (A nilpotent operator dies within $dim 𝑉$ steps), Theorem 4.1.10 (Independent lists are short), Theorem 1.5.5 (Independence is decided at zero), Proposition 2.1.17 (Compositions of linear maps are linear), Proposition 1.2.35 (Zero products), Definition 1.1.28 (Characteristic)

Techniques. Apply an operator to a relation to kill terms (Technique 4.1.25), Too many vectors force a dependence (Technique 4.1.30)

Hint 1. Let

𝜑 : 𝐹^{𝑛 \times 𝑛} \to

𝐹^{𝑛 \times 𝑛}

𝜑 (𝑋) = 𝑋 𝐵 - 𝐵 𝑋

. Show that

𝜑

is linear and that

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

for all

𝑘 \geq 1

Hint 2. Suppose

𝐴^{1}, \dots, 𝐴^{𝑁}

are all nonzero, with

𝑁 = 𝑛^{2} + 1

. Show they are independent: to isolate the coefficient of

𝐴^{𝑚}

in a relation, apply the composite of the maps

𝜑 - 𝑗 id

for

𝑗 \neq 𝑚

Hint 3. So some

𝐴^{𝑘}

with

𝑘 \leq 𝑛^{2} + 1

0

. Finish with Corollary 4.1.27.

Sketch.

𝜑 (𝑋) = 𝑋 𝐵 - 𝐵 𝑋

is linear, and

𝜑 (𝐴^{𝑘 + 1}) =

𝐴 𝜑 (𝐴^{𝑘}) +

𝜑 (𝐴) 𝐴^{𝑘}

gives

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

. If

𝐴, \dots, 𝐴^{𝑁}

(

𝑁 = 𝑛^{2} + 1

) were all nonzero, applying

\prod_{𝑗 \neq 𝑚} (𝜑 - 𝑗 id)

to a relation

\sum 𝑐_{𝑘} 𝐴^{𝑘} = 0

would leave

𝑐_{𝑚} \prod_{𝑗 \neq 𝑚} (𝑚 - 𝑗) 𝐴^{𝑚} =

0

, and

\prod_{𝑗 \neq 𝑚} (𝑚 - 𝑗)

is a nonzero integer, nonzero in

𝐹

. So

𝑐_{𝑚} = 0

for all

𝑚

, and

𝑁 > 𝑛^{2}

independent matrices is impossible. Hence

𝐴

is nilpotent, and

𝐴^{𝑛} = 0

Let $𝜑 : 𝐹^{𝑛 \times 𝑛} \to$ $𝐹^{𝑛 \times 𝑛}$ be $𝜑 (𝑋) = 𝑋 𝐵 - 𝐵 𝑋$ . It is linear, since $(𝑋 + 𝑐 𝑌) 𝐵 -$ $𝐵 (𝑋 + 𝑐 𝑌) =$ $(𝑋 𝐵 - 𝐵 𝑋) +$ $𝑐 (𝑌 𝐵 - 𝐵 𝑌)$ . We show $𝜑 (𝐴^{𝑘}) = 𝑘 𝐴^{𝑘}$ for $𝑘 \geq 1$ by induction. For $𝑘 = 1$ this is the hypothesis. If it holds for $𝑘$ , then

𝜑 (𝐴^{𝑘 + 1}) = 𝐴 𝐴^{𝑘} 𝐵 - 𝐵 𝐴 𝐴^{𝑘} = 𝐴 (𝐴^{𝑘} 𝐵 - 𝐵 𝐴^{𝑘}) + (𝐴 𝐵 - 𝐵 𝐴) 𝐴^{𝑘} = 𝐴 (𝑘 𝐴^{𝑘}) + 𝐴 𝐴^{𝑘} = (𝑘 + 1) 𝐴^{𝑘 + 1} .

For an integer $𝑗$ , let $𝐿_{𝑗} = 𝜑 - 𝑗 id$ , a linear map on $𝐹^{𝑛 \times 𝑛}$ ; here $𝑗$ stands for $𝑗 \cdot 1 \in 𝐹$ . Then $𝐿_{𝑗} (𝐴^{𝑘}) =$ $(𝑘 - 𝑗) 𝐴^{𝑘}$ , and therefore $𝐿_{𝑗} (𝑐 𝐴^{𝑘}) =$ $𝑐 (𝑘 - 𝑗) 𝐴^{𝑘}$ for every scalar $𝑐$ .

Let $𝑁 = 𝑛^{2} + 1$ , and suppose, to the contrary, that $𝐴^{𝑘} \neq 0$ for $𝑘 = 1, \dots, 𝑁$ . We show that $𝐴, 𝐴^{2}, \dots, 𝐴^{𝑁}$ is independent. Let $\sum_{𝑘 = 1}^{𝑁} 𝑐_{𝑘} 𝐴^{𝑘} = 0$ , and fix $𝑚 \in {1, \dots, 𝑁}$ . Apply the composite $𝐿 =$ $𝐿_{1} \dots 𝐿_{𝑚 - 1} 𝐿_{𝑚 + 1} \dots 𝐿_{𝑁}$ , which is linear (Proposition 2.1.17). Applying the factors one at a time,

𝐿 (𝐴^{𝑘}) = (\prod_{𝑗 \neq 𝑚} (𝑘 - 𝑗)) 𝐴^{𝑘},

which is $0$ for $𝑘 \neq 𝑚$ , because the product contains the factor $𝑘 - 𝑘 = 0$ . So applying $𝐿$ to the relation leaves

𝑐_{𝑚} (\prod_{𝑗 \neq 𝑚} (𝑚 - 𝑗)) 𝐴^{𝑚} = 0 .

The product is a product of nonzero integers, hence a nonzero integer, and in a field of characteristic $0$ a nonzero integer is a nonzero element. Since $𝐴^{𝑚} \neq 0$ , Proposition 1.2.35 gives $𝑐_{𝑚} = 0$ . As $𝑚$ was arbitrary, the relation is trivial, and $𝐴, \dots, 𝐴^{𝑁}$ is an independent list of $𝑛^{2} + 1$ vectors in $𝐹^{𝑛 \times 𝑛}$ , contradicting Theorem 4.1.10(a).

So $𝐴^{𝑘} = 0$ for some $𝑘$ with $1 \leq 𝑘 \leq 𝑛^{2} + 1$ , and Corollary 4.1.27 gives $𝐴^{𝑛} = 0$ .

The hypothesis on $𝐹$ is needed. Over $𝔽_{3}$ , the matrices

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

satisfy $𝐴 𝐵 - 𝐵 𝐴 = 𝐴$ (check it), while $𝐴^{3} = 𝐼_{3}$ . In the proof, the integers $1, 2, 3, \dots$ are no longer distinct in $𝔽_{3}$ , so $𝜑$ cannot tell the powers of $𝐴$ apart.

More practice

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