2.7 The Fundamental Theorems

For a matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , the last two sections produced a long list of properties. The map $𝑇_{𝐴}$ can be injective or surjective, its kernel can be ${𝟎}$ and its image $𝐹^{𝑚}$ , the columns of $𝐴$ can be linearly independent or span $𝐹^{𝑚}$ , $𝐴$ can have a left or a right inverse, and the equation $𝐴 𝐱 = 𝐲$ can have at most one or at least one solution for each $𝐲$ . Many of these turned out to be the same property in different words. The three Fundamental Theorems sort them into three groups: the conditions that say “at most one”, those that say “at least one”, and those that say “exactly one”. Almost every equivalence among them is a result we already have, read the right way. The exception is that an injective $𝑇_{𝐴}$ has a linear left inverse, and a surjective one a linear right inverse. These need a construction, which the lecture postpones until row reduction is available (Section 3.5). We give a direct construction here as well.

Each theorem is a list of equivalent statements, so we start with how such lists are proved. Throughout, $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , and $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ is the linear map $𝐱 \mapsto 𝐴 𝐱$ (Definition 2.3.15).

2.7.1Proving that statements are equivalent

A theorem of the form “the following are equivalent” (TFAE) about statements $𝑃_{1}, \dots, 𝑃_{𝑘}$ asserts that they are all true or all false. Proving every implication $𝑃_{𝑖} \Rightarrow 𝑃_{𝑗}$ separately would take $𝑘 (𝑘 - 1)$ arguments, which is $20$ for the five conditions of a Fundamental Theorem. Implications can be chained, so far fewer are needed.

Technique 2.7.1 (Proving TFAE). To prove that $𝑃_{1}, \dots, 𝑃_{𝑘}$ are equivalent, prove some implications $𝑃_{𝑖} \Rightarrow 𝑃_{𝑗}$ such that every statement can be reached from every other by following implications. Then any $𝑃_{𝑖}$ implies any $𝑃_{𝑗}$ , by chaining. Two shapes cover most cases.

A cycle $𝑃_{1} \Rightarrow$ $𝑃_{2} \Rightarrow$ $\dots \Rightarrow$ $𝑃_{𝑘} \Rightarrow$ $𝑃_{1}$ uses $𝑘$ implications, the fewest possible. The order is ours to choose, and a good order makes every step short. Usually one goes from the most informative statement (one that hands us an object, such as an inverse) toward the least informative, and closes the loop with the one step that needs an idea.
A hub with spokes fixes one statement, say $𝑃_{1}$ , and proves $𝑃_{𝑖} \Leftrightarrow 𝑃_{1}$ for every other $𝑖$ . It uses more implications than a cycle, but it is the natural shape when earlier results already relate each $𝑃_{𝑖}$ to $𝑃_{1}$ . Each spoke is then a citation, and the citations are a complete proof, because equivalence is transitive.

Mixed shapes are fine. Draw the statements as points and the proved implications as arrows, and check that you can travel from any point to any other along arrows. Two mistakes are common. Equivalences inside two separate groups of statements say nothing about one group versus the other (Exercise 2.7.21). And each arrow must be proved without the theorem it belongs to, and without any result that depends on that theorem. Going around a cycle is not circular reasoning, since every arrow is proved on its own; quoting the theorem to prove one of its own arrows would be.

The payoff comes after the proof. To show that one of the statements holds, check whichever is easiest; to use one, use whichever is strongest. We have already seen cycles in Theorem 1.4.3 and Theorem 2.1.3. The canonical example is the First Fundamental Theorem (Theorem 2.7.2), whose proof is a hub with three spokes plus two implications about inverses.

Used in 38 places and 3 practice exercises

Theorem 1.4.3, Theorem 2.7.2, Theorem 2.7.4, Exercise 2.7.6, Theorem 2.7.8, Exercise 2.7.15, Corollary 2.7.16, Exercise 2.7.19, Exercise 2.7.21, Exercise 2.7.23, Exercise 2.8.11, Corollary 3.4.20, Theorem 3.5.12, Theorem 3.5.13, Theorem 3.5.14, Corollary 3.5.25, Exercise 4.2.50, Theorem 4.4.7, Corollary 4.5.21, Theorem 4.5.25, Lemma 4.6.14, Theorem 4.7.22, Theorem 4.7.37, Proposition 6.3.34, Exercise 6.4.57, Exercise 6.6.40, Theorem 7.4.16, Proposition 7.5.2, Theorem 7.6.15, Theorem 8.2.5, Theorem 8.2.12, Theorem 8.3.5, Proposition 8.3.15, Theorem 8.4.4, Theorem 8.4.11, Theorem 8.4.15, Theorem A.2.1, Lemma A.3.5; 3 practice exercises.

2.7.2The First and Second Fundamental Theorems

Intuition (Five ways to say that nothing is lost). Each condition of the First Fundamental Theorem says, in its own language, that

𝑇_{𝐴}

loses no information. In (I), different inputs give different outputs. In (II), each equation

𝐴 𝐱 = 𝐲

pins down

𝐱

whenever it has a solution at all. In (III), no nontrivial combination of the columns vanishes, so the coefficients of a combination can be recovered from its value. In (IV), no nonzero vector is sent to

𝟎

. In (V), a linear map recovers the input from the output. The first four are visibly one statement in four languages, and Section 2.6 proved as much. The fifth is of a different kind, since it asserts that a certain map exists.

Theorem 2.7.2 (First Fundamental Theorem). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝑇_{𝐴}$ is injective.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has at most one solution $𝐱 \in 𝐹^{𝑛}$ .
(III)The columns of $𝐴$ are linearly independent.
(IV) $ker 𝑇_{𝐴} = {𝟎}$ .
(V) $𝑇_{𝐴}$ has a left inverse: a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑆 \circ 𝑇_{𝐴} = {id}_{𝐹^{𝑛}}$ .

We use (I) as the hub. Parts 1 and 2 of the proof only reread earlier results. Part 3 needs a construction, and it is given in Section 2.7.4.

Proof, part 1 of 3: (I)–(IV) are equivalent.routine

Uses. Definition 2.6.1 (Injective), Definition 2.3.15 (The linear map of a matrix), Corollary 2.6.24 (The columns decide), Proposition 2.3.13 (Linearity of the product), Theorem 2.6.11 (Injectivity is decided at $𝟎$ )

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Each of (II), (III), and (IV) is equivalent to (I) by a definition or by a result of Section 2.6. Find the right one for each.

Hint 2. In the language of the map

𝑇_{𝐴}

, what is a solution of

𝐴 𝐱 = 𝐲

? What are the values of

𝑇_{𝐴}

on the standard basis?

Hint 3. (I)

\Leftrightarrow

(III) is Corollary 2.6.24(a), and (I)

\Leftrightarrow

(IV) is Theorem 2.6.11.

Sketch. Hub at (I). A solution of

𝐴 𝐱 = 𝐲

is a preimage of

𝐲

under

𝑇_{𝐴}

, so (II) is the definition of injectivity. The columns are the values

𝑇_{𝐴} (𝐞_{𝑗})

, so (I)

\Leftrightarrow

(III) is the basis test of Corollary 2.6.24(a). Since

𝑇_{𝐴}

is linear, (I)

\Leftrightarrow

(IV) is Theorem 2.6.11.

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

(I) $\Leftrightarrow$ (II). By Definition 2.3.15, $𝐱$ is a solution of $𝐴 𝐱 = 𝐲$ exactly when $𝑇_{𝐴} (𝐱) = 𝐲$ , that is, when $𝐱$ is a preimage of $𝐲$ under $𝑇_{𝐴}$ . So (II) says that every $𝐲 \in 𝐹^{𝑚}$ has at most one preimage under $𝑇_{𝐴}$ , which is the definition of injectivity (Definition 2.6.1).

(I) $\Leftrightarrow$ (III). This is Corollary 2.6.24(a).

(I) $\Leftrightarrow$ (IV). $𝑇_{𝐴}$ is linear (Proposition 2.3.13), so this is Theorem 2.6.11 applied to $𝑇 = 𝑇_{𝐴}$ .

Proof, part 2 of 3: (V) $\Rightarrow$ (I).routine

Uses. Proposition 2.5.4 (Left inverses give uniqueness)

Hint 1. Suppose

𝑆 \circ 𝑇_{𝐴} = {id}_{𝐹^{𝑛}}

and

𝐴 𝐱 = 𝐴 𝐱^{'}

. Apply

𝑆

to both sides.

Hint 2. This is Proposition 2.5.4.

Sketch. Applying

𝑆

𝐴 𝐱 = 𝐴 𝐱^{'}

gives

𝐱 = 𝐱^{'}

. This is Proposition 2.5.4.

Let $𝑆$ be a left inverse of $𝑇_{𝐴}$ . By Proposition 2.5.4, $𝑇_{𝐴}$ is injective. Explicitly, if $𝑇_{𝐴} (𝐱) =$ $𝑇_{𝐴} (𝐱^{'})$ , then

𝐱 = 𝑆 (𝑇_{𝐴} (𝐱)) = 𝑆 (𝑇_{𝐴} (𝐱^{'})) = 𝐱^{'} .

What remains is to show that an injective $𝑇_{𝐴}$ has a left inverse. Since (I)–(IV) are already known to be equivalent, we may start from whichever of them is most convenient, and in Section 2.7.4 we start from (III). Figure 2.7.1 shows the whole web of implications.

Figure 2.7.1. The implications proved for Theorem 2.7.2. The solid arrows are parts 1 and 2 of the proof, which reread earlier results. The dashed arrow (III)

\Rightarrow

(V) is the construction of part 3 (Section 2.7.4). Every node can be reached from every other, so (I)–(V) are equivalent. The faint node is a sixth condition,

rank 𝐴 = 𝑛

, which Section 3.5.2 attaches by the faint arrows. For Theorem 2.7.4 the picture is the same, except that the construction starts from (II), and (VI) attaches at (II) rather than (IV).

Remark 2.7.3 (Reinterpreting earlier results). Part 1 of the proof cites one definition and two earlier results, and nothing else, yet it is a complete proof. Each spoke is a definition or a theorem proved earlier, the hypotheses of the theorems hold here, and equivalence is transitive. What part 1 adds is the translation that lets each earlier result be read as a statement about $𝐴$ . A solution of $𝐴 𝐱 = 𝐲$ is a preimage of $𝐲$ under $𝑇_{𝐴}$ . The columns of $𝐴$ are the values of $𝑇_{𝐴}$ on the standard basis. And $𝑇_{𝐴}$ is linear, so every theorem about linear maps applies to it.

When you cite a result in this way, check two things: that its hypotheses really hold, and that its conclusion, after translation, is literally the implication you need. For instance, Proposition 2.6.22(a) decides injectivity from the values on a basis of the domain; Corollary 2.6.24 is its special case for the standard basis of $𝐹^{𝑛}$ , whose values are the columns. The real work was done in Section 2.6. Collecting the conditions into one theorem is still worthwhile, because in a problem we rarely know in advance which of them is easiest to check, and the theorem lets us check that one and use any other.

Intuition (Five ways to say that everything is reached). The Second Fundamental Theorem is the mirror image of the first. Each of its conditions says that

𝑇_{𝐴}

reaches every vector of

𝐹^{𝑚}

: as a map (I); as a statement about equations (II); as a statement about combinations of the columns (III); as a statement about the image (IV); and, in (V), by a linear map that produces, for each

𝐲

, an input that reaches it.

Theorem 2.7.4 (Second Fundamental Theorem). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝑇_{𝐴}$ is surjective.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has at least one solution $𝐱 \in 𝐹^{𝑛}$ .
(III)The columns of $𝐴$ span $𝐹^{𝑚}$ .
(IV) $im 𝑇_{𝐴} = 𝐹^{𝑚}$ .
(V) $𝑇_{𝐴}$ has a right inverse: a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑇_{𝐴} \circ 𝑆 = {id}_{𝐹^{𝑚}}$ .

Proof, part 1 of 3: (I)–(IV) are equivalent.routine

Uses. Definition 2.6.2 (Surjective), Definition 2.6.6 (Image), Definition 2.3.15 (The linear map of a matrix), Corollary 2.6.24 (The columns decide)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Use (I) as the hub again. Two of the spokes are the definition of surjectivity, read in two ways.

Hint 2. (I)

\Leftrightarrow

(III) is the other half of Corollary 2.6.24.

Sketch. A solution of

𝐴 𝐱 = 𝐲

is a preimage of

𝐲

, so (I)

\Leftrightarrow

(II) is the definition of surjectivity, and so is (I)

\Leftrightarrow

(IV), since

im 𝑇_{𝐴}

is the set of values of

𝑇_{𝐴}

. (I)

\Leftrightarrow

(III) is Corollary 2.6.24(b).

(I) $\Leftrightarrow$ (II). As in the proof of Theorem 2.7.2, the solutions of $𝐴 𝐱 = 𝐲$ are the preimages of $𝐲$ under $𝑇_{𝐴}$ . So (II) says that every $𝐲 \in 𝐹^{𝑚}$ has at least one preimage, which is Definition 2.6.2.

(I) $\Leftrightarrow$ (IV). By Definition 2.6.6, $im 𝑇_{𝐴}$ is the set of values of $𝑇_{𝐴}$ , so $im 𝑇_{𝐴} = 𝐹^{𝑚}$ says that every vector of $𝐹^{𝑚}$ is a value, which is again Definition 2.6.2.

(I) $\Leftrightarrow$ (III). This is Corollary 2.6.24(b).

Instead of the last spoke we could have linked (III) and (IV) directly, since $im 𝑇_{𝐴}$ is the span of the columns (Proposition 2.6.18). The resulting chain (II) $\Leftrightarrow$ (I) $\Leftrightarrow$ (IV) $\Leftrightarrow$ (III) is just as good.

Proof, part 2 of 3: (V) $\Rightarrow$ (I).routine

Uses. Proposition 2.5.5 (Right inverses give existence)

Hint 1. Suppose

𝑇_{𝐴} \circ 𝑆 = {id}_{𝐹^{𝑚}}

, and let

𝐲 \in 𝐹^{𝑚}

. Which vector could

𝑇_{𝐴}

send to

𝐲

Hint 2. This is Proposition 2.5.5.

Sketch.

𝑇_{𝐴} (𝑆 (𝐲)) = 𝐲

for every

𝐲

. This is Proposition 2.5.5.

Let

𝑆

be a right inverse of

𝑇_{𝐴}

. For every

𝐲 \in 𝐹^{𝑚}

𝑇_{𝐴} (𝑆 (𝐲)) = 𝐲

, so

𝐲

is a value of

𝑇_{𝐴}

. This is Proposition 2.5.5.

Again the implication from (I)–(IV) to (V) needs a construction, and it is part 3 of the proof, in Section 2.7.4.

Example 2.7.5 (A tall matrix). Let

𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{matrix}) \in 𝐹^{3 \times 2}, 𝑇_{𝐴} (𝑥, 𝑦) = (𝑥, 𝑥 + 𝑦, 𝑦),

over any field $𝐹$ . Its columns $𝐚_{1} = (1, 1, 0)$ and $𝐚_{2} = (0, 1, 1)$ are linearly independent: if $𝑥 𝐚_{1} +$ $𝑦 𝐚_{2} =$ $(𝑥, 𝑥 + 𝑦, 𝑦) =$ $𝟎$ , then $𝑥 = 𝑦 = 0$ . So condition (III) of Theorem 2.7.2 holds, and with it all of (I)–(V). For instance, by (II) each system $𝐴 𝐱 = 𝐲$ has at most one solution, and by (V) there is a left inverse. Here one is easy to find, since $𝑥$ and $𝑦$ can be read off the first and third entries of $(𝑥, 𝑥 + 𝑦, 𝑦)$ :

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

They can also be read off differently, using $𝑥 = (𝑥 + 𝑦) - 𝑦$ :

𝐶^{'} = (\begin{matrix} 0 & 1 & - 1 \\ 0 & 0 & 1 \end{matrix}), 𝐶^{'} 𝐴 = 𝐼_{2} .

Indeed, the first row of $𝐶^{'}$ sends $𝐚_{1}$ to $0 + 1 - 0 = 1$ and $𝐚_{2}$ to $0 + 1 - 1 = 0$ .

On the other hand, $𝑇_{𝐴}$ is not surjective. The vector $(0, 1, 0)$ would need $𝑥 = 0$ , $𝑦 = 0$ , and $𝑥 + 𝑦 = 1$ , which is impossible. So no condition of Theorem 2.7.4 holds: the columns do not span $𝐹^{3}$ , and there is no right inverse. (Corollary 2.5.11 also rules out a right inverse, since $𝐶 \neq 𝐶^{'}$ .) Uniqueness of solutions and existence of solutions really are independent properties.

Over $ℝ$ , the span explorer below shows the columns of this $𝐴$ and a target $𝐰$ . While $𝐰$ lies in the plane spanned by the columns, the explorer finds coefficients $𝑥, 𝑦$ with $𝑥 𝐚_{1} + 𝑦 𝐚_{2} = 𝐰$ , and they are unique: this is (II) of Theorem 2.7.2. Drag $𝐰$ off the plane and there are none, as Theorem 2.7.4 fails. Adding a third vector off the plane makes the list independent (Proposition 1.5.14), and the explorer reports that it also spans $ℝ^{3}$ ; for three vectors in $ℝ^{3}$ that is no accident (Corollary 3.5.16). The $3 \times 3$ matrix with these columns then satisfies all three theorems.

\begin{matrix} (1, 2, 1) = 𝐚_{1} + 𝐚_{2}, \\ span (𝐚_{1}, 𝐚_{2}) = {(𝑎, 𝑏, 𝑐) \in ℝ^{3} | 𝑏 = 𝑎 + 𝑐} . \end{matrix}

The columns

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

and

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

of the matrix

𝐴

of Example 2.7.5. They are independent, so a target in their span has exactly one pair of coefficients; the target

𝐰 =

(1, 2, 1) =

𝐚_{1} +

𝐚_{2}

gives

(𝑥, 𝑦) = (1, 1)

. A target off the plane has none.

Exercise 2.7.6.routine Let

𝐚 \in 𝐹^{𝑚}

, regarded as a matrix in

𝐹^{𝑚 \times 1}

, so that

𝑇_{𝐚} : 𝐹 \to 𝐹^{𝑚}

𝑥 \mapsto 𝑥 𝐚

. Show directly, without quoting Theorem 2.7.2, that the following are equivalent: (i)

𝑇_{𝐚}

is injective; (ii)

𝐚 \neq 𝟎

; (iii)

𝐚

has a left inverse

𝐜 \in 𝐹^{1 \times 𝑚}

, that is,

𝐜 𝐚 = 1

. Which step corresponds to the construction in part 3 of the proof of Theorem 2.7.2?

Solution.

Uses. Proposition 2.5.4 (Left inverses give uniqueness), Definition 2.6.1 (Injective), Definition 2.4.1 (Matrix product)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Prove (i)

\Rightarrow

(ii)

\Rightarrow

(iii)

\Rightarrow

(i). The last step is Proposition 2.5.4.

Hint 2. For (ii)

\Rightarrow

(iii), some entry

𝑎_{𝑘}

𝐚

is nonzero. Find a row

𝐜

that reads off

𝑎_{𝑘}

and divides by it.

Sketch. (i)

\Rightarrow

(ii):

𝑇_{𝐚} (1) = 𝐚

and

𝑇_{𝐚} (0) = 𝟎

, so

𝐚 = 𝟎

would contradict injectivity. (ii)

\Rightarrow

(iii): if

𝑎_{𝑘} \neq 0

, the row

𝐜 = 𝑎_{𝑘}^{- 1} 𝐞_{𝑘}^{𝖳}

has

𝐜 𝐚 = 𝑎_{𝑘}^{- 1} 𝑎_{𝑘} = 1

. (iii)

\Rightarrow

(i): left-invertible maps are injective. The construction is (ii)

\Rightarrow

(iii).

We prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i).

(i) $\Rightarrow$ (ii). $𝑇_{𝐚} (1) = 𝐚$ and $𝑇_{𝐚} (0) = 𝟎$ . If $𝐚 = 𝟎$ , these are two different inputs with the same value, so $𝑇_{𝐚}$ would not be injective (Definition 2.6.1).

(ii) $\Rightarrow$ (iii). Since $𝐚 \neq 𝟎$ , some entry $𝑎_{𝑘}$ is nonzero. Let $𝐜 \in 𝐹^{1 \times 𝑚}$ be the row with entry $𝑎_{𝑘}^{- 1}$ in position $𝑘$ and $0$ elsewhere. By Definition 2.4.1, $𝐜 𝐚 = 𝑎_{𝑘}^{- 1} 𝑎_{𝑘} = 1$ .

(iii) $\Rightarrow$ (i). If $𝐜 𝐚 = 1$ , then $𝑇_{𝐜}$ is a left inverse of $𝑇_{𝐚}$ , since $𝐜 (𝑥 𝐚) =$ $𝑥 (𝐜 𝐚) =$ $𝑥$ . So $𝑇_{𝐚}$ is injective by Proposition 2.5.4.

The step (ii) $\Rightarrow$ (iii) produces the left inverse, so it is the case $𝑛 = 1$ of the construction in part 3. Run on the single column $𝐚$ , that construction appends every $𝐞_{𝑖}$ except $𝐞_{𝑘}$ for the last index $𝑘$ with $𝑎_{𝑘} \neq 0$ , and it produces exactly the row $𝐜 = 𝑎_{𝑘}^{- 1} 𝐞_{𝑘}^{𝖳}$ .

2.7.3The Third Fundamental Theorem

For the Third Fundamental Theorem, the implication from bijectivity to invertibility is much easier than the corresponding implications for one-sided inverses. As the lecture puts it, there is only one plausible choice for the inverse.

Intuition (Only one candidate). Let

𝑇 \in L (𝑉, 𝑊)

be bijective. If

𝑆

is a two-sided inverse of

𝑇

, then

𝑇 (𝑆 (𝐰)) = 𝐰

for every

𝐰 \in 𝑊

, so

𝑆 (𝐰)

is a preimage of

𝐰

. Since

𝑇

is bijective,

𝐰

has exactly one preimage. So

𝑆

has to be the inverse function of

𝑇

, which sends each

𝐰

to its unique preimage, and the only question is whether that function is linear. For a left inverse of an injective map there is no such uniqueness: its values off the image are free, and many choices are not linear (Remark 2.5.8).

Proposition 2.7.7 (Bijective linear maps are invertible). Let

𝑇 \in L (𝑉, 𝑊)

be bijective, and let

𝑆 : 𝑊 \to 𝑉

be its inverse function:

𝑆 (𝐰)

is the unique

𝐯 \in 𝑉

with

𝑇 (𝐯) = 𝐰

. Then

𝑆

is linear. Consequently

𝑇

is invertible, and

𝑇^{- 1} = 𝑆

Proof.routine

Uses. Definition 2.6.3 (Bijective), Definition 2.1.1 (Linear map), Definition 2.5.12 (Invertible), Section A.1

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

Hint 1. To compute

𝑆

at a vector, find the vector that

𝑇

sends there. Fix

𝐰_{1}, \dots, 𝐰_{𝑘} \in 𝑊

and scalars

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

, and look for the vector that

𝑇

sends to

𝑎_{1} 𝐰_{1} + \dots + 𝑎_{𝑘} 𝐰_{𝑘}

Hint 2. Put

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

, so that

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

. What is

𝑇 (𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘})

Sketch. With

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

, linearity of

𝑇

gives

𝑇 (\sum 𝑎_{𝑖} 𝐯_{𝑖}) =

\sum 𝑎_{𝑖} 𝐰_{𝑖}

, so by the definition of

𝑆

𝑆 (\sum 𝑎_{𝑖} 𝐰_{𝑖}) =

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

\sum 𝑎_{𝑖} 𝑆 (𝐰_{𝑖})

. Since

𝑆

is the inverse function,

𝑆 𝑇 = {id}_{𝑉}

and

𝑇 𝑆 = {id}_{𝑊}

Since $𝑇$ is bijective, every $𝐰 \in 𝑊$ has exactly one preimage (Definition 2.6.3), so $𝑆$ is a well-defined function $𝑊 \to 𝑉$ , and $𝑇 (𝑆 (𝐰)) = 𝐰$ for every $𝐰$ .

Fix $𝐰_{1}, \dots, 𝐰_{𝑘} \in 𝑊$ and $𝑎_{1}, \dots, 𝑎_{𝑘} \in 𝐹$ . We will show that $𝑆 (𝑎_{1} 𝐰_{1} + \dots + 𝑎_{𝑘} 𝐰_{𝑘}) =$ $𝑎_{1} 𝑆 (𝐰_{1}) +$ $\dots +$ $𝑎_{𝑘} 𝑆 (𝐰_{𝑘})$ . Put $𝐯_{𝑖} = 𝑆 (𝐰_{𝑖})$ , so that $𝑇 (𝐯_{𝑖}) = 𝐰_{𝑖}$ . Since $𝑇$ is linear,

\begin{aligned} 𝑇 (𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘}) & = 𝑎_{1} 𝑇 (𝐯_{1}) + \dots + 𝑎_{𝑘} 𝑇 (𝐯_{𝑘}) \\ = 𝑎_{1} 𝐰_{1} + \dots + 𝑎_{𝑘} 𝐰_{𝑘} . \end{aligned}

So $𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘}$ is the preimage of $𝑎_{1} 𝐰_{1} + \dots + 𝑎_{𝑘} 𝐰_{𝑘}$ , and by the definition of $𝑆$ ,

\begin{aligned} 𝑆 (𝑎_{1} 𝐰_{1} + \dots + 𝑎_{𝑘} 𝐰_{𝑘}) & = 𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘} \\ = 𝑎_{1} 𝑆 (𝐰_{1}) + \dots + 𝑎_{𝑘} 𝑆 (𝐰_{𝑘}), \end{aligned}

as desired. Thus $𝑆$ is linear (Definition 2.1.1).

Finally, $𝑆$ is the inverse function of $𝑇$ (Section A.1): $𝑆 (𝑇 (𝐯)) = 𝐯$ , because $𝐯$ is the preimage of $𝑇 (𝐯)$ , and $𝑇 (𝑆 (𝐰)) = 𝐰$ . So $𝑆$ is a linear map that is both a left and a right inverse of $𝑇$ , and $𝑇$ is invertible with $𝑇^{- 1} = 𝑆$ (Definition 2.5.12). □

No basis appeared in the proof, so the proposition holds for every bijective linear map, between any two vector spaces. Together with Proposition 2.5.4 and Proposition 2.5.5 it says that a linear map is invertible if and only if it is bijective.

Intuition (The third theorem from the first two). “Exactly one” means “at most one and at least one”. Each condition (I)–(IV) of the Third Fundamental Theorem below is, in the same way, the combination of condition (I)–(IV) of Theorem 2.7.2 with the same condition of Theorem 2.7.4: bijective means injective and surjective, a basis is an independent spanning list, and (IV) is written as a combination. So the equivalence of (I)–(IV) is inherited from the first two theorems, and only (V) needs an argument.

Theorem 2.7.8 (Third Fundamental Theorem). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝑇_{𝐴}$ is bijective.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has exactly one solution $𝐱 \in 𝐹^{𝑛}$ .
(III)The columns of $𝐴$ form a basis of $𝐹^{𝑚}$ .
(IV) $ker 𝑇_{𝐴} = {𝟎}$ and $im 𝑇_{𝐴} = 𝐹^{𝑚}$ .
(V) $𝑇_{𝐴}$ is invertible.

Proof, part 1 of 3: (I)–(IV) are equivalent.routine

Uses. Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Definition 2.6.3 (Bijective), Proposition 1.6.2 (Bases are independent spanning lists)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Write each of (I)–(IV) as “

𝑃

and

𝑄

”, where

𝑃

is the corresponding condition of Theorem 2.7.2 and

𝑄

that of Theorem 2.7.4.

Hint 2. If

𝑃_{𝑖} \Leftrightarrow 𝑃_{𝑗}

and

𝑄_{𝑖} \Leftrightarrow 𝑄_{𝑗}

, then (

𝑃_{𝑖}

and

𝑄_{𝑖}

)

\Leftrightarrow

(

𝑃_{𝑗}

and

𝑄_{𝑗}

). Use only parts 1 of the proofs of the first two theorems.

Sketch. Bijective = injective and surjective; exactly one = at most one and at least one; basis = independent and spanning (Proposition 1.6.2); (IV) is the combination of the two (IV)s. By parts 1 of the proofs of Theorem 2.7.2 and Theorem 2.7.4, the first halves are equivalent to each other, and so are the second halves; hence so are the conjunctions.

Each of the conditions (I)–(IV) of the present theorem combines the condition with the same numeral in Theorem 2.7.2 with the one in Theorem 2.7.4:

(I) says that $𝑇_{𝐴}$ is injective and surjective (Definition 2.6.3);
(II) says that $𝐴 𝐱 = 𝐲$ has at most one and at least one solution, for every $𝐲$ ;
(III) says that the columns of $𝐴$ are linearly independent and span $𝐹^{𝑚}$ (Proposition 1.6.2);
(IV) says that $ker 𝑇_{𝐴} = {𝟎}$ and $im 𝑇_{𝐴} = 𝐹^{𝑚}$ .

By part 1 of the proof of Theorem 2.7.2, the first halves of these four conditions are equivalent to one another, and by part 1 of the proof of Theorem 2.7.4, so are the second halves. If $𝑃 \Leftrightarrow 𝑃^{'}$ and $𝑄 \Leftrightarrow 𝑄^{'}$ , then ( $𝑃$ and $𝑄$ ) $\Leftrightarrow$ ( $𝑃^{'}$ and $𝑄^{'}$ ). So (I)–(IV) are equivalent.

Proof, part 2 of 3: (V) $\Rightarrow$ (I).routine

Uses. Definition 2.5.12 (Invertible), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 2.5.5 (Right inverses give existence)

Hint 1. An inverse is both a left and a right inverse.

Hint 2. Apply Proposition 2.5.4 and Proposition 2.5.5.

Sketch.

𝑇_{𝐴}^{- 1}

is a left inverse, so

𝑇_{𝐴}

is injective, and a right inverse, so

𝑇_{𝐴}

is surjective.

𝑇_{𝐴}

is invertible, then

𝑇_{𝐴}^{- 1}

is a left inverse and a right inverse of

𝑇_{𝐴}

(Definition 2.5.12). By Proposition 2.5.4 and Proposition 2.5.5,

𝑇_{𝐴}

is injective and surjective, that is, bijective.

For the last step we give two proofs. The first is the lecture’s; the second builds the inverse on a basis, and it is the model for the constructions in Section 2.7.4.

Proof (via the inverse function), part 3 of 3: (I) $\Rightarrow$ (V).routine

Uses. Proposition 2.7.7 (Bijective linear maps are invertible), Proposition 2.3.13 (Linearity of the product)

Hint.

𝑇_{𝐴}

is a bijective linear map. What do we know about the inverse function of such a map?

Sketch. The inverse function of the bijective linear map

𝑇_{𝐴}

is linear (Proposition 2.7.7), so it is a linear two-sided inverse.

𝑇_{𝐴}

is linear (Proposition 2.3.13) and, by (I), bijective. By Proposition 2.7.7 it is invertible. □

Proof (by building the inverse on a basis), part 3 of 3: (III) $\Rightarrow$ (V).routine

Uses. Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 1.6.7 (Standard bases), Proposition 2.3.13 (Linearity of the product)

Techniques. Construct a map by choosing it on a basis (Technique 2.2.4), Check it on a basis (Technique 2.2.7)

Hint 1. An inverse

𝑆

must send

𝐚_{𝑗} = 𝑇_{𝐴} (𝐞_{𝑗})

back to

𝐞_{𝑗}

. Since

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

is a basis of

𝐹^{𝑚}

, these values can be prescribed.

Hint 2. Let

𝑆

be the linear map with

𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}

. Check

𝑆 \circ 𝑇_{𝐴} = id

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

, and

𝑇_{𝐴} \circ 𝑆 = id

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

Sketch. By Theorem 2.2.1 there is a linear

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

with

𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}

. Then

𝑆 (𝑇_{𝐴} (𝐞_{𝑗})) =

𝐞_{𝑗}

and

𝑇_{𝐴} (𝑆 (𝐚_{𝑗})) =

𝐚_{𝑗}

, so

𝑆 \circ 𝑇_{𝐴}

and

𝑇_{𝐴} \circ 𝑆

agree with the identity on a basis, and are the identity.

Suppose the columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ form a basis of $𝐹^{𝑚}$ . By Theorem 2.2.1 there is a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}$ for $𝑗 = 1, \dots, 𝑛$ . Recall that $𝑇_{𝐴} (𝐞_{𝑗}) =$ $𝐴 𝐞_{𝑗} =$ $𝐚_{𝑗}$ (Proposition 2.3.13(c)). Then

\begin{aligned} (𝑆 \circ 𝑇_{𝐴}) (𝐞_{𝑗}) & = 𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}, \\ (𝑇_{𝐴} \circ 𝑆) (𝐚_{𝑗}) & = 𝑇_{𝐴} (𝐞_{𝑗}) = 𝐚_{𝑗} \end{aligned}

for every $𝑗$ . So the linear maps $𝑆 \circ 𝑇_{𝐴}$ and ${id}_{𝐹^{𝑛}}$ agree on the basis $𝐞_{1}, \dots, 𝐞_{𝑛}$ of $𝐹^{𝑛}$ (Proposition 1.6.7), and $𝑇_{𝐴} \circ 𝑆$ and ${id}_{𝐹^{𝑚}}$ agree on the basis $𝐚_{1}, \dots, 𝐚_{𝑛}$ of $𝐹^{𝑚}$ . By the uniqueness in Theorem 2.2.1, $𝑆 \circ 𝑇_{𝐴} = {id}_{𝐹^{𝑛}}$ and $𝑇_{𝐴} \circ 𝑆 = {id}_{𝐹^{𝑚}}$ . So $𝑆$ is a linear two-sided inverse of $𝑇_{𝐴}$ . □

The first proof works for any bijective linear map, with no bases at all. The second uses that the columns are a basis of the target, and it explains where the inverse comes from: it undoes $𝑇_{𝐴}$ on the columns, and the columns are a basis, so nothing else needs to be decided. In Section 2.7.4 the columns will only be independent, or only spanning, and then something does have to be decided.

Example 2.7.9 (One matrix over three fields). Let $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ . The system $𝐴 𝐱 = 𝐲$ reads

𝑥_{1} + 𝑥_{2} = 𝑦_{1}, 𝑥_{1} - 𝑥_{2} = 𝑦_{2} .

Adding and subtracting the equations shows that every solution satisfies $2 𝑥_{1} = 𝑦_{1} + 𝑦_{2}$ and $2 𝑥_{2} = 𝑦_{1} - 𝑦_{2}$ , where $2 = 1 + 1$ .

Over $ℚ$ , or any field with $2 \neq 0$ , this gives $𝑥_{1} = 2^{- 1} (𝑦_{1} + 𝑦_{2})$ and $𝑥_{2} = 2^{- 1} (𝑦_{1} - 𝑦_{2})$ , and conversely these values solve the system. So the system has exactly one solution for every $𝐲$ , which is (II) of Theorem 2.7.8, and $𝐴$ is invertible. The solution formula is the inverse:

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

Over $𝔽_{3}$ , where $2^{- 1} = 2$ and $- 1 = 2$ , this reads $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix})$ and $𝐴^{- 1} = (\begin{matrix} 2 & 2 \\ 2 & 1 \end{matrix})$ , and indeed $𝐴 𝐴^{- 1} = (\begin{matrix} 4 & 3 \\ 6 & 4 \end{matrix}) = 𝐼_{2}$ in $𝔽_{3}$ .

Over $𝔽_{2}$ , $- 1 = 1$ , so both columns are $(1, 1)$ , and $𝐴 (1, 1) = 𝟎$ . So (IV) of Theorem 2.7.2 fails, and with it every condition of Theorem 2.7.2 and Theorem 2.7.8. Every value $𝐴 𝐱 =$ $(𝑥_{1} + 𝑥_{2}) (1, 1)$ is a multiple of $(1, 1)$ , so $(1, 0)$ is not a value, and every condition of Theorem 2.7.4 fails as well.

2.7.4Constructing one-sided inverses

It remains to prove (I) $\Rightarrow$ (V) in the first two theorems: an injective $𝑇_{𝐴}$ has a left inverse, and a surjective $𝑇_{𝐴}$ has a right inverse.

Intuition (What has to be chosen). A left inverse

𝑆

of an injective

𝑇_{𝐴}

is forced on the image: it must send

𝐴 𝐱

𝐱

. Off the image nothing forces it, but whatever we choose there has to fit together into a linear map on all of

𝐹^{𝑚}

. A right inverse of a surjective

𝑇_{𝐴}

must pick, for each

𝐲 \in 𝐹^{𝑚}

, one solution

𝑆 (𝐲)

𝐴 𝐱 = 𝐲

, and when

𝑇_{𝐴}

is not injective there are many solutions to pick from. Again the picks must fit together linearly. Choices made one vector at a time usually do not, as the next example shows. Choices made on a basis always do, by Theorem 2.2.1, and that is all the proofs below use (Technique 2.2.4).

The lecture does not prove these implications at this point. It returns to them in Section 3.5, after row reduction, where left and right inverses are computed from $rref (𝐴)$ as explicit matrices (Proposition 3.5.9, Proposition 3.5.8), and the completed theorems (Theorem 3.5.12, Theorem 3.5.13) close the loops through a sixth condition. That is the route to use for computing. Here is a second route, which needs only Theorem 2.2.1 (and, for left inverses, Proposition 1.5.14) and no row reduction.

Non-example 2.7.10 (Choices that are not linear).

(a)Let $𝑇 : 𝐹 \to 𝐹^{2}$ , $𝑇 (𝑥) = (𝑥, 0)$ , the map of Example 2.5.3. Undo $𝑇$ on its image and send everything else to $0$ :
$𝑔 (𝑥, 0) = 𝑥, 𝑔 (𝑥, 𝑦) = 0 if 𝑦 \neq 0 .$
Then $𝑔 (𝑇 (𝑥)) = 𝑥$ for every $𝑥$ , but $𝑔$ is not linear, since $𝑔 (1, 1) = 0$ while $𝑔 (1, 0) +$ $𝑔 (0, 1) =$ $1 +$ $0 =$ $1$ .
(b)Let $𝐴 = (\begin{matrix} 1 & 1 \end{matrix}) \in ℝ^{1 \times 2}$ , so $𝑇_{𝐴} (𝑥_{1}, 𝑥_{2}) =$ $𝑥_{1} +$ $𝑥_{2}$ . For each $𝑦 \in ℝ$ , choose the solution
$ℎ (𝑦) = (𝑦, 0) if 𝑦 \geq 0, ℎ (𝑦) = (0, 𝑦) if 𝑦 < 0 .$
Then $𝑇_{𝐴} (ℎ (𝑦)) = 𝑦$ for every $𝑦$ , but $ℎ$ is not linear, since $ℎ (1) + ℎ (- 1) = (1, - 1)$ while $ℎ (0) = (0, 0)$ .

For a right inverse, the basis to choose on is the standard basis of the target.

Proof of Theorem 2.7.4, part 3 of 3: (II) $\Rightarrow$ (V).routine

Uses. Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 1.6.7 (Standard bases), Definition 2.5.2 (Right inverse)

Techniques. Construct a map by choosing it on a basis (Technique 2.2.4), Check it on a basis (Technique 2.2.7)

Hint 1. A right inverse has to choose a solution of

𝐴 𝐱 = 𝐲

for every

𝐲

. Make the choice only for

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

Hint 2. Choose solutions

𝐱_{𝑖}

𝐴 𝐱 = 𝐞_{𝑖}

, let

𝑆

be the linear map with

𝑆 (𝐞_{𝑖}) = 𝐱_{𝑖}

, and check

𝑇_{𝐴} \circ 𝑆 = id

on the standard basis.

Sketch. By (II), choose

𝐱_{𝑖}

with

𝐴 𝐱_{𝑖} = 𝐞_{𝑖}

for

𝑖 = 1, \dots, 𝑚

. Let

𝑆

be the linear map with

𝑆 (𝐞_{𝑖}) = 𝐱_{𝑖}

(Theorem 2.2.1). Then

𝑇_{𝐴} (𝑆 (𝐞_{𝑖})) =

𝐞_{𝑖}

, so

𝑇_{𝐴} \circ 𝑆

agrees with

{id}_{𝐹^{𝑚}}

on a basis and equals it. In matrices,

𝐴 𝐵 = 𝐼_{𝑚}

for the matrix

𝐵

with columns

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

Suppose (II). For each $𝑖 = 1, \dots, 𝑚$ , the equation $𝐴 𝐱 = 𝐞_{𝑖}$ has a solution; choose one and call it $𝐱_{𝑖}$ . Since $𝐞_{1}, \dots, 𝐞_{𝑚}$ is a basis of $𝐹^{𝑚}$ (Proposition 1.6.7), Theorem 2.2.1 gives a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑆 (𝐞_{𝑖}) = 𝐱_{𝑖}$ for every $𝑖$ . Then

(𝑇_{𝐴} \circ 𝑆) (𝐞_{𝑖}) = 𝐴 𝐱_{𝑖} = 𝐞_{𝑖} = {id}_{𝐹^{𝑚}} (𝐞_{𝑖}) (𝑖 = 1, \dots, 𝑚),

so the linear maps $𝑇_{𝐴} \circ 𝑆$ and ${id}_{𝐹^{𝑚}}$ agree on a basis, and they are equal by the uniqueness in Theorem 2.2.1. So $𝑆$ is a right inverse of $𝑇_{𝐴}$ (Definition 2.5.2). In matrix terms, $𝑆 = 𝑇_{𝐵}$ for the matrix $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ with columns $𝐱_{1}, \dots, 𝐱_{𝑚}$ , and $𝐴 𝐵 = 𝐼_{𝑚}$ . □

For a left inverse the values on the columns are forced, $𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}$ . The columns are independent but need not span $𝐹^{𝑚}$ , so before we can use Theorem 2.2.1 we must complete them to a basis.

Proof of Theorem 2.7.2, part 3 of 3: (III) $\Rightarrow$ (V).standard

Uses. Proposition 1.5.14 (Appending a vector), Proposition 1.4.14 (The span is the smallest subspace containing a list), Proposition 1.6.7 (Standard bases), Proposition 1.6.2 (Bases are independent spanning lists), Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 2.3.13 (Linearity of the product), Definition 2.5.1 (Left inverse)

Techniques. Construct a map by choosing it on a basis (Technique 2.2.4), Check it on a basis (Technique 2.2.7)

Hint 1. A left inverse must send

𝐚_{𝑗} = 𝑇_{𝐴} (𝐞_{𝑗})

𝐞_{𝑗}

. To prescribe these values with Theorem 2.2.1, the

𝐚_{𝑗}

have to be part of a basis of

𝐹^{𝑚}

Hint 2. Go through

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

in turn, and append each one that is not in the span of the list built so far. Why does the final list span

𝐹^{𝑚}

, and why is it still independent?

Hint 3. Define

𝑆

on the resulting basis by

𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}

and

𝑆 = 𝟎

on the appended vectors. Check

𝑆 \circ 𝑇_{𝐴} = id

on the standard basis of

𝐹^{𝑛}

Sketch. Append to

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

each

𝐞_{𝑖}

that is not in the span of the list so far. By Proposition 1.5.14 the list stays independent, and every

𝐞_{𝑖}

ends up in its span, so it becomes a basis

𝐚_{1},

\dots,

𝐚_{𝑛},

𝐞_{𝑖_{1}},

\dots,

𝐞_{𝑖_{𝑡}}

𝐹^{𝑚}

. Let

𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}

and

𝑆 (𝐞_{𝑖_{𝑠}}) = 𝟎

. Then

𝑆 (𝑇_{𝐴} (𝐞_{𝑗})) =

𝐞_{𝑗}

, so

𝑆 \circ 𝑇_{𝐴} = {id}_{𝐹^{𝑛}}

Suppose the columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ are linearly independent.

Completing the columns to a basis. Let ${ℒ︀}_{0}$ be the list $𝐚_{1}, \dots, 𝐚_{𝑛}$ . For $𝑖 = 1, \dots, 𝑚$ in turn, let ${ℒ︀}_{𝑖} = {ℒ︀}_{𝑖 - 1}$ if $𝐞_{𝑖} \in span ({ℒ︀}_{𝑖 - 1})$ , and let ${ℒ︀}_{𝑖}$ be ${ℒ︀}_{𝑖 - 1}$ with $𝐞_{𝑖}$ appended otherwise. By Proposition 1.5.14 and induction on $𝑖$ , every ${ℒ︀}_{𝑖}$ is linearly independent. For each $𝑖$ , the vector $𝐞_{𝑖}$ lies in $span ({ℒ︀}_{𝑖})$ , either because it was already in $span ({ℒ︀}_{𝑖 - 1})$ or because it was appended, and $span ({ℒ︀}_{𝑖}) \subseteq$ $span ({ℒ︀}_{𝑚})$ , since ${ℒ︀}_{𝑖}$ is an initial part of ${ℒ︀}_{𝑚}$ . So the subspace $span ({ℒ︀}_{𝑚})$ contains $𝐞_{1}, \dots, 𝐞_{𝑚}$ , hence all of their linear combinations (Proposition 1.4.14), which is all of $𝐹^{𝑚}$ (Proposition 1.6.7). Thus

{ℒ︀}_{𝑚} = 𝐚_{1}, \dots, 𝐚_{𝑛}, 𝐞_{𝑖_{1}}, \dots, 𝐞_{𝑖_{𝑡}}

is linearly independent and spans $𝐹^{𝑚}$ , so it is a basis of $𝐹^{𝑚}$ (Proposition 1.6.2).

Defining $𝑆$ . By Theorem 2.2.1 there is a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with

\begin{aligned} 𝑆 (𝐚_{𝑗}) & = 𝐞_{𝑗} (𝑗 = 1, \dots, 𝑛), \\ 𝑆 (𝐞_{𝑖_{𝑠}}) & = 𝟎 (𝑠 = 1, \dots, 𝑡) . \end{aligned}

Since $𝑇_{𝐴} (𝐞_{𝑗}) = 𝐚_{𝑗}$ (Proposition 2.3.13(c)), we get $(𝑆 \circ 𝑇_{𝐴}) (𝐞_{𝑗}) =$ $𝑆 (𝐚_{𝑗}) =$ $𝐞_{𝑗}$ for every $𝑗$ . So $𝑆 \circ 𝑇_{𝐴}$ and ${id}_{𝐹^{𝑛}}$ agree on the standard basis of $𝐹^{𝑛}$ , and they are equal by the uniqueness in Theorem 2.2.1. That is, $𝑆$ is a left inverse of $𝑇_{𝐴}$ (Definition 2.5.1). □

This completes the proofs of all three theorems.

Remark 2.7.11 (What was chosen, and what was not). In both constructions, the choices are exactly the freedom that one-sided inverses have. A right inverse is determined by its values $𝑆 (𝐞_{𝑖})$ , which may be any solutions of $𝐴 𝐱 = 𝐞_{𝑖}$ ; when $𝑇_{𝐴}$ is not injective, each of these equations has many solutions. A left inverse is forced on the columns, and its values on the appended vectors $𝐞_{𝑖_{𝑠}}$ were set to $𝟎$ only for definiteness; any values work. So when $𝑇_{𝐴}$ is injective but not surjective, it has many left inverses, in line with Corollary 2.5.11.

The completion step is the special case of Theorem 4.1.16 in which the spanning list is $𝐞_{1}, \dots, 𝐞_{𝑚}$ . In $𝐹^{𝑚}$ it needs no theory of dimension, because each of the $𝑚$ standard basis vectors is tested once. The same proof works for $𝑇 \in L (𝑉, 𝑊)$ whenever $𝑉$ and $𝑊$ have finite bases: if $𝑇$ is injective and $ℬ︀$ is a basis of $𝑉$ , complete the independent list $𝑇 (ℬ︀)$ to a basis of $𝑊$ , testing the vectors of a basis of $𝑊$ in place of $𝐞_{1}, \dots, 𝐞_{𝑚}$ (compare Corollary 2.7.16 below). For arbitrary vector spaces one needs Zorn’s lemma (Remark 2.5.25).

Example 2.7.12 (All left inverses of the tall matrix). Return to $𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{matrix})$ from Example 2.7.5, with columns $𝐚_{1} = (1, 1, 0)$ and $𝐚_{2} = (0, 1, 1)$ . Their span consists of the vectors $(𝑥, 𝑥 + 𝑦, 𝑦)$ , whose middle entry is the sum of the other two. The vector $𝐞_{1} = (1, 0, 0)$ fails this test, so it is appended. Now every vector is a combination of $𝐚_{1}, 𝐚_{2}, 𝐞_{1}$ , since

(𝑝, 𝑞, 𝑟) = 𝛼 𝐚_{1} + 𝛽 𝐚_{2} + 𝛾 𝐞_{1} = (𝛼 + 𝛾, 𝛼 + 𝛽, 𝛽)

holds for $𝛽 = 𝑟$ , $𝛼 = 𝑞 - 𝑟$ , and $𝛾 = 𝑝 - 𝑞 + 𝑟$ . So $𝐞_{2}$ and $𝐞_{3}$ are not appended, and $𝐚_{1}, 𝐚_{2}, 𝐞_{1}$ is a basis of $𝐹^{3}$ .

A linear map $𝑆 : 𝐹^{3} \to 𝐹^{2}$ is a left inverse of $𝑇_{𝐴}$ exactly when $𝑆 (𝐚_{1}) = 𝐞_{1}$ and $𝑆 (𝐚_{2}) = 𝐞_{2}$ (check $𝑆 \circ 𝑇_{𝐴} = id$ on $𝐞_{1}, 𝐞_{2}$ ). Its value $𝑆 (𝐞_{1}) = (𝑐, 𝑑)$ is free. With the coordinates above,

𝑆 (𝑝, 𝑞, 𝑟) = (𝑞 - 𝑟) 𝐞_{1} + 𝑟 𝐞_{2} + (𝑝 - 𝑞 + 𝑟) (𝑐, 𝑑) .

Collecting the coefficients of $𝑝$ , $𝑞$ , and $𝑟$ in each entry, the left inverses of $𝐴$ are exactly the matrices

𝑆_{𝑐, 𝑑} = (\begin{matrix} 𝑐 & 1 - 𝑐 & 𝑐 - 1 \\ 𝑑 & - 𝑑 & 1 + 𝑑 \end{matrix}) (𝑐, 𝑑 \in 𝐹) .

The construction in the proof, with $𝑆 (𝐞_{1}) = 𝟎$ , gives $𝑆_{0, 0} = 𝐶^{'}$ , and $𝑆_{1, 0} = 𝐶$ ; these are the two left inverses found by inspection in Example 2.7.5. Over $𝔽_{2}$ there are exactly four left inverses, and over $ℚ$ infinitely many.

With the constructions in hand, the theorems can be used in the direction that the propositions of Section 2.5 could not reach: a matrix without a one-sided inverse fails the other conditions too.

Exercise 2.7.13.routine Let

𝐴 =

(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) \in

𝐹^{2 \times 2}

. Show that the following are equivalent:

𝑇_{𝐴}

is injective;

𝑇_{𝐴}

is surjective;

𝑎 𝑑 - 𝑏 𝑐 \neq 0

. (Use Proposition 2.5.28.)

Solution.

Uses. Proposition 2.5.28 (Inverse of a $2 \times 2$ matrix), Proposition 2.5.20 (Inverses and matrices), Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Theorem 2.7.8 (Third Fundamental Theorem)

Hint 1. Treat the two cases

𝑎 𝑑 - 𝑏 𝑐 \neq 0

and

𝑎 𝑑 - 𝑏 𝑐 = 0

separately. In each case, Proposition 2.5.28 tells you which inverses

𝐴

has.

Hint 2. If

𝑎 𝑑 - 𝑏 𝑐 = 0

𝐴

has no left inverse. Which condition of Theorem 2.7.2 fails, and what does that say about (I)?

Sketch. If

Δ = 𝑎 𝑑 - 𝑏 𝑐 \neq 0

, then

𝐴

is invertible, so

𝑇_{𝐴}

is invertible and hence injective and surjective (Theorem 2.7.8). If

Δ = 0

, then

𝐴

has no left and no right inverse, so neither does

𝑇_{𝐴}

; (V) fails in Theorem 2.7.2 and Theorem 2.7.4, so (I) fails in both:

𝑇_{𝐴}

is neither injective nor surjective. In both cases the three statements have the same truth value.

Let $Δ = 𝑎 𝑑 - 𝑏 𝑐$ . By Proposition 2.5.20(c), $𝐴$ has a left inverse, a right inverse, or an inverse exactly when $𝑇_{𝐴}$ does.

If $Δ \neq 0$ , then $𝐴$ is invertible by Proposition 2.5.28(a), so $𝑇_{𝐴}$ is invertible, and by Theorem 2.7.8 it is bijective. So all three statements hold.

If $Δ = 0$ , then by Proposition 2.5.28(b), $𝐴$ has neither a left nor a right inverse, so neither does $𝑇_{𝐴}$ . Condition (V) of Theorem 2.7.2 fails, so (I) fails: $𝑇_{𝐴}$ is not injective. Condition (V) of Theorem 2.7.4 fails, so $𝑇_{𝐴}$ is not surjective. So all three statements fail.

The second case used (I) $\Rightarrow$ (V) in both theorems, in contrapositive form. Without the constructions of this section, we would only know that $𝐴$ has no inverse on either side.

2.7.5Using the theorems

Once a list of conditions is known to be equivalent, a question posed in one language can be answered in another. The following is a typical instance.

Example 2.7.14 (Products of matrices with independent columns). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ both have linearly independent columns. We claim that $𝐴 𝐵$ does too.

Stated with columns, the claim takes some unwinding, since the columns of $𝐴 𝐵$ are the vectors $𝐴 𝐛_{𝑘}$ , each a combination of the columns of $𝐴$ with coefficients from a column of $𝐵$ (Proposition 2.4.8). In the language of kernels it takes one line. By Theorem 2.7.2, (III) $\Rightarrow$ (IV), $ker 𝑇_{𝐴} = {𝟎}$ and $ker 𝑇_{𝐵} = {𝟎}$ . If $(𝐴 𝐵) 𝐱 = 𝟎$ , then $𝐴 (𝐵 𝐱) = 𝟎$ , so $𝐵 𝐱 \in ker 𝑇_{𝐴}$ , so $𝐵 𝐱 = 𝟎$ , so $𝐱 = 𝟎$ . Thus $ker 𝑇_{𝐴 𝐵} = {𝟎}$ , and by (IV) $\Rightarrow$ (III) for $𝐴 𝐵$ , the columns of $𝐴 𝐵$ are independent.

Condition (V) gives another one-line proof. By Proposition 2.5.20(c), (V) says that the matrix has a left inverse. If $𝐶 𝐴 = 𝐼_{𝑛}$ and $𝐷 𝐵 = 𝐼_{𝑝}$ , then $(𝐷 𝐶) (𝐴 𝐵) =$ $𝐷 (𝐶 𝐴) 𝐵 =$ $𝐷 𝐵 =$ $𝐼_{𝑝}$ , so $𝐴 𝐵$ has a left inverse (Proposition 2.5.26(a)).

Exercise 2.7.15.routine Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

𝐵 \in 𝐹^{𝑛 \times 𝑝}

. Show that if the columns of

𝐴

span

𝐹^{𝑚}

and the columns of

𝐵

span

𝐹^{𝑛}

, then the columns of

𝐴 𝐵

span

𝐹^{𝑚}

Solution.

Uses. Theorem 2.7.4 (Second Fundamental Theorem), Theorem 2.4.2 (The matrix of a composite), Proposition 2.5.26 (One-sided inverses of composites)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Translate “the columns span” into a condition of Theorem 2.7.4 in which products are easy to handle.

Hint 2. Use (I):

𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}

. Or use (V): right inverses of a product.

Sketch. By Theorem 2.7.4,

𝑇_{𝐴}

and

𝑇_{𝐵}

are surjective.

𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}

is then surjective: given

𝐲

, pick

𝐳

with

𝐴 𝐳 = 𝐲

and

𝐱

with

𝐵 𝐱 = 𝐳

. So the columns of

𝐴 𝐵

span

𝐹^{𝑚}

By Theorem 2.7.4, (III) $\Rightarrow$ (I), $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ and $𝑇_{𝐵} : 𝐹^{𝑝} \to 𝐹^{𝑛}$ are surjective. Let $𝐲 \in 𝐹^{𝑚}$ . There is $𝐳 \in 𝐹^{𝑛}$ with $𝐴 𝐳 = 𝐲$ , and then $𝐱 \in 𝐹^{𝑝}$ with $𝐵 𝐱 = 𝐳$ , so $(𝐴 𝐵) 𝐱 =$ $𝐴 (𝐵 𝐱) =$ $𝐲$ . Thus $𝑇_{𝐴 𝐵}$ is surjective, and by (I) $\Rightarrow$ (III) for $𝐴 𝐵$ , the columns of $𝐴 𝐵$ span $𝐹^{𝑚}$ .

Alternatively, by (V), there are $𝐶 \in 𝐹^{𝑛 \times 𝑚}$ and $𝐷 \in 𝐹^{𝑝 \times 𝑛}$ with $𝐴 𝐶 = 𝐼_{𝑚}$ and $𝐵 𝐷 = 𝐼_{𝑛}$ . Then $(𝐴 𝐵) (𝐷 𝐶) =$ $𝐴 (𝐵 𝐷) 𝐶 =$ $𝐴 𝐶 =$ $𝐼_{𝑚}$ (Proposition 2.5.26(a)), so $𝐴 𝐵$ has a right inverse, which is (V) for $𝐴 𝐵$ .

2.7.6Linear maps between spaces with bases

The theorems are stated for maps $𝐹^{𝑛} \to 𝐹^{𝑚}$ , but every linear map between spaces with finite bases is represented by a matrix (Technique 2.3.27), and injectivity, surjectivity, and one-sided inverses all survive the translation.

Corollary 2.7.16 (The Fundamental Theorems for linear maps). Let

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

be a basis of

𝑉

and

𝒞︀

a basis of

𝑊

of length

𝑚

, let

𝑇 \in L (𝑉, 𝑊)

, and let

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

, whose columns are the coordinate vectors

{[𝑇 (𝐯_{𝑗})]}_{𝒞︀}

(a)The following are equivalent: $𝑇$ is injective; $ker 𝑇 = {𝟎}$ ; the list $𝑇 (ℬ︀)$ is linearly independent; the columns of $𝐴$ are linearly independent; $𝑇$ has a left inverse.
(b)The following are equivalent: $𝑇$ is surjective; $im 𝑇 = 𝑊$ ; the list $𝑇 (ℬ︀)$ spans $𝑊$ ; the columns of $𝐴$ span $𝐹^{𝑚}$ ; $𝑇$ has a right inverse.
(c)The following are equivalent: $𝑇$ is bijective; the list $𝑇 (ℬ︀)$ is a basis of $𝑊$ ; the columns of $𝐴$ form a basis of $𝐹^{𝑚}$ ; $𝑇$ is invertible.

Proof.standard

Uses. Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Proposition 2.6.22 (Testing injectivity and surjectivity on a basis), Proposition 2.6.20 (Kernel and image in coordinates), Proposition 2.5.20 (Inverses and matrices), Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Theorem 2.7.8 (Third Fundamental Theorem), Proposition 2.7.7 (Bijective linear maps are invertible), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 2.5.5 (Right inverses give existence)

Techniques. Proving TFAE (Technique 2.7.1), Translate between maps and matrices (Technique 2.3.27)

Hint 1. Use “

𝑇

is injective” (in (b): surjective; in (c): bijective) as a hub. Two spokes are results of Section 2.6 about

𝑇

itself.

Hint 2. The other spokes cross over to

𝑇_{𝐴}

. Which results transfer injectivity, surjectivity, and one-sided inverses between

𝑇

and its matrix?

Hint 3. Proposition 2.6.20(c) and Proposition 2.5.20(b), (c). Then apply the Fundamental Theorems to

𝐴

Sketch. Hub at “

𝑇

is injective”.

ker 𝑇 = {𝟎}

by Theorem 2.6.11;

𝑇 (ℬ︀)

independent by Proposition 2.6.22(a).

𝑇

is injective iff

𝑇_{𝐴}

is (Proposition 2.6.20(c)), iff the columns of

𝐴

are independent, iff

𝑇_{𝐴}

has a left inverse (Theorem 2.7.2), iff

𝐴

does, iff

𝑇

does (Proposition 2.5.20). Part (b) is the same with Theorem 2.7.4, and (c) uses Theorem 2.7.8 and Proposition 2.7.7.

(a) We use “ $𝑇$ is injective” as the hub. By Theorem 2.6.11 it is equivalent to $ker 𝑇 = {𝟎}$ , and by Proposition 2.6.22(a) to the linear independence of $𝑇 (ℬ︀)$ . By Proposition 2.6.20(c), $𝑇$ is injective if and only if $𝑇_{𝐴}$ is, and by Theorem 2.7.2, (I) $\Leftrightarrow$ (III), this holds if and only if the columns of $𝐴$ are linearly independent. Finally, by Proposition 2.5.20(b) and (c), $𝑇$ has a left inverse if and only if $𝐴$ does, if and only if $𝑇_{𝐴}$ does, and by Theorem 2.7.2, (I) $\Leftrightarrow$ (V), this holds if and only if $𝑇_{𝐴}$ is injective, that is, if and only if $𝑇$ is.

(b) The same argument with “surjective” in place of “injective”. $𝑇$ is surjective if and only if $im 𝑇 = 𝑊$ (Definition 2.6.2), if and only if $𝑇 (ℬ︀)$ spans $𝑊$ (Proposition 2.6.22(b)), if and only if $𝑇_{𝐴}$ is surjective (Proposition 2.6.20(c)), and Theorem 2.7.4 and Proposition 2.5.20(b), (c) handle the columns of $𝐴$ and right inverses.

(c) $𝑇$ is bijective if and only if $𝑇 (ℬ︀)$ is a basis of $𝑊$ (Proposition 2.6.22(c)). By Proposition 2.6.20(c), $𝑇$ is bijective if and only if $𝑇_{𝐴}$ is, and by Theorem 2.7.8, (I) $\Leftrightarrow$ (III), if and only if the columns of $𝐴$ form a basis of $𝐹^{𝑚}$ . Finally, a bijective linear map is invertible (Proposition 2.7.7), and an invertible one is injective and surjective (Proposition 2.5.4, Proposition 2.5.5). □

So injectivity, surjectivity, and invertibility of $𝑇$ can be read off any one matrix of $𝑇$ , whatever bases were used to compute it.

Example 2.7.17 (Differentiation plus the identity). Let $𝑇 : {𝐹 [𝑥]}_{\leq 2} \to$ ${𝐹 [𝑥]}_{\leq 2}$ , $𝑇 (𝑝) = 𝑝 + 𝐷 (𝑝)$ , where $𝐷$ is differentiation (Example 2.1.9). On the basis $ℬ︀ = 1, 𝑥, 𝑥^{2}$ ,

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

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

The system ${[𝑇]}_{ℬ︀ ℬ︀} 𝐜 = 𝐲$ reads $𝑐_{1} + 𝑐_{2} = 𝑦_{1}$ , $𝑐_{2} + 2 𝑐_{3} = 𝑦_{2}$ , $𝑐_{3} = 𝑦_{3}$ , and working from the bottom up it has exactly one solution,

𝑐_{3} = 𝑦_{3}, 𝑐_{2} = 𝑦_{2} - 2 𝑦_{3}, 𝑐_{1} = 𝑦_{1} - 𝑦_{2} + 2 𝑦_{3} .

By Theorem 2.7.8, (II) $\Rightarrow$ (III), the columns of the matrix form a basis of $𝐹^{3}$ , so by Corollary 2.7.16(c), $𝑇$ is invertible and $1, 1 + 𝑥, 2 𝑥 + 𝑥^{2}$ is a basis of ${𝐹 [𝑥]}_{\leq 2}$ , over every field. The solution formula gives the inverse: for $𝑞 =$ $𝑦_{1} +$ $𝑦_{2} 𝑥 +$ $𝑦_{3} 𝑥^{2}$ ,

\begin{aligned} 𝑇^{- 1} (𝑞) & = (𝑦_{1} - 𝑦_{2} + 2 𝑦_{3}) + (𝑦_{2} - 2 𝑦_{3}) 𝑥 + 𝑦_{3} 𝑥^{2} \\ = 𝑞 - 𝐷 (𝑞) + 𝐷^{2} (𝑞) . \end{aligned}

So $𝑇^{- 1} = 𝐷^{2} - 𝐷 + id$ . This is the geometric series of Technique 2.5.16, cut off because $𝐷^{3} = 0$ on ${𝐹 [𝑥]}_{\leq 2}$ : indeed $𝑇 = 𝐷 + id$ , and $(𝐷 + id) (𝐷^{2} - 𝐷 + id) =$ $𝐷^{3} +$ $id =$ $id$ .

2.7.7The theorems side by side

Table 2.7.1 lines up the three theorems condition by condition. In each row, the entry for the third theorem is the combination of the other two.

	First	Second	Third
(I)	injective	surjective	bijective
(II)	at most one	at least one	exactly one
(III)	independent	span $𝐹^{𝑚}$	basis of $𝐹^{𝑚}$
(IV)	$ker 𝑇_{𝐴} = {𝟎}$	$im 𝑇_{𝐴} = 𝐹^{𝑚}$	both
(V)	left inverse	right inverse	inverse
(VI)	$rank 𝐴 = 𝑛$	$rank 𝐴 = 𝑚$	$rank 𝐴 = 𝑚 = 𝑛$
size	$𝑛 \leq 𝑚$	$𝑛 \geq 𝑚$	$𝑛 = 𝑚$

Table 2.7.1. The three Fundamental Theorems (Theorem 2.7.2, Theorem 2.7.4, Theorem 2.7.8) for

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. Rows (I), (IV), and (V) are about the map

𝑇_{𝐴}

; row (II) gives the number of solutions of

𝐴 𝐱 = 𝐲

, for every

𝐲 \in 𝐹^{𝑚}

; row (III) is about the columns of

𝐴

. The last two rows are added in Section 3.5.2.

The lecture’s statements of the theorems contain two more pieces. Each theorem has a sixth condition, about a single number computed from $𝐴$ by row reduction, and each ends with a constraint on the shape of $𝐴$ : “moreover, $𝑛 \leq 𝑚$ ” for the first theorem, $𝑛 \geq 𝑚$ for the second, and $𝑛 = 𝑚$ for the third. The sixth condition needs row reduction. The constraints on the shape can already be proved with the tools of this chapter (Exercise 2.7.32), but the text proves both pieces together in Section 3.5.2. There the rank of $𝐴$ is defined as the number of pivots of $rref (𝐴)$ (Definition 3.5.1); the sixth conditions are $rank 𝐴 = 𝑛$ , $rank 𝐴 = 𝑚$ , and $rank 𝐴 = 𝑚 = 𝑛$ (Theorem 3.5.12, Theorem 3.5.13, Theorem 3.5.14); and the constraints on the shape follow from $rank 𝐴 \leq min (𝑚, 𝑛)$ . In particular, invertible matrices are square (Corollary 3.5.15).

Intuition (Why the shape is constrained). An injective

𝑇_{𝐴}

sends the

𝑛

independent vectors

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

to the

𝑛

independent columns of

𝐴

𝐹^{𝑚}

, and

𝐹^{𝑚}

should not have room for more than

𝑚

independent vectors. A surjective

𝑇_{𝐴}

produces all of

𝐹^{𝑚}

from combinations of

𝑛

columns, and

𝑚

“directions” should need at least

𝑚

vectors. Making “room” and “directions” precise is what dimension does (Section 4.1). With what we already have, the constraints are within reach by an induction on

𝑚

(Exercise 2.7.32), and over

𝔽_{𝑝}

by counting (Exercise 2.6.44).

The dictionary in Table 3.1.1 arranges the same facts by the three ways of reading a linear system: as equations, as the map $𝑇_{𝐴}$ , and as a question about the columns.

Remark 2.7.18 (On the name). The name follows the lecture, and the course notes abbreviate the three theorems FTLA1, FTLA2, and FTLA3. Elsewhere, “fundamental theorem” refers to other results. In LADR, the fundamental theorem of linear maps is rank–nullity,

dim 𝑉 =

dim ker 𝑇 +

dim im 𝑇

(Theorem 4.2.11). Strang’s fundamental theorem of linear algebra describes the four subspaces attached to a matrix and their dimensions (Definition 4.3.12). The statements of this section are closest to what many books call the invertible matrix theorem, a list of conditions equivalent to invertibility of a square matrix (Corollary 3.5.25). The Fundamental Theorems split it into an injective half and a surjective half, and do not assume that

𝐴

is square.

Exercises

Exercise 2.7.19.routine For each matrix, decide which of the three Fundamental Theorems have their conditions satisfied, and justify your answer by checking one convenient condition of each theorem.

(a) $(\begin{matrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{matrix})$ over $ℚ$ .
(b) $(\begin{matrix} 1 & 𝑖 \\ 𝑖 & - 1 \\ 0 & 1 \end{matrix})$ over $ℂ$ .
(c) $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ over $𝔽_{2}$ .
(d) $(\begin{matrix} 1 & 2 & 0 \\ 0 & 1 & 2 \end{matrix})$ over $𝔽_{3}$ .

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Theorem 2.7.8 (Third Fundamental Theorem)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. For injectivity, look for a nonzero vector in the kernel, or show that there is none. For surjectivity, try to solve

𝐴 𝐱 = 𝐲

for a general

𝐲

, or find a condition that every value

𝐴 𝐱

satisfies.

Hint 2. (b) Compare the second entry of

𝐴 𝐱

with

𝑖

times the first. (d) Try

𝐱 = (1, 1, 1)

Sketch. (a) Every column is a multiple of

(1, 2)

(2, - 1, 0) \in ker

and

(1, 0) \notin im

, so no theorem applies. (b)

𝐴 (𝑥, 𝑦) =

(𝑥 + 𝑖 𝑦, 𝑖 𝑥 - 𝑦, 𝑦)

𝟎

only for

𝑥 = 𝑦 = 0

, and its second entry is always

𝑖

times the first; only the first theorem applies. (c)

𝐴 𝐱 = 𝐲

has the unique solution

𝑥_{1} = 𝑦_{2}

𝑥_{2} = 𝑦_{1} + 𝑦_{2}

; all three apply. (d)

𝐴 𝐱 = 𝐲

is solved by

(𝑦_{1} + 𝑦_{2}, 𝑦_{2}, 0)

, and

(1, 1, 1) \in ker

; only the second applies.

(a) The columns are $(1, 2)$ , $2 (1, 2)$ , and $3 (1, 2)$ . So $𝐴 (2, - 1, 0) =$ $2 (1, 2) -$ $2 (1, 2) =$ $𝟎$ , and condition (IV) of Theorem 2.7.2 fails. Every value $𝐴 𝐱$ is a multiple of $(1, 2)$ , and $(1, 0)$ is not ( $𝑡 (1, 2) = (1, 0)$ forces $𝑡 = 1$ and $2 𝑡 = 0$ ), so condition (I) of Theorem 2.7.4 fails. Since $𝑇_{𝐴}$ is not injective, Theorem 2.7.8 fails as well.

(b) $𝐴 (𝑥, 𝑦) =$ $(𝑥 + 𝑖 𝑦, 𝑖 𝑥 - 𝑦, 𝑦)$ . If this is $𝟎$ , the third entry gives $𝑦 = 0$ and then the first gives $𝑥 = 0$ , so (IV) of Theorem 2.7.2 holds. The second entry is $𝑖 𝑥 -$ $𝑦 =$ $𝑖 (𝑥 + 𝑖 𝑦)$ , $𝑖$ times the first, for every $(𝑥, 𝑦)$ . The vector $(0, 1, 0)$ fails this, so it is not a value, and Theorem 2.7.4 and Theorem 2.7.8 fail.

(c) Over $𝔽_{2}$ , $𝐴 𝐱 = 𝐲$ reads $𝑥_{1} + 𝑥_{2} = 𝑦_{1}$ , $𝑥_{1} = 𝑦_{2}$ , whose only solution is $𝑥_{1} = 𝑦_{2}$ , $𝑥_{2} =$ $𝑦_{1} -$ $𝑦_{2} =$ $𝑦_{1} +$ $𝑦_{2}$ . So (II) of Theorem 2.7.8 holds, and all three theorems apply. The inverse is $(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ ; check: $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}) =$ $(\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}) =$ $𝐼_{2}$ in $𝔽_{2}$ .

(d) Over $𝔽_{3}$ , $𝐴 𝐱 = 𝐲$ reads $𝑥_{1} + 2 𝑥_{2} = 𝑦_{1}$ , $𝑥_{2} + 2 𝑥_{3} = 𝑦_{2}$ . Taking $𝑥_{3} = 0$ gives the solution $(𝑦_{1} - 2 𝑦_{2}, 𝑦_{2}, 0) =$ $(𝑦_{1} + 𝑦_{2}, 𝑦_{2}, 0)$ , so (II) of Theorem 2.7.4 holds. But $𝐴 (1, 1, 1) =$ $(1 + 2, 1 + 2) =$ $(0, 0)$ in $𝔽_{3}$ , so (IV) of Theorem 2.7.2 fails, and with it Theorem 2.7.8.

Exercise 2.7.20.routine

(a)Let $𝑇 : {𝐹 [𝑥]}_{\leq 2} \to 𝐹^{3}$ , $𝑇 (𝑝) =$ $(𝑝 (0), (𝐷 𝑝) (0), 𝑝 (1))$ , where $𝐷$ is differentiation. Use Corollary 2.7.16 to show that $𝑇$ is invertible over every field, and find $𝑇^{- 1}$ .
(b)Let $𝑈 : {𝐹 [𝑥]}_{\leq 2} \to 𝐹^{3}$ , $𝑈 (𝑝) =$ $(𝑝 (0), (𝐷 𝑝) (0), (𝐷 𝑝) (1))$ . For which fields $𝐹$ is $𝑈$ invertible?

Solution.

Uses. Corollary 2.7.16 (The Fundamental Theorems for linear maps), Theorem 2.7.8 (Third Fundamental Theorem), Definition 2.3.1 (Matrix of a linear map)

Hint 1. Compute the matrix in the bases

1, 𝑥, 𝑥^{2}

and

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

, or directly the values on

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

Hint 2. For (b),

(𝐷 𝑝) (1) = 𝑏 + 2 𝑐

. What happens when

2 = 0

𝐹

Sketch. (a)

𝑇 (𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}) =

(𝑎, 𝑏, 𝑎 + 𝑏 + 𝑐)

, and

𝑇 (𝑝) =

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

has the unique solution

𝑎 = 𝑦_{1}

𝑏 = 𝑦_{2}

𝑐 = 𝑦_{3} - 𝑦_{1} - 𝑦_{2}

; so

𝑇^{- 1} (𝐲) =

𝑦_{1} +

𝑦_{2} 𝑥 +

(𝑦_{3} - 𝑦_{1} - 𝑦_{2}) 𝑥^{2}

. (b)

𝑈 (𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}) =

(𝑎, 𝑏, 𝑏 + 2 𝑐)

. If

2 \neq 0

, solve uniquely with

𝑐 = 2^{- 1} (𝑦_{3} - 𝑦_{2})

; if

2 = 0

, then

𝑈 (𝑥^{2}) = 𝟎

, so

𝑈

is not injective.

Write $𝑝 = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}$ , so that $𝐷 𝑝 = 𝑏 + 2 𝑐 𝑥$ .

(a) $𝑇 (𝑝) =$ $(𝑎, 𝑏, 𝑎 + 𝑏 + 𝑐)$ , and the matrix of $𝑇$ in the bases $1, 𝑥, 𝑥^{2}$ and $𝐞_{1}, 𝐞_{2}, 𝐞_{3}$ has columns $𝑇 (1) = (1, 0, 1)$ , $𝑇 (𝑥) = (0, 1, 1)$ , $𝑇 (𝑥^{2}) = (0, 0, 1)$ . The equation $𝑇 (𝑝) =$ $(𝑦_{1}, 𝑦_{2}, 𝑦_{3})$ , that is, $[𝑇] (𝑎, 𝑏, 𝑐) =$ $(𝑦_{1}, 𝑦_{2}, 𝑦_{3})$ , has exactly one solution,

𝑎 = 𝑦_{1}, 𝑏 = 𝑦_{2}, 𝑐 = 𝑦_{3} - 𝑦_{1} - 𝑦_{2} .

No division occurred, so this holds over every field. By Theorem 2.7.8, (II) $\Rightarrow$ (III), the columns of $[𝑇]$ form a basis of $𝐹^{3}$ , and by Corollary 2.7.16(c), $𝑇$ is invertible, with

𝑇^{- 1} (𝑦_{1}, 𝑦_{2}, 𝑦_{3}) = 𝑦_{1} + 𝑦_{2} 𝑥 + (𝑦_{3} - 𝑦_{1} - 𝑦_{2}) 𝑥^{2} .

Check: this polynomial has value $𝑦_{1}$ at $0$ , derivative $𝑦_{2}$ at $0$ , and value $𝑦_{1} +$ $𝑦_{2} +$ $𝑦_{3} -$ $𝑦_{1} -$ $𝑦_{2} =$ $𝑦_{3}$ at $1$ .

(b) $𝑈 (𝑝) =$ $(𝑎, 𝑏, 𝑏 + 2 𝑐)$ . If $2 \neq 0$ in $𝐹$ , then $𝑈 (𝑝) =$ $(𝑦_{1}, 𝑦_{2}, 𝑦_{3})$ has exactly one solution, $𝑎 = 𝑦_{1}$ , $𝑏 = 𝑦_{2}$ , $𝑐 = 2^{- 1} (𝑦_{3} - 𝑦_{2})$ , and as in (a), $𝑈$ is invertible. If $2 = 0$ , that is, if $𝐹$ has characteristic $2$ , then $𝑈 (𝑥^{2}) = (0, 0, 0)$ , so $𝑈$ is not injective (Theorem 2.6.11) and not invertible. So $𝑈$ is invertible exactly when $1 + 1 \neq 0$ in $𝐹$ .

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

Claim. For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , the following are equivalent: (i) $𝑇_{𝐴}$ is injective; (ii) the columns of $𝐴$ are linearly independent; (iii) $𝑇_{𝐴}$ is surjective; (iv) the columns of $𝐴$ span $𝐹^{𝑚}$ .

Proof. (i) $\Leftrightarrow$ (ii) is Corollary 2.6.24(a), and (iii) $\Leftrightarrow$ (iv) is Corollary 2.6.24(b). Hence the four statements are equivalent.

Solution.

Uses. Corollary 2.6.24 (The columns decide), Example 2.7.5 (A tall matrix)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18), Proving TFAE (Technique 2.7.1)

Hint 1. Draw the four statements as points and the proved implications as arrows. Can you get from (i) to (iii)?

Hint 2. For a counterexample, look for a map that is injective but not surjective, such as the one in Example 2.7.5.

Sketch. The proof only links (i) with (ii) and (iii) with (iv); no implication connects the two pairs. The claim is false:

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

gives an injective

𝑇_{𝐴} (𝑥) = (𝑥, 0)

that is not surjective.

The two equivalences are correct, but they form two separate groups: no proved implication leads from (i) or (ii) to (iii) or (iv), or back. So nothing has been shown about, say, (i) versus (iii).

The claim is in fact false. For $𝐴 = (\begin{matrix} 1 \\ 0 \end{matrix}) \in 𝐹^{2 \times 1}$ , $𝑇_{𝐴} (𝑥) = (𝑥, 0)$ is injective, since $(𝑥, 0) = 𝟎$ forces $𝑥 = 0$ , but not surjective, since $(0, 1)$ is not a value. Example 2.7.5 is another example. (For square matrices the claim is true, but its proof needs Section 3.5; see Corollary 3.5.25.)

Exercise 2.7.22.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ . Prove or disprove each statement.

(a)If $𝐴 𝐱 = 𝟎$ has only the solution $𝐱 = 𝟎$ , then $𝐴 𝐱 = 𝐲$ has a solution for every $𝐲 \in 𝐹^{𝑚}$ .
(b)If $𝐴$ has two different left inverses, then $𝑇_{𝐴}$ is not surjective.
(c)If $𝑇_{𝐴 𝐵}$ is bijective, then $𝑇_{𝐴}$ and $𝑇_{𝐵}$ are bijective.
(d)If $𝑇_{𝐴 𝐵}$ is bijective, then the columns of $𝐴$ span $𝐹^{𝑚}$ and the columns of $𝐵$ are linearly independent.

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Corollary 2.5.11 (Many one-sided inverses), Proposition 2.5.20 (Inverses and matrices), Proposition 2.6.15 (Kernels and images of composites), Theorem 2.4.2 (The matrix of a composite), Example 2.5.27 (An invertible product of non-invertible factors)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. (a) and (c) are false; look for small non-square matrices.

Hint 2. (b) Two different left inverses rule out a right inverse (Corollary 2.5.11). Which theorem turns “no right inverse” into a statement about surjectivity?

Hint 3. (d)

𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}

. What does Proposition 2.6.15(c) say?

Sketch. (a) False:

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

. (b) True: no right inverse, so by Theorem 2.7.4, (I)

\Rightarrow

(V),

𝑇_{𝐴}

is not surjective. (c) False:

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

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

𝐴 𝐵 = (1)

. (d) True:

𝑇_{𝐴} \circ 𝑇_{𝐵}

bijective makes

𝑇_{𝐴}

surjective and

𝑇_{𝐵}

injective; translate with (I)

\Leftrightarrow

(III).

(a) False. For $𝐴 = (\begin{matrix} 1 \\ 0 \end{matrix}) \in 𝐹^{2 \times 1}$ , $𝐴 𝑥 = (𝑥, 0) = 𝟎$ only for $𝑥 = 0$ , but $𝐴 𝑥 = (0, 1)$ has no solution.

(b) True. By Corollary 2.5.11, a matrix with two different left inverses has no right inverse, and by Proposition 2.5.20(c) neither does $𝑇_{𝐴}$ . So condition (V) of Theorem 2.7.4 fails, and therefore so does (I): $𝑇_{𝐴}$ is not surjective. This uses the implication (I) $\Rightarrow$ (V) of Theorem 2.7.4.

(c) False. With $𝐴 = (\begin{matrix} 1 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 \\ 0 \end{matrix})$ , $𝐴 𝐵 = (1) = 𝐼_{1}$ , so $𝑇_{𝐴 𝐵} = {id}_{𝐹}$ is bijective, but $𝑇_{𝐴} (𝑥, 𝑦) = 𝑥$ is not injective and $𝑇_{𝐵} (𝑥) = (𝑥, 0)$ is not surjective (Example 2.5.27).

(d) True. $𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}$ by Theorem 2.4.2. Since this composite is injective, $𝑇_{𝐵}$ is injective, and since it is surjective, $𝑇_{𝐴}$ is surjective (Proposition 2.6.15(c)). By Theorem 2.7.2 and Theorem 2.7.4, (I) $\Rightarrow$ (III), the columns of $𝐵$ are linearly independent and the columns of $𝐴$ span $𝐹^{𝑚}$ .

Exercise 2.7.23.standard Let

𝑃 \in L (𝑉)

satisfy

𝑃^{2} = 𝑃

. Show that the following are equivalent: (i)

𝑃

is injective; (ii)

𝑃

is surjective; (iii)

𝑃

is invertible; (iv)

𝑃 = {id}_{𝑉}

. Here

𝑉

need not have a finite basis.

Solution.

Uses. Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 2.5.5 (Right inverses give existence), Definition 2.5.12 (Invertible)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. (iv) is the strongest statement, so make it the hub: prove that (i) and (ii) each imply (iv), and that (iv) implies the rest.

Hint 2. For (i)

\Rightarrow

(iv), compute

𝑃 (𝑃 𝐯 - 𝐯)

. For (ii)

\Rightarrow

(iv), write a vector as

𝑃 𝐰

and apply

𝑃

Sketch. (iv)

\Rightarrow

(iii)

\Rightarrow

(i) and (iii)

\Rightarrow

(ii) hold for every operator. (i)

\Rightarrow

(iv):

𝑃 (𝑃 𝐯 - 𝐯) =

𝑃^{2} 𝐯 -

𝑃 𝐯 =

𝟎

, so

𝑃 𝐯 = 𝐯

. (ii)

\Rightarrow

(iv): if

𝐯 = 𝑃 𝐰

, then

𝑃 𝐯 =

𝑃^{2} 𝐰 =

𝑃 𝐰 =

𝐯

We prove (iv) $\Rightarrow$ (iii), (iii) $\Rightarrow$ (i), (iii) $\Rightarrow$ (ii), (i) $\Rightarrow$ (iv), and (ii) $\Rightarrow$ (iv). From each statement one can reach (iv) and from (iv) every statement, so this suffices.

(iv) $\Rightarrow$ (iii). ${id}_{𝑉}$ is invertible, with inverse ${id}_{𝑉}$ .

(iii) $\Rightarrow$ (i) and (iii) $\Rightarrow$ (ii). An invertible map has a left inverse and a right inverse (Definition 2.5.12), so it is injective (Proposition 2.5.4) and surjective (Proposition 2.5.5).

(i) $\Rightarrow$ (iv). Let $𝐯 \in 𝑉$ . Then $𝑃 (𝑃 𝐯 - 𝐯) =$ $𝑃^{2} 𝐯 -$ $𝑃 𝐯 =$ $𝑃 𝐯 -$ $𝑃 𝐯 =$ $𝟎$ , so $𝑃 𝐯 -$ $𝐯 \in$ $ker 𝑃 =$ ${𝟎}$ (Theorem 2.6.11). Hence $𝑃 𝐯 = 𝐯$ for every $𝐯$ , that is, $𝑃 = {id}_{𝑉}$ .

(ii) $\Rightarrow$ (iv). Let $𝐯 \in 𝑉$ . Since $𝑃$ is surjective, $𝐯 = 𝑃 𝐰$ for some $𝐰$ , and $𝑃 𝐯 =$ $𝑃^{2} 𝐰 =$ $𝑃 𝐰 =$ $𝐯$ . So $𝑃 = {id}_{𝑉}$ .

No basis was used, so the result holds in every vector space. Without the hypothesis $𝑃^{2} = 𝑃$ , (i) and (ii) are not equivalent for operators on $𝐹 [𝑥]$ (Example 2.6.4(e)).

Exercise 2.7.24.standard Find the error in the following argument, and repair it.

Claim. If $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ is injective, then $𝑇_{𝐴}$ has a left inverse.

Proof. Regard $𝑇_{𝐴}$ as a map $𝐹^{𝑛} \to im 𝑇_{𝐴}$ . As such it is linear, injective, and surjective, so by Proposition 2.7.7 it has a linear inverse $𝑅 : im 𝑇_{𝐴} \to 𝐹^{𝑛}$ , with $𝑅 (𝑇_{𝐴} (𝐱)) = 𝐱$ for every $𝐱 \in 𝐹^{𝑛}$ . So $𝑅$ is a left inverse of $𝑇_{𝐴}$ .

Solution.

Uses. Definition 2.5.1 (Left inverse), Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 2.6.18 (The column space is spanned by the columns)

Hint 1. Compare the domain of

𝑅

with the domain that Definition 2.5.1 requires of a left inverse of

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

Hint 2. To repair the argument,

𝑅

has to be extended from

im 𝑇_{𝐴}

to a linear map on all of

𝐹^{𝑚}

. The columns of

𝐴

form a basis of

im 𝑇_{𝐴}

. What does part 3 of the proof of Theorem 2.7.2 do with them?

Sketch. A left inverse of

𝑇_{𝐴}

must be a linear map

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

, but

𝑅

is defined only on the subspace

im 𝑇_{𝐴}

, which is all of

𝐹^{𝑚}

only when

𝑇_{𝐴}

is surjective. Repair: the columns form a basis of

im 𝑇_{𝐴}

; complete them to a basis of

𝐹^{𝑚}

and extend

𝑅

by prescribing values on the added vectors, as in part 3 of the proof of Theorem 2.7.2.

Everything up to the last sentence is correct: $𝑇_{𝐴}$ , regarded as a map onto its image, is a linear bijection, and its inverse $𝑅 : im 𝑇_{𝐴} \to 𝐹^{𝑛}$ is linear. The error is the conclusion. By Definition 2.5.1, a left inverse of $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ is a linear map $𝐹^{𝑚} \to 𝐹^{𝑛}$ , defined on all of $𝐹^{𝑚}$ , while $𝑅$ is defined only on $im 𝑇_{𝐴}$ . These agree only when $im 𝑇_{𝐴} = 𝐹^{𝑚}$ , that is, when $𝑇_{𝐴}$ is also surjective. For example, for $𝐴 = (\begin{matrix} 1 \\ 0 \end{matrix})$ , $𝑅$ is defined on the $𝑥$ -axis of $𝐹^{2}$ and says nothing about $(0, 1)$ .

Repair. The map $𝑅$ has to be extended linearly to $𝐹^{𝑚}$ . Since $𝑇_{𝐴}$ is injective, the columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ are linearly independent (Theorem 2.7.2), and they span $im 𝑇_{𝐴}$ (Proposition 2.6.18), so they are a basis of $im 𝑇_{𝐴}$ , and $𝑅 (𝐚_{𝑗}) = 𝐞_{𝑗}$ . Complete them to a basis $𝐚_{1},$ $\dots,$ $𝐚_{𝑛},$ $𝐞_{𝑖_{1}},$ $\dots,$ $𝐞_{𝑖_{𝑡}}$ of $𝐹^{𝑚}$ as in part 3 of the proof of Theorem 2.7.2, and let $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ be the linear map with $𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}$ and $𝑆 (𝐞_{𝑖_{𝑠}}) = 𝟎$ (Theorem 2.2.1). Then $𝑆$ agrees with $𝑅$ on the basis $𝐚_{1}, \dots, 𝐚_{𝑛}$ of $im 𝑇_{𝐴}$ , hence on all of $im 𝑇_{𝐴}$ , and $𝑆 (𝑇_{𝐴} (𝐱)) =$ $𝑅 (𝑇_{𝐴} (𝐱)) =$ $𝐱$ . So $𝑆$ is a left inverse.

Exercise 2.7.25.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . The columns of $𝐴^{𝖳}$ are the rows of $𝐴$ , read as vectors in $𝐹^{𝑛}$ . Show that:

(a)the columns of $𝐴$ are linearly independent if and only if the rows of $𝐴$ span $𝐹^{𝑛}$ ;
(b)the columns of $𝐴$ span $𝐹^{𝑚}$ if and only if the rows of $𝐴$ are linearly independent.

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Exercise 2.5.45, Proposition 2.5.20 (Inverses and matrices), Proposition 2.4.22 (Transpose is a linear involution)

Hint 1. Which condition of the Fundamental Theorems behaves well under transposition?

Hint 2. Condition (V):

𝐶 𝐴 = 𝐼_{𝑛}

if and only if

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

(Exercise 2.5.45).

Sketch. (a) Columns of

𝐴

independent

\Leftrightarrow

𝐴

has a left inverse

𝐶

(Theorem 2.7.2)

\Leftrightarrow

𝐴^{𝖳}

has the right inverse

𝐶^{𝖳}

\Leftrightarrow

the columns of

𝐴^{𝖳}

span

𝐹^{𝑛}

(Theorem 2.7.4). (b) Apply (a) to

𝐴^{𝖳}

, using

{(𝐴^{𝖳})}^{𝖳} = 𝐴

(a) By Theorem 2.7.2, (III) $\Leftrightarrow$ (V), the columns of $𝐴$ are linearly independent if and only if $𝑇_{𝐴}$ has a left inverse, which by Proposition 2.5.20(c) means that $𝐶 𝐴 = 𝐼_{𝑛}$ for some $𝐶 \in 𝐹^{𝑛 \times 𝑚}$ . By Exercise 2.5.45, $𝐶 𝐴 = 𝐼_{𝑛}$ if and only if $𝐴^{𝖳} 𝐶^{𝖳} = 𝐼_{𝑛}$ . So $𝐴$ has a left inverse if and only if $𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ has a right inverse, that is, if and only if $𝑇_{𝐴^{𝖳}}$ has a right inverse (Proposition 2.5.20(c)), which by Theorem 2.7.4, (V) $\Leftrightarrow$ (III), happens if and only if the columns of $𝐴^{𝖳}$ span $𝐹^{𝑛}$ . These columns are the rows of $𝐴$ .

(b) Apply (a) to $𝐴^{𝖳}$ : the columns of $𝐴^{𝖳}$ are linearly independent if and only if the columns of ${(𝐴^{𝖳})}^{𝖳} = 𝐴$ span $𝐹^{𝑚}$ (Proposition 2.4.22). The columns of $𝐴^{𝖳}$ are the rows of $𝐴$ .

Exercise 2.7.26.standard Let $𝑝$ be a prime.

(a)Show that exactly $(𝑝^{3} - 1) (𝑝^{3} - 𝑝)$ linear maps $𝔽_{𝑝}^{2} \to 𝔽_{𝑝}^{3}$ are injective.
(b)By Exercise 2.6.45, the same number of linear maps $𝔽_{𝑝}^{3} \to 𝔽_{𝑝}^{2}$ are surjective. Explain the coincidence with Exercise 2.7.25.

Solution.

Uses. Theorem 2.3.20 (Linear maps correspond to matrices), Proposition 2.3.16 (The matrix of $𝑇_{𝐴}$ ), Theorem 2.7.2 (First Fundamental Theorem), Proposition 1.5.14 (Appending a vector), Proposition 1.5.15 (Short lists, zeros, and repeats), Corollary 1.5.17 (Sublists), Proposition 1.2.35 (Zero products), Exercise 2.7.25

Hint 1. Every linear map

𝔽_{𝑝}^{2} \to 𝔽_{𝑝}^{3}

𝑇_{𝐴}

for exactly one

𝐴 \in 𝔽_{𝑝}^{3 \times 2}

. Count the matrices whose two columns are independent.

Hint 2. The first column must be nonzero, and the second must avoid the span of the first. How many vectors does

span (𝐚_{1})

contain?

Hint 3. For (b),

𝐴 \mapsto 𝐴^{𝖳}

is a bijection from

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

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

Sketch. By Theorem 2.7.2, count pairs

𝐚_{1}, 𝐚_{2}

𝔽_{𝑝}^{3}

that are independent:

𝐚_{1} \neq 𝟎

(

𝑝^{3} - 1

choices) and

𝐚_{2} \notin span (𝐚_{1})

, which has

𝑝

elements (

𝑝^{3} - 𝑝

choices). (b) By Exercise 2.7.25,

𝑇_{𝐴}

is injective iff

𝑇_{𝐴^{𝖳}}

is surjective, and transposition is a bijection between the two sets of matrices.

(a) Every linear map $𝔽_{𝑝}^{2} \to 𝔽_{𝑝}^{3}$ is $𝑇_{𝐴}$ for exactly one $𝐴 \in 𝔽_{𝑝}^{3 \times 2}$ (Theorem 2.3.20, Proposition 2.3.16), and by Theorem 2.7.2, $𝑇_{𝐴}$ is injective if and only if the columns $𝐚_{1}, 𝐚_{2}$ are linearly independent. This holds if and only if $𝐚_{1} \neq 𝟎$ and $𝐚_{2} \notin span (𝐚_{1})$ : if the pair is independent, so is its sublist $𝐚_{1}$ (Corollary 1.5.17), so $𝐚_{1} \neq 𝟎$ (Proposition 1.5.15(b)), and then $𝐚_{2} \notin span (𝐚_{1})$ by Proposition 1.5.14; the converse is Proposition 1.5.15(b) and Proposition 1.5.14 again. There are $𝑝^{3} - 1$ choices of $𝐚_{1} \neq 𝟎$ . For each, $span (𝐚_{1}) =$ ${𝑡 𝐚_{1} | 𝑡 \in 𝔽_{𝑝}}$ has exactly $𝑝$ elements, since $𝑡 𝐚_{1} = 𝑡^{'} 𝐚_{1}$ gives $(𝑡 - 𝑡^{'}) 𝐚_{1} = 𝟎$ and hence $𝑡 = 𝑡^{'}$ (Proposition 1.2.35). So there are $𝑝^{3} - 𝑝$ choices of $𝐚_{2}$ , and $(𝑝^{3} - 1) (𝑝^{3} - 𝑝)$ injective maps in all.

(b) By Exercise 2.7.25(a), the columns of $𝐴 \in 𝔽_{𝑝}^{3 \times 2}$ are independent if and only if the columns of $𝐴^{𝖳} \in 𝔽_{𝑝}^{2 \times 3}$ span $𝔽_{𝑝}^{2}$ , that is, $𝑇_{𝐴}$ is injective if and only if $𝑇_{𝐴^{𝖳}}$ is surjective. Since $𝐴 \mapsto 𝐴^{𝖳}$ is a bijection $𝔽_{𝑝}^{3 \times 2} \to 𝔽_{𝑝}^{2 \times 3}$ (it is its own inverse), it matches the injective maps $𝔽_{𝑝}^{2} \to 𝔽_{𝑝}^{3}$ with the surjective maps $𝔽_{𝑝}^{3} \to 𝔽_{𝑝}^{2}$ one to one. So the two counts agree.

Exercise 2.7.27.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . Prove or disprove: if the columns of $𝐴$ are linearly independent, then so are the columns of $𝐴^{𝖳} 𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .

(a) For $𝐹 = ℝ$ . (b) For $𝐹 = ℂ$ . (c) For $𝐹 = 𝔽_{2}$ .

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Proposition 2.4.23 (Transpose of a product), Definition 2.4.1 (Matrix product), Exercise 2.4.44

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. By Theorem 2.7.2, the claim is that

𝐴^{𝖳} 𝐴 𝐱 = 𝟎

forces

𝐱 = 𝟎

. Multiply

𝐴^{𝖳} 𝐴 𝐱 = 𝟎

on the left by

𝐱^{𝖳}

Hint 2.

𝐱^{𝖳} 𝐴^{𝖳} 𝐴 𝐱 =

{(𝐴 𝐱)}^{𝖳} (𝐴 𝐱)

is the sum of the squares of the entries of

𝐴 𝐱

. When does such a sum vanish?

Sketch. (a) True: if

𝐴^{𝖳} 𝐴 𝐱 = 𝟎

, then

0 =

𝐱^{𝖳} 𝐴^{𝖳} 𝐴 𝐱 =

\sum_{𝑖} {(𝐴 𝐱)}_{𝑖}^{2}

, so

𝐴 𝐱 = 𝟎

and

𝐱 = 𝟎

. (b) False:

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

gives

𝐴^{𝖳} 𝐴 =

(1 + 𝑖^{2}) =

(0)

. (c) False:

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

gives

𝐴^{𝖳} 𝐴 = (1 + 1) = (0)

By Theorem 2.7.2, (III) $\Leftrightarrow$ (IV), the columns of $𝐴^{𝖳} 𝐴$ are independent if and only if $𝐴^{𝖳} 𝐴 𝐱 = 𝟎$ only for $𝐱 = 𝟎$ , and likewise for $𝐴$ .

(a) True. Let $𝐴^{𝖳} 𝐴 𝐱 = 𝟎$ , and put $𝐳 = 𝐴 𝐱 \in ℝ^{𝑚}$ . By Proposition 2.4.23, $𝐱^{𝖳} 𝐴^{𝖳} =$ ${(𝐴 𝐱)}^{𝖳} =$ $𝐳^{𝖳}$ , so

0 = 𝐱^{𝖳} (𝐴^{𝖳} 𝐴 𝐱) = 𝐳^{𝖳} 𝐳 = 𝑧_{1}^{2} + \dots + 𝑧_{𝑚}^{2},

where the left side is the $1 \times 1$ matrix $𝐱^{𝖳} 𝟎 = (0)$ , read as a number. A sum of squares of real numbers is $0$ only if every term is, so $𝐳 = 𝐴 𝐱 = 𝟎$ , and $𝐱 = 𝟎$ because the columns of $𝐴$ are independent.

(b) False. Let $𝐴 = (\begin{matrix} 1 \\ 𝑖 \end{matrix}) \in ℂ^{2 \times 1}$ . Its single column is nonzero, hence independent, but $𝐴^{𝖳} 𝐴 =$ $(1 \cdot 1 + 𝑖 \cdot 𝑖) =$ $(0)$ , whose column is $𝟎$ .

(c) False. Let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix}) \in 𝔽_{2}^{2 \times 1}$ . Then $𝐴^{𝖳} 𝐴 = (1 + 1) = (0)$ .

The proof of (a) breaks down exactly where sums of squares can vanish without each term vanishing, as in Exercise 2.4.44(d). Over $ℂ$ , replacing $𝐴^{𝖳}$ by the conjugate transpose repairs it (Section 6.5).

Exercise 2.7.28.standard For $𝑐 \in 𝐹$ , let

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

(a) Show that $𝐴_{𝑐}$ is invertible if and only if $1 + 𝑐^{3} \neq 0$ , and that otherwise $𝑇_{𝐴_{𝑐}}$ is neither injective nor surjective.

(b) List the $𝑐$ for which $𝐴_{𝑐}$ is not invertible over $ℝ$ , over $ℂ$ , and over $𝔽_{7}$ .

Solution.

Uses. Theorem 2.7.8 (Third Fundamental Theorem), Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem)

Hint 1. Solve

𝐴_{𝑐} 𝐱 = (𝑎, 𝑏, 𝑑)

by hand: express

𝑥_{2}

through

𝑥_{3}

using the second equation, then

𝑥_{1}

through

𝑥_{3}

using the first, and substitute into the third.

Hint 2. You should reach

(1 + 𝑐^{3}) 𝑥_{3} =

𝑑 -

𝑐 𝑎 +

𝑐^{2} 𝑏

. If

1 + 𝑐^{3} = 0

, try

𝑥_{3} = 1

for a vector in the kernel.

Sketch. The system is equivalent to

𝑥_{2} = 𝑏 - 𝑐 𝑥_{3}

𝑥_{1} =

𝑎 -

𝑐 𝑏 +

𝑐^{2} 𝑥_{3}

(1 + 𝑐^{3}) 𝑥_{3} =

𝑑 -

𝑐 𝑎 +

𝑐^{2} 𝑏

. If

1 + 𝑐^{3} \neq 0

there is exactly one solution, so

𝐴_{𝑐}

is invertible. If

1 + 𝑐^{3} = 0

, then

(𝑐^{2}, - 𝑐, 1)

is a nonzero kernel vector and

(0, 0, 1)

is not a value. Not invertible exactly for:

𝑐 = - 1

over

ℝ

;

𝑐 = - 1, (1 \pm 𝑖 \sqrt{3}) / 2

over

ℂ

;

𝑐 = 3, 5, 6

over

𝔽_{7}

(a) The system $𝐴_{𝑐} 𝐱 = (𝑎, 𝑏, 𝑑)$ is

𝑥_{1} + 𝑐 𝑥_{2} = 𝑎, 𝑥_{2} + 𝑐 𝑥_{3} = 𝑏, 𝑐 𝑥_{1} + 𝑥_{3} = 𝑑 .

The second equation says $𝑥_{2} = 𝑏 - 𝑐 𝑥_{3}$ ; given this, the first says $𝑥_{1} =$ $𝑎 -$ $𝑐 𝑥_{2} =$ $𝑎 -$ $𝑐 𝑏 +$ $𝑐^{2} 𝑥_{3}$ ; given both, the third says $𝑐 (𝑎 - 𝑐 𝑏 + 𝑐^{2} 𝑥_{3}) +$ $𝑥_{3} =$ $𝑑$ , that is,

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

So the system is equivalent to these three equations for $𝑥_{2}$ , $𝑥_{1}$ , and $𝑥_{3}$ .

If $1 + 𝑐^{3} \neq 0$ , the last equation determines $𝑥_{3}$ , and then $𝑥_{2}$ and $𝑥_{1}$ are determined. So the system has exactly one solution for every right-hand side, which is (II) of Theorem 2.7.8, and $𝐴_{𝑐}$ is invertible.

If $1 + 𝑐^{3} = 0$ , take $(𝑎, 𝑏, 𝑑) =$ $(0, 0, 1)$ : the last equation reads $0 = 1$ , so $(0, 0, 1)$ is not a value, and $𝑇_{𝐴_{𝑐}}$ is not surjective. Take $(𝑎, 𝑏, 𝑑) = 𝟎$ and $𝑥_{3} = 1$ : then $𝐱 = (𝑐^{2}, - 𝑐, 1)$ is a nonzero solution of $𝐴_{𝑐} 𝐱 = 𝟎$ (check: $𝑐^{2} - 𝑐^{2} = 0$ , $- 𝑐 + 𝑐 = 0$ , $𝑐^{3} + 1 = 0$ ), so $𝑇_{𝐴_{𝑐}}$ is not injective.

(b) Over $ℝ$ , $𝑐^{3} = - 1$ only for $𝑐 = - 1$ . Over $ℂ$ , $𝑐^{3} +$ $1 =$ $(𝑐 + 1) (𝑐^{2} - 𝑐 + 1)$ , so $𝑐 = - 1$ or $𝑐 = (1 \pm 𝑖 \sqrt{3}) / 2$ . Over $𝔽_{7}$ , the cubes of $0, 1, \dots, 6$ are $0, 1, 1, 6, 1, 6, 6$ (for instance $3^{3} = 27 = 3 \cdot 7 + 6$ ), so $𝑐^{3} = - 1 = 6$ exactly for $𝑐 = 3, 5, 6$ .

Exercise 2.7.29.hard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)Show that $𝐴$ has exactly one left inverse if and only if $𝐴$ is invertible.
(b)Show that $𝐴$ has exactly one right inverse if and only if $𝐴$ is invertible.

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Theorem 2.7.8 (Third Fundamental Theorem), Theorem 2.5.10 (Left and right inverses agree), Theorem 2.2.1 (Linear maps are determined by a basis), Proposition 2.5.20 (Inverses and matrices), Definition 2.4.1 (Matrix product), Exercise 2.5.45

Techniques. Construct a map by choosing it on a basis (Technique 2.2.4)

Hint 1. If

𝐴

is invertible, every one-sided inverse equals

𝐴^{- 1}

(Theorem 2.5.10). For the converse in (a), show that a left-invertible

𝐴

with

𝑇_{𝐴}

not surjective has at least two left inverses.

Hint 2. Use the construction in part 3 of the proof of Theorem 2.7.2. If the columns do not span

𝐹^{𝑚}

, at least one standard basis vector

𝐞_{𝑖_{1}}

is appended, and the value of the left inverse there can be chosen in two ways.

Hint 3. For (b), if

𝐴 𝐵 = 𝐼_{𝑚}

and

𝐴 𝐳 = 𝟎

with

𝐳 \neq 𝟎

, change one column of

𝐵

𝐳

Sketch. If

𝐴

is invertible, every one-sided inverse equals

𝐴^{- 1}

. (a) If

𝐴

has exactly one left inverse, then

𝑇_{𝐴}

is injective. If it were not surjective, completing the columns to a basis

𝐚_{1},

\dots,

𝐚_{𝑛},

𝐞_{𝑖_{1}},

\dots,

𝐞_{𝑖_{𝑡}}

would append

𝑡 \geq 1

vectors, and

𝑆 (𝐞_{𝑖_{1}}) = 𝟎

𝐞_{1}

would give two left inverses. So

𝑇_{𝐴}

is bijective. (b) If

𝐴 𝐵 = 𝐼_{𝑚}

and

𝐳 \neq 𝟎

lies in

ker 𝑇_{𝐴}

, then adding

𝐳

to the first column of

𝐵

gives a second right inverse. So a unique right inverse forces

𝑇_{𝐴}

to be injective as well as surjective.

By Proposition 2.5.20(c), $𝐶 \mapsto 𝑇_{𝐶}$ matches the left (right) inverses of $𝐴$ with the left (right) inverses of $𝑇_{𝐴}$ , so we may count either.

If $𝐴$ is invertible, then every left inverse $𝐶$ equals $𝐴^{- 1}$ by Theorem 2.5.10, since $𝐴^{- 1}$ is a right inverse; likewise every right inverse equals $𝐴^{- 1}$ . This proves “if” in (a) and (b).

(a) Suppose $𝐴$ has exactly one left inverse. Then $𝑇_{𝐴}$ has a left inverse, so by Theorem 2.7.2 the columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ are linearly independent. Suppose, for contradiction, that $𝑇_{𝐴}$ is not surjective. Complete the columns to a basis $𝐚_{1},$ $\dots,$ $𝐚_{𝑛},$ $𝐞_{𝑖_{1}},$ $\dots,$ $𝐞_{𝑖_{𝑡}}$ of $𝐹^{𝑚}$ as in part 3 of the proof of Theorem 2.7.2. Since the columns do not span $𝐹^{𝑚}$ (Theorem 2.7.4), $𝑡 \geq 1$ . By Theorem 2.2.1 there are linear maps $𝑆, 𝑆^{'} : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with

\begin{aligned} 𝑆 (𝐚_{𝑗}) = 𝑆^{'} (𝐚_{𝑗}) & = 𝐞_{𝑗} (𝑗 = 1, \dots, 𝑛), \\ 𝑆 (𝐞_{𝑖_{𝑠}}) = 𝑆^{'} (𝐞_{𝑖_{𝑠}}) & = 𝟎 (𝑠 \geq 2), \end{aligned}

and $𝑆 (𝐞_{𝑖_{1}}) = 𝟎$ , $𝑆^{'} (𝐞_{𝑖_{1}}) = 𝐞_{1}$ . Both are left inverses of $𝑇_{𝐴}$ , by the computation in part 3 of the proof of Theorem 2.7.2, and $𝑆 \neq 𝑆^{'}$ since $𝐞_{1} \neq 𝟎$ . This contradicts uniqueness. So $𝑇_{𝐴}$ is injective and surjective, and by Theorem 2.7.8, $𝑇_{𝐴}$ and hence $𝐴$ are invertible.

(b) Suppose $𝐴$ has exactly one right inverse $𝐵$ . Then $𝑇_{𝐴}$ is surjective (Theorem 2.7.4). Suppose, for contradiction, that $𝑇_{𝐴}$ is not injective, and let $𝐳 \neq 𝟎$ with $𝐴 𝐳 = 𝟎$ . Let $𝐵^{'}$ be $𝐵$ with $𝐳$ added to its first column. By Definition 2.4.1, the columns of $𝐴 𝐵^{'}$ are those of $𝐴 𝐵 = 𝐼_{𝑚}$ , except the first, which is $𝐴 (𝐛_{1} + 𝐳) =$ $𝐴 𝐛_{1} +$ $𝟎 =$ $𝐞_{1}$ . So $𝐴 𝐵^{'} = 𝐼_{𝑚}$ and $𝐵^{'} \neq 𝐵$ , a contradiction. So $𝑇_{𝐴}$ is bijective, and $𝐴$ is invertible by Theorem 2.7.8.

Transposing gives a second route to (a): $𝐶 \mapsto 𝐶^{𝖳}$ matches the left inverses of $𝐴$ with the right inverses of $𝐴^{𝖳}$ (Exercise 2.5.45), and $𝐴$ is invertible if and only if $𝐴^{𝖳}$ is, so (a) for $𝐴$ is (b) for $𝐴^{𝖳}$ . Done directly, the two parts are not symmetric in difficulty: a second right inverse comes from a single vector of the kernel, while a second left inverse needs the columns to be completed to a basis.

Exercise 2.7.30.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ with $𝐴 𝐵 = 𝐼_{𝑚}$ .

(a)Show that if $𝑇_{𝐵}$ is surjective, then $𝐵 𝐴 = 𝐼_{𝑛}$ .
(b)Show that if $𝑇_{𝐴}$ is injective, then $𝐵 𝐴 = 𝐼_{𝑛}$ .

Solution.

Uses. Proposition 2.5.4 (Left inverses give uniqueness), Proposition 2.5.5 (Right inverses give existence), Theorem 2.7.8 (Third Fundamental Theorem), Theorem 2.5.10 (Left and right inverses agree), Proposition 2.5.20 (Inverses and matrices)

Hint 1.

𝐴 𝐵 = 𝐼_{𝑚}

says that

𝐴

is a left inverse of

𝐵

and

𝐵

is a right inverse of

𝐴

. What does each of these say about injectivity or surjectivity?

Hint 2. In (a),

𝑇_{𝐵}

is injective and surjective. Apply Theorem 2.7.8, and then Theorem 2.5.10 to compare

𝐴

with

𝐵^{- 1}

Sketch. (a)

𝐴

is a left inverse of

𝐵

, so

𝑇_{𝐵}

is injective; with surjectivity,

𝐵

is invertible by Theorem 2.7.8, and the left inverse

𝐴

equals

𝐵^{- 1}

, so

𝐵 𝐴 = 𝐼_{𝑛}

. (b)

𝐵

is a right inverse of

𝐴

, so

𝑇_{𝐴}

is surjective; with injectivity,

𝐴

is invertible and

𝐵 = 𝐴^{- 1}

(a) Since $𝐴 𝐵 = 𝐼_{𝑚}$ , $𝑇_{𝐴}$ is a left inverse of $𝑇_{𝐵}$ , so $𝑇_{𝐵}$ is injective (Proposition 2.5.4). It is also surjective, so by Theorem 2.7.8 it is invertible, and by Proposition 2.5.20(c) so is $𝐵$ . Now $𝐴$ is a left inverse and $𝐵^{- 1}$ a right inverse of $𝐵$ , so $𝐴 = 𝐵^{- 1}$ by Theorem 2.5.10, and $𝐵 𝐴 = 𝐵 𝐵^{- 1} = 𝐼_{𝑛}$ .

(b) Since $𝐴 𝐵 = 𝐼_{𝑚}$ , $𝑇_{𝐵}$ is a right inverse of $𝑇_{𝐴}$ , so $𝑇_{𝐴}$ is surjective (Proposition 2.5.5). It is also injective, so $𝐴$ is invertible as in (a). Then $𝐵$ is a right inverse and $𝐴^{- 1}$ a left inverse of $𝐴$ , so $𝐵 = 𝐴^{- 1}$ , and $𝐵 𝐴 = 𝐴^{- 1} 𝐴 = 𝐼_{𝑛}$ .

Exercise 2.7.31.standard Let $𝑛 \geq 2$ , let $𝐽 \in 𝐹^{𝑛 \times 𝑛}$ be the matrix with every entry $1$ , and let $𝐴 = 𝐽 - 𝐼_{𝑛}$ , the matrix with $0$ on the diagonal and $1$ elsewhere. Write $𝑛$ also for $𝑛 * 1 \in 𝐹$ .

(a)Show that $𝐽^{2} = 𝑛 𝐽$ .
(b)Show that if $𝑛 - 1 \neq 0$ in $𝐹$ , then $𝐴$ is invertible with $𝐴^{- 1} =$ ${(𝑛 - 1)}^{- 1} 𝐽 -$ $𝐼_{𝑛}$ .
(c)Show that if $𝑛 - 1 = 0$ in $𝐹$ , then $𝑇_{𝐴}$ is neither injective nor surjective.
(d)For which primes $𝑝$ is the $5 \times 5$ matrix $𝐴$ invertible over $𝔽_{𝑝}$ ?

Solution.

Uses. Definition 2.4.1 (Matrix product), Proposition 2.4.14 (Algebra of matrices), Definition 2.5.12 (Invertible), Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem)

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

Hint 1. (a) Every entry of

𝐽^{2}

is a sum of

𝑛

products

1 \cdot 1

Hint 2. (b) Multiply

(𝐽 - 𝐼_{𝑛}) ({(𝑛 - 1)}^{- 1} 𝐽 - 𝐼_{𝑛})

out with (a). Both factors are combinations of

𝐽

and

𝐼_{𝑛}

, so they commute.

Hint 3. (c) Apply

𝐴

to the vector

𝟏

with all entries

1

. For surjectivity, add up the entries of

𝐴 𝐱

Sketch. (a) Each entry of

𝐽^{2}

\sum_{𝑘} 1 \cdot 1 = 𝑛

. (b)

(𝐽 - 𝐼) ({(𝑛 - 1)}^{- 1} 𝐽 - 𝐼) =

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

𝐽 +

𝐼 =

𝐼

, and the factors commute. (c)

𝐴 𝟏 = (𝑛 - 1) 𝟏 = 𝟎

, and the entries of

𝐴 𝐱

add up to

(𝑛 - 1) (𝑥_{1} + \dots + 𝑥_{𝑛}) =

0

, so

𝐞_{1}

is not a value. (d)

𝑛 - 1 = 4

, so

𝐴

is invertible over

𝔽_{𝑝}

exactly for

𝑝 \neq 2

(a) By Definition 2.4.1, the $(𝑖, 𝑗)$ entry of $𝐽^{2}$ is $\sum_{𝑘 = 1}^{𝑛} 1 \cdot 1 = 𝑛$ , which is the $(𝑖, 𝑗)$ entry of $𝑛 𝐽$ .

(b) Let $𝐵 =$ ${(𝑛 - 1)}^{- 1} 𝐽 -$ $𝐼_{𝑛}$ . By Proposition 2.4.14 and (a),

\begin{aligned} 𝐴 𝐵 & = {(𝑛 - 1)}^{- 1} 𝐽^{2} - 𝐽 - {(𝑛 - 1)}^{- 1} 𝐽 + 𝐼_{𝑛} \\ = {(𝑛 - 1)}^{- 1} (𝑛 - 1) 𝐽 - 𝐽 + 𝐼_{𝑛} = 𝐼_{𝑛} . \end{aligned}

The same expansion gives $𝐵 𝐴 = 𝐼_{𝑛}$ , since $𝐽$ commutes with itself and with $𝐼_{𝑛}$ . So $𝐴$ is invertible with $𝐴^{- 1} = 𝐵$ (Definition 2.5.12).

(c) Let $𝟏 \in 𝐹^{𝑛}$ have every entry $1$ . Each entry of $𝐴 𝟏$ is the sum of the $𝑛 - 1$ off-diagonal entries of a row, which is $𝑛 - 1 = 0$ . So $𝟏$ is a nonzero vector of $ker 𝑇_{𝐴}$ , and $𝑇_{𝐴}$ is not injective (Theorem 2.7.2). For $𝐱 \in 𝐹^{𝑛}$ with $𝑠 = 𝑥_{1} + \dots + 𝑥_{𝑛}$ , the $𝑖$ th entry of $𝐴 𝐱$ is $𝑠 - 𝑥_{𝑖}$ , so the entries of $𝐴 𝐱$ add up to $𝑛 𝑠 -$ $𝑠 =$ $(𝑛 - 1) 𝑠 =$ $0$ . The vector $𝐞_{1}$ , whose entries add up to $1$ , is therefore not a value, and $𝑇_{𝐴}$ is not surjective (Theorem 2.7.4).

(d) Here $𝑛 - 1 = 4$ , which is $0$ in $𝔽_{𝑝}$ exactly when $𝑝 = 2$ . So $𝐴$ is invertible over $𝔽_{𝑝}$ for every odd prime $𝑝$ , by (b), and not over $𝔽_{2}$ , by (c).

Exercise 2.7.32.hard This exercise proves the constraints on the shape of $𝐴$ without rank.

(a)Show by induction on $𝑚 \geq 1$ that every list of $𝑚 + 1$ vectors in $𝐹^{𝑚}$ is linearly dependent.
(b)Deduce that if $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ is injective, then $𝑛 \leq 𝑚$ ; that if $𝑇_{𝐴}$ is surjective, then $𝑛 \geq 𝑚$ ; and that if $𝐴$ is invertible, then $𝑚 = 𝑛$ .

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Corollary 1.5.17 (Sublists), Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Proposition 2.5.4 (Left inverses give uniqueness), induction on $𝑚$

Hint 1. For the inductive step, look at the last entries

𝑐_{1}, \dots, 𝑐_{𝑚 + 1}

of the vectors

𝐯_{1}, \dots, 𝐯_{𝑚 + 1} \in 𝐹^{𝑚}

. If they are all

0

, the vectors live in a copy of

𝐹^{𝑚 - 1}

Hint 2. If some last entry is nonzero, say

𝑐_{𝑚 + 1} \neq 0

, subtract multiples of

𝐯_{𝑚 + 1}

from the others to make their last entries

0

. Apply the inductive hypothesis to

𝑚

of the resulting vectors, viewed in

𝐹^{𝑚 - 1}

Hint 3. For (b), a surjective

𝑇_{𝐴}

has a right inverse

𝐵

, and

𝑇_{𝐵}

is injective.

Sketch. (a)

𝑚 = 1

: two scalars

𝑎, 𝑏

satisfy a nontrivial relation. Step: if all last entries vanish, drop them and apply the hypothesis to

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

. Otherwise, with

𝑐_{𝑚 + 1} \neq 0

, the vectors

𝐮_{𝑖} =

𝐯_{𝑖} -

(𝑐_{𝑖} / 𝑐_{𝑚 + 1}) 𝐯_{𝑚 + 1}

𝑖 \leq 𝑚

, have last entry

0

, so they satisfy a nontrivial relation, which expands to one among the

𝐯_{𝑖}

with some coefficient of

𝐯_{𝑖}

𝑖 \leq 𝑚

, nonzero. (b) Independent columns in

𝐹^{𝑚}

number at most

𝑚

. A right inverse

𝐵 \in 𝐹^{𝑛 \times 𝑚}

𝐴

has

𝐴

as a left inverse, so

𝑇_{𝐵} : 𝐹^{𝑚} \to 𝐹^{𝑛}

is injective and

𝑚 \leq 𝑛

(a) Base case $𝑚 = 1$ . Two vectors of $𝐹^{1} = 𝐹$ are scalars $𝑎, 𝑏$ . If $𝑎 = 0$ , then $1 \cdot 𝑎 + 0 \cdot 𝑏 = 0$ is a nontrivial relation; otherwise $𝑏 \cdot 𝑎 + (- 𝑎) \cdot 𝑏 = 0$ is one, since $- 𝑎 \neq 0$ .

Inductive step. Let $𝑚 \geq 2$ , assume the claim for $𝑚 - 1$ , and let $𝐯_{1}, \dots, 𝐯_{𝑚 + 1} \in 𝐹^{𝑚}$ . Let $𝑐_{𝑖}$ be the last entry of $𝐯_{𝑖}$ . For a vector of $𝐹^{𝑚}$ with last entry $0$ , write $𝐮 \in 𝐹^{𝑚 - 1}$ for the vector of its first $𝑚 - 1$ entries. If $𝐮_{1}, \dots, 𝐮_{𝑘} \in 𝐹^{𝑚}$ all have last entry $0$ , then a relation $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} = 𝟎$ in $𝐹^{𝑚 - 1}$ implies $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} = 𝟎$ in $𝐹^{𝑚}$ , since the last entries vanish anyway.

Case 1: all $𝑐_{𝑖} = 0$ . The $𝑚$ vectors $𝐯_{1}, \dots, 𝐯_{𝑚} \in 𝐹^{𝑚 - 1}$ satisfy a nontrivial relation by the inductive hypothesis, hence so do $𝐯_{1}, \dots, 𝐯_{𝑚}$ , and adding $0 \cdot 𝐯_{𝑚 + 1}$ gives a nontrivial relation among all $𝑚 + 1$ vectors.

Case 2: some $𝑐_{𝑘} \neq 0$ . Reordering the list does not affect dependence, so we may assume $𝑐_{𝑚 + 1} \neq 0$ . For $𝑖 = 1, \dots, 𝑚$ let $𝐮_{𝑖} =$ $𝐯_{𝑖} -$ $(𝑐_{𝑖} / 𝑐_{𝑚 + 1}) 𝐯_{𝑚 + 1}$ , whose last entry is $𝑐_{𝑖} - 𝑐_{𝑖} = 0$ . By the inductive hypothesis applied to $𝐮_{1}, \dots, 𝐮_{𝑚} \in 𝐹^{𝑚 - 1}$ , there are $𝑎_{1}, \dots, 𝑎_{𝑚}$ , not all $0$ , with $\sum_{𝑖 = 1}^{𝑚} 𝑎_{𝑖} 𝐮_{𝑖} =$ $𝟎$ . Expanding,

𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑚} 𝐯_{𝑚} - (\sum_{𝑖 = 1}^{𝑚} 𝑎_{𝑖} 𝑐_{𝑖} / 𝑐_{𝑚 + 1}) 𝐯_{𝑚 + 1} = 𝟎,

a relation among $𝐯_{1}, \dots, 𝐯_{𝑚 + 1}$ in which some $𝑎_{𝑖}$ with $𝑖 \leq 𝑚$ is nonzero. So the list is dependent (Theorem 1.5.5).

(b) If $𝑇_{𝐴}$ is injective, its $𝑛$ columns are linearly independent in $𝐹^{𝑚}$ (Theorem 2.7.2). If $𝑛 > 𝑚$ , the first $𝑚 + 1$ columns would be an independent sublist (Corollary 1.5.17) of $𝑚 + 1$ vectors in $𝐹^{𝑚}$ , contradicting (a). So $𝑛 \leq 𝑚$ .

If $𝑇_{𝐴}$ is surjective, it has a right inverse by Theorem 2.7.4, (I) $\Rightarrow$ (V), that is, $𝐴 𝐵 = 𝐼_{𝑚}$ for some $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ . Then $𝐴$ is a left inverse of $𝐵$ , so $𝑇_{𝐵} : 𝐹^{𝑚} \to 𝐹^{𝑛}$ is injective (Proposition 2.5.4), and by the first part, $𝑚 \leq 𝑛$ .

If $𝐴$ is invertible, $𝑇_{𝐴}$ is both, so $𝑛 \leq 𝑚$ and $𝑛 \geq 𝑚$ .

Exercise 2.7.33.routine Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

, and let

𝐺 \in 𝐹^{𝑚 \times 𝑚}

and

𝐻 \in 𝐹^{𝑛 \times 𝑛}

be invertible. Show that

𝑇_{𝐺 𝐴 𝐻}

is injective if and only if

𝑇_{𝐴}

is, and surjective if and only if

𝑇_{𝐴}

is. Deduce that

𝐺 𝐴 𝐻

is invertible if and only if

𝐴

is.

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Theorem 2.7.4 (Second Fundamental Theorem), Theorem 2.7.8 (Third Fundamental Theorem), Proposition 2.5.20 (Inverses and matrices), Proposition 2.4.14 (Algebra of matrices)

Hint 1. Use condition (V). If

𝐶 𝐴 = 𝐼_{𝑛}

, find a left inverse of

𝐺 𝐴 𝐻

built from

𝐶

𝐺^{- 1}

, and

𝐻^{- 1}

Hint 2. For the converse, write

𝐴 =

𝐺^{- 1} (𝐺 𝐴 𝐻) 𝐻^{- 1}

and apply the first direction with

𝐺^{- 1}

and

𝐻^{- 1}

Sketch. If

𝐶 𝐴 = 𝐼_{𝑛}

, then

(𝐻^{- 1} 𝐶 𝐺^{- 1}) (𝐺 𝐴 𝐻) =

𝐻^{- 1} (𝐶 𝐴) 𝐻 =

𝐼_{𝑛}

; if

𝐴 𝐶 = 𝐼_{𝑚}

, then

(𝐺 𝐴 𝐻) (𝐻^{- 1} 𝐶 𝐺^{- 1}) =

𝐼_{𝑚}

. By (I)

\Leftrightarrow

(V) of the first two theorems, injectivity and surjectivity pass from

𝐴

𝐺 𝐴 𝐻

, and back since

𝐴 =

𝐺^{- 1} (𝐺 𝐴 𝐻) 𝐻^{- 1}

. Then apply Theorem 2.7.8.

By Proposition 2.5.20(c) and Theorem 2.7.2, (I) $\Leftrightarrow$ (V), $𝑇_{𝐴}$ is injective if and only if $𝐶 𝐴 = 𝐼_{𝑛}$ for some $𝐶 \in 𝐹^{𝑛 \times 𝑚}$ . If so, then by Proposition 2.4.14,

\begin{aligned} (𝐻^{- 1} 𝐶 𝐺^{- 1}) (𝐺 𝐴 𝐻) & = 𝐻^{- 1} 𝐶 (𝐺^{- 1} 𝐺) 𝐴 𝐻 \\ = 𝐻^{- 1} (𝐶 𝐴) 𝐻 = 𝐻^{- 1} 𝐻 = 𝐼_{𝑛}, \end{aligned}

so $𝐺 𝐴 𝐻$ has a left inverse and $𝑇_{𝐺 𝐴 𝐻}$ is injective. Likewise, if $𝐴 𝐶 = 𝐼_{𝑚}$ , then $(𝐺 𝐴 𝐻) (𝐻^{- 1} 𝐶 𝐺^{- 1}) =$ $𝐺 (𝐴 𝐶) 𝐺^{- 1} =$ $𝐼_{𝑚}$ , so by Theorem 2.7.4, (V) $\Rightarrow$ (I), $𝑇_{𝐺 𝐴 𝐻}$ is surjective whenever $𝑇_{𝐴}$ is.

For the converses, apply what we just proved to the matrix $𝐺 𝐴 𝐻$ and the invertible matrices $𝐺^{- 1}$ and $𝐻^{- 1}$ : since $𝐴 =$ $𝐺^{- 1} (𝐺 𝐴 𝐻) 𝐻^{- 1}$ , injectivity and surjectivity pass from $𝐺 𝐴 𝐻$ back to $𝐴$ . Finally, by Theorem 2.7.8 and Proposition 2.5.20(c), a matrix is invertible if and only if its map is injective and surjective, so $𝐺 𝐴 𝐻$ is invertible if and only if $𝐴$ is.

Exercise 2.7.34.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝑝 \geq 1$ , and let $𝐿_{𝐴} : 𝐹^{𝑛 \times 𝑝} \to$ $𝐹^{𝑚 \times 𝑝}$ , $𝐿_{𝐴} (𝑋) = 𝐴 𝑋$ .

(a)Show that $𝐿_{𝐴}$ is linear.
(b)Show that $𝐿_{𝐴}$ is injective if and only if $𝑇_{𝐴}$ is injective.
(c)Show that $𝐿_{𝐴}$ is surjective if and only if $𝑇_{𝐴}$ is surjective.
(d)Deduce that $𝐿_{𝐴}$ is invertible if and only if $𝐴$ is invertible.

Solution.

Uses. Proposition 2.4.14 (Algebra of matrices), Proposition 2.4.8 (Four views of the product), Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Theorem 2.7.8 (Third Fundamental Theorem), Proposition 2.7.7 (Bijective linear maps are invertible), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 2.5.5 (Right inverses give existence), Proposition 2.5.20 (Inverses and matrices)

Hint 1. By the column view of the product, column

𝑘

𝐴 𝑋

𝐴 𝐱_{𝑘}

, where

𝐱_{𝑘}

is column

𝑘

𝑋

. So

𝐴 𝑋 = 𝑌

𝑝

separate systems

𝐴 𝐱_{𝑘} = 𝐲_{𝑘}

Hint 2. For “only if” in (b), turn a nonzero

𝐯 \in ker 𝑇_{𝐴}

into a nonzero matrix

𝑋

with

𝐴 𝑋 = 0

. For “only if” in (c), solve

𝐴 𝑋 = 𝑌

for a

𝑌

whose first column is a given

𝐲

Sketch. (a)

𝐴 (𝑐 𝑋 + 𝑌) =

𝑐 𝐴 𝑋 +

𝐴 𝑌

. (b) If

𝑇_{𝐴}

is injective and

𝐴 𝑋 = 0

, every column of

𝑋

is in

ker 𝑇_{𝐴} = {𝟎}

. If

𝐴 𝐯 = 𝟎

with

𝐯 \neq 𝟎

, the matrix with first column

𝐯

and other columns

𝟎

is a nonzero element of

ker 𝐿_{𝐴}

. (c) Solve column by column; conversely, the first column of a solution of

𝐴 𝑋 = (𝐲, 𝟎, \dots, 𝟎)

solves

𝐴 𝐱 = 𝐲

. (d) Combine (b), (c), Theorem 2.7.8, and Proposition 2.7.7.

Write $𝐱_{1}, \dots, 𝐱_{𝑝}$ for the columns of $𝑋 \in 𝐹^{𝑛 \times 𝑝}$ . By Proposition 2.4.8, column $𝑘$ of $𝐴 𝑋$ is $𝐴 𝐱_{𝑘}$ .

(a) By Proposition 2.4.14, $𝐴 (𝑐 𝑋 + 𝑌) =$ $𝑐 𝐴 𝑋 +$ $𝐴 𝑌$ for $𝑋, 𝑌 \in 𝐹^{𝑛 \times 𝑝}$ and $𝑐 \in 𝐹$ , so $𝐿_{𝐴}$ is linear.

(b) Suppose $𝑇_{𝐴}$ is injective, and $𝐴 𝑋 = 0$ . Then $𝐴 𝐱_{𝑘} = 𝟎$ for every $𝑘$ , so every $𝐱_{𝑘} = 𝟎$ , and $𝑋 = 0$ . So $ker 𝐿_{𝐴} = {0}$ , and $𝐿_{𝐴}$ is injective (Theorem 2.6.11). Conversely, suppose $𝑇_{𝐴}$ is not injective, and let $𝐯 \neq 𝟎$ with $𝐴 𝐯 = 𝟎$ . Let $𝑋$ have first column $𝐯$ and all other columns $𝟎$ (this uses $𝑝 \geq 1$ ). Then $𝑋 \neq 0$ and $𝐴 𝑋 = 0$ , so $𝐿_{𝐴}$ is not injective.

(c) Suppose $𝑇_{𝐴}$ is surjective, and let $𝑌 \in 𝐹^{𝑚 \times 𝑝}$ have columns $𝐲_{1}, \dots, 𝐲_{𝑝}$ . Choose $𝐱_{𝑘}$ with $𝐴 𝐱_{𝑘} = 𝐲_{𝑘}$ , and let $𝑋$ have columns $𝐱_{1}, \dots, 𝐱_{𝑝}$ ; then $𝐴 𝑋 = 𝑌$ . Conversely, suppose $𝐿_{𝐴}$ is surjective, and let $𝐲 \in 𝐹^{𝑚}$ . Some $𝑋$ satisfies $𝐴 𝑋 = 𝑌$ , where $𝑌$ has first column $𝐲$ and all other columns $𝟎$ . Comparing first columns, $𝐴 𝐱_{1} = 𝐲$ . So $𝑇_{𝐴}$ is surjective.

(d) A linear map is invertible if and only if it is bijective (Proposition 2.7.7, Proposition 2.5.4, Proposition 2.5.5). By (b) and (c), $𝐿_{𝐴}$ is bijective if and only if $𝑇_{𝐴}$ is, which by Theorem 2.7.8 and Proposition 2.5.20(c) holds if and only if $𝐴$ is invertible.

Exercise 2.7.35.challenge For a matrix $𝐴$ with integer entries and a prime $𝑝$ , let $𝐴 \in 𝔽_{𝑝}^{𝑚 \times 𝑛}$ be the matrix of remainders of the entries of $𝐴$ modulo $𝑝$ .

(a)Let $𝐴 \in ℤ^{𝑚 \times 𝑛}$ . Show that if the columns of $𝐴$ are linearly independent over $𝔽_{𝑝}$ , then the columns of $𝐴$ are linearly independent over $ℚ$ .
(b)Show that every $𝑛 \times 𝑛$ matrix with odd integers on the diagonal and even integers off the diagonal has linearly independent columns over $ℚ$ .
(c)Show that the converse of (a) is false.

Solution.

Uses. Theorem 2.7.2 (First Fundamental Theorem), Lemma 1.1.21 (Arithmetic in $ℤ / 𝑛 ℤ$ ), Proposition 1.1.24 ( $ℤ / 𝑛 ℤ$ is a field if and only if $𝑛$ is prime)

Hint 1. By Theorem 2.7.2, it suffices to show that

𝐴 𝐱 = 𝟎

with

𝐱 \in ℚ^{𝑛}

forces

𝐱 = 𝟎

. Suppose not. Can you make

𝐱

an integer vector?

Hint 2. Clear denominators, then divide by the largest power of

𝑝

that divides every entry. The result is an integer solution with some entry not divisible by

𝑝

. Now reduce modulo

𝑝

Hint 3. (b) Take

𝑝 = 2

. (c) A

1 \times 1

example suffices.

Sketch. If

𝐴 𝐱 = 𝟎

with

𝐱 \in ℚ^{𝑛}

nonzero, scale

𝐱

to an integer vector, not all of whose entries are divisible by

𝑝

. Reducing each equation

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

modulo

𝑝

(Lemma 1.1.21) gives

𝐴 𝐱 = 𝟎

with

𝐱 \neq 𝟎

, contradicting Theorem 2.7.2 over

𝔽_{𝑝}

. (b) With

𝑝 = 2

𝐴 = 𝐼_{𝑛}

. (c)

𝐴 = (𝑝)

(a) By Theorem 2.7.2, (III) $\Leftrightarrow$ (IV), over $ℚ$ and over $𝔽_{𝑝}$ , it suffices to show: if $𝐴 𝐳 = 𝟎$ has only the solution $𝐳 = 𝟎$ in $𝔽_{𝑝}^{𝑛}$ , then $𝐴 𝐱 = 𝟎$ has only the solution $𝐱 = 𝟎$ in $ℚ^{𝑛}$ .

Suppose, for contradiction, that $𝐴 𝐱 = 𝟎$ for some nonzero $𝐱 \in ℚ^{𝑛}$ . Multiplying $𝐱$ by the product of the denominators of its entries, we may assume that $𝐱 \in ℤ^{𝑛}$ , still nonzero. Some entry $𝑥_{𝑘}$ is a nonzero integer, and $𝑝^{𝑒} ∣ 𝑥_{𝑘}$ only for $𝑝^{𝑒} \leq | 𝑥_{𝑘} |$ , so there is a largest $𝑒 \geq 0$ such that $𝑝^{𝑒}$ divides every entry of $𝐱$ . Dividing by $𝑝^{𝑒}$ , we may assume that $𝐱 \in ℤ^{𝑛}$ , $𝐴 𝐱 = 𝟎$ , and some entry of $𝐱$ is not divisible by $𝑝$ .

For each $𝑖$ , $\sum_{𝑗 = 1}^{𝑛} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} =$ $0$ in $ℤ$ . Reduction modulo $𝑝$ respects sums and products (Lemma 1.1.21(a)), so $\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} = 0 = 0$ in $𝔽_{𝑝}$ , where $𝑎$ is the remainder of $𝑎$ modulo $𝑝$ . That is, $𝐴 𝐱 = 𝟎$ , where $𝐱 \in 𝔽_{𝑝}^{𝑛}$ has entries $𝑥_{𝑗}$ . Since some $𝑥_{𝑗}$ is not divisible by $𝑝$ , $𝑥_{𝑗} \neq 0$ , so $𝐱 \neq 𝟎$ . This contradicts the hypothesis on $𝐴$ .

(b) With $𝑝 = 2$ , an odd integer has remainder $1$ and an even one remainder $0$ , so $𝐴 = 𝐼_{𝑛}$ , whose columns $𝐞_{1}, \dots, 𝐞_{𝑛}$ are independent over $𝔽_{2}$ . By (a), the columns of $𝐴$ are independent over $ℚ$ .

(c) $𝐴 = (𝑝) \in ℤ^{1 \times 1}$ has a nonzero column, which is independent over $ℚ$ , but $𝐴 = (0)$ .

For (b), Section 3.5 shows that a square matrix with independent columns is invertible (Corollary 3.5.25), so these matrices are invertible over $ℚ$ .

More practice

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