3.6 Proof patterns · Matrix Theory

Nearly every proof in this chapter ran through Gauss–Jordan elimination, but it used the algorithm in only a handful of ways: as a reduction to a simpler matrix, as an object whose correctness had to be proved, as a way to settle existence questions, and as a table from which structure can be read. This section sorts the chapter’s proofs by the question they answer, compares the tools on examples from the chapter, and says when each tool is the wrong one. The exercises at the end practice one move at a time, and the chapter’s problems (Problems for Chapter 3) mix them.

3.6.1Proving a statement about every matrix

The chapter has two reductions. Technique 3.3.22 replaces $𝐴$ by $rref (𝐴) = 𝐺 𝐴$ with $𝐺$ invertible (Theorem 3.3.10). Technique 5.4.6, which is named in Section 5.4 but first used here, writes an invertible matrix as a product of elementary matrices (Theorem 3.5.19) and checks the three types one at a time. The rank normal form $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ (Theorem 3.5.27) is a two-sided version of the first. To choose between them, ask what the property you want has to survive.

Reducing to RREF needs a property $𝑃$ with $𝑃 (𝐴) \Leftrightarrow 𝑃 (𝐺 𝐴)$ for every invertible $𝐺$ . The chapter found many: the kernel (Corollary 3.2.23), the linear relations among the columns (Corollary 3.2.17), and everything defined from these, such as which columns are pivot columns (Corollary 3.3.19), the rank (Proposition 3.5.2(c)), and, for square $𝐴$ , invertibility. Solution sets survive only if the right-hand side moves too: $𝐴 𝐱 = 𝐲$ becomes $rref (𝐴) 𝐱 = 𝐺 𝐲$ (Proposition 3.2.14). Once invariance is checked, the question is about a matrix whose pivot columns are $𝐞_{1}, \dots, 𝐞_{𝑟}$ and whose zero rows are visible, and it usually answers itself. This is how Theorem 3.3.23, Proposition 3.4.15, and Corollary 3.3.20 were proved.

Reducing to elementary matrices needs something else: a statement about invertible matrices that survives products. Then two checks suffice, one computation for each type and one step showing that the statement passes from $𝐴$ to $𝐸 𝐴$ (or $𝐴 𝐸$ ). Invariance under $𝐴 \mapsto 𝐺 𝐴$ plays no role. This is how Corollary 3.5.22 turned “multiply by invertible matrices” into “perform row and column operations”, and how Section 5.4 proves $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ . The method only reaches invertible matrices, because products of elementary matrices are invertible. A statement about all square matrices needs a second argument for the others. Often both sides of the claim simply vanish there; otherwise one reduces to RREF, writes $𝐴 = 𝐺^{- 1} rref (𝐴)$ , and uses the zero row of $rref (𝐴)$ (Exercise 3.6.10). Forgetting this case is the error in Exercise 5.4.35.

Example 3.6.1 (Which reduction fits). Commuting with every invertible matrix. Which $𝑀 \in 𝐹^{𝑛 \times 𝑛}$ satisfy $𝑀 𝑋 = 𝑋 𝑀$ for every invertible $𝑋$ ? Reducing to RREF is useless here, since $𝑀$ commuting with $𝑋$ says nothing about $𝑀$ commuting with $𝐺 𝑋$ . But the property survives products: if $𝑀 𝑋 = 𝑋 𝑀$ and $𝑀 𝑌 = 𝑌 𝑀$ , then $𝑀 𝑋 𝑌 =$ $𝑋 𝑀 𝑌 =$ $𝑋 𝑌 𝑀$ . So by Theorem 3.5.19, $𝑀$ commutes with every invertible matrix if and only if it commutes with every elementary one, and for $𝑛 \geq 2$ the type 3 matrices alone already force $𝑀 = 𝜆 𝐼_{𝑛}$ (Exercise 3.2.52; for $𝑛 = 1$ every $𝑀$ works).

Rank under row and column operations. That $rank (𝐺 𝐴) = rank 𝐴$ for invertible $𝐺$ is one line by reducing to RREF: $rref (𝐺 𝐴) =$ $rref (𝐴)$ (Corollary 3.3.18(a)). The same attempt for $𝐴 𝐻$ fails. With $𝐴 = (\begin{matrix} 0 & 1 \end{matrix})$ and $𝐻 = 𝐸_{12}$ we get $𝐴 𝐻 = (\begin{matrix} 1 & 0 \end{matrix})$ , and $𝐴$ and $𝐴 𝐻$ are both in RREF, so $rref (𝐴 𝐻) \neq$ $rref (𝐴)$ , although both have rank $1$ . Right multiplication does not preserve the reduced form, so the reduction cannot see that $rank (𝐴 𝐻) = rank 𝐴$ . A different argument is needed: the uniqueness of the rank normal form (Exercise 3.5.41), or transposition, which turns the column operations into row operations of $𝐴^{𝖳}$ and so reduces the question to the equality $rank 𝐴^{𝖳} = rank 𝐴$ of Section 4.3.

3.6.2Proving that an algorithm is correct

An algorithm proves that something exists once two things are shown about every run (Technique 3.3.5). For termination, find a quantity that moves in one direction and cannot do so forever: in Gauss–Jordan elimination, the number $𝑘$ of pivoted rows grows by $1$ in each pass and never exceeds $𝑚$ (Proposition 3.3.6). For correctness, find an invariant that the starting state satisfies and every step preserves, and that, combined with the reason for halting, gives the property of the output.

The invariant is where the work is, and its typical feature is visible in Lemma 3.3.7. The property we want at the end, conditions (R1)–(R4), is not preserved pass by pass: halfway through, the unpivoted rows are an arbitrary mess. The invariant has to say something about that mess, and part (e) does: the unpivoted rows vanish in every column up to the last pivot. Part (e) is what forces each new pivot to lie to the right of the old ones, which is (b), and it, together with the vanishing of the new pivot row to the left of its pivot, is exactly what choosing the leftmost column in step 1 of Algorithm 3.3.1 keeps true. Drop that choice and both the proof and the algorithm break (Exercise 3.3.47). The same pattern recurs in the exercises: Euclid’s algorithm by row operations has the monovariant $| 𝑏 |$ and the invariant “the common divisors of the two entries” (Exercise 3.2.54), and elimination on a strictly diagonally dominant matrix needs no swap because the block still to be processed stays diagonally dominant (Exercise 3.3.56). Even Theorem 3.3.12 was proved by running the algorithm, on a matrix of the right shape, with the invariant “nothing has changed yet”. Exercise 3.6.11 practices the technique on an algorithm that has nothing to do with elimination.

An algorithm proves that some output with the guaranteed properties exists. It does not prove that this output is the only object with those properties, and a run that made different choices could, as far as the invariant knows, stop somewhere else. That is why the uniqueness of the reduced row echelon form needed its own theorem (Theorem 3.3.17), and why, before it, we could not say that another way of reducing $𝐴$ finds the same pivots, or that $rank (𝐺 𝐴) = rank 𝐴$ (Remark 3.3.2). For echelon forms that are not reduced, uniqueness really fails (Example 3.3.29).

3.6.3Turning an existence question into a linear system

“Is there a polynomial, a combination, a map, a set of weights, such that …?” The move of Technique 3.1.9 is to write the unknown object with unknown scalars, translate each requirement into an equation in them, and check that the equations are linear. The question has become the consistency of a linear system, and the set of all answers has the shape of Technique 3.1.18: one answer plus everything that solves the homogeneous version. The chapter used this for membership in a span (Example 3.1.10), interpolation (Theorem 3.4.24), chemical balancing (Exercise 3.1.39), quadrature weights (Exercise 3.4.43), and antiderivatives, where the homogeneous solutions are the constants (Example 3.1.20).

Example 3.6.2 (One question, three answers). Which polynomials take the values $2, 1, 4$ at $- 1, 0, 1$ ? The answer depends on how many coefficients we allow, that is, on the number of unknowns against the three equations (Exercise 3.1.37).

In ${ℝ [𝑥]}_{\leq 1}$ , write $𝑝 = 𝑎 + 𝑏 𝑥$ . The conditions $𝑎 - 𝑏 = 2$ , $𝑎 = 1$ , $𝑎 + 𝑏 = 4$ give $𝑏 = - 1$ and $𝑏 = 3$ , so there is no solution: three equations, two unknowns, and an inconsistent system.
In ${ℝ [𝑥]}_{\leq 2}$ there are three unknowns and exactly one solution, $1 + 𝑥 + 2 𝑥^{2}$ .
In ${ℝ [𝑥]}_{\leq 3}$ there are four unknowns, and the solutions are $1 +$ $𝑥 +$ $2 𝑥^{2} +$ $𝑡 (𝑥^{3} - 𝑥)$ for $𝑡 \in ℝ$ : the particular solution from the previous case plus the cubics that vanish at $- 1, 0, 1$ .

The count of unknowns against equations predicts what can happen (Corollary 3.4.19), but only the system decides. The square case has exactly one solution here because of a structural fact, which is the subject of the next subsection.

The technique is the wrong tool when the requirements are not linear in the unknowns. Asking for a matrix $𝑋$ with $𝑋^{2} = 𝐴$ gives quadratic equations in the entries of $𝑋$ , and elimination does not apply. Side conditions such as positivity or integrality are not linear either: the linear system only finds the subspace of all balancings in Exercise 3.1.39, and a separate divisibility argument picks the smallest positive integer one; the nonnegative flows of Exercise 3.1.38 come from an inequality on the parameter. Also remember that the system lives over a field, and solving it divides by scalars: in Example 3.1.10 the same equations are solvable over $ℝ$ and inconsistent over $𝔽_{2}$ , because one step divided by $2$ .

3.6.4When uniqueness gives existence

Uniqueness and existence behave differently. Uniqueness is a property of the homogeneous problem alone, for a matrix of any size: a consistent system has exactly one solution if and only if $ker 𝑇_{𝐴} = {𝟎}$ (Corollary 3.1.22). Existence for every right-hand side is a property of the zero rows of $rref (𝐴)$ (Proposition 3.4.16). For a square matrix the two conditions coincide, since both say $rank 𝐴 = 𝑛$ (Corollary 3.4.20). So for square problems the homogeneous statement buys existence for free (Technique 3.4.21). The homogeneous statement says that a single object is zero, and it is usually proved by structure rather than computation: a polynomial with too many roots (Lemma 3.4.23), a maximum principle (Exercise 3.1.47), or the observation that $𝐵 𝐴 = 𝐼_{𝑛}$ leaves no room for free variables (Theorem 3.5.23).

Example 3.6.3 (Existence, with and without a formula). Interpolation (Theorem 3.4.24) was proved without solving anything:

𝑛 + 1

conditions on

𝑛 + 1

coefficients, and a polynomial of degree at most

𝑛

with

𝑛 + 1

roots is zero. The Lagrange polynomials (Definition 3.4.26) were then defined through the theorem, so Lagrange’s formula did not give a second existence proof. That needs the closed form

𝐿_{𝑖} =

\prod_{𝑗 \neq 𝑖} (𝑥 - 𝑐_{𝑗}) / (𝑐_{𝑖} - 𝑐_{𝑗})

, which is a construction, and which waits for polynomial multiplication in Section 7.1. The construction gives more, a formula, but only when a formula is available. For the plate of Exercise 3.1.47 there is none, and uniqueness is the natural route to existence.

There are three ways to misuse the technique. First, on a non-square system it proves nothing: $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix})$ has trivial kernel and $𝐴 𝑥 = (1, 0)$ has no solution (Exercise 3.1.34). Second, counting conditions is not the proof; the homogeneous problem must actually have only the zero solution, and when it does not, existence fails too for some data. In the cyclic system of Exercise 3.1.46 with $𝑛$ even, the homogeneous solution $(1, - 1, \dots, 1, - 1)$ comes with the condition that the alternating sum of the right-hand sides vanish, since the alternating sum of the left sides is $0$ . Exercise 3.6.14 is a smaller instance. Third, the technique depends on finite size. On $𝐹 [𝑥]$ , the shift $𝑆$ with $𝑆 (𝑥^{𝑘}) = 𝑥^{𝑘 + 1}$ has a left inverse but is not surjective (the intuition after Theorem 3.5.23), and Section 4.2 replaces “square” by $dim 𝑉 = dim 𝑊$ .

3.6.5Reading structure off the reduced form

Once $𝐺 𝐴 = 𝑅 = rref (𝐴)$ is computed, a great deal can be read off without further work:

a pivot in every column means at most one solution for each $𝐲$ , independent columns, and injectivity of $𝑇_{𝐴}$ (Proposition 3.4.15, Theorem 3.5.12); a pivot in every row means solutions for every $𝐲$ , spanning columns, and surjectivity (Proposition 3.4.16, Theorem 3.5.13);
the pivot columns are the columns of $𝐴$ that are not combinations of earlier ones, and the entries of $𝑅$ in a free column are the coefficients that build that column of $𝐴$ from the pivot columns (Corollary 3.3.19);
the basic solutions, one for each free column, describe $ker 𝑇_{𝐴}$ (Theorem 3.4.9);
the last $𝑚 - rank 𝐴$ rows of $𝐺$ give the consistency conditions, so they describe $im 𝑇_{𝐴}$ (Corollary 3.4.4), and they are also the relations among the rows of $𝐴$ (Exercise 3.3.57).

Everything in the first three items is about relations among the columns, and $𝑅$ carries it alone. The image is different: it needs $𝐺$ , or the original columns of $𝐴$ .

Example 3.6.4 (Everything about one matrix). For the matrix $𝐴$ of Example 3.3.3, with columns $𝐚_{1}, \dots, 𝐚_{4}$ ,

\begin{aligned} 𝐴 & = (\begin{matrix} 0 & 0 & 2 & 4 \\ 2 & 4 & 2 & 0 \\ 1 & 2 & 3 & 4 \end{matrix}), \\ 𝑅 & = (\begin{matrix} 1 & 2 & 0 & - 2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{matrix}), \\ 𝐺 & = (\begin{matrix} - 1 / 2 & 1 / 2 & 0 \\ 1 / 2 & 0 & 0 \\ - 1 & - 1 / 2 & 1 \end{matrix}) . \end{aligned}

The rank is $2$ , with pivot columns $1, 3$ and free columns $2, 4$ . From the entries of $𝑅$ , $𝐚_{2} = 2 𝐚_{1}$ and $𝐚_{4} = - 2 𝐚_{1} + 2 𝐚_{3}$ . The basic solutions $(- 2, 1, 0, 0)$ and $(2, 0, - 2, 1)$ describe $ker 𝑇_{𝐴}$ (Example 3.4.10). The last row of $𝐺$ gives the single consistency condition $- 𝑦_{1} - 𝑦_{2} / 2 + 𝑦_{3} = 0$ , so $im 𝑇_{𝐴}$ is the plane $2 𝑦_{3} = 2 𝑦_{1} + 𝑦_{2}$ (Example 3.4.6), spanned by the pivot columns $𝐚_{1} = (0, 2, 1)$ and $𝐚_{3} = (2, 2, 3)$ of $𝐴$ .

The classic error is to take the pivot columns of $𝑅$ instead. They are $𝐞_{1}$ and $𝐞_{2}$ , and $𝐞_{1} = (1, 0, 0)$ is not in $im 𝑇_{𝐴}$ , since $2 \cdot 0 \neq 2 \cdot 1 + 0$ . The columns of $𝑅$ span $im 𝑇_{𝑅}$ , which is $im 𝑇_{𝐴}$ moved by $𝐺$ (Non-example 3.2.19). The fix is to read which columns are pivot columns from $𝑅$ and to take those columns from $𝐴$ . Exercise 3.6.6 and Exercise 3.6.7 practice the distinction.

3.6.6Row operations and column operations

Row operations multiply on the left by an invertible $𝐺$ , and column operations multiply on the right by an invertible $𝐻$ . They preserve different things (Table 3.6.1).

Property of $𝐴$	Row operations, $𝐴 \mapsto 𝐺 𝐴$	Column operations, $𝐴 \mapsto 𝐴 𝐻$
$ker 𝑇_{𝐴}$	kept (Corollary 3.2.23)	moved by $𝐻^{- 1}$
relations among the columns	kept (Corollary 3.2.17)	changed
$im 𝑇_{𝐴}$ , the span of the columns	moved by $𝐺$	kept (Proposition 3.2.30)
relations among the rows	changed	kept (Exercise 3.6.8)
$rref (𝐴)$ and the pivot columns	kept (Corollary 3.3.18)	changed
$rank 𝐴$	kept (Proposition 3.5.2)	kept (Exercise 3.5.41)

Table 3.6.1. What the two kinds of operations preserve. “Moved by

𝐺

” means that the new image is

{𝐺 𝐲 | 𝐲 \in im 𝑇_{𝐴}}

, and similarly for the kernel, which becomes

{𝐻^{- 1} 𝐱 | 𝐱 \in ker 𝑇_{𝐴}}

. Transposing turns column operations on

𝐴

into row operations on

𝐴^{𝖳}

(Technique 3.2.27); for instance, the relations among the rows of

𝐴

form the kernel of

𝑇_{𝐴^{𝖳}}

, which is why column operations keep them.

Example 3.6.5 (One matrix, both operations). Let

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

, so

ker 𝑇_{𝐴} =

span ((1, - 1))

and

im 𝑇_{𝐴} =

span ((1, 1))

. The row operation

𝐸_{1, - 1, 2}

gives

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

, with the same kernel and the image

span ((1, 0))

. The column operation “add

- 1

times column

1

to column

2

”, which is right multiplication by

𝐻 =

𝐸_{2, - 1, 1} =

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

, gives

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

, with the same image and the kernel

span ((0, 1))

. Indeed

𝐻^{- 1} (1, - 1) =

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

(0, - 1)

, as the table predicts.

So row operations are the tool for solving systems and for finding relations among the columns, and column operations are the tool for questions about the span of the columns. Using column operations to solve $𝐴 𝐱 = 𝐲$ changes the unknowns: $𝐴 𝐻 𝐱^{'} = 𝐲$ is solved by $𝐱^{'}$ exactly when $𝐴 𝐱 = 𝐲$ is solved by $𝐱 = 𝐻 𝐱^{'}$ , so the answer must be translated back. Using row operations on a question about the span of the columns moves the span. This is why the bad right-hand side in the proof of Proposition 3.4.16 is $𝐺^{- 1} 𝐞_{𝑚}$ and not $𝐞_{𝑚}$ (Remark 3.4.17). With both kinds of operations allowed, only the rank survives, and every matrix of rank $𝑘$ becomes $𝑁_{𝑘}$ (Theorem 3.5.27).

3.6.7Reading the chapter’s proofs

Uniqueness of the reduced form, two ways. Writing $𝑅^{'} = 𝐺 𝑅$ column by column suggests the first proof of Theorem 3.3.17: track $𝐺$ , and show pivot by pivot, from the left, that the pivot columns agree and that $𝐺$ fixes $𝐞_{1}, \dots, 𝐞_{𝑟}$ . It needs invertibility of $𝐺$ in a concrete form, the independence of its columns, to rule out a pivot that appears too early in one matrix. The second proof forgets $𝐺$ . It notices that everything about a matrix in RREF, which columns are pivot columns and what the other columns are, is determined by the linear relations among its columns (Lemma 3.3.16), and that row operations preserve those relations. The comparison teaches a habit: after a proof, list the hypotheses it actually used. The second proof used one consequence of $𝑅^{'} = 𝐺 𝑅$ , namely that $𝑅$ and $𝑅^{'}$ have the same kernel, so it proves the stronger statement Corollary 3.3.20 at no extra cost. The first proof, in turn, says something the second does not: $𝐺$ is rigid on $𝐞_{1}, \dots, 𝐞_{𝑟}$ and free elsewhere (Exercise 3.3.46).

Constructive and structural proofs. Several results got one proof of each kind. Proposition 3.4.15 was proved by setting one free variable to $1$ , which produces a nonzero solution, and by the linear dependence lemma, which explains what a missing pivot means. Proposition 3.5.9 was proved from the pivots, which gives a formula, and by extending the columns to a basis, which works for linear maps between abstract vector spaces as long as the domain has a finite basis and the target a finite spanning list (Exercise 3.5.40). Theorem 3.5.27 was proved by clearing columns and by row reducing the transpose. The computational proof usually produces a formula or a witness, and the structural one usually survives the passage to abstract vector spaces.

Do it to the identity. To find the matrix of an operation that acts on each column by the same linear map, perform the operation on $𝐼_{𝑚}$ (Lemma 3.2.6, the first proof of Proposition 3.2.7). The same idea, run along with the algorithm, records the whole elimination: carrying $𝐼_{𝑚}$ next to $𝐴$ produces $𝐺$ (Proposition 3.3.11), and carrying $𝐼_{𝑛}$ next to a square $𝐴$ produces $𝐴^{- 1}$ (Algorithm 3.3.24).

3.6.8Common errors

Each of these appears in the chapter, most of them as find-the-error exercises.

Simultaneous row operations. Replacing two equations at once, where the second replacement uses an equation the first one changed, can gain solutions (Exercise 3.1.35). So can scaling a row by $0$ , which is why it is not an elementary operation.
The order of the factors. The first row operation is the rightmost factor of $𝐺 = 𝐸_{𝑡} \dots 𝐸_{1}$ (Example 3.2.8); for column operations it is the leftmost (Remark 3.2.29).
Row operations do not preserve the image. $𝐴 𝐱 = 𝐲$ is equivalent to $𝐺 𝐴 𝐱 = 𝐺 𝐲$ , not to $𝐺 𝐴 𝐱 = 𝐲$ (Exercise 3.2.43, Remark 3.4.17), and the columns of $rref (𝐴)$ do not span $im 𝑇_{𝐴}$ (Exercise 3.6.6).
Uniqueness is not existence. A trivial kernel gives at most one solution, not one (Exercise 3.1.34). Checking that some vectors are solutions does not show that they are all of them (Exercise 3.4.34, Remark 3.4.12). Counting equations and unknowns does not replace proving uniqueness (Exercise 3.6.14).
The shape bounds the rank only from above. $rank 𝐴 \leq min (𝑚, 𝑛)$ , and equality is a condition to check, not a consequence of the shape (Problem 3.7).
One-sided inverses of non-square matrices. Cancelling a matrix that has only a right inverse, or inverting $𝐴 𝐵$ when $𝐴$ is not square, is invalid (Exercise 3.5.26, Exercise 3.5.35).
Rigidity overstated. $𝐺 𝑅 = 𝑅$ with $𝑅$ in RREF does not force $𝐺 = 𝐼_{𝑚}$ (Exercise 3.3.46).
Reducing to elementary matrices beyond its reach. Only invertible matrices are products of elementary matrices; the other case needs its own argument (Exercise 5.4.35, Problem 3.7).
Hidden division. Pivots, ranks, and inverses depend on the field, because elimination divides (Example 3.5.3, Exercise 3.3.27).
Pictures from the plane. Three planes in $ℝ^{3}$ , no two of them parallel, can still have no common point (Exercise 3.1.36).

Exercises

Exercise 3.6.6.routine Let

𝐴 = (\begin{matrix} 1 & 2 & 0 \\ 2 & 4 & 1 \\ 3 & 6 & 1 \end{matrix}) \in ℝ^{3 \times 3}, rref (𝐴) = (\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) .

A student argues: “Row operations do not change the linear relations among the columns, and the pivot columns of $rref (𝐴)$ are independent. So $im 𝑇_{𝐴}$ has the independent spanning list $(1, 0, 0), (0, 1, 0)$ , the pivot columns of $rref (𝐴)$ .”

(a)Show that $(1, 0, 0) \notin im 𝑇_{𝐴}$ , and find the error.
(b)Find two vectors that span $im 𝑇_{𝐴}$ , and an equation for $im 𝑇_{𝐴}$ .

Solution.

Uses. Corollary 3.3.19 (Pivot columns, intrinsically), Corollary 3.2.17 (Row operations preserve relations among columns), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Corollary 3.4.4 (Consistency), Non-example 3.2.19 (Row operations move the column space)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. Every column of

𝐴

has third entry equal to the sum of the first two. Does

(1, 0, 0)

Hint 2. Row operations preserve the relations among the columns, so they preserve which columns are pivot columns. Do they preserve the columns themselves?

Hint 3. Use Corollary 3.3.19(b): every column of

𝐴

is a combination of the pivot columns of $𝐴$ .

Sketch. (a) The columns

(1, 2, 3)

(2, 4, 6)

(0, 1, 1)

all satisfy

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

, so every vector of

im 𝑇_{𝐴}

does, and

(1, 0, 0)

does not. The relations transfer, but the columns of

rref (𝐴) = 𝐺 𝐴

are

𝐺 𝐚_{𝑗}

, and they span

im 𝑇_{𝐺 𝐴}

, not

im 𝑇_{𝐴}

. (b) The pivot columns of

𝐴

(1, 2, 3)

and

(0, 1, 1)

, span

im 𝑇_{𝐴}

, which is the plane

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

(a) The columns of $𝐴$ are $𝐚_{1} = (1, 2, 3)$ , $𝐚_{2} = (2, 4, 6)$ , and $𝐚_{3} = (0, 1, 1)$ , and each satisfies $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ . This condition is preserved by sums and scalar multiples, so every linear combination of the columns satisfies it, and by Proposition 3.1.8(a) every vector of $im 𝑇_{𝐴}$ does. The vector $(1, 0, 0)$ has $0 \neq 1 + 0$ , so it is not in $im 𝑇_{𝐴}$ .

The first sentence of the argument is correct (Corollary 3.2.17), and it does show that columns $1$ and $3$ of $𝐴$ are independent and that column $2$ is a combination of them. The error is the step from relations to the vectors themselves. Writing $rref (𝐴) = 𝐺 𝐴$ with $𝐺$ invertible, the columns of $rref (𝐴)$ are $𝐺 𝐚_{1}, 𝐺 𝐚_{2}, 𝐺 𝐚_{3}$ , so they span $im 𝑇_{𝐺 𝐴}$ , the image of $𝑇_{𝐴}$ moved by $𝐺$ . Row operations move the image (Non-example 3.2.19).

(b) By Corollary 3.3.19(b), the non-pivot column $𝐚_{2}$ is a combination of the pivot column $𝐚_{1}$ (indeed $𝐚_{2} = 2 𝐚_{1}$ , read off the entry $2$ of $rref (𝐴)$ ). So $im 𝑇_{𝐴} =$ $span (𝐚_{1}, 𝐚_{2}, 𝐚_{3}) =$ $span (𝐚_{1}, 𝐚_{3}) =$ $span ((1, 2, 3), (0, 1, 1))$ . For an equation: we showed that every vector of $im 𝑇_{𝐴}$ satisfies $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ . Conversely, if $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ , then

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

so $𝐲 \in im 𝑇_{𝐴}$ . Hence $im 𝑇_{𝐴} =$ ${𝐲 \in ℝ^{3} | 𝑦_{3} = 𝑦_{1} + 𝑦_{2}}$ . (The same equation comes out of Corollary 3.4.4: reducing $𝐴$ uses $𝐸_{1, - 2, 2}$ , $𝐸_{1, - 3, 3}$ , and $𝐸_{2, - 1, 3}$ , and the last row of $𝐺$ is $(- 1, - 1, 1)$ .)

Exercise 3.6.7.routine A matrix $𝐴 \in ℝ^{3 \times 4}$ has

rref (𝐴) = (\begin{matrix} 1 & 2 & 0 & - 1 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 \end{matrix}),

and its first and third columns are $𝐚_{1} = (1, 1, 2)$ and $𝐚_{3} = (0, 1, - 1)$ .

(a)Find $𝐴$ .
(b)Find vectors spanning $ker 𝑇_{𝐴}$ , and an equation describing $im 𝑇_{𝐴}$ .

Solution.

Uses. Corollary 3.3.19 (Pivot columns, intrinsically), Theorem 3.4.9 (All solutions), Definition 3.4.8 (Basic solutions), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ )

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. Columns

1

and

3

are the pivot columns. What does Corollary 3.3.19(b) say about columns

2

and

4

Hint 2. The kernel depends only on

rref (𝐴)

: use the basic solutions. The image is spanned by the pivot columns of

𝐴

Sketch. (a)

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

and

𝐚_{4} =

- 𝐚_{1} +

3 𝐚_{3} =

(- 1, 2, - 5)

. (b)

ker 𝑇_{𝐴} =

span ((- 2, 1, 0, 0), (1, 0, - 3, 1))

, and

im 𝑇_{𝐴} =

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

, which is the plane

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

(a) The pivot columns of $rref (𝐴)$ are $1$ and $3$ , so these are the pivot columns of $𝐴$ , and columns $2$ and $4$ are free. By Corollary 3.3.19(b), each free column of $𝐴$ is the combination of the pivot columns to its left whose coefficients are the entries of the corresponding column of $rref (𝐴)$ :

𝐚_{2} = 2 𝐚_{1} = (2, 2, 4), 𝐚_{4} = - 𝐚_{1} + 3 𝐚_{3} = (- 1, - 1 + 3, - 2 - 3) = (- 1, 2, - 5) .

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

(b) By Theorem 3.4.9, $ker 𝑇_{𝐴}$ is spanned by the basic solutions (Definition 3.4.8), one for each free column, read off from $rref (𝐴)$ : $𝐬_{1} = (- 2, 1, 0, 0)$ and $𝐬_{2} = (1, 0, - 3, 1)$ . As a check, $𝐴 𝐬_{1} =$ $- 2 𝐚_{1} +$ $𝐚_{2} =$ $𝟎$ and $𝐴 𝐬_{2} =$ $𝐚_{1} -$ $3 𝐚_{3} +$ $𝐚_{4} =$ $𝟎$ .

By (a), every column of $𝐴$ is a combination of $𝐚_{1}$ and $𝐚_{3}$ , so $im 𝑇_{𝐴} =$ $span (𝐚_{1}, 𝐚_{3})$ (Proposition 3.1.8(a)). A vector $𝐲$ lies in it if and only if $𝐲 =$ $𝑠 (1, 1, 2) +$ $𝑡 (0, 1, - 1) =$ $(𝑠, 𝑠 + 𝑡, 2 𝑠 - 𝑡)$ for some $𝑠, 𝑡$ . Such $𝑠, 𝑡$ must be $𝑠 = 𝑦_{1}$ and $𝑡 = 𝑦_{2} - 𝑦_{1}$ , and then the third entry is $2 𝑦_{1} -$ $(𝑦_{2} - 𝑦_{1}) =$ $3 𝑦_{1} -$ $𝑦_{2}$ . So $im 𝑇_{𝐴} =$ ${𝐲 \in ℝ^{3} | 𝑦_{3} = 3 𝑦_{1} - 𝑦_{2}}$ .

Exercise 3.6.8.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and let $𝐻 \in 𝐹^{𝑛 \times 𝑛}$ be invertible. Decide which of the following are always the same for $𝐴$ and for $𝐴 𝐻$ , with a proof or a counterexample.

(a)The image $im 𝑇_{𝐴}$ .
(b)The kernel $ker 𝑇_{𝐴}$ .
(c)The set of row vectors $𝐳 \in 𝐹^{1 \times 𝑚}$ with $𝐳 𝐴 = 𝟎$ (the relations among the rows).
(d)The reduced row echelon form.
(e)The rank.
(f)Whether there is a left inverse.

Solution.

Uses. Proposition 3.2.30 (Column operations preserve the image), Non-example 3.2.31 (Column operations change the kernel), Corollary 3.2.23 (Row equivalent matrices have the same kernel), Proposition 2.4.23 (Transpose of a product), Exercise 3.5.41, Definition 2.5.1 (Left inverse)

Techniques. Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. (a) and (b) are in Section 3.2.5. For (c), transpose:

𝐳 𝐴 = 𝟎

says

𝐴^{𝖳} 𝐳^{𝖳} = 𝟎

. What is

{(𝐴 𝐻)}^{𝖳}

Hint 2. For (d), try

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

and a swap. For (f), if

𝐶 𝐴 = 𝐼_{𝑛}

, find a left inverse of

𝐴 𝐻

Sketch. (a) Same, Proposition 3.2.30. (b) Not always:

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

and

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

. (c) Same:

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

is a row operation applied to

𝐴^{𝖳}

, which keeps the kernel; or directly,

𝐳 𝐴 𝐻 = 𝟎 \Leftrightarrow 𝐳 𝐴 = 𝟎

. (d) Not always:

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

and

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

. (e) Same, by Exercise 3.5.41(c). (f) Same:

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

𝐼_{𝑛}

Since $𝐴 = (𝐴 𝐻) 𝐻^{- 1}$ and $𝐻^{- 1}$ is invertible, a property that passes from $𝐴$ to $𝐴 𝐻$ for every invertible $𝐻$ also passes back from $𝐴 𝐻$ to $𝐴$ . So in each “same” case it suffices to show one direction.

(a) Always the same, by Proposition 3.2.30.

(b) Not always. For $𝐴 = (\begin{matrix} 1 & 1 \end{matrix})$ and $𝐻 = 𝐸_{1, - 1, 2}$ (which adds $- 1$ times column $2$ to column $1$ ), $𝐴 𝐻 = (\begin{matrix} 0 & 1 \end{matrix})$ , and the kernels are $span ((1, - 1))$ and $span ((1, 0))$ (Non-example 3.2.31).

(c) Always the same. Transposing, $𝐳 𝐴 = 𝟎$ says $𝐴^{𝖳} 𝐳^{𝖳} = 𝟎$ , that is, $𝐳^{𝖳} \in ker 𝑇_{𝐴^{𝖳}}$ . By Proposition 2.4.23, ${(𝐴 𝐻)}^{𝖳} = 𝐻^{𝖳} 𝐴^{𝖳}$ , and $𝐻^{𝖳}$ is invertible, with inverse ${(𝐻^{- 1})}^{𝖳}$ . So by Corollary 3.2.23, $ker 𝑇_{{(𝐴 𝐻)}^{𝖳}} =$ $ker 𝑇_{𝐻^{𝖳} 𝐴^{𝖳}} =$ $ker 𝑇_{𝐴^{𝖳}}$ . (Directly: if $𝐳 𝐴 = 𝟎$ then $𝐳 𝐴 𝐻 = 𝟎$ , and the converse follows by multiplying on the right by $𝐻^{- 1}$ .) This is Corollary 3.2.23 seen in the mirror of Technique 3.2.27.

(d) Not always. $𝐴 = (\begin{matrix} 0 & 1 \end{matrix})$ is in RREF, and with $𝐻 = 𝐸_{12}$ , $𝐴 𝐻 = (\begin{matrix} 1 & 0 \end{matrix})$ is also in RREF. They are different matrices, so their reduced forms differ (and so do their pivot columns).

(e) Always the same, by Exercise 3.5.41(c).

(f) Always the same. If $𝐶 𝐴 = 𝐼_{𝑛}$ , then $(𝐻^{- 1} 𝐶) (𝐴 𝐻) =$ $𝐻^{- 1} (𝐶 𝐴) 𝐻 =$ $𝐻^{- 1} 𝐻 =$ $𝐼_{𝑛}$ , so $𝐻^{- 1} 𝐶$ is a left inverse of $𝐴 𝐻$ .

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

(a)Show that $ker 𝑇_{𝐴} \subseteq ker 𝑇_{𝐵}$ if and only if $𝐵 = 𝑋 𝐴$ for some $𝑋 \in 𝐹^{𝑝 \times 𝑚}$ .
(b)Deduce that $ker 𝑇_{𝐴} \subseteq ker 𝑇_{𝐵}$ if and only if every row of $𝐵$ is a linear combination of the rows of $𝐴$ .

Solution.

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Corollary 3.2.23 (Row equivalent matrices have the same kernel), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.3.8 (Matrix–vector product), Definition 2.4.1 (Matrix product)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. One direction is one line. For the other, first treat the case where

𝐴 = 𝑅

is in RREF, then use

𝑅 = 𝐺 𝐴

Hint 2. If

𝐴 = 𝑅

is in RREF with pivot columns

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

, guess

𝑌

with

𝑌 𝑅 = 𝐵

from the pivot columns:

𝑅 𝐞_{𝑝_{𝑠}} = 𝐞_{𝑠}

, so

𝑌

must send

𝐞_{𝑠}

to column

𝑝_{𝑠}

𝐵

Hint 3. For a free column

𝑗

, the relation

𝐫_{𝑗} =

\sum_{𝑠} 𝑟_{𝑠 𝑗} 𝐫_{𝑝_{𝑠}}

among the columns of

𝑅

is a vector of

ker 𝑇_{𝑅}

. Transfer it to

𝐵

Sketch. If

𝐵 = 𝑋 𝐴

and

𝐴 𝐱 = 𝟎

, then

𝐵 𝐱 = 𝟎

. Conversely, let

𝑅 = 𝐺 𝐴 = rref (𝐴)

, so

ker 𝑇_{𝑅} =

ker 𝑇_{𝐴} \subseteq

ker 𝑇_{𝐵}

. Let

𝑌

have column

𝑠

equal to column

𝑝_{𝑠}

𝐵

for

𝑠 \leq 𝑟

and

𝟎

for

𝑠 > 𝑟

. Every column of

𝑅

𝐫_{𝑗} =

\sum_{𝑠 \leq 𝑟} 𝑟_{𝑠 𝑗} 𝐞_{𝑠}

, and the relation

𝐫_{𝑗} =

\sum_{𝑠} 𝑟_{𝑠 𝑗} 𝐫_{𝑝_{𝑠}}

lies in

ker 𝑇_{𝑅}

, so it holds in

𝐵

𝐛_{𝑗} =

\sum_{𝑠} 𝑟_{𝑠 𝑗} 𝐛_{𝑝_{𝑠}} =

𝑌 𝐫_{𝑗}

. Hence

𝑌 𝑅 = 𝐵

, and

𝑋 = 𝑌 𝐺

works. (b) Row

𝑘

𝑋 𝐴

is the combination of the rows of

𝐴

with coefficients from row

𝑘

𝑋

(a) Suppose $𝐵 = 𝑋 𝐴$ . If $𝐴 𝐱 = 𝟎$ , then $𝐵 𝐱 = 𝑋 (𝐴 𝐱) = 𝟎$ . So $ker 𝑇_{𝐴} \subseteq ker 𝑇_{𝐵}$ .

Conversely, suppose $ker 𝑇_{𝐴} \subseteq ker 𝑇_{𝐵}$ . By Theorem 3.3.10, $𝑅 = rref (𝐴) = 𝐺 𝐴$ for an invertible $𝐺$ , and $ker 𝑇_{𝑅} = ker 𝑇_{𝐴}$ (Corollary 3.2.23), so $ker 𝑇_{𝑅} \subseteq ker 𝑇_{𝐵}$ . Let $𝑝_{1} < \dots < 𝑝_{𝑟}$ be the pivot columns, write $𝐫_{𝑗}$ and $𝐛_{𝑗}$ for the columns of $𝑅$ and $𝐵$ , and let $𝑌 \in 𝐹^{𝑝 \times 𝑚}$ be the matrix whose column $𝑠$ is $𝐛_{𝑝_{𝑠}}$ for $𝑠 \leq 𝑟$ and $𝟎$ for $𝑠 > 𝑟$ . We show $𝑌 𝑅 = 𝐵$ , column by column.

Fix $𝑗$ . By Lemma 3.3.16(a) (with $𝑠 = 𝑟$ ), $𝐫_{𝑗} =$ $\sum_{𝑠 = 1}^{𝑟} 𝑟_{𝑠 𝑗} 𝐞_{𝑠}$ , so by Definition 2.3.8,

𝑌 𝐫_{𝑗} = \sum_{𝑠 = 1}^{𝑟} 𝑟_{𝑠 𝑗} 𝑌 𝐞_{𝑠} = \sum_{𝑠 = 1}^{𝑟} 𝑟_{𝑠 𝑗} 𝐛_{𝑝_{𝑠}} .

On the other hand, $𝐫_{𝑝_{𝑠}} = 𝐞_{𝑠}$ (Lemma 3.3.16(b)), so $𝐫_{𝑗} =$ $\sum_{𝑠 = 1}^{𝑟} 𝑟_{𝑠 𝑗} 𝐫_{𝑝_{𝑠}}$ . This says that the vector

𝐱 = 𝐞_{𝑗} - \sum_{𝑠 = 1}^{𝑟} 𝑟_{𝑠 𝑗} 𝐞_{𝑝_{𝑠}}

satisfies $𝑅 𝐱 = 𝟎$ . (If $𝑗 = 𝑝_{𝑡}$ is itself a pivot column, then $𝑟_{𝑠 𝑗} = 0$ for $𝑠 \neq 𝑡$ and $𝑟_{𝑡 𝑗} = 1$ , so $𝐱 = 𝟎$ , and the argument still works.) Hence $𝐱 \in ker 𝑇_{𝐵}$ , that is, $𝐛_{𝑗} =$ $\sum_{𝑠} 𝑟_{𝑠 𝑗} 𝐛_{𝑝_{𝑠}} =$ $𝑌 𝐫_{𝑗}$ . So the columns of $𝑌 𝑅$ are those of $𝐵$ , and $𝑌 𝑅 = 𝐵$ (Definition 2.4.1). With $𝑋 = 𝑌 𝐺$ , we get $𝑋 𝐴 =$ $𝑌 (𝐺 𝐴) =$ $𝑌 𝑅 =$ $𝐵$ , as desired.

(b) By the row description of a product (Definition 2.4.1, as in the second proof of Proposition 3.2.7), row $𝑘$ of $𝑋 𝐴$ is $𝑥_{𝑘 1}$ times row $1$ of $𝐴$ , plus $\dots$ , plus $𝑥_{𝑘 𝑚}$ times row $𝑚$ of $𝐴$ . So “ $𝐵 = 𝑋 𝐴$ for some $𝑋$ ” says exactly that every row of $𝐵$ is a linear combination of the rows of $𝐴$ , and (b) is a restatement of (a).

If $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ , then (b) applies in both directions, so $𝐴$ and $𝐵$ have the same row space; this generalizes one half of Exercise 3.3.50(b) to matrices with different numbers of rows. The proof of (a) is the second proof of Theorem 3.3.17 once more: it used only relations among the columns.

Exercise 3.6.10.standard For

𝑋 =

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

𝐹^{2 \times 2}

, let

𝐷 (𝑋) = 𝑎 𝑑 - 𝑏 𝑐

. Prove that

𝐷 (𝑋 𝑌) =

𝐷 (𝑋) 𝐷 (𝑌)

for all

𝑋, 𝑌 \in 𝐹^{2 \times 2}

, by reducing to elementary matrices: first for invertible

𝑋

, then separately for

𝑋

that are not invertible. You may use Exercise 3.2.42.

Solution.

Uses. Exercise 3.2.42, Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Theorem 3.3.23 (Invertibility and RREF), Corollary 3.4.20 (Square systems), Proposition 3.3.8 (Properties of the output), Proposition 3.2.10 (Inverses of elementary matrices)

Techniques. Reduce to elementary matrices (Technique 5.4.6), Reduce to RREF (Technique 3.3.22)

Hint 1. By Exercise 3.2.42,

𝐷 (𝐸 𝑌) =

𝐷 (𝐸) 𝐷 (𝑌)

for every elementary

𝐸

and every

𝑌

: check that

𝐷 (𝐸)

1

- 1

, or

𝑠

for the three types.

Hint 2. If

𝑋 = 𝐸_{1} \dots 𝐸_{𝑡}

, apply the previous hint

𝑡

times, once to

𝑋 𝑌

and once to

𝑋 = 𝑋 𝐼_{2}

Hint 3. If

𝑋

is not invertible, write

𝑋 = 𝐺^{- 1} 𝑅

with

𝑅 = rref (𝑋) \neq 𝐼_{2}

. What is the second row of

𝑅

, and of

𝑅 𝑌

Sketch. For elementary

𝐸

𝐷 (𝐸 𝑌) =

𝐷 (𝐸) 𝐷 (𝑌)

: the factors

1

- 1

𝑠

of Exercise 3.2.42 are

𝐷 (𝐸)

. For

𝑋 = 𝐸_{1} \dots 𝐸_{𝑡}

, induction gives

𝐷 (𝑋 𝑌) =

𝐷 (𝐸_{1}) \dots 𝐷 (𝐸_{𝑡}) 𝐷 (𝑌)

, and with

𝑌 = 𝐼_{2}

𝐷 (𝑋) =

𝐷 (𝐸_{1}) \dots 𝐷 (𝐸_{𝑡})

. If

𝑋

is not invertible,

𝑋 = 𝑃 𝑅

with

𝑃 = 𝐺^{- 1}

a product of elementary matrices and

𝑅 = rref (𝑋)

having zero second row; then

𝐷 (𝑋 𝑌) =

𝐷 (𝑃) 𝐷 (𝑅 𝑌) =

0

and

𝐷 (𝑋) =

𝐷 (𝑃) 𝐷 (𝑅) =

0

Step 1: elementary matrices. By Exercise 3.2.42, for every $𝑌 \in 𝐹^{2 \times 2}$ , $𝐷 (𝐸 𝑌) = 𝐷 (𝑌)$ if $𝐸$ has type 3, $𝐷 (𝐸_{12} 𝑌) =$ $- 𝐷 (𝑌)$ , and $𝐷 (𝐸_{𝑖 𝑠} 𝑌) =$ $𝑠 𝐷 (𝑌)$ . Directly from the definition, $𝐷 (𝐸) = 1$ for $𝐸 = (\begin{matrix} 1 & 0 \\ 𝑡 & 1 \end{matrix})$ or $(\begin{matrix} 1 & 𝑡 \\ 0 & 1 \end{matrix})$ , $𝐷 (𝐸_{12}) =$ $0 \cdot$ $0 -$ $1 \cdot$ $1 =$ $- 1$ , and $𝐷 (𝐸_{1 𝑠}) =$ $𝐷 (𝐸_{2 𝑠}) =$ $𝑠$ . So in all cases

𝐷 (𝐸 𝑌) = 𝐷 (𝐸) 𝐷 (𝑌) for every elementary 𝐸 and every 𝑌 .

(3.6.1)

Step 2: invertible $𝑋$ . By Theorem 3.5.19, $𝑋 = 𝐸_{1} 𝐸_{2} \dots 𝐸_{𝑡}$ with each $𝐸_{𝑖}$ elementary. Applying (3.6.1) $𝑡$ times,

𝐷 (𝑋 𝑌) = 𝐷 (𝐸_{1} (𝐸_{2} \dots 𝐸_{𝑡} 𝑌)) = 𝐷 (𝐸_{1}) 𝐷 (𝐸_{2} \dots 𝐸_{𝑡} 𝑌) = \dots = 𝐷 (𝐸_{1}) \dots 𝐷 (𝐸_{𝑡}) 𝐷 (𝑌) .

With $𝑌 = 𝐼_{2}$ , and $𝐷 (𝐼_{2}) = 1$ , this gives $𝐷 (𝑋) =$ $𝐷 (𝐸_{1}) \dots 𝐷 (𝐸_{𝑡})$ . Hence $𝐷 (𝑋 𝑌) =$ $𝐷 (𝑋) 𝐷 (𝑌)$ .

Step 3: $𝑋$ not invertible. Let $𝑅 = rref (𝑋) = 𝐺 𝑋$ with $𝐺$ a product of elementary matrices (Theorem 3.3.10). Since $𝑋$ is not invertible, $𝑅 \neq 𝐼_{2}$ (Theorem 3.3.23). A $2 \times 2$ matrix in RREF with two pivots is $𝐼_{2}$ (Corollary 3.4.20, (i) $\Leftrightarrow$ (iii)), so $𝑅$ has at most one pivot and its second row is zero (Proposition 3.3.8(a)). Then the second row of $𝑅 𝑌$ is zero as well (row $2$ of $𝑅 𝑌$ is row $2$ of $𝑅$ times $𝑌$ ), so $𝐷 (𝑅) = 0$ and $𝐷 (𝑅 𝑌) = 0$ , since a matrix with zero second row has $𝑐 = 𝑑 = 0$ . Now $𝑃 = 𝐺^{- 1}$ is a product of elementary matrices (Proposition 3.2.10), and $𝑋 = 𝑃 𝑅$ , so Step 2 applied to $𝑃$ gives

𝐷 (𝑋 𝑌) = 𝐷 (𝑃 (𝑅 𝑌)) = 𝐷 (𝑃) 𝐷 (𝑅 𝑌) = 0, 𝐷 (𝑋) = 𝐷 (𝑃 𝑅) = 𝐷 (𝑃) 𝐷 (𝑅) = 0 .

So $𝐷 (𝑋 𝑌) =$ $0 =$ $𝐷 (𝑋) 𝐷 (𝑌)$ .

Step 3 is the part that is easy to forget, since a matrix that is not invertible is not a product of elementary matrices at all. In Section 5.4 the same strategy (elementary matrices, then invertible matrices, then a separate argument for the rest) proves $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ for every $𝑛$ (Theorem 5.4.10).

Exercise 3.6.11.standard Start with a real $𝑚 \times 𝑛$ matrix. A move chooses a row or a column whose entries have a negative sum and multiplies every entry of it by $- 1$ .

(a)Show that every sequence of moves is finite, whatever choices are made.
(b)Deduce that some finite sequence of moves produces a matrix all of whose row sums and column sums are nonnegative.
(c)Express the final matrix as $𝐷_{1} 𝐴 𝐷_{2}$ , where $𝐴$ is the starting matrix and $𝐷_{1}$ , $𝐷_{2}$ are products of elementary matrices of one type.

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.28 (Column operations are right multiplications)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Look for a quantity that every move increases. What happens to the sum of all entries when a row with sum

𝑠 < 0

is negated?

Hint 2. An increasing quantity proves termination only if it can take finitely many values. Which matrices can occur? Find an invariant relating each entry to the starting entry.

Sketch. Invariant: every entry is

\pm

the corresponding starting entry, so at most

2^{𝑚 𝑛}

matrices can occur. Monovariant: negating a row or column with sum

𝑠 < 0

changes the total sum

𝑆

- 2 𝑠 > 0

. So

𝑆

strictly increases, no matrix occurs twice, and there are fewer than

2^{𝑚 𝑛}

moves. When no move is possible, all row and column sums are

\geq 0

. Each move is left multiplication by

𝐸_{𝑖, - 1}

or right multiplication by

𝐸_{𝑗, - 1}

(a) Let $𝐴$ be the starting matrix and $𝑀$ the current one.

Invariant. Every entry of $𝑀$ is $\pm$ the corresponding entry of $𝐴$ . This holds at the start, and a move multiplies some entries by $- 1$ , which keeps it true. So $𝑀$ is one of at most $2^{𝑚 𝑛}$ matrices (two choices of sign for each entry).

Monovariant. Let $𝑆 (𝑀)$ be the sum of all entries of $𝑀$ . If a move negates a row or column whose entries sum to $𝑠 < 0$ , the entries of that line now sum to $- 𝑠$ , and no other entry changes, so $𝑆$ changes by $- 𝑠 - 𝑠 = - 2 𝑠 > 0$ . So $𝑆$ strictly increases with every move.

In a sequence of moves $𝑀_{0} = 𝐴, 𝑀_{1}, 𝑀_{2}, \dots$ , the values $𝑆 (𝑀_{0}) <$ $𝑆 (𝑀_{1}) <$ $\dots$ are distinct, so the matrices $𝑀_{0}, 𝑀_{1}, \dots$ are distinct. By the invariant they come from a set of at most $2^{𝑚 𝑛}$ matrices, so the sequence has at most $2^{𝑚 𝑛}$ terms, that is, fewer than $2^{𝑚 𝑛}$ moves.

(b) Make moves as long as one is possible. By (a) this stops, and it stops exactly when no row and no column has a negative sum.

(c) Negating row $𝑖$ is left multiplication by $𝐸_{𝑖, - 1}$ (Proposition 3.2.7), and negating column $𝑗$ is right multiplication by the $𝑛 \times 𝑛$ matrix $𝐸_{𝑗, - 1}$ (Proposition 3.2.28). Since $(𝐸 𝑋) 𝐸^{'} =$ $𝐸 (𝑋 𝐸^{'})$ , the final matrix is $𝐷_{1} 𝐴 𝐷_{2}$ , where $𝐷_{1}$ is the product of the row negations (the last one leftmost) and $𝐷_{2}$ the product of the column negations (the first one leftmost). Both are diagonal with entries $\pm 1$ , and they are products of type 2 elementary matrices.

The proof follows the two halves of Technique 3.3.5. The monovariant alone would not do: an increasing real number can increase forever. The invariant supplies the finiteness.

Exercise 3.6.12.standard

(a)Find all $𝑝 \in {ℚ [𝑥]}_{\leq 4}$ such that $𝑝 (𝑡 + 1) -$ $𝑝 (𝑡) =$ $𝑡^{3}$ for every $𝑡 \in ℚ$ .
(b)Deduce that $0^{3} +$ $1^{3} +$ $\dots +$ ${(𝑁 - 1)}^{3} =$ ${(𝑁 (𝑁 - 1) / 2)}^{2}$ for every integer $𝑁 \geq 1$ .

Solution.

Uses. Definition 1.2.17 (Evaluation), Lemma 3.4.23 (Too many roots), Proposition 3.1.19 (Solution sets are translates of the kernel)

Techniques. Undetermined coefficients (Technique 3.1.9), Particular plus homogeneous (Technique 3.1.18)

Hint 1. Write

𝑝 =

𝑎_{0} +

𝑎_{1} 𝑥 +

\dots +

𝑎_{4} 𝑥^{4}

and expand

{(𝑡 + 1)}^{𝑘} - 𝑡^{𝑘}

for

𝑘 = 1, \dots, 4

. The difference

𝑝 (𝑡 + 1) - 𝑝 (𝑡)

is then a polynomial expression of degree at most

3

𝑡

Hint 2. A polynomial of degree at most

3

that vanishes at every

𝑡 \in ℚ

is the zero polynomial (Lemma 3.4.23). So you may compare coefficients: four linear equations in

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

Hint 3. The system is triangular. What does

𝑎_{0}

do? For (b), sum

𝑝 (𝑘 + 1) - 𝑝 (𝑘)

over

𝑘 = 0, \dots, 𝑁 - 1

Sketch. The difference is

(𝑎_{1} + 𝑎_{2} + 𝑎_{3} + 𝑎_{4}) +

(2 𝑎_{2} + 3 𝑎_{3} + 4 𝑎_{4}) 𝑡 +

(3 𝑎_{3} + 6 𝑎_{4}) 𝑡^{2} +

4 𝑎_{4} 𝑡^{3}

. Comparing with

𝑡^{3}

𝑎_{4} = 1 / 4

𝑎_{3} = - 1 / 2

𝑎_{2} = 1 / 4

𝑎_{1} = 0

, and

𝑎_{0}

is free. So

𝑝 =

{(𝑥 (𝑥 - 1) / 2)}^{2} +

𝑎_{0}

: a particular solution plus the constants, which are the homogeneous solutions. Telescoping gives (b).

(a) Write $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2} +$ $𝑎_{3} 𝑥^{3} +$ $𝑎_{4} 𝑥^{4}$ . By the binomial theorem,

\begin{aligned} (𝑡 + 1) - 𝑡 = 1, & {(𝑡 + 1)}^{2} - 𝑡^{2} = 2 𝑡 + 1, \\ {(𝑡 + 1)}^{3} - 𝑡^{3} = 3 𝑡^{2} + 3 𝑡 + 1, & {(𝑡 + 1)}^{4} - 𝑡^{4} = 4 𝑡^{3} + 6 𝑡^{2} + 4 𝑡 + 1, \end{aligned}

so for every $𝑡 \in ℚ$ (Definition 1.2.17),

𝑝 (𝑡 + 1) - 𝑝 (𝑡) = 𝑐_{0} + 𝑐_{1} 𝑡 + 𝑐_{2} 𝑡^{2} + 𝑐_{3} 𝑡^{3},

where

𝑐_{0} = 𝑎_{1} + 𝑎_{2} + 𝑎_{3} + 𝑎_{4}, 𝑐_{1} = 2 𝑎_{2} + 3 𝑎_{3} + 4 𝑎_{4}, 𝑐_{2} = 3 𝑎_{3} + 6 𝑎_{4}, 𝑐_{3} = 4 𝑎_{4} .

The condition is that $𝑞 =$ $(𝑐_{0} - 0) +$ $𝑐_{1} 𝑥 +$ $𝑐_{2} 𝑥^{2} +$ $(𝑐_{3} - 1) 𝑥^{3} \in$ ${ℚ [𝑥]}_{\leq 3}$ satisfies $𝑞 (𝑡) = 0$ for every $𝑡 \in ℚ$ . If $𝑞$ vanishes at all of $ℚ$ , it vanishes at the four distinct points $0, 1, 2, 3$ , so $𝑞 = 𝟎$ by Lemma 3.4.23; conversely, $𝑞 = 𝟎$ certainly vanishes everywhere. So the condition is the linear system

𝑎_{1} + 𝑎_{2} + 𝑎_{3} + 𝑎_{4} = 0, 2 𝑎_{2} + 3 𝑎_{3} + 4 𝑎_{4} = 0, 3 𝑎_{3} + 6 𝑎_{4} = 0, 4 𝑎_{4} = 1

in the unknowns $𝑎_{0}, \dots, 𝑎_{4}$ , in which $𝑎_{0}$ does not occur. Solving from the bottom: $𝑎_{4} = 1 / 4$ , $𝑎_{3} = - 2 𝑎_{4} = - 1 / 2$ , $2 𝑎_{2} =$ $- 3 𝑎_{3} -$ $4 𝑎_{4} =$ $3 / 2 -$ $1 =$ $1 / 2$ , so $𝑎_{2} = 1 / 4$ , and $𝑎_{1} =$ $- (𝑎_{2} + 𝑎_{3} + 𝑎_{4}) =$ $0$ . So the solutions are

𝑝 = 𝑎_{0} + \frac{1}{4} 𝑥^{2} - \frac{1}{2} 𝑥^{3} + \frac{1}{4} 𝑥^{4} (𝑎_{0} \in ℚ),

and $\frac{1}{4} 𝑥^{2} - \frac{1}{2} 𝑥^{3} + \frac{1}{4} 𝑥^{4}$ is the polynomial whose value at $𝑡$ is ${(𝑡 (𝑡 - 1) / 2)}^{2}$ , since $𝑡^{2} {(𝑡 - 1)}^{2} =$ $𝑡^{4} -$ $2 𝑡^{3} +$ $𝑡^{2}$ . In the language of Proposition 3.1.19, applied to the linear map $𝑝 \mapsto$ ${(𝑝 (𝑡 + 1) - 𝑝 (𝑡))}_{𝑡}$ , this is a particular solution plus the homogeneous solutions, which are the constants: the same triangular system with right-hand side $0$ forces $𝑎_{1} = \dots = 𝑎_{4} = 0$ .

(b) Let $𝑝$ be the solution with $𝑎_{0} = 0$ , so $𝑝 (𝑡) =$ ${(𝑡 (𝑡 - 1) / 2)}^{2}$ . Summing $𝑝 (𝑘 + 1) -$ $𝑝 (𝑘) =$ $𝑘^{3}$ over $𝑘 = 0, \dots, 𝑁 - 1$ , the left side telescopes:

0^{3} + 1^{3} + \dots + {(𝑁 - 1)}^{3} = 𝑝 (𝑁) - 𝑝 (0) = {(𝑁 (𝑁 - 1) / 2)}^{2} .

The method needs a field in which comparing coefficients is allowed, which used four distinct points $0, 1, 2, 3$ , and in which $2$ , $3$ , $4$ are nonzero, for the triangular solve. Over $𝔽_{𝑝}$ with $𝑝 \geq 5$ both hold. Over $𝔽_{2}$ and $𝔽_{3}$ both fail: for instance $𝑥^{3} - 𝑥$ vanishes at every point of $𝔽_{3}$ , so a polynomial identity on the field no longer determines the coefficients.

Exercise 3.6.13.standard Let $𝑛 \geq 3$ . Read indices modulo $𝑛$ , so that $𝑥_{0} = 𝑥_{𝑛}$ and $𝑥_{𝑛 + 1} = 𝑥_{1}$ .

(a)Show that for every $𝐲 \in ℝ^{𝑛}$ there is exactly one $𝐱 \in ℝ^{𝑛}$ with
$4 𝑥_{𝑖} - 𝑥_{𝑖 - 1} - 𝑥_{𝑖 + 1} = 𝑦_{𝑖} (𝑖 = 1, \dots, 𝑛) .$
(b)Now replace $4$ by $2$ . Show that the system $2 𝑥_{𝑖} -$ $𝑥_{𝑖 - 1} -$ $𝑥_{𝑖 + 1} =$ $𝑦_{𝑖}$ ( $𝑖 = 1, \dots, 𝑛$ ) has a solution if and only if $𝑦_{1} + \dots + 𝑦_{𝑛} = 0$ . You may use Exercise 3.5.37.

Solution.

Uses. Corollary 3.4.20 (Square systems), Exercise 3.5.37, Proposition 2.4.23 (Transpose of a product)

Techniques. Uniqueness gives existence (Technique 3.4.21), Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. The system in (a) is square. By Corollary 3.4.20 it suffices to show that

4 𝑥_{𝑖} =

𝑥_{𝑖 - 1} +

𝑥_{𝑖 + 1}

for all

𝑖

forces

𝐱 = 𝟎

Hint 2. Choose

𝑘

with

| 𝑥_{𝑘} |

as large as possible, and compare

4 | 𝑥_{𝑘} |

with

| 𝑥_{𝑘 - 1} | + | 𝑥_{𝑘 + 1} |

Hint 3. In (b), the vector

(1, \dots, 1)

is a homogeneous solution. Show it spans the homogeneous solutions (look at a largest entry again), note that the matrix is symmetric, and apply Exercise 3.5.37.

Sketch. (a) For a homogeneous solution, take

𝑘

with

| 𝑥_{𝑘} |

maximal:

4 | 𝑥_{𝑘} | \leq

| 𝑥_{𝑘 - 1} | +

| 𝑥_{𝑘 + 1} | \leq

2 | 𝑥_{𝑘} |

, so

𝑥_{𝑘} = 0

and

𝐱 = 𝟎

; the system is square, so Corollary 3.4.20 gives existence and uniqueness. (b) Summing the equations gives

0 = \sum 𝑦_{𝑖}

, which is necessary. The homogeneous solutions are the constant vectors (at a largest entry

𝑥_{𝑘}

, both neighbors equal

𝑥_{𝑘}

; go around the cycle). The matrix

𝐿

is symmetric, so

𝐳^{𝖳} 𝐿 = 𝟎

iff

𝐿 𝐳 = 𝟎

iff

𝐳

is constant, and Exercise 3.5.37 says

𝐿 𝐱 = 𝐲

is solvable iff

𝐳^{𝖳} 𝐲 = 0

for those

𝐳

, that is, iff

\sum 𝑦_{𝑖} = 0

(a) This is a system of $𝑛$ equations in $𝑛$ unknowns, so by Corollary 3.4.20 ((iv) $\Rightarrow$ (vi)) it suffices to show that the homogeneous system has only the trivial solution. Let $𝐱$ satisfy $4 𝑥_{𝑖} =$ $𝑥_{𝑖 - 1} +$ $𝑥_{𝑖 + 1}$ for all $𝑖$ , and choose $𝑘$ with $| 𝑥_{𝑘} | \geq | 𝑥_{𝑖} |$ for all $𝑖$ (an extremal choice). Then

4 | 𝑥_{𝑘} | = | 𝑥_{𝑘 - 1} + 𝑥_{𝑘 + 1} | \leq | 𝑥_{𝑘 - 1} | + | 𝑥_{𝑘 + 1} | \leq 2 | 𝑥_{𝑘} |,

so $2 | 𝑥_{𝑘} | \leq 0$ and $𝑥_{𝑘} = 0$ . As $| 𝑥_{𝑘} |$ is the largest of the $| 𝑥_{𝑖} |$ , every $𝑥_{𝑖} = 0$ .

(b) Let $𝐿 \in ℝ^{𝑛 \times 𝑛}$ be the coefficient matrix: $2$ on the diagonal, $- 1$ in the positions $(𝑖, 𝑖 - 1)$ and $(𝑖, 𝑖 + 1)$ (modulo $𝑛$ ), and $0$ elsewhere. It is symmetric, $𝐿^{𝖳} = 𝐿$ , because $𝑗 = 𝑖 + 1$ exactly when $𝑖 = 𝑗 - 1$ . Let $𝟏 = (1, \dots, 1)$ .

Necessity. Each $𝑥_{𝑗}$ occurs in three equations, with total coefficient $2 - 1 - 1 = 0$ (in equation $𝑗$ with $2$ , and in equations $𝑗 - 1$ and $𝑗 + 1$ with $- 1$ ; these are three different equations since $𝑛 \geq 3$ ). So summing all equations gives $0 = 𝑦_{1} + \dots + 𝑦_{𝑛}$ , and a solution can exist only if $\sum 𝑦_{𝑖} = 0$ .

The homogeneous solutions are the constant vectors. Constant vectors are solutions, since $2 𝑐 - 𝑐 - 𝑐 = 0$ . Conversely, let $𝐿 𝐱 = 𝟎$ , and let $𝑥_{𝑘}$ be a largest entry. Then $2 𝑥_{𝑘} =$ $𝑥_{𝑘 - 1} +$ $𝑥_{𝑘 + 1}$ with $𝑥_{𝑘 - 1} \leq 𝑥_{𝑘}$ and $𝑥_{𝑘 + 1} \leq 𝑥_{𝑘}$ , which forces $𝑥_{𝑘 - 1} =$ $𝑥_{𝑘 + 1} =$ $𝑥_{𝑘}$ . So the neighbors of a largest entry are largest entries too, and going around the cycle, all entries equal $𝑥_{𝑘}$ . Thus $𝐿 𝐱 = 𝟎$ if and only if $𝐱 \in span (𝟏)$ .

Sufficiency. Suppose $\sum 𝑦_{𝑖} = 0$ but $𝐿 𝐱 = 𝐲$ has no solution. By Exercise 3.5.37 there is $𝐳$ with $𝐳^{𝖳} 𝐿 = 𝟎$ and $𝐳^{𝖳} 𝐲 \neq 0$ . Transposing (Proposition 2.4.23), $𝐿^{𝖳} 𝐳 = 𝐿 𝐳 = 𝟎$ , so $𝐳 = 𝑐 𝟏$ for some $𝑐$ , and then $𝐳^{𝖳} 𝐲 =$ $𝑐 (𝑦_{1} + \dots + 𝑦_{𝑛}) =$ $0$ , a contradiction.

So with $4$ the homogeneous system has only the trivial solution and every $𝐲$ is reached; with $2$ there is a homogeneous solution $𝟏$ , and in exchange one condition on $𝐲$ . For a square system the two failures come together, as Corollary 3.4.20 says they must.

Exercise 3.6.14.routine For $𝑝 =$ $𝑎 +$ $𝑏 𝑥 +$ $𝑐 𝑥^{2} \in$ ${ℝ [𝑥]}_{\leq 2}$ , write $𝑝^{'} = 𝑏 + 2 𝑐 𝑥$ . Find the error in the following argument, and decide for which $(𝑢, 𝑣, 𝑤) \in ℝ^{3}$ the conclusion holds.

Claim. For all $𝑢, 𝑣, 𝑤 \in ℝ$ there is exactly one $𝑝 \in {ℝ [𝑥]}_{\leq 2}$ with $𝑝 (0) = 𝑢$ , $𝑝 (1) = 𝑣$ , and $𝑝^{'} (1 / 2) = 𝑤$ .

Proof. The three conditions are linear equations in the three unknown coefficients of $𝑝$ . The system is square, so by Technique 3.4.21 it has exactly one solution.

Solution.

Uses. Corollary 3.4.20 (Square systems), Proposition 3.1.19 (Solution sets are translates of the kernel)

Techniques. Uniqueness gives existence (Technique 3.4.21)

Hint 1. Squareness only sets the technique up; its content is the homogeneous uniqueness. Check it: is there a nonzero

𝑝

with

𝑝 (0) =

𝑝 (1) =

𝑝^{'} (1 / 2) =

0

Hint 2. Compare

𝑝^{'} (1 / 2)

with

𝑝 (1) - 𝑝 (0)

for a general

𝑝

Sketch. The argument never proves that the homogeneous system has only the trivial solution, and it does not:

𝑥^{2} - 𝑥

is a nonzero solution. Since

𝑝^{'} (1 / 2) =

𝑏 +

𝑐 =

𝑝 (1) -

𝑝 (0)

for every

𝑝

, a solution exists only if

𝑤 = 𝑣 - 𝑢

, and then the solutions are

𝑢 +

(𝑣 - 𝑢) 𝑥 +

𝑡 (𝑥^{2} - 𝑥)

, infinitely many. So the claim fails for every

(𝑢, 𝑣, 𝑤)

The argument checks that the problem is linear and square, which is what makes Technique 3.4.21 applicable, and then skips the technique itself: the homogeneous problem must be shown to have only the trivial solution, and here it does not. For $𝑝 = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}$ , the homogeneous conditions are $𝑎 = 0$ , $𝑎 + 𝑏 + 𝑐 = 0$ , and $𝑏 + 𝑐 = 0$ , and $𝑝 = 𝑥^{2} - 𝑥$ (that is, $𝑎 = 0$ , $𝑏 = - 1$ , $𝑐 = 1$ ) satisfies all three.

In fact, for every $𝑝$ ,

𝑝 (1) - 𝑝 (0) = 𝑏 + 𝑐 = 𝑝^{'} (1 / 2) .

So a solution can exist only if $𝑤 = 𝑣 - 𝑢$ . If $𝑤 = 𝑣 - 𝑢$ , then $𝑢 + (𝑣 - 𝑢) 𝑥$ is a solution, and by Proposition 3.1.19 the solutions are $𝑢 +$ $(𝑣 - 𝑢) 𝑥 +$ $𝑡 (𝑥^{2} - 𝑥)$ for $𝑡 \in ℝ$ , since the homogeneous solutions are the multiples of $𝑥^{2} - 𝑥$ (the first two homogeneous equations give $𝑎 = 0$ and $𝑐 = - 𝑏$ , and the third is then automatic). So the conclusion “exactly one” holds for no $(𝑢, 𝑣, 𝑤)$ : there are no solutions when $𝑤 \neq 𝑣 - 𝑢$ and infinitely many when $𝑤 = 𝑣 - 𝑢$ . By Corollary 3.4.20 this had to be so once uniqueness failed.