1.7 Proof patterns · Matrix Theory

Most proofs in this chapter are short, and most of their steps were forced. Once a claim is written out with its definitions unpacked and its quantifiers in order, its shape usually decides the first move. This section sorts the chapter’s proofs by the question they answer. For each question it compares the moves that answer it, on examples from the chapter, and says when a move is the wrong tool. The exercises at the end practice one move at a time, and the chapter’s problem set (Problems for Chapter 1) mixes them.

1.7.1Showing that two sets are equal

The default is double containment (Technique 1.3.14), with each containment proved by chasing a generic element (Technique 1.3.13). The two halves are rarely alike. In Example 1.3.15, the containment $span ({ℒ︀}_{1}) \subseteq 𝑊$ was a computation that handled every linear combination at once, while $𝑊 \subseteq span ({ℒ︀}_{1})$ needed a linear combination built for each element of $𝑊$ . Expect one half to be a check and the other a construction, and look for the construction first, since that is where proofs get stuck.

When the sets carry structure, finitely many checks can replace a containment.

If both sets are spans, compare entries: $span (ℒ︀) = span (ℳ︀)$ exactly when each list lies in the span of the other (Corollary 1.3.19).
If one set is a subspace $𝑈$ , then $span (ℒ︀) \subseteq 𝑈$ as soon as the entries of $ℒ︀$ lie in $𝑈$ (Proposition 1.4.14(b)).
If one set is defined as the smallest subspace with some property, use the property instead of the elements, as in the proof of Corollary 1.4.17.

Example 1.7.1 (One equality, two ways). Let $𝑃 =$ ${𝐱 \in ℝ^{3} | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0}$ . Exercise 1.3.16 proved $span ((1, 0, - 1), (0, 1, - 1)) =$ $𝑃$ by chasing an element through each containment. With the structure in view, one half needs no computation: $𝑃$ is a subspace (Example 1.4.8) that contains $(1, 0, - 1)$ and $(0, 1, - 1)$ , so it contains their span by Proposition 1.4.14(b). The other half is the construction, and with the tools of this chapter it cannot be avoided. For $(𝑥, 𝑦, 𝑧) \in 𝑃$ we have $𝑧 = - 𝑥 - 𝑦$ , so

(𝑥, 𝑦, 𝑧) = 𝑥 (1, 0, - 1) + 𝑦 (0, 1, - 1) .

In the same way, Example 1.3.21 replaced both halves of Example 1.3.15 by two observations about entries.

Chasing elements is the wrong tool for showing that two sets differ. Then one element of one set outside the other is enough, and the way to find it is a property that every element of one set has. Every vector $(𝑎, 𝑎 + 𝑏, 𝑏)$ of $span ((1, 1, 0), (0, 1, 1))$ has middle coordinate equal to the sum of the other two, and $(1, 2, 3)$ does not (Example 1.3.8). For finite sets there is a third option: a containment together with equal sizes gives equality. Over a finite field this decides when a list is a basis of $𝐹^{𝑛}$ (Exercise 1.6.38). From Section 4.1 on, dimension plays the role of size over every field (Proposition 4.1.21).

Exercise 1.7.5 practices the choice between these tools, and Exercise 1.3.30 shows what is lost when one half is forgotten.

1.7.2Showing that something is unique

Every “the” in this chapter, such as the zero vector or the coordinate vector, rests on a uniqueness proof. There were two ways to give one.

The first is uniqueness via two candidates (Technique 1.1.8): take two candidates and show that they are equal, as for identities and inverses (Theorem 1.1.9, Proposition 1.2.27, Proposition 1.2.28). With vectors, the comparison is usually a subtraction, and the difference of two candidates solves the homogeneous version of the problem. Two representations of $𝐰$ differ by a representation of $𝟎$ , which is how (II) $\Rightarrow$ (I) of Theorem 1.5.5 went, and two solutions of $𝑎 𝐱 = 𝐰$ differ by a solution of $𝑎 𝐱 = 𝟎$ (Corollary 1.2.36). So uniqueness reduces to the statement that the homogeneous problem has only the zero solution, a question about one fixed vector. Section 3.1 builds on this reduction (Technique 3.1.18).

The second is to derive the formula: suppose $𝑥$ is a solution, deduce that it must equal a specific expression, and check that this expression is a solution. This proves existence and uniqueness at once, and it computes the object. Proposition 1.1.13 was proved this way.

Example 1.7.2 (A basis, two ways). Is $(1, 1), (1, - 1)$ a basis of $ℝ^{2}$ ? Following Proposition 1.6.2, we can check two things separately. Spanning needs coefficients for each $(𝑥, 𝑦)$ , which still have to be found (they turn out to be $(𝑥 + 𝑦) / 2$ and $(𝑥 - 𝑦) / 2$ ), and independence needs $𝑎 + 𝑏 = 𝑎 - 𝑏 = 0$ to force $𝑎 = 𝑏 = 0$ , which it does (add and subtract the equations). Deriving the formula instead: if $𝑎 (1, 1) +$ $𝑏 (1, - 1) =$ $(𝑥, 𝑦)$ , then $𝑎 + 𝑏 = 𝑥$ and $𝑎 - 𝑏 = 𝑦$ , so

𝑎 = \frac{𝑥 + 𝑦}{2}, 𝑏 = \frac{𝑥 - 𝑦}{2},

and these values are a solution. So every $(𝑥, 𝑦)$ has exactly one representation, and we have its coordinates as a bonus (Example 1.6.3). Both routes divide by $2$ , and both fail over $𝔽_{2}$ , where the list repeats an entry.

The formula is shorter here, but it needs equations that can be solved in general. For the polynomials of Exercise 1.6.6, no formula was needed: spanning came from Exercise 1.3.32 and independence from degrees (Proposition 1.5.24).

Before proving that something is unique, check that it is. The index $𝑗$ of Lemma 1.5.10 is not unique (Example 1.5.11), and a vector does not determine its coefficients with respect to a spanning list that is dependent (Exercise 1.6.31). Uniqueness also says nothing about existence: a list in which every vector has at most one representation need not span (Exercise 1.6.35). Practice: Exercise 1.7.6, Exercise 1.7.7, and Exercise 1.2.43.

1.7.3Showing that a list is independent, or dependent

Dependence is shown by a certificate: one nontrivial relation, which anyone can check by computing a single linear combination (Theorem 1.5.5). Independence is a statement about all relations, and the chapter proved it in several ways.

The test at zero. Assume $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ and solve for the coefficients (Example 1.5.6).
One entry at a time. Show that each entry lies outside the span of the entries before it (Corollary 1.5.13, Proposition 1.5.14). Usually some property is shared by the whole span of the earlier entries and fails for the new entry, such as having degree at most $𝑛$ .
An extreme term. Look at the largest degree (Proposition 1.5.24) or the fastest-growing function (Example 1.5.27, second proof), which nothing else in a relation can cancel.
Evaluation and operators, for functions: evaluate a relation at well-chosen points (Example 1.5.26), or apply an operation such as differentiation that eliminates terms (Example 1.5.27, first proof).
Transfer. Pass to coordinates (Proposition 1.6.20), apply the moves of Proposition 1.5.18, recognize the list as a sublist of a list already known to be independent (Corollary 1.5.17), or change the field: independence over $𝐹$ gives independence over a subfield (Proposition 1.5.20), and for lists of real vectors, independence over $ℝ$ gives independence over $ℂ$ (Proposition 1.5.21).

Example 1.7.3 (Three tools on one list). Let $𝑝_{1} = 1 + 𝑥$ , $𝑝_{2} = 𝑥 + 𝑥^{2}$ , and $𝑝_{3} = 1 + 𝑥^{2}$ in $𝐹 [𝑥]$ .

The test at zero. The combination $𝑎 𝑝_{1} +$ $𝑏 𝑝_{2} +$ $𝑐 𝑝_{3} =$ $(𝑎 + 𝑐) +$ $(𝑎 + 𝑏) 𝑥 +$ $(𝑏 + 𝑐) 𝑥^{2}$ is $𝟎$ exactly when $𝑎 +$ $𝑐 =$ $𝑎 +$ $𝑏 =$ $𝑏 +$ $𝑐 =$ $0$ . The first two equations give $𝑏 = 𝑐 = - 𝑎$ , and then the third reads $- (1 + 1) 𝑎 = 0$ . So if $1 + 1 \neq 0$ , the only relation is trivial and the list is independent; if $1 + 1 = 0$ , then $𝑎 = 𝑏 = 𝑐 = 1$ is a dependence relation.

One entry at a time. $𝑝_{1} \neq 𝟎$ . Every vector of $span (𝑝_{1})$ has degree at most $1$ , so $𝑝_{2} \notin span (𝑝_{1})$ . The vectors of $span (𝑝_{1}, 𝑝_{2})$ are $𝑎 +$ $(𝑎 + 𝑏) 𝑥 +$ $𝑏 𝑥^{2}$ , and this is $𝑝_{3}$ exactly when $𝑎 = 𝑏 = 1$ and $𝑎 + 𝑏 = 0$ , which is possible only when $1 + 1 = 0$ . Same answer, with more information: over $𝔽_{2}$ , $𝑝_{3}$ is the first entry in the span of the earlier ones, $𝑝_{3} = 𝑝_{1} + 𝑝_{2}$ .

An extreme term. Proposition 1.5.24 does not apply, since $𝑝_{2}$ and $𝑝_{3}$ both have degree $2$ . Its hypothesis is doing real work: the leading terms of $𝑝_{2}$ and $𝑝_{3}$ can cancel, and over $𝔽_{2}$ the relation $𝑝_{1} + 𝑝_{2} + 𝑝_{3} = 𝟎$ cancels them. When a tool’s hypothesis fails, fall back on the test at zero.

Two tempting shortcuts are invalid. For functions on an infinite set, evaluating at finitely many points can prove independence but not dependence, since a combination that vanishes at a few points need not vanish everywhere (Section 1.5.6). And a list in which no entry is a multiple of another can still be dependent (Exercise 1.5.16). Practice: Exercise 1.7.8, Exercise 1.7.9, and Exercise 1.7.12.

1.7.4Proving a statement about every list

Claims about lists of every length, or about linear combinations of every length, are proved by induction on the length of the list (Technique 1.6.9), usually with the empty list as the base case. The arithmetic of linear combinations (Lemma 1.3.9), (III) $\Rightarrow$ (II) of Theorem 1.4.3, and Proposition 1.6.19(c) split off the last term of a sum. Theorem 1.6.10 deletes a well-chosen entry.

That theorem has three proofs, and they are one idea in three forms: delete redundant entries until none is left. The induction deletes one entry and hands the shorter list to the inductive hypothesis. The extremal proof takes a shortest sublist with the same span and shows that the dependence lemma could not shorten it further. Sifting reads the list once, from left to right, and keeps exactly the entries that the earlier ones do not account for. When only existence is needed, the extremal form is the shortest. When something must be carried along from step to step, as the coefficients are in Proposition 1.6.19(c), the induction is the natural form. When the output itself matters, sifting is the one to use, because it produces a definite sublist; its kept entries return as pivot columns (Section 4.2).

Two things go wrong in inductions on length. The shorter list must satisfy the hypotheses of the statement: deleting the last entry of a spanning list need not leave a spanning list, which is why the entry to delete is supplied by Lemma 1.5.10 (Exercise 1.6.30). And the inductive step must work from the base case on, not only for long lists (Exercise 1.7.10). Finally, induction proves things about all finite lists, but it does not show that a process of adding vectors stops. Thinning a spanning list stops because its length drops at every step, while growing an independent list need not stop, and in $𝐹 [𝑥]$ it never does (Remark 1.6.26). Practice: Exercise 1.7.10 and Exercise 1.7.11.

1.7.5Proving a statement with “or”

Several results of the chapter conclude “ $𝑃$ or $𝑄$ ”, among them Proposition 1.1.17, Proposition 1.2.35, and Proposition 1.4.20, and each of these has a proof by the same move.

Technique 1.7.4 (Proving a disjunction). To prove “ $𝑃$ or $𝑄$ ”, assume that $𝑃$ fails and prove $𝑄$ . The failure of $𝑃$ is a hypothesis you can use, and it usually hands you an object: an inverse $𝑎^{- 1}$ when $𝑎 \neq 0$ , or a vector of $𝑈$ outside $𝑊$ when $𝑈 ⊈ 𝑊$ . If one alternative is easier to negate usefully, negate that one. The other route is the contrapositive: assume that both alternatives fail and derive the negation of the hypothesis (or a contradiction). It hands you two objects at once, which helps when the argument needs both.

Reach for it whenever a conclusion reads “ $\dots$ or $\dots$ ”. The canonical example is Proposition 1.4.20, which has one proof of each kind.

Used in 1 place

Exercise 1.7.13.

In Proposition 1.1.17 and Proposition 1.2.35, the conclusion is “ $𝑎 = 0$ or $\dots$ ”, and assuming $𝑎 \neq 0$ supplies $𝑎^{- 1}$ , which cancels $𝑎$ . In the first proof of Proposition 1.4.20, the failure of $𝑈 \subseteq 𝑊$ supplies one vector $𝐮 \in 𝑈$ outside $𝑊$ , and adding $𝐮$ to each vector of $𝑊$ pushes that vector into $𝑈$ . The second proof negates both alternatives and uses the two witnesses to rebuild the counterexample of the two axes.

The invalid version of this move is a case split on two objects at once: “ $𝐯$ lies in $𝑈$ or in $𝑊$ , and so does $𝐰$ , so $𝐯 + 𝐰$ lies in $𝑈$ or in $𝑊$ ”. The split forgets the mixed case, $𝐯 \in 𝑈$ and $𝐰 \in 𝑊$ , which is where the claim fails (Exercise 1.4.30). Practice: Exercise 1.7.13.

1.7.6Disproving a claim, and proving that no object exists

To disprove “every $𝑋$ has property $𝑃$ ”, one $𝑋$ without $𝑃$ suffices (Technique 1.4.18), and the smallest examples are the place to look (Technique 1.2.38): the zero space, $𝐹^{1}$ and $𝐹^{2}$ , lists of length one or two, and the field $𝔽_{2}$ . Most of the chapter’s counterexamples were of this size: $𝐯 = - 𝐯$ in $𝔽_{2}^{2}$ (Example 1.2.39), the scaling move of Corollary 1.3.20(d) with the scalar $- 2$ , which is $0$ in $𝔽_{2}$ (Example 1.3.22), the two axes of $ℝ^{2}$ (Non-example 1.4.13), and $𝑥^{2} = 1$ in $𝔽_{2}$ (Exercise 1.1.42). “Small” means the smallest case in which the claim says something. The claim that a list with no entry a multiple of another is independent is true for two vectors, so its counterexample needs three (Exercise 1.5.16).

Showing that no object of some kind exists is a different task, and one failure is not enough. In Example 1.2.25, each candidate operation on $ℝ^{2}$ was refuted by one instance of one failing axiom. But to show that no scalar multiplication makes $[0, 1)$ with addition modulo $1$ a real vector space (Example 1.2.40), testing candidates one at a time cannot finish. Instead we found a consequence of the axioms that involves only the addition, which is the part held fixed, and showed that this addition violates it. The same need to rule out every candidate appeared on a smaller scale in Non-example 1.2.21: to show that the line $𝑥 + 2 𝑦 = 2$ has no zero vector under the operations of $ℝ^{2}$ , it was not enough to note that $(0, 0)$ is not on the line; every candidate $𝐳$ had to be excluded. Practice: Exercise 1.7.15 and Exercise 1.7.14.

1.7.7Reading the chapter’s proofs

Most of the chapter’s proofs were found by reading the definitions slowly. Here is what to look at first.

The definitions and the quantifiers. Unpack every definition in the claim and keep the quantifiers in order. Then the shape is visible. “For all” calls for a generic element, “there exists” for a construction, “unique” for two candidates, and “or” for negating one alternative. For instance, independence says that every vector of the span has at most one representation. Its negation hands us a vector with two representations, and subtracting them gives a relation. That is the proof of (II) $\Rightarrow$ (I) in Theorem 1.5.5, found by negating the definition. The subspace criterion came from sorting (A1)–(A8) by their quantifiers: identities that hold for all vectors are inherited by any subset closed under the operations, and the existence statements (A3) and (A4) are where a subset can fail (the intuition before Theorem 1.4.3). The same sorting proved Proposition 1.1.33 and Proposition 1.2.19. When a fact has to connect two operations, list the axioms that mention both: distributivity for $0 𝑎 = 0$ (Proposition 1.1.15), and (A7) and (A8) for vectors.

The extreme choice. A dependence relation can be solved for any entry whose coefficient is nonzero. The dependence lemma wants only earlier entries on the other side, so the proof solves for the last entry with a nonzero coefficient (Lemma 1.5.10). Solving for the first one instead puts that entry in the span of the later entries (Exercise 1.7.8). The same move, a largest index or degree, runs Proposition 1.5.24 and the second proof in Example 1.5.27, and a shortest sublist runs the second proof of Theorem 1.6.10. Extremality is a hypothesis we get for free: “the largest $𝑗$ with $𝑎_{𝑗} \neq 0$ ” also says that every later coefficient is $0$ .

The degenerate cases. The empty list, the zero space, and the index $𝑗 = 1$ are where the conventions get tested: $span (()) = {𝟎}$ , the empty list is independent and is the basis of ${𝟎}$ , and $𝑗 = 1$ in Lemma 1.5.10 means $𝐯_{1} = 𝟎$ . The subspace criterion needs its nonemptiness condition exactly once, to produce $𝟎$ (Remark 1.4.5).

The counterexample, read closely. The natural first guess is that $𝑈 \cup 𝑊$ is a subspace whenever $𝑈$ and $𝑊$ are. The two axes of $ℝ^{2}$ refute it. Reading the counterexample, it used only one vector of the first axis outside the second and one vector of the second outside the first, whose sum lies on neither (Lemma 1.4.19). So the failure needs each subspace to stick out of the other. That suggests the corrected statement, Proposition 1.4.20, and its second proof is the counterexample run on general $𝑈$ and $𝑊$ . The same reading turned the counterexample over $𝔽_{2}$ in Example 1.2.39 into the hypothesis $1 + 1 \neq 0$ : the computation $𝐯 + 𝐯 = (1 + 1) 𝐯$ located the scalar that has to be invertible.

1.7.8Common errors

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

Unions. “ $𝑈 \cup 𝑊$ is closed under addition because $𝑈$ and $𝑊$ are.” The case split forgets the mixed case (Exercise 1.4.30). The repair is Proposition 1.4.20, and the smallest subspace containing both is $𝑈 + 𝑊$ (Proposition 1.4.24).
$𝟎$ in a span versus $𝟎$ in a list. $𝟎$ lies in every span, including $span (()) = {𝟎}$ , and this says nothing about independence. A list that contains $𝟎$ is always dependent (Proposition 1.5.15(c)), while the empty list is independent. Relatedly, the zero vector of a structure is whatever satisfies (A3) for its addition, not the number $0$ or the vector $(0, 0)$ (Exercise 1.2.24, Example 1.2.23). A subspace, on the other hand, always has the zero vector of the ambient space (Remark 1.4.4), which is the point of Exercise 1.4.29.
Lists versus sets. The list $𝐯, 𝐯$ is dependent, although its set of entries is ${𝐯}$ . The span forgets order and repetition (Remark 1.3.23). Independence does not forget repetition, and coordinates do not forget order: reordering a basis reorders the coordinates. A vector determines its coefficients only with respect to an independent list (Exercise 1.3.29, Exercise 1.6.31).
Pairwise is not enough. A list of three vectors, none a multiple of another, can be dependent (Exercise 1.5.16). Two independent lists can have a dependent concatenation (Exercise 1.7.12).
The wrong redundant entry. The last entry of a dependent list need not lie in the span of the others (Exercise 1.5.30), and an induction that deletes an arbitrary entry of a spanning list breaks (Exercise 1.6.30).
Half of a double containment. Showing that a span lies in $𝑉$ proves nothing about whether the list spans $𝑉$ (Exercise 1.3.30).
Hidden division. An argument that divides by $1 + 1$ , assumes $1 \neq - 1$ , or cancels a zero divisor fails over $𝔽_{2}$ or $ℤ / 𝑛 ℤ$ (Exercise 1.1.42, Exercise 1.1.45, Example 1.3.22).
Local versus global. The zero vector is unique among vectors that satisfy $𝐯 + 𝐳 = 𝐯$ for every $𝐯$ ; a vector that works for one $𝐯$ needs a separate argument (Exercise 1.2.43). Deriving (A4) from $(- 1) 𝐯$ is circular, because the proof of $0 𝐯 = 𝟎$ used (A4) (Exercise 1.2.54).

Exercises

Exercise 1.7.5.routine For each equality, decide which containments are finite checks and which need a construction, and prove the equality.

(a) $span (𝐯_{1}, 𝐯_{2}, 𝐯_{3}) =$ $span (𝐯_{1} - 𝐯_{2}, 𝐯_{2} - 𝐯_{3}, 𝐯_{3})$ , for any $𝐯_{1}, 𝐯_{2}, 𝐯_{3} \in 𝑉$ .
(b) ${𝑝 \in {𝐹 [𝑥]}_{\leq 2} | 𝑝 (0) = 𝑝 (1)} =$ $span (1, 𝑥^{2} - 𝑥)$ .

Solution.

Uses. Corollary 1.3.19 (Equal spans), Proposition 1.4.14 (The span is the smallest subspace containing a list), Theorem 1.4.3 (Subspace criterion), Proposition 1.2.18 (Degree and evaluation versus the operations), Definition 1.2.17 (Evaluation)

Techniques. Double containment (Technique 1.3.14), Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. In (a) both sides are spans, so Corollary 1.3.19 reduces the equality to six memberships. In (b) the left side is a subspace.

Hint 2. For (a), write

𝐯_{1}

and

𝐯_{2}

in terms of the new list. For (b),

span (1, 𝑥^{2} - 𝑥) \subseteq 𝑊

follows from Proposition 1.4.14(b); for the other containment, write

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

and see what

𝑝 (0) = 𝑝 (1)

says about

𝑏

and

𝑐

Sketch. (a) The new entries are visibly combinations of the old ones, and

𝐯_{3} = 𝐯_{3}

𝐯_{2} = (𝐯_{2} - 𝐯_{3}) + 𝐯_{3}

𝐯_{1} =

(𝐯_{1} - 𝐯_{2}) +

(𝐯_{2} - 𝐯_{3}) +

𝐯_{3}

. (b) The left side

𝑊

is a subspace containing

1

and

𝑥^{2} - 𝑥

, so it contains their span. Conversely

𝑝 =

𝑎 +

𝑏 𝑥 +

𝑐 𝑥^{2} \in

𝑊

means

𝑏 + 𝑐 = 0

, so

𝑝 =

𝑎 \cdot

1 +

𝑐 (𝑥^{2} - 𝑥)

(a) Both sides are spans, so by Corollary 1.3.19 it suffices to check that each list lies in the span of the other. Each of $𝐯_{1} - 𝐯_{2}$ , $𝐯_{2} - 𝐯_{3}$ , $𝐯_{3}$ is a linear combination of $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ , with coefficients $1, - 1, 0$ , then $0, 1, - 1$ , then $0, 0, 1$ . In the other direction,

\begin{aligned} 𝐯_{3} & = 𝐯_{3}, \\ 𝐯_{2} & = (𝐯_{2} - 𝐯_{3}) + 𝐯_{3}, \\ 𝐯_{1} & = (𝐯_{1} - 𝐯_{2}) + (𝐯_{2} - 𝐯_{3}) + 𝐯_{3} . \end{aligned}

Neither containment needs a generic element; the constructions are the last two lines, and there are only finitely many of them.

(b) Let $𝑊$ be the left side. First, $𝑊$ is a subspace of ${𝐹 [𝑥]}_{\leq 2}$ : the zero polynomial has $𝟎 (0) = 𝟎 (1) = 0$ , and if $𝑝 (0) = 𝑝 (1)$ and $𝑞 (0) = 𝑞 (1)$ , then $(𝑝 + 𝑞) (0) =$ $𝑝 (0) +$ $𝑞 (0) =$ $𝑝 (1) +$ $𝑞 (1) =$ $(𝑝 + 𝑞) (1)$ and $(𝑎 𝑝) (0) =$ $𝑎 𝑝 (0) =$ $𝑎 𝑝 (1) =$ $(𝑎 𝑝) (1)$ by Proposition 1.2.18(c). So Theorem 1.4.3 applies.

$span (1, 𝑥^{2} - 𝑥) \subseteq 𝑊$ . The constant $1$ takes the value $1$ at $0$ and at $1$ , and $𝑥^{2} - 𝑥$ takes the value $0$ at both. So both entries lie in the subspace $𝑊$ , and their span does by Proposition 1.4.14(b). This half is a finite check.

$𝑊 \subseteq span (1, 𝑥^{2} - 𝑥)$ . Let $𝑝 =$ $𝑎 +$ $𝑏 𝑥 +$ $𝑐 𝑥^{2} \in$ $𝑊$ . By Definition 1.2.17, $𝑝 (0) = 𝑎$ and $𝑝 (1) = 𝑎 + 𝑏 + 𝑐$ , so $𝑝 (0) = 𝑝 (1)$ gives $𝑏 + 𝑐 = 0$ , that is, $𝑏 = - 𝑐$ . Hence

𝑝 = 𝑎 + (- 𝑐) 𝑥 + 𝑐 𝑥^{2} = 𝑎 \cdot 1 + 𝑐 (𝑥^{2} - 𝑥) \in span (1, 𝑥^{2} - 𝑥) .

This half is the construction: it produces coefficients for a generic element of $𝑊$ . The argument works over every field.

Exercise 1.7.6.routine Let $𝐮, 𝐰 \in 𝑉$ , and consider the equation $𝐦 - 𝐮 = 𝐰 - 𝐦$ for an unknown $𝐦 \in 𝑉$ .

(a)Suppose $1 + 1 \neq 0$ in $𝐹$ . Show that the equation has exactly one solution, and find it.
(b)Suppose $𝐹 = 𝔽_{2}$ . Show that the equation has a solution only if $𝐮 = 𝐰$ , and that in that case every $𝐦 \in 𝑉$ is a solution.

Solution.

Uses. Proposition 1.2.30 (Additive arithmetic), Proposition 1.2.34 (Negatives and the scalar $- 1$ ), Definition 1.2.1 (Vector space), Exercise 1.2.37, Proposition 1.2.32 (The scalar zero)

Techniques. Uniqueness via two candidates (Technique 1.1.8), Try small cases and small fields (Technique 1.2.38)

Hint 1. Rewrite the equation so that all occurrences of

𝐦

are on one side. You should get

𝐦 + 𝐦 = 𝐮 + 𝐰

Hint 2. By (A5) and (A8),

𝐦 + 𝐦 = (1 + 1) 𝐦

. When can you divide by

1 + 1

Sketch. Adding

𝐦 + 𝐮

to both sides shows that the equation is equivalent to

(1 + 1) 𝐦 = 𝐮 + 𝐰

. If

1 + 1 \neq 0

, this has exactly one solution,

𝐦 = {(1 + 1)}^{- 1} (𝐮 + 𝐰)

. If

1 + 1 = 0

, the left side is always

𝟎

, so there is a solution exactly when

𝐮 + 𝐰 = 𝟎

, that is,

𝐰 = - 𝐮 = 𝐮

, and then every

𝐦

works.

We first rewrite the equation. If $𝐦 - 𝐮 = 𝐰 - 𝐦$ , then adding $𝐦 + 𝐮$ to both sides and regrouping with (A1)–(A4) gives $𝐦 + 𝐦 = 𝐰 + 𝐮$ . Conversely, if $𝐦 + 𝐦 = 𝐰 + 𝐮$ , then adding $- 𝐦 - 𝐮$ to both sides gives back the original equation. So the equation is equivalent to $𝐦 + 𝐦 = 𝐮 + 𝐰$ , and by (A5) and (A8), $𝐦 +$ $𝐦 =$ $1 𝐦 +$ $1 𝐦 =$ $(1 + 1) 𝐦$ . So it is equivalent to

(1 + 1) 𝐦 = 𝐮 + 𝐰 .

(a) If $1 + 1 \neq 0$ , this equation has exactly one solution, $𝐦 = {(1 + 1)}^{- 1} (𝐮 + 𝐰)$ , by Exercise 1.2.37(a), applied with $𝑎 = 1 + 1$ , with $𝟎$ in place of its $𝐮$ , and with $𝐮 + 𝐰$ in place of its $𝐰$ . Over $ℝ$ this is the midpoint $(𝐮 + 𝐰) / 2$ . Uniqueness here is the two-candidate argument in disguise: two solutions $𝐦, 𝐦^{'}$ satisfy $(1 + 1) 𝐦 = (1 + 1) 𝐦^{'}$ , and the nonzero scalar $1 + 1$ cancels.

(b) Over $𝔽_{2}$ , $1 + 1 = 0$ , so the left side is $0 𝐦 = 𝟎$ for every $𝐦$ (Proposition 1.2.32). The equation becomes $𝟎 = 𝐮 + 𝐰$ , which holds for all $𝐦$ or for none. It holds exactly when $𝐰 = - 𝐮$ (Proposition 1.2.30(a)), and $- 𝐮 = (- 1) 𝐮 = 1 𝐮 = 𝐮$ by Proposition 1.2.34, since $- 1 = 1$ in $𝔽_{2}$ . So there is a solution only if $𝐰 = 𝐮$ , and then every $𝐦$ is one. If $𝑉 \neq {𝟎}$ , choosing $𝐮 \neq 𝐰$ gives no solution and choosing $𝐮 = 𝐰$ gives more than one, so the hypothesis $1 + 1 \neq 0$ in (a) cannot be dropped.

Exercise 1.7.7.standard Let $𝑛 \geq 2$ , and let $𝐯_{1}, \dots, 𝐯_{𝑛}$ be a linearly dependent list in $𝑉$ such that every sublist of length $𝑛 - 1$ is linearly independent.

(a)Show that every dependence relation $𝑐_{1}, \dots, 𝑐_{𝑛}$ of the list has all $𝑐_{𝑖} \neq 0$ .
(b)Show that any two dependence relations are proportional: if $𝑐_{1}, \dots, 𝑐_{𝑛}$ and $𝑑_{1}, \dots, 𝑑_{𝑛}$ are dependence relations, then $𝑑_{𝑖} = 𝜆 𝑐_{𝑖}$ for all $𝑖$ , for some $𝜆 \in 𝐹$ .
(c)Find such a list of length $3$ in $ℝ^{2}$ , and all of its linear relations.

Solution.

Uses. Definition 1.5.3 (Linear relation), Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.2.32 (The scalar zero), Proposition 1.5.15 (Short lists, zeros, and repeats)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For (a), if

𝑐_{𝑗} = 0

, what does the relation say about the list with

𝐯_{𝑗}

deleted?

Hint 2. For (b), the two relations are two candidates; compare them after making one coefficient agree. Subtract

(𝑑_{1} / 𝑐_{1})

times the first relation from the second, and apply (a) to the result.

Sketch. (a) If

𝑐_{𝑗} = 0

, dropping the

𝑗

-th term gives a nontrivial relation of the sublist without

𝐯_{𝑗}

, which is independent. (b) With

𝜆 = 𝑑_{1} / 𝑐_{1}

, the coefficients

𝑑_{𝑖} - 𝜆 𝑐_{𝑖}

form a linear relation whose first coefficient is

0

; by (a) it is not a dependence relation, so it is trivial. (c)

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

, whose relations are

𝜆, 𝜆, - 𝜆

(a) Let $𝑐_{1}, \dots, 𝑐_{𝑛}$ be a dependence relation, and suppose $𝑐_{𝑗} = 0$ for some $𝑗$ . The term $𝑐_{𝑗} 𝐯_{𝑗} = 0 𝐯_{𝑗} = 𝟎$ can be dropped, so the coefficients $𝑐_{𝑖}$ , $𝑖 \neq 𝑗$ , form a linear relation of the sublist obtained by deleting $𝐯_{𝑗}$ . Not all of them are $0$ , since $𝑐_{𝑗} = 0$ and the relation is nontrivial. So that sublist, of length $𝑛 - 1$ , is dependent by Theorem 1.5.5, contrary to the hypothesis. Hence all $𝑐_{𝑖} \neq 0$ .

(b) Let $𝑐$ and $𝑑$ be dependence relations. By (a), $𝑐_{1} \neq 0$ , so we may set $𝜆 = 𝑑_{1} / 𝑐_{1}$ . By Lemma 1.3.9,

\sum_{𝑖 = 1}^{𝑛} (𝑑_{𝑖} - 𝜆 𝑐_{𝑖}) 𝐯_{𝑖} = \sum_{𝑖 = 1}^{𝑛} 𝑑_{𝑖} 𝐯_{𝑖} - 𝜆 \sum_{𝑖 = 1}^{𝑛} 𝑐_{𝑖} 𝐯_{𝑖} = 𝟎 - 𝜆 𝟎 = 𝟎,

so the scalars $𝑒_{𝑖} = 𝑑_{𝑖} - 𝜆 𝑐_{𝑖}$ form a linear relation. Its first coefficient is $𝑒_{1} =$ $𝑑_{1} -$ $(𝑑_{1} / 𝑐_{1}) 𝑐_{1} =$ $0$ . By (a), a dependence relation has no zero coefficient, so $𝑒$ is not a dependence relation: it is the trivial relation. Hence $𝑑_{𝑖} = 𝜆 𝑐_{𝑖}$ for every $𝑖$ .

(c) Take $(1, 0), (0, 1), (1, 1)$ . It is dependent, since $(1, 0) +$ $(0, 1) -$ $(1, 1) =$ $𝟎$ , and no entry is a multiple of another, so each sublist of length $2$ is independent by Proposition 1.5.15(d). By (b), every linear relation is a multiple of $1, 1, - 1$ , and conversely each $𝜆, 𝜆, - 𝜆$ is a relation, by Lemma 1.3.9(b). So the relations are $𝜆, 𝜆, - 𝜆$ for $𝜆 \in ℝ$ (with $𝜆 = 0$ giving the trivial relation).

So for such a list the relations form a single line through the trivial relation. This is the uniqueness-by-subtraction pattern: two candidates, normalized so that one coordinate agrees, differ by a solution of a problem that has only the zero solution.

Exercise 1.7.8.routine Let $𝐯_{1}, \dots, 𝐯_{𝑘}$ be a list in $𝑉$ . Show that it is linearly independent if and only if

𝐯_{𝑗} \notin span (𝐯_{𝑗 + 1}, \dots, 𝐯_{𝑘}) for every 𝑗 \in {1, \dots, 𝑘} .

For the backward direction, argue directly with an extremal choice of index, without reordering the list and quoting Corollary 1.5.13.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Lemma 1.3.9 (Arithmetic of linear combinations), Proposition 1.2.34 (Negatives and the scalar $- 1$ )

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. For (

\Leftarrow

), take a nontrivial relation and solve it for one entry. Which choice of entry leaves only later entries on the other side?

Hint 2. Let

𝑖

be the smallest index with

𝑎_{𝑖} \neq 0

. For (

\Rightarrow

), turn

𝐯_{𝑗} =

\sum_{𝑙 > 𝑗} 𝑏_{𝑙} 𝐯_{𝑙}

into a relation.

Sketch. (

\Leftarrow

) In a nontrivial relation, let

𝑖

be the smallest index with

𝑎_{𝑖} \neq 0

. The earlier terms vanish, so

𝐯_{𝑖} =

\sum_{𝑙 > 𝑖} (- 𝑎_{𝑙} / 𝑎_{𝑖}) 𝐯_{𝑙} \in

span (𝐯_{𝑖 + 1}, \dots, 𝐯_{𝑘})

, a contradiction. (

\Rightarrow

) If

𝐯_{𝑗} =

\sum_{𝑙 > 𝑗} 𝑏_{𝑙} 𝐯_{𝑙}

, the coefficients

0,

\dots,

0,

- 1,

𝑏_{𝑗 + 1},

\dots,

𝑏_{𝑘}

form a nontrivial relation.

( $\Leftarrow$ ) Suppose the condition holds, and suppose for contradiction that $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ with not all $𝑎_{𝑙} = 0$ . Let $𝑖$ be the smallest index with $𝑎_{𝑖} \neq 0$ . Then $𝑎_{𝑙} = 0$ for $𝑙 < 𝑖$ , and those terms vanish, so

𝑎_{𝑖} 𝐯_{𝑖} + \sum_{𝑙 = 𝑖 + 1}^{𝑘} 𝑎_{𝑙} 𝐯_{𝑙} = 𝟎, hence 𝐯_{𝑖} = \sum_{𝑙 = 𝑖 + 1}^{𝑘} (- \frac{𝑎_{𝑙}}{𝑎_{𝑖}}) 𝐯_{𝑙},

by the computation in the proof of Lemma 1.5.10. So $𝐯_{𝑖} \in$ $span (𝐯_{𝑖 + 1}, \dots, 𝐯_{𝑘})$ ; if $𝑖 = 𝑘$ , the sum is empty and this says $𝐯_{𝑘} = 𝟎 \in span (())$ . Either way the condition fails for $𝑗 = 𝑖$ , a contradiction. By Theorem 1.5.5 the list is independent.

( $\Rightarrow$ ) We prove the contrapositive. Suppose $𝐯_{𝑗} =$ $𝑏_{𝑗 + 1} 𝐯_{𝑗 + 1} +$ $\dots +$ $𝑏_{𝑘} 𝐯_{𝑘}$ for some $𝑗$ . The linear combination with coefficients $0$ on $𝐯_{1}, \dots, 𝐯_{𝑗 - 1}$ , $- 1$ on $𝐯_{𝑗}$ , and $𝑏_{𝑙}$ on $𝐯_{𝑙}$ for $𝑙 > 𝑗$ represents $- 𝐯_{𝑗} + 𝐯_{𝑗} = 𝟎$ , by Proposition 1.2.34 and Lemma 1.3.9. Its coefficient on $𝐯_{𝑗}$ is $- 1 \neq 0$ , so the list is dependent.

The proof of Lemma 1.5.10 chose the largest index to get earlier entries on the other side. Choosing the smallest gets later ones. Which extreme to choose is decided by which side the conclusion wants.

Exercise 1.7.9.standard Let $𝑋$ be a set, let $𝑓_{1}, \dots, 𝑓_{𝑛} \in 𝐹^{𝑋}$ , and let $𝑡_{1}, \dots, 𝑡_{𝑛} \in 𝑋$ be points such that

𝑓_{𝑖} (𝑡_{𝑖}) \neq 0 for every 𝑖, and 𝑓_{𝑖} (𝑡_{𝑗}) = 0 whenever 𝑗 < 𝑖 .

(a)Show that $𝑓_{1}, \dots, 𝑓_{𝑛}$ is linearly independent.
(b)For $𝑖 \geq 0$ , let $𝑟_{𝑖} \in ℝ^{ℝ}$ be the ramp $𝑟_{𝑖} (𝑡) =$ $max (0, 𝑡 - 𝑖)$ . Show that $1,$ $𝑟_{0},$ $𝑟_{1},$ $\dots,$ $𝑟_{𝑛 - 1}$ is linearly independent in $ℝ^{ℝ}$ for every $𝑛 \geq 1$ , where $1$ is the constant function.

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.9 (Function spaces), Proposition 1.1.17 (No zero divisors)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. In a nontrivial relation

\sum 𝑎_{𝑙} 𝑓_{𝑙} = 𝟎

, choose the smallest index

𝑖

with

𝑎_{𝑖} \neq 0

, and evaluate the relation at

𝑡_{𝑖}

Hint 2. For (b), list the functions as

1, 𝑟_{0}, \dots, 𝑟_{𝑛 - 1}

and choose the points

- 1, 1, 2, \dots, 𝑛

Sketch. (a) Evaluating at

𝑡_{𝑖}

kills the terms with

𝑙 < 𝑖

(their coefficients vanish) and with

𝑙 > 𝑖

(as

𝑓_{𝑙} (𝑡_{𝑖}) = 0

), leaving

𝑎_{𝑖} 𝑓_{𝑖} (𝑡_{𝑖}) = 0

, so

𝑎_{𝑖} = 0

. (b) With

𝑔_{0} = 1

𝑔_{𝑖 + 1} = 𝑟_{𝑖}

and points

𝑠_{0} = - 1

𝑠_{𝑖 + 1} = 𝑖 + 1

𝑔_{𝑚} (𝑠_{𝑚}) = 1

, and

𝑟_{𝑖} (𝑠_{𝑗}) = 0

for

𝑗 \leq 𝑖

because

𝑠_{𝑗} \leq 𝑖

(a) Suppose $𝑎_{1} 𝑓_{1} +$ $\dots +$ $𝑎_{𝑛} 𝑓_{𝑛} =$ $𝟎$ , the zero function, and suppose for contradiction that some $𝑎_{𝑙} \neq 0$ . Let $𝑖$ be the smallest index with $𝑎_{𝑖} \neq 0$ . A relation among functions holds at every point (Definition 1.2.9), so at $𝑡_{𝑖}$ ,

\sum_{𝑙 = 1}^{𝑛} 𝑎_{𝑙} 𝑓_{𝑙} (𝑡_{𝑖}) = 0 .

For $𝑙 < 𝑖$ we have $𝑎_{𝑙} = 0$ , and for $𝑙 > 𝑖$ we have $𝑓_{𝑙} (𝑡_{𝑖}) = 0$ by hypothesis (as $𝑖 < 𝑙$ ). So the sum is $𝑎_{𝑖} 𝑓_{𝑖} (𝑡_{𝑖})$ , and $𝑎_{𝑖} 𝑓_{𝑖} (𝑡_{𝑖}) = 0$ with $𝑓_{𝑖} (𝑡_{𝑖}) \neq 0$ forces $𝑎_{𝑖} = 0$ (Proposition 1.1.17), a contradiction. By Theorem 1.5.5 the list is independent.

(b) Write $𝑔_{0} = 1$ and $𝑔_{𝑖 + 1} = 𝑟_{𝑖}$ for $0 \leq 𝑖 \leq 𝑛 - 1$ , and choose the points $𝑠_{0} = - 1$ and $𝑠_{𝑖 + 1} = 𝑖 + 1$ . We check the hypotheses of (a) for the list $𝑔_{0}, \dots, 𝑔_{𝑛}$ and the points $𝑠_{0}, \dots, 𝑠_{𝑛}$ . First, $𝑔_{0} (𝑠_{0}) = 1 \neq 0$ and $𝑔_{𝑖 + 1} (𝑠_{𝑖 + 1}) =$ $𝑟_{𝑖} (𝑖 + 1) =$ $max (0, 1) =$ $1 \neq$ $0$ . Next, let $𝑗 < 𝑖 + 1$ , that is, $𝑗 \leq 𝑖$ . Then $𝑠_{𝑗} = - 1$ or $𝑠_{𝑗} = 𝑗$ , so $𝑠_{𝑗} \leq 𝑖$ and $𝑠_{𝑗} - 𝑖 \leq 0$ , which gives $𝑔_{𝑖 + 1} (𝑠_{𝑗}) =$ $𝑟_{𝑖} (𝑠_{𝑗}) =$ $max (0, 𝑠_{𝑗} - 𝑖) =$ $0$ . (For $𝑔_{0}$ there is nothing to check, since no index is smaller than $0$ .) By (a), with the indices shifted by one, $1, 𝑟_{0}, \dots, 𝑟_{𝑛 - 1}$ is independent.

The pattern is a triangular one: each function is invisible at the points before its own, so evaluating at the points in order reads off one coefficient at a time.

Exercise 1.7.10.routine Find the error in the following argument, and show that its claim is false. Then show that the argument does prove the following statement: if every two of the nonzero vectors $𝐯_{1}, \dots, 𝐯_{𝑘}$ lie on a common line, then all of them do.

Claim. Any nonzero vectors $𝐯_{1}, \dots, 𝐯_{𝑘} \in 𝑉$ , with $𝑘 \geq 1$ , lie on a common line: there is a vector $𝐮$ with $𝐯_{1},$ $\dots,$ $𝐯_{𝑘} \in$ $span (𝐮)$ .

Proof. Induction on $𝑘$ . For $𝑘 = 1$ , take $𝐮 = 𝐯_{1}$ . Suppose the claim holds for all lists of length $𝑘$ , and let $𝐯_{1}, \dots, 𝐯_{𝑘 + 1}$ be nonzero. Applying the inductive hypothesis to $𝐯_{1}, \dots, 𝐯_{𝑘}$ gives $𝐮$ with $𝐯_{1},$ $\dots,$ $𝐯_{𝑘} \in$ $span (𝐮)$ , and applying it to $𝐯_{2}, \dots, 𝐯_{𝑘 + 1}$ gives $𝐮^{'}$ with $𝐯_{2},$ $\dots,$ $𝐯_{𝑘 + 1} \in$ $span (𝐮^{'})$ . The vector $𝐯_{2}$ lies on both lines and is nonzero, so $span (𝐮) =$ $span (𝐯_{2}) =$ $span (𝐮^{'})$ . Hence all of $𝐯_{1}, \dots, 𝐯_{𝑘 + 1}$ lie in $span (𝐮)$ .

Solution.

Uses. Exercise 1.3.28

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

Hint 1. Run the inductive step with

𝑘 = 1

. Which vectors are in the two shorter lists?

Hint 2. For the corrected statement, start the induction at

𝑘 = 2

and check that the step from

𝑘

𝑘 + 1

is valid when

𝑘 \geq 2

Sketch. For

𝑘 = 1

the shorter lists are

𝐯_{1}

and

𝐯_{2}

, which share no entry, so “

𝐯_{2}

lies on both lines” is false; the step from

1

2

fails. The claim is false for

(1, 0), (0, 1)

. With base case

𝑘 = 2

(the hypothesis), the step is valid for

𝑘 \geq 2

, because then the two shorter lists share

𝐯_{2}

, and a nonzero

𝐯_{2} \in span (𝐮)

has

span (𝐯_{2}) =

span (𝐮)

The error. The inductive step uses the vector $𝐯_{2}$ as a common entry of the lists $𝐯_{1}, \dots, 𝐯_{𝑘}$ and $𝐯_{2}, \dots, 𝐯_{𝑘 + 1}$ . When $𝑘 = 1$ these lists are $𝐯_{1}$ and $𝐯_{2}$ , which have no entry in common, and $𝐯_{2}$ is not in the first. So the step from $𝑘 = 1$ to $𝑘 = 2$ is invalid. The base case and the steps from $𝑘$ to $𝑘 + 1$ for $𝑘 \geq 2$ are fine, but without the step from $1$ to $2$ the induction proves nothing beyond $𝑘 = 1$ .

The claim is false. In $ℝ^{2}$ , suppose $(1, 0) = 𝑎 𝐮$ and $(0, 1) = 𝑏 𝐮$ . Both vectors are nonzero, so $𝑎, 𝑏 \neq 0$ , and $(0, 1) =$ $𝑏 𝐮 =$ $(𝑏 / 𝑎) (1, 0)$ , whose second coordinate is $0$ . This is a contradiction, so $(1, 0)$ and $(0, 1)$ lie on no common line.

The corrected statement. Suppose every two of the nonzero vectors $𝐯_{1}, \dots, 𝐯_{𝑘}$ lie on a common line; we show by induction on $𝑘 \geq 2$ that all of them do (for $𝑘 = 1$ there is nothing to prove). For $𝑘 = 2$ this is the hypothesis. Suppose it holds for lists of length $𝑘 \geq 2$ satisfying the hypothesis, and let $𝐯_{1}, \dots, 𝐯_{𝑘 + 1}$ satisfy it. Both shorter lists satisfy it as well, so the argument above gives $𝐮$ and $𝐮^{'}$ . Since $𝑘 \geq 2$ , the vector $𝐯_{2}$ is an entry of both shorter lists. It lies in $span (𝐮)$ , say $𝐯_{2} = 𝑐 𝐮$ , and $𝑐 \neq 0$ because $𝐯_{2} \neq 𝟎$ . So $span (𝐯_{2}) =$ $span (𝐮)$ by Exercise 1.3.28(b); likewise $span (𝐯_{2}) =$ $span (𝐮^{'})$ . Hence $𝐯_{𝑘 + 1} \in$ $span (𝐮^{'}) =$ $span (𝐮)$ , and all the vectors lie on the line $span (𝐮)$ .

When an inductive step combines two shorter lists through a shared entry, check that the shared entry exists for the smallest $𝑘$ at which the step is used.

Exercise 1.7.11.standard Let $𝑉$ be a vector space over $𝔽_{2}$ and $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ a list in $𝑉$ . Let $𝑍 (ℒ︀)$ be the number of subsets $𝐼 \subseteq {1, \dots, 𝑘}$ with $\sum_{𝑖 \in 𝐼} 𝐯_{𝑖} = 𝟎$ , where the empty set counts, with the empty sum $𝟎$ .

(a)Let $𝐰 \in 𝑉$ . Show that $𝑍 (ℒ︀, 𝐰) = 𝑍 (ℒ︀)$ if $𝐰 \notin span (ℒ︀)$ , and $𝑍 (ℒ︀, 𝐰) = 2 𝑍 (ℒ︀)$ if $𝐰 \in span (ℒ︀)$ .
(b)Deduce that $𝑍 (ℒ︀) = 2^{𝑑}$ , where $𝑑$ is the number of entries that sifting deletes from $ℒ︀$ (the third proof of Theorem 1.6.10). In particular, $𝑍 (ℒ︀) = 1$ if and only if $ℒ︀$ is linearly independent.

Solution.

Uses. Definition 1.3.4 (Linear combination), Lemma 1.3.9 (Arithmetic of linear combinations), Theorem 1.5.5 (Independence is decided at zero), Theorem 1.6.10 (Every spanning list contains a basis), Corollary 1.5.13 (Independence, one entry at a time)

Techniques. Induction on the length of a list (Technique 1.6.9), Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Over

𝔽_{2}

, a subset

𝐼

is the same thing as a list of coefficients in

{0, 1}

, that is, a linear combination of

ℒ︀

. So

𝑍 (ℒ︀)

counts the linear relations of

ℒ︀

Hint 2. Split the zero-sum subsets of

{1, \dots, 𝑘 + 1}

according to whether they contain

𝑘 + 1

. Those that do correspond to linear combinations of

ℒ︀

representing

𝐰

. Fix one such representation and add relations to it.

Hint 3. For (b), induct on

𝑘

. Sifting reads from left to right, so sifting

ℒ︀, 𝐰

deletes what sifting

ℒ︀

deletes, plus

𝐰

exactly when

𝐰 \in span (ℒ︀)

Sketch. Subsets of

{1, \dots, 𝑘}

are linear combinations of

ℒ︀

over

𝔽_{2}

. A zero-sum subset of

{1, \dots, 𝑘 + 1}

either avoids

𝑘 + 1

(

𝑍 (ℒ︀)

of them) or is

𝐽 \cup {𝑘 + 1}

with

\sum_{𝐽} 𝐯_{𝑗} = - 𝐰 = 𝐰

. The representations of

𝐰

number

0

𝐰 \notin span (ℒ︀)

, and otherwise as many as the relations, since

𝑐 \mapsto 𝑎 + 𝑐

is a bijection from relations to representations for any fixed representation

𝑎

. For (b), induct on

𝑘

with

𝑍 (()) = 1 = 2^{0}

Over $𝔽_{2}$ the only scalars are $0$ and $1$ , so a linear combination of $ℒ︀$ is a list of coefficients in ${0, 1}$ , and it represents $\sum_{𝑖 \in 𝐼} 𝐯_{𝑖}$ , where $𝐼$ is the set of positions with coefficient $1$ . This is a bijection between subsets of ${1, \dots, 𝑘}$ and linear combinations of $ℒ︀$ . In particular, $𝑍 (ℒ︀)$ is the number of linear relations of $ℒ︀$ , and for $𝐰 \in 𝑉$ the number $𝑁 (𝐰)$ of linear combinations of $ℒ︀$ representing $𝐰$ is the number of $𝐼$ with $\sum_{𝑖 \in 𝐼} 𝐯_{𝑖} = 𝐰$ .

(a) Split the subsets $𝐼^{'} \subseteq {1, \dots, 𝑘 + 1}$ with $\sum_{𝑖 \in 𝐼^{'}} 𝐯_{𝑖} = 𝟎$ (writing $𝐯_{𝑘 + 1} = 𝐰$ ) into those that do not contain $𝑘 + 1$ and those that do. The first kind are the zero-sum subsets of ${1, \dots, 𝑘}$ , and there are $𝑍 (ℒ︀)$ of them. The second kind are the sets $𝐽 \cup {𝑘 + 1}$ with $𝐽 \subseteq {1, \dots, 𝑘}$ and $\sum_{𝑗 \in 𝐽} 𝐯_{𝑗} + 𝐰 = 𝟎$ , that is, $\sum_{𝑗 \in 𝐽} 𝐯_{𝑗} = - 𝐰 = 𝐰$ (over $𝔽_{2}$ , $- 𝐰 = (- 1) 𝐰 = 𝐰$ ). There are $𝑁 (𝐰)$ of them.

If $𝐰 \notin span (ℒ︀)$ , then $𝑁 (𝐰) = 0$ . If $𝐰 \in span (ℒ︀)$ , fix one representation $𝑎_{1}, \dots, 𝑎_{𝑘}$ of $𝐰$ . For a linear relation $𝑐$ , the coefficients $𝑎 + 𝑐$ represent $𝐰 + 𝟎 = 𝐰$ (Lemma 1.3.9). Conversely, for a representation $𝑏$ of $𝐰$ , the coefficients $𝑏 - 𝑎$ represent $𝐰 - 𝐰 = 𝟎$ . These two maps are inverse to each other, so $𝑁 (𝐰)$ equals the number of relations, $𝑍 (ℒ︀)$ . Hence $𝑍 (ℒ︀, 𝐰) =$ $𝑍 (ℒ︀) +$ $𝑁 (𝐰)$ is $𝑍 (ℒ︀)$ or $2 𝑍 (ℒ︀)$ , as claimed.

(b) For a list $ℳ︀$ , write $𝑑 (ℳ︀)$ for the number of entries that sifting deletes from it. We show $𝑍 (ℒ︀) = 2^{𝑑 (ℒ︀)}$ by induction on $𝑘$ . For $𝑘 = 0$ , the only subset is $\emptyset$ , whose sum is $𝟎$ , so $𝑍 (()) = 1 = 2^{0}$ , and sifting deletes nothing. Suppose the claim holds for lists of length $𝑘$ , and consider $ℒ︀, 𝐰$ . Sifting decides about each entry by looking only at the entries before it, so on the first $𝑘$ entries, sifting $ℒ︀, 𝐰$ makes the same decisions as sifting $ℒ︀$ . It deletes $𝐰$ exactly when $𝐰 \in span (ℒ︀)$ . So $𝑑 (ℒ︀, 𝐰) = 𝑑 (ℒ︀)$ if $𝐰 \notin span (ℒ︀)$ , and $𝑑 (ℒ︀) + 1$ otherwise, and by (a) and the inductive hypothesis, $𝑍 (ℒ︀, 𝐰) =$ $2^{𝑑 (ℒ︀, 𝐰)}$ in both cases.

Finally, $𝑍 (ℒ︀) = 1$ means that the trivial relation is the only one, which is independence (Theorem 1.5.5). Equivalently $𝑑 = 0$ : sifting deletes nothing exactly when no entry lies in the span of the earlier ones, which is independence by Corollary 1.5.13.

Exercise 1.7.12.standard

(a)Disprove: if $ℒ︀$ and $ℳ︀$ are linearly independent lists in $𝑉$ , then the concatenation $ℒ︀, ℳ︀$ is linearly independent. Use the smallest counterexample you can find.
(b)What do $span (ℒ︀)$ and $span (ℳ︀)$ have in common in your counterexample? Use the answer to formulate a corrected statement.
(c)Prove: if $ℒ︀$ and $ℳ︀$ are linearly independent, then $ℒ︀, ℳ︀$ is linearly independent if and only if $span (ℒ︀) \cap$ $span (ℳ︀) =$ ${𝟎}$ .

Solution.

Uses. Theorem 1.5.5 (Independence is decided at zero), Proposition 1.5.15 (Short lists, zeros, and repeats), Lemma 1.3.9 (Arithmetic of linear combinations), Definition 1.3.10 (Span), Proposition 1.3.17 (A list lies in its span)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Take

𝑉

as small as possible and both lists of length one.

Hint 2. In your counterexample, the two spans share a nonzero vector. For (c), a vector in both spans gives a relation of

ℒ︀, ℳ︀

, and a relation of

ℒ︀, ℳ︀

gives a vector in both spans.

Sketch. (a)

ℒ︀ = ℳ︀ = 𝐯

with

𝐯 \neq 𝟎

: each is independent, but

𝐯, 𝐯

is not. (b) The spans share

𝐯

; conjecture that a common nonzero vector is the only obstruction. (c) If

𝐱 =

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

\sum 𝑏_{𝑗} 𝐰_{𝑗}

, then

𝑎, - 𝑏

is a relation of

ℒ︀, ℳ︀

, trivial by independence, so

𝐱 = 𝟎

. Conversely a relation

\sum 𝑎_{𝑖} 𝐮_{𝑖} +

\sum 𝑏_{𝑗} 𝐰_{𝑗} =

𝟎

gives

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

\sum (- 𝑏_{𝑗}) 𝐰_{𝑗}

in both spans, hence

𝟎

, and independence of each list kills the coefficients.

(a) Let $𝑉$ be any nonzero vector space, $𝐯 \neq 𝟎$ , and $ℒ︀ = ℳ︀ = 𝐯$ . Each list is independent by Proposition 1.5.15(b), but $ℒ︀, ℳ︀ = 𝐯, 𝐯$ has a repeated entry and is dependent by Proposition 1.5.15(c). No counterexample is smaller: lists of length $0$ add nothing, and in the zero space every nonempty list is dependent. (The same counterexample settles Exercise 1.5.34(c).)

(b) The two spans are both $span (𝐯)$ , and they share the nonzero vector $𝐯$ . Any counterexample must be like this: a relation among the concatenation that involves both lists produces a vector that both lists can represent. This suggests that concatenating independent lists can fail only when their spans share a nonzero vector, which is (c).

(c) Write $ℒ︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ and $ℳ︀ = 𝐰_{1}, \dots, 𝐰_{𝑚}$ .

( $\Rightarrow$ ) Suppose $ℒ︀, ℳ︀$ is independent, and let $𝐱 \in$ $span (ℒ︀) \cap$ $span (ℳ︀)$ , say $𝐱 =$ $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} =$ $\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗}$ . By Lemma 1.3.9, the coefficients $𝑎_{1},$ $\dots,$ $𝑎_{𝑘},$ $- 𝑏_{1},$ $\dots,$ $- 𝑏_{𝑚}$ represent $𝐱 - 𝐱 = 𝟎$ , so they form a linear relation of $ℒ︀, ℳ︀$ . It is trivial, so every $𝑎_{𝑖} = 0$ and $𝐱 = 𝟎$ . Since $𝟎$ lies in both spans (Proposition 1.3.17), the intersection is ${𝟎}$ .

( $\Leftarrow$ ) Suppose $span (ℒ︀) \cap$ $span (ℳ︀) =$ ${𝟎}$ , and let $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} +$ $\sum_{𝑗} 𝑏_{𝑗} 𝐰_{𝑗} =$ $𝟎$ . Then

𝐱 = \sum_{𝑖 = 1}^{𝑘} 𝑎_{𝑖} 𝐮_{𝑖} = \sum_{𝑗 = 1}^{𝑚} (- 𝑏_{𝑗}) 𝐰_{𝑗}

lies in both spans, so $𝐱 = 𝟎$ . Since $ℒ︀$ is independent, $\sum_{𝑖} 𝑎_{𝑖} 𝐮_{𝑖} = 𝟎$ forces all $𝑎_{𝑖} = 0$ , and since $ℳ︀$ is independent, $\sum_{𝑗} (- 𝑏_{𝑗}) 𝐰_{𝑗} = 𝟎$ forces all $𝑏_{𝑗} = 0$ . So the relation is trivial, and $ℒ︀, ℳ︀$ is independent by Theorem 1.5.5.

For two subspaces, the condition $span (ℒ︀) \cap$ $span (ℳ︀) =$ ${𝟎}$ characterizes direct sums (Section 4.4).

Exercise 1.7.13.routine Let $𝑈$ be a subspace of $𝑉$ , and let $𝐯, 𝐰 \in 𝑉$ with $𝐯 \notin 𝑈$ .

(a)Suppose $1 + 1 \neq 0$ in $𝐹$ . Show that $𝐯 + 𝐰 \notin 𝑈$ or $𝐯 - 𝐰 \notin 𝑈$ .
(b)Show that (a) fails over $𝔽_{2}$ .

Solution.

Uses. Theorem 1.4.3 (Subspace criterion), Definition 1.2.1 (Vector space)

Techniques. Proving a disjunction (Technique 1.7.4), Try small cases and small fields (Technique 1.2.38)

Hint 1. Assume that

𝐯 + 𝐰 \in 𝑈

, and show that

𝐯 - 𝐰 \notin 𝑈

Hint 2. If both were in

𝑈

, so would be their sum. What is it? For (b), try the smallest possible

𝑉

and

𝑈

Sketch. If

𝐯 + 𝐰 \in 𝑈

and also

𝐯 - 𝐰 \in 𝑈

, then their sum

(1 + 1) 𝐯

lies in

𝑈

, and so does

{(1 + 1)}^{- 1} (1 + 1) 𝐯 = 𝐯

, a contradiction. Over

𝔽_{2}

𝑉 = 𝔽_{2}

𝑈 = {0}

𝐯 = 𝐰 = 1

, where

𝐯 + 𝐰 = 𝐯 - 𝐰 = 0 \in 𝑈

(a) Assume that $𝐯 + 𝐰 \in 𝑈$ ; we show that $𝐯 - 𝐰 \notin 𝑈$ . Suppose instead that $𝐯 - 𝐰 \in 𝑈$ . Since $𝑈$ is closed under addition (Theorem 1.4.3), it contains

(𝐯 + 𝐰) + (𝐯 - 𝐰) = 𝐯 + 𝐯 = (1 + 1) 𝐯,

using (A1)–(A4) to cancel $𝐰$ , then (A5) and (A8). Since $1 + 1 \neq 0$ , closure under scalar multiplication gives ${(1 + 1)}^{- 1} ((1 + 1) 𝐯) =$ $𝐯 \in$ $𝑈$ by (A6) and (A5), contradicting $𝐯 \notin 𝑈$ . So $𝐯 - 𝐰 \notin 𝑈$ , and the disjunction holds.

(b) Take $𝑉 = 𝔽_{2}$ , regarded as a vector space over itself, $𝑈 = {0}$ , and $𝐯 = 𝐰 = 1$ . Then $𝐯 \notin 𝑈$ , but $𝐯 + 𝐰 = 1 + 1 = 0 \in 𝑈$ and $𝐯 - 𝐰 = 0 \in 𝑈$ . The proof of (a) breaks exactly at the division by $1 + 1$ .

Exercise 1.7.14.standard Show that there is no field

𝐹

, and no scalar multiplication

𝐹 \times ℤ \to ℤ

, that make

ℤ

with its usual addition a vector space over

𝐹

. (Exercise 1.2.46 treated the fields

𝔽_{𝑝}

Solution.

Uses. Definition 1.2.1 (Vector space), Proposition 1.2.27 (Uniqueness of the zero vector), Proposition 1.2.32 (The scalar zero), Example 1.2.39 (When does $𝐯 = - 𝐯$ force $𝐯 = 𝟎$ ?)

Techniques. Proving from axioms (Technique 1.1.7)

Hint 1. The scalar multiplication is unknown, so look for a consequence of the axioms that involves only the addition. Example 1.2.39 computed

𝐯 + 𝐯 = (1 + 1) 𝐯

Hint 2. Split into the cases

1 + 1 = 0

and

1 + 1 \neq 0

𝐹

. In the second case, consider the vector

{(1 + 1)}^{- 1} ⊙ 1

, where

1 \in ℤ

Sketch. Write

𝑒 = 1 + 1 \in 𝐹

. In every vector space,

𝐯 + 𝐯 = 𝑒 𝐯

. If

𝑒 = 0

, then

𝐯 + 𝐯 = 𝟎

for all

𝐯

, but

1 + 1 = 2 \neq 0

ℤ

. If

𝑒 \neq 0

, then

𝐱 = 𝑒^{- 1} ⊙ 1

satisfies

𝐱 +

𝐱 =

𝑒 ⊙ (𝑒^{- 1} ⊙ 1) =

1

, but no integer

𝑥

has

𝑥 + 𝑥 = 1

Suppose, for contradiction, that some field $𝐹$ and some scalar multiplication $⊙$ make $ℤ$ , with its usual addition, a vector space over $𝐹$ . Its zero vector is the integer $0$ , the unique element with $𝑛 + 0 = 𝑛$ for all $𝑛$ . Write $𝑒 = 1 + 1 \in 𝐹$ . For every integer $𝑛$ , by (A5) and (A8),

𝑛 + 𝑛 = 1 ⊙ 𝑛 + 1 ⊙ 𝑛 = (1 + 1) ⊙ 𝑛 = 𝑒 ⊙ 𝑛 .

Case $𝑒 = 0$ . Then $𝑛 + 𝑛 = 0 ⊙ 𝑛 = 0$ for every $𝑛$ , by Proposition 1.2.32. But $1 + 1 = 2 \neq 0$ in $ℤ$ .

Case $𝑒 \neq 0$ . Let $𝑥 = 𝑒^{- 1} ⊙ 1 \in ℤ$ . By the display, (A6), and (A5),

𝑥 + 𝑥 = 𝑒 ⊙ (𝑒^{- 1} ⊙ 1) = (𝑒 𝑒^{- 1}) ⊙ 1 = 1 ⊙ 1 = 1 .

But $𝑥 + 𝑥 = 2 𝑥$ is even for every integer $𝑥$ , so it is not $1$ .

Both cases are impossible, so no such $𝐹$ and $⊙$ exist. The argument never examined a particular scalar multiplication. It used a consequence of the axioms, $𝐯 + 𝐯 = (1 + 1) 𝐯$ , that every candidate must satisfy and that mentions the scalar multiplication only through the field, and it showed that the addition of $ℤ$ is incompatible with both possible values of $1 + 1$ .

Exercise 1.7.15.routine Prove or disprove: every subspace of

𝐹^{2}

is the solution set

{(𝑥, 𝑦) \in 𝐹^{2} | 𝑎 𝑥 + 𝑏 𝑦 = 0}

of a single equation, for some

𝑎, 𝑏 \in 𝐹

. If the claim is false, find the subspaces for which it holds, and prove that it holds for them.

Solution.

Uses. Theorem 1.4.25 (The subspaces of $𝐹^{2}$ ), Definition 1.3.10 (Span)

Techniques. Try small cases and small fields (Technique 1.2.38), Finding counterexamples and minimal examples (Technique 1.4.18), Double containment (Technique 1.3.14)

Hint 1. Test the smallest subspace first.

Hint 2. By Theorem 1.4.25, the other subspaces are

𝐹^{2}

and the lines

span ((𝑝, 𝑞))

with

(𝑝, 𝑞) \neq 𝟎

. For a line, the equation

𝑞 𝑥 - 𝑝 𝑦 = 0

is a natural guess; prove the equality by double containment, splitting into the cases

𝑝 \neq 0

and

𝑝 = 0

Sketch. False for

{𝟎}

: if

(𝑎, 𝑏) = 𝟎

the solution set is

𝐹^{2}

, and otherwise it contains

(- 𝑏, 𝑎) \neq 𝟎

. True for every other subspace:

𝐹^{2}

is the solution set of

0 𝑥 + 0 𝑦 = 0

, and

span ((𝑝, 𝑞))

is that of

𝑞 𝑥 - 𝑝 𝑦 = 0

. Every multiple of

(𝑝, 𝑞)

satisfies the equation, and a solution

(𝑥, 𝑦)

(𝑥 / 𝑝) (𝑝, 𝑞)

𝑝 \neq 0

, or

(𝑦 / 𝑞) (𝑝, 𝑞)

𝑝 = 0

The claim is false, and the smallest subspace is the counterexample. Let $𝑎, 𝑏 \in 𝐹$ and let $𝑆$ be the solution set of $𝑎 𝑥 + 𝑏 𝑦 = 0$ . If $𝑎 = 𝑏 = 0$ , then $𝑆 = 𝐹^{2}$ . Otherwise $(- 𝑏, 𝑎) \neq 𝟎$ and $𝑎 (- 𝑏) + 𝑏 𝑎 = 0$ , so $𝑆$ contains a nonzero vector. Either way $𝑆 \neq {𝟎}$ , so ${𝟎}$ is not the solution set of a single equation. (It is the solution set of the two equations $𝑥 = 0$ and $𝑦 = 0$ .)

Every other subspace is. By Theorem 1.4.25, the subspaces other than ${𝟎}$ are $𝐹^{2}$ , which is the solution set of $0 𝑥 + 0 𝑦 = 0$ , and the lines $𝐿 = span ((𝑝, 𝑞))$ with $(𝑝, 𝑞) \neq 𝟎$ . We show that $𝐿 = 𝑆$ for the equation $𝑞 𝑥 - 𝑝 𝑦 = 0$ , by double containment.

$𝐿 \subseteq 𝑆$ . A vector of $𝐿$ is $(𝑐 𝑝, 𝑐 𝑞)$ for some $𝑐 \in 𝐹$ , and $𝑞 (𝑐 𝑝) -$ $𝑝 (𝑐 𝑞) =$ $0$ .

$𝑆 \subseteq 𝐿$ . Let $(𝑥, 𝑦)$ satisfy $𝑞 𝑥 = 𝑝 𝑦$ . If $𝑝 \neq 0$ , then $𝑦 = 𝑞 𝑥 / 𝑝$ , and $(𝑥, 𝑦) =$ $(𝑥 / 𝑝) (𝑝, 𝑞) \in$ $𝐿$ . If $𝑝 = 0$ , then $𝑞 \neq 0$ , and $𝑞 𝑥 = 0$ forces $𝑥 = 0$ ; then $(𝑥, 𝑦) =$ $(0, 𝑦) =$ $(𝑦 / 𝑞) (0, 𝑞) =$ $(𝑦 / 𝑞) (𝑝, 𝑞) \in$ $𝐿$ .