Index of techniques

When objects are defined by axioms, as fields are here and vector spaces will be in Section 1.2, the only facts available are the axioms and what has already been proved from them. A fact that is obvious for real numbers is not available until it is proved, because a general field need not look like $ℝ$.

The move is to write the argument as a chain of equalities that changes one thing at a time, and to justify each link by the axiom or earlier result it uses. Watch for steps that move a term past another (commutativity) or regroup (associativity): in $ℝ$ we make these without noticing.

Reach for it whenever the hypotheses are an axiom system and the claim is an identity or an elementary property. If you are stuck, ask which axioms can connect the objects in the claim. For example, distributivity is the only axiom that involves both $+$ and $\cdot$, so any fact relating $0$ (an additive object) to multiplication must go through it. The canonical example is $0𝑎=0$ (Proposition 1.1.15).

To show that at most one object has a property $𝑃$, suppose $𝑥$ and ${𝑥}^{\prime }$ both have $𝑃$ and prove $𝑥={𝑥}^{\prime }$. Usually one evaluates a single well-chosen expression in two ways, once using that $𝑥$ has $𝑃$ and once using that ${𝑥}^{\prime }$ has $𝑃$.

Reach for it whenever a claim says “the”, “unique”, or “exactly one”. Existence and uniqueness are separate claims: prove existence by producing an object, and uniqueness by this technique. The canonical example is the uniqueness of $0$ in Theorem 1.1.9, where the expression is $0+0^{\prime }$.

Before proving a general claim, test it on the smallest examples available: the zero space, ${𝐹}^1$ and ${𝐹}^2$, and small fields, especially ${𝔽}_2$, where $1+1=0$. Small cases are where counterexamples live. When the claim survives them, the computation often shows why it is true and which hypothesis a proof must use.

Reach for it when a claim feels obvious from experience with ${ℝ}^2$, and whenever a hypothesis such as $1+1\ne 0$ or $𝑉\ne \{\mathrm{𝟎}\}$ might be needed. The canonical example is Example 1.2.39: $𝐯=-𝐯$ forces $𝐯=\mathrm{𝟎}$ over $ℝ$, but not over ${𝔽}_2$.

To prove $𝐴\subseteq 𝐵$, let $𝑥$ be an arbitrary element of $𝐴$. Unpack the definition of $𝐴$ until $𝑥$ is described concretely, manipulate that description until it matches the definition of $𝐵$, and conclude that $𝑥\in 𝐵$. Since $𝑥$ was arbitrary, $𝐴\subseteq 𝐵$.

Reach for it for every containment between sets defined by properties. Once both definitions are written out, the proof has a fixed shape: the first line is “let $𝑥\in 𝐴$”, the next uses the definition of $𝐴$, and the last uses the definition of $𝐵$. For spans, unpacking produces scalars (“let $𝐰\in span(\mathrm{ℒ︀})$, say $𝐰=$${𝑎}_1{𝐯}_1+$$\cdots +$${𝑎}_{𝑘}{𝐯}_{𝑘}$”), and repacking means exhibiting scalars. The canonical example is each half of Example 1.3.15.

To prove that two sets $𝐴$ and $𝐵$ are equal, prove $𝐴\subseteq 𝐵$ and $𝐵\subseteq 𝐴$ separately, each by Technique 1.3.13.

Reach for it whenever a claim says that two sets are equal. The two containments usually need different ideas, and one is often much easier than the other. For a span, “$span(\mathrm{ℒ︀})\subseteq 𝐵$” is a computation with an arbitrary linear combination, while “$𝐵\subseteq span(\mathrm{ℒ︀})$” requires constructing coefficients for each element of $𝐵$. A common mistake is to prove one containment carefully and forget the other (Exercise 1.3.30). The canonical example is Example 1.3.15.

To disprove a claim about all objects of some kind, a single object for which it fails is enough. Look for one by shrinking everything: the smallest space, the fewest vectors, the simplest field (Technique 1.2.38). Then read the counterexample. Ask which features made it work; often they point to the exact hypothesis under which the claim does hold, and the counterexample, run on general objects, turns into a proof.

Reach for it whenever a claim seems plausible but no proof suggests itself, and in every “prove or disprove”. The canonical example is the claim that the union of two subspaces is a subspace. It fails for the two axes of ${ℝ}^2$, since $(1,0)+(0,1)$ lies on neither (Non-example 1.4.13). The failure used only one vector of the first subspace outside the second and one vector of the second outside the first. So nested subspaces escape the counterexample, and Proposition 1.4.20 shows that only they do.

An implication “$𝑃$ implies $𝑄$” is logically equivalent to its contrapositive, “not $𝑄$ implies not $𝑃$”. Prove the contrapositive when “not $𝑄$” gives you more to work with than $𝑃$ does. The typical case is a conclusion $𝑄$ asserting that something holds for every object, or that some object is unique. Then “not $𝑄$” hands you a specific object, a counterexample or a second candidate, and you can compute with it.

Reach for it when the hypothesis is hard to use directly and the conclusion is a “for all” or a uniqueness statement. The canonical example is (II) $\Rightarrow$ (I) in Theorem 1.5.5. Statement (I) asserts uniqueness for every vector of the span. Its negation provides one vector with two different representations, and subtracting them shows that (II) fails.

When a proof needs an object with special properties, choose one that is extreme in some respect: the largest index with a nonzero coefficient, a polynomial of largest degree, a dependence relation with the fewest nonzero coefficients, a smallest counterexample. Extremality is a hypothesis you get for free. “The largest $𝑗$ with ${𝑎}_{𝑗}\ne 0$” also says that every later coefficient is $0$. “A relation with the fewest nonzero coefficients” also says that every relation with fewer nonzero coefficients is trivial.

It combines with contradiction. To show that no object has some property, suppose that some do, take an extreme one, and use it to build another object with the property that is more extreme still. This contradicts the choice.

Reach for it when a relation or a sum has many terms and the argument would be easy if most of them vanished. The canonical example is the linear dependence lemma (Lemma 1.5.10), which solves for the largest index with a nonzero coefficient. The same choice, of a largest degree, proves Proposition 1.5.24, and the contradiction form appears in Exercise 1.5.44.

Many statements are about all lists in $𝑉$, or about linear combinations of every length. To prove one, induct on the length $𝑘$. The base case is usually the empty list, where the claim tends to be immediate: $span(())=\{\mathrm{𝟎}\}$, the empty list is independent, and the empty sum is $\mathrm{𝟎}$. In the inductive step, take a list of length $𝑘+1$, produce from it a list of length $𝑘$ (by deleting a well-chosen entry, or by splitting off the last term of a sum), apply the inductive hypothesis to the shorter list, and carry the conclusion back to the original list.

Two things need care. First, the inductive hypothesis must cover every list of length $𝑘$, since the shorter list is produced by the argument and is not known in advance. Second, if the statement has hypotheses (for instance, that the list spans $𝑉$), the shorter list must satisfy them too. Deleting an arbitrary entry of a spanning list can destroy spanning, which is why the deleted entry has to be chosen (Exercise 1.6.30).

Reach for it when removing one entry or one term reduces a claim to the same claim for a shorter list. The canonical example is Theorem 1.6.10, which deletes an entry supplied by Lemma 1.5.10. The arithmetic of linear combinations (Lemma 1.3.9) was proved by splitting off the last term, and so is Proposition 1.6.19(c) below. Later, the exchange lemma (Lemma 4.1.2) and Gram–Schmidt (Algorithm 6.4.14) are built the same way.

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 $𝑎\ne 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.

To show that a map is linear, write it as a sum, scalar multiple, or composite of maps already known to be linear. By Proposition 2.1.23 and Proposition 2.1.17 the result is linear, with no computation.

Reach for it when a map is given by a formula built out of evaluations, derivatives, integrals, coordinates, projections, or other maps from the examples above. It also handles whole families at once. For instance, for $𝑇\in \mathrm{L}(𝑉)$ and ${𝑎}_0,\dots ,{𝑎}_{𝑛}\in 𝐹$, every ${𝑎}_0{\text{id}}_{𝑉}+$${𝑎}_1𝑇+$$\cdots +$${𝑎}_{𝑛}{𝑇}^{𝑛}$ is linear. Conversely, a formula that involves a product of two inputs, a constant term, or a nonlinear function of a coordinate is a candidate for a counterexample; test $𝑇(\mathrm{𝟎})$ and $𝑇(2𝐯)$ first. The canonical example is the reflection ${𝑆}_{\ell }=2{Pr}_{\ell }-{\text{id}}_{{ℝ}^2}$ (Example 2.1.27).

To produce a linear map with some property, choose a basis of the domain that is adapted to the property, decide where each basis vector should go, and let Theorem 2.2.1 extend the choice to a linear map. Linearity then costs nothing, and the property itself can usually be checked on the basis (Technique 2.2.7). If a formula is wanted, write a general vector in the chosen basis and apply (2.2.1).

Reach for it when the property is easy to state on special vectors (vectors to be fixed, sent to $\mathrm{𝟎}$, swapped, or scaled), or when all you need is that some linear map with a given behaviour exists, as when building a counterexample. The canonical example is the projection and reflection of Example 2.2.3. Another is that a subspace is the image of one linear map and the set of vectors sent to $\mathrm{𝟎}$ by another (Exercise 2.2.35).

To prove that two linear maps $𝑆,𝑇:𝑉\to 𝑊$ are equal, it is enough to check $𝑆({𝐯}_{𝑖})=𝑇({𝐯}_{𝑖})$ for the vectors of a basis of $𝑉$, or of any spanning list (Corollary 2.2.6). Many statements can be put in this form. An identity such as ${𝑃}^2=𝑃$, $𝑆𝑇=𝑇𝑆$, or $𝑇=𝑎\text{id}+𝑏𝑅$ is an equation between linear maps, because sums, scalar multiples, and composites of linear maps are linear (Proposition 2.1.23, Proposition 2.1.17). A containment $𝑇(𝑉)\subseteq 𝑈$, for a subspace $𝑈$ of $𝑊$, holds as soon as $𝑇({𝐯}_{𝑖})\in 𝑈$ for every vector of a spanning list, because $𝑇(𝑉)$ is the span of the $𝑇({𝐯}_{𝑖})$ (Proposition 2.1.16).

Reach for it when the basis vectors are easy to compute with, typically for a basis on which the maps involved act simply, and when a computation at a general vector would be messy. Before using it, make sure that both sides really are linear in the vector. A condition such as “$𝑇(𝐯)$ is a multiple of $𝐯$” is not an equation between linear maps, and it can hold on a basis without holding everywhere (Exercise 2.2.25). The canonical example is Corollary 2.2.6 itself.

A linear map between spaces with chosen bases and its matrix carry the same information, so a question about one can be translated into a question about the other, using the dictionary above.

In one direction, to compute with a linear map, replace vectors by their coordinate vectors and the map by its matrix. Evaluating $𝑇$ becomes a matrix–vector product, and an equation $𝑇(𝐯)=𝐰$ becomes the linear system ${[𝑇]}_{\mathrm{𝒞︀}\mathrm{ℬ︀}}𝐱=$${[𝐰]}_{\mathrm{𝒞︀}}$ in the unknown coordinates $𝐱$ of $𝐯$ (Section 3.1). In the other direction, to prove a statement about a matrix $𝐴$, read it as a statement about the linear map ${𝑇}_{𝐴}$, prove it with the theory of linear maps, which needs no indices, and translate back with the uniqueness in Proposition 2.3.17.

Reach for the first direction when you need numbers, and for the second when a matrix identity would otherwise need a computation with indices. A rule of thumb: compute with matrices, prove with maps. Before translating, fix the bases and keep track of which basis each coordinate vector refers to; most errors come from mixing them up. The canonical example is Example 2.3.28. Later instances: matrix multiplication is defined by translating composition (Section 2.4), the rank of a matrix is the rank of its map (Section 4.2), and the determinant and the eigenvalues of an operator are read off from its matrix in any basis (Section 5.4, Section 7.3).

To prove an identity between matrices, show that the $(𝑖,𝑗)$ entries of the two sides agree for all $𝑖$ and $𝑗$. Write each entry of a product with Proposition 2.4.8(a), using a new summation index for every product, then rearrange: pull constant factors out of sums, exchange the order of two finite sums, ${\sum }_{𝑘}{\sum }_{𝑙}={\sum }_{𝑙}{\sum }_{𝑘}$, and collapse sums containing a Kronecker delta, ${\sum }_{𝑘}{𝛿}_{𝑖𝑘}{𝑥}_{𝑘}=$${𝑥}_{𝑖}$.

Reach for it when the statement is about the entries themselves (transposes, traces, triangular or block shapes), or when there is no linear map in sight, for example for matrices whose entries are integers, polynomials, or other matrices. Two things go wrong in practice. Reusing a summation index in a nested sum silently identifies two different indices. And moving a factor past another needs commutativity of the entries, which holds for scalars but not for blocks (Section 2.4.8). The canonical example is the second proof of associativity below.

The trace is linear, and it does not see the order of two factors: $tr(𝐴𝐵)=tr(𝐵𝐴)$, so $tr({𝐴}_1{𝐴}_2\cdots {𝐴}_{𝑘})$ is unchanged by rotating the factors cyclically. Take the trace of both sides of a claimed identity. If the traces differ, the identity is false; and quantities such as $𝐴𝐵-𝐵𝐴$, which are invisible to the trace, can be eliminated.

Reach for it when commutators $𝐴𝐵-𝐵𝐴$ appear (they always have trace $0$), when a product is conjugated as in ${𝑆}^{-1}𝐴𝑆$ (once inverses are available, $tr({𝑆}^{-1}𝐴𝑆)=$$tr(𝐴𝑆{𝑆}^{-1})=$$tr𝐴$, which makes the trace a similarity invariant, Section 4.5), and when an inner product of matrices is written as $tr({𝐵}^{\text{𝖳}}𝐴)$ (Section 6.1). Only cyclic rotations are allowed: $tr(𝐴𝐵𝐶)$ and $tr(𝐵𝐴𝐶)$ differ in general. And the trace detects nothing about a matrix of trace $0$; it is a single number, so it can rule things out but rarely proves them. The canonical example is Proposition 2.4.30.

Split matrices into blocks that match the structure of the problem, and compute with the blocks as if they were entries (Theorem 2.4.34). Typical splittings: off a single first row and column, to set up an induction on the size; along a basis that is split into two parts, for example a basis of a subspace extended to a basis of the whole space; or around a block of zeros or a copy of $𝐼$.

Reach for it when a matrix has large zero or identity blocks, when an argument should reduce from size $𝑛$ to size $𝑛-1$, or when a statement concerns a map that preserves a subspace. Two checks: the partitions must match, and products of blocks must keep their order. The canonical example is Proposition 2.4.36. Later it computes determinants of block triangular matrices (Section 5.4), compares $𝐴𝐵$ with $𝐵𝐴$ (Section 7.3), and organizes the generalized eigenspace decomposition and the Jordan form (Section 10.2, Section 10.3).

To show that $𝑇$ is invertible and to identify ${𝑇}^{-1}$, produce a candidate $𝑆$ and verify $𝑆𝑇=\text{id}$ and $𝑇𝑆=\text{id}$. Then $𝑇$ is invertible and $𝑆={𝑇}^{-1}$, by the uniqueness in Theorem 2.5.10. How the candidate was found plays no role in the proof.

Candidates come from undoing: to undo a rotation by $𝜃$, rotate by $-𝜃$, and to undo a composite, undo its steps in reverse order. A polynomial identity also produces one: if ${𝑇}^2+𝑇=\text{id}$, then $𝑇(𝑇+\text{id})=$$\text{id}=$$(𝑇+\text{id})𝑇$, and if ${𝑁}^{𝑘}=0$, then $(\text{id}-𝑁)(\text{id}+𝑁+\cdots +{𝑁}^{𝑘-1})=$$\text{id}-$${𝑁}^{𝑘}=$$\text{id}$, which is the geometric series $1/(1-𝑥)=$$1+$$𝑥+$${𝑥}^2+$$\cdots$ cut off (Exercise 2.5.39). Heuristics of this kind may be as informal as you like, because the verification is what proves the result.

Check both products, unless you already know that $𝑇$ has an inverse on the other side. One product shows only that $𝑆$ is a one-sided inverse, and one-sided inverses need not be two-sided (Example 2.5.24). The canonical example is Proposition 2.5.17.

To prove that a linear map $𝑇$ is injective, take a vector $𝐯$ with $𝑇(𝐯)=\mathrm{𝟎}$ and show that $𝐯=\mathrm{𝟎}$ (Theorem 2.6.11). This replaces a statement about all pairs of vectors by a statement about one equation, and $𝑇(𝐯)=\mathrm{𝟎}$ is usually the easiest equation to analyze. To prove that $𝑇$ is not injective, exhibit a single nonzero vector of $ker𝑇$.

The same move is how injectivity gets used. A relation ${𝑎}_1𝑇({𝐯}_1)+$$\cdots +$${𝑎}_{𝑘}𝑇({𝐯}_{𝑘})=$$\mathrm{𝟎}$ can be pulled back through $𝑇$: by linearity it says $𝑇({𝑎}_1{𝐯}_1+\cdots +{𝑎}_{𝑘}{𝐯}_{𝑘})=$$\mathrm{𝟎}$, and if $𝑇$ is injective, then ${𝑎}_1{𝐯}_1+$$\cdots +$${𝑎}_{𝑘}{𝐯}_{𝑘}=$$\mathrm{𝟎}$.

Reach for it whenever injectivity of a linear map is to be proved or used. Check linearity first: for other functions the test proves nothing, as $𝑥\mapsto {𝑥}^2$ shows. The canonical example is Example 2.6.13.

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

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

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

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

To decide whether an object with prescribed properties exists, and to find all such objects, write the unknown object in terms of unknown scalars, the undetermined coefficients, and translate each requirement into an equation in those scalars. When the requirements are linear in the scalars, the result is a linear system, and the question becomes whether that system is consistent and what its solution set is.

Reach for it whenever you are asked whether a vector is a linear combination of given vectors, whether a list is linearly independent, or whether a polynomial or a linear map with given properties exists. Membership of $𝐰$ in $span({𝐯}_1,\dots ,{𝐯}_{𝑘})$ is the system ${𝑐}_1{𝐯}_1+$$\cdots +$${𝑐}_{𝑘}{𝐯}_{𝑘}=$$𝐰$ in the unknowns ${𝑐}_{𝑖}$. Linear independence of ${𝐯}_1,\dots ,{𝐯}_{𝑘}$ asks whether the homogeneous system ${𝑐}_1{𝐯}_1+$$\cdots +$${𝑐}_{𝑘}{𝐯}_{𝑘}=$$\mathrm{𝟎}$ has only the trivial solution. The canonical example is Example 3.1.10.

To find every solution of a linear equation $𝑇(𝐱)=𝐲$, find one solution ${𝐱}_0$, called a particular solution, and all solutions of the homogeneous equation $𝑇(𝐳)=\mathrm{𝟎}$. Every solution is ${𝐱}_0+𝐳$ for exactly one such $𝐳$. This splits the problem in two: existence of a solution depends on $𝐲$, while the shape of the solution set, and in particular uniqueness, depends on $ker𝑇$ alone.

Reach for it whenever you need all solutions of a linear problem, such as a linear system, a linear recurrence, or a linear differential equation, and whenever you need to show that a solution is unique: a solution, if one exists, is unique exactly when the homogeneous equation has only the trivial solution. The canonical example is Proposition 3.1.19.

The transpose turns the rows of a matrix into the columns of ${𝐴}^{\text{𝖳}}$, and it reverses products: ${(𝐴𝐵)}^{\text{𝖳}}={𝐵}^{\text{𝖳}}{𝐴}^{\text{𝖳}}$ (Proposition 2.4.23). So a statement about the rows of $𝐴$, or about left multiplication, becomes a statement about the columns of ${𝐴}^{\text{𝖳}}$, or about right multiplication, once everything is transposed. Prove whichever version is easier, and transpose to get the other.

Reach for it whenever you have a result about rows and need its mirror image about columns, or the other way around. The canonical example is Proposition 3.2.28, where column operations come from row operations. Later instances are the equality of row rank and column rank (Section 4.3) and $det{𝐴}^{\text{𝖳}}=det𝐴$, which makes every column property of the determinant a row property too (Section 5.4).

To prove that something exists, it is often enough to give a procedure that builds it. Two things then have to be proved about the procedure.

Termination. Find a quantity that moves in one direction at every step and cannot do so forever, such as a nonnegative integer that decreases, or an integer that increases and is bounded above. (Such a quantity is sometimes called a monovariant.)

Correctness. Find an invariant: a statement about the current state that is true at the start and that each step keeps true. When the procedure halts, the invariant together with the reason for halting gives the property of the output. Formally this is induction on the number of steps.

The art is in choosing the invariant. The property we want at the end is rarely preserved step by step on its own, and usually has to be strengthened, by adding facts about the intermediate states, until it is. Reach for this technique whenever a result says that some reduction is always possible (“every matrix can be brought to the form …”, “the process ends with …”). The canonical example is Gauss–Jordan elimination: termination is Proposition 3.3.6, and the invariant is Lemma 3.3.7. Later examples are Gram–Schmidt orthogonalization (Section 6.4) and the Euclidean algorithm for polynomials (Section 7.1); Exercise 3.2.54 is a small one.

Many properties of a matrix $𝐴$ do not change when $𝐴$ is replaced by $𝐺𝐴$ with $𝐺$ invertible: for example, the kernel $ker{𝑇}_{𝐴}$ (Corollary 3.2.23), the linear relations among the columns (Corollary 3.2.17), and, for square $𝐴$, invertibility. To decide such a property, replace $𝐴$ by $rref(𝐴)=𝐺𝐴$ (Theorem 3.3.10), where the answer can be read off the pivots and the zero rows. Two things have to be checked: that the property really is unchanged by left multiplication by invertible matrices, and what the property says about a matrix in RREF.

Reach for it whenever a question about $𝐴$ is really about $ker{𝑇}_{𝐴}$, about relations among the columns of $𝐴$, or about solutions of $𝐴𝐱=𝐲$ (where $𝐲$ must be replaced by $𝐺𝐲$, Proposition 3.2.14). The canonical example is Theorem 3.3.23. It is the method of Section 3.4 and Section 3.5, and later of rank–nullity (Section 4.2) and of the equality of row rank and column rank (Section 4.3).

To show that a linear problem has a solution for every choice of data, it can be much easier to show that it has at most one. This works whenever the problem is a square linear system, with as many conditions as unknowns: by Corollary 3.4.20, if the homogeneous problem has only the zero solution, then every instance of the problem has exactly one solution. Uniqueness is usually the easier half because it is a statement about the homogeneous problem, where all data vanish, and it amounts to showing that some object is zero, often by a structural argument (a polynomial with too many roots, a maximum principle) rather than by computation. Existence then comes for free, without ever constructing a solution.

The setup has two requirements: the conditions are linear in the unknowns, and the number of conditions equals the number of unknowns. With those in place, the one thing left to prove is uniqueness itself, namely that the homogeneous problem has only the zero solution. Counting conditions and unknowns alone proves nothing (Exercise 3.6.14). Reach for it when existence looks hard and uniqueness looks easy, typically for interpolation-type problems (find an object of a given size with prescribed values) and for discrete boundary value problems such as Exercise 3.1.47. The canonical example is polynomial interpolation (Theorem 3.4.24). Section 4.2 extends it from square matrices to linear maps $𝑉\to 𝑊$ with $dim𝑉=dim𝑊$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A matrix of rank one is $𝐮{𝐯}^{\text{𝖳}}$ with $𝐮,𝐯\ne \mathrm{𝟎}$ (Proposition 4.3.16). In this form products collapse to scalars, because ${𝐯}^{\text{𝖳}}𝐰$ is a $1\times 1$ matrix and can be moved out of the way:

Reach for it when a hypothesis says that a matrix has rank one, when a matrix differs from a known one by a rank-one matrix (as ${𝐼}_{𝑛}+𝐮{𝐯}^{\text{𝖳}}$ or $𝐴+𝐮{𝐯}^{\text{𝖳}}$ do), and when a matrix is to be split into simple pieces. The canonical example is Proposition 4.3.16, and Example 4.3.18 shows the collapse at work. Later instances are the matrix determinant lemma for $det(𝐴+𝐮{𝐯}^{\text{𝖳}})$ (Theorem 5.5.27) and the singular value decomposition, which writes every matrix as a sum of rank-one pieces in the best possible way (Section 9.1).

In a direct sum, an equation between decompositions splits into one equation per summand. If ${𝐮}_1+$$\cdots +$${𝐮}_{𝑘}=$${𝐮}_1^{\prime }+$$\cdots +$${𝐮}_{𝑘}^{\prime }$ with ${𝐮}_{𝑖},{𝐮}_{𝑖}^{\prime }\in {𝑈}_{𝑖}$ and the sum is direct, then ${𝐮}_{𝑖}={𝐮}_{𝑖}^{\prime }$ for every $𝑖$. This is the analogue of comparing coefficients with respect to a basis. To use it, sort every term of an equation into the summand it belongs to, then read off the components one at a time.

Proving that a sum is direct runs the same move backwards. Take two decompositions of one vector, subtract them, and move terms across so that the two sides of the resulting equation lie in different subspaces. Then both sides lie in the intersection, and if the intersection is $\{\mathrm{𝟎}\}$, both sides vanish. For two subspaces this is the whole argument: $𝐮+𝐰={𝐮}^{\prime }+{𝐰}^{\prime }$ gives $𝐮-$${𝐮}^{\prime }=$${𝐰}^{\prime }-$$𝐰\in$$𝑈\cap$$𝑊$.

Reach for it whenever a vector is given as a sum of pieces from known subspaces. The canonical example is Theorem 4.4.7. Later uses include orthogonal decompositions (Section 6.4), the independence of eigenvectors with distinct eigenvalues (Section 7.2), and the generalized eigenspace decomposition (Section 10.2).

To prove a statement about $𝑘$ subspaces ${𝑈}_1,\dots ,{𝑈}_{𝑘}$, group the first $𝑘-1$ of them into $𝑆={𝑈}_1+\cdots +{𝑈}_{𝑘-1}$ and treat $𝑆+{𝑈}_{𝑘}$ as a sum of two subspaces. Proposition 4.4.2(a) says that $𝑆+{𝑈}_{𝑘}$ is the whole sum, and Proposition 4.4.9 says that it is direct exactly when $𝑆$ is direct and $𝑆\cap {𝑈}_{𝑘}=\{\mathrm{𝟎}\}$. So the two-subspace case and the inductive hypothesis for $𝑆$ combine into the case of $𝑘$ subspaces.

Reach for it when the statement for two subspaces is easy, typically because it reduces to $𝑈\cap 𝑊=\{\mathrm{𝟎}\}$, and the general case looks messy. Watch the hypothesis in the inductive step: it needs $𝑆\cap {𝑈}_{𝑘}=\{\mathrm{𝟎}\}$, an intersection with a sum, and not just ${𝑈}_{𝑖}\cap {𝑈}_{𝑘}=\{\mathrm{𝟎}\}$ for each $𝑖<𝑘$ (Non-example 4.4.6(b)). The canonical example is the second proof of Theorem 4.4.7. The same induction shows that eigenspaces for distinct eigenvalues are independent (Section 7.2).

When $𝑉={𝑈}_1\oplus \cdots \oplus {𝑈}_{𝑘}$, choose a basis of each ${𝑈}_{𝑖}$ and concatenate. The result is a basis of $𝑉$ (Theorem 4.4.13) adapted to the decomposition: each basis vector lies in one summand, so the coordinates of a vector split into blocks, one block for each component. In the other direction, to show that subspaces are independent, it suffices to check that bases of them concatenate to an independent list, or just to compare dimensions.

Reach for it to compute the dimension of a direct sum, or to turn a statement about subspaces into one about lists. The canonical example is Theorem 4.4.13. Later, a basis glued from bases of eigenspaces is an eigenbasis (Section 7.4), and Jordan bases are glued from chains (Section 10.3).

To decompose $𝑉$ as a direct sum, look for an operator $𝑃$ with ${𝑃}^2=𝑃$. Then $𝑉=im𝑃\oplus ker𝑃$, every vector splits as $𝐯=$$𝑃(𝐯)+$$(𝐯-𝑃(𝐯))$, and $im𝑃$ is the set of vectors that $𝑃$ fixes (Theorem 4.4.27). In the other direction, every decomposition $𝑉=𝑈\oplus 𝑊$ comes with its projections, and statements about decompositions become algebra of operators: ${𝑃}^2=𝑃$, $𝑃+𝑄={\text{id}}_{𝑉}$, $𝑃𝑄=𝑄𝑃=0$.

Reach for it when a formula suggests “the part of $𝐯$ that …”, such as the symmetric part $(𝐴+{𝐴}^{\text{𝖳}})/2$ of a matrix, or more generally the average of $𝐯$ and $𝑇(𝐯)$ for an operator with ${𝑇}^2={\text{id}}_{𝑉}$ (Exercise 4.4.43). Each is $𝑃(𝐯)$ for an idempotent $𝑃$. The canonical example is Theorem 4.4.27. Later, idempotent matrices over $\mathbb{Q}$, $ℝ$, $ℂ$ have trace equal to rank (Exercise 4.3.43), and orthogonal projections are the idempotents that are self-adjoint (Section 6.6).

An isomorphism $𝑇:𝑉\to 𝑊$ carries every statement about $𝑉$ that is phrased in terms of the vector space operations (independence, span, bases, subspaces and their dimensions, kernels and images of linear maps) to the corresponding statement about $𝑊$, and back. So to answer such a question about an unfamiliar space, transport it along an isomorphism to a space where it is easier, answer it there, and transport the answer back.

Reach for it when the space is made of polynomials, matrices, functions, or linear maps, and the question only involves linear structure. The usual target is ${𝐹}^{𝑛}$, through coordinates: Proposition 1.6.20 was an early instance, and Theorem 4.5.6 says that every $𝑛$-dimensional space can be transported to ${𝐹}^{𝑛}$. The canonical example is the computation of $dim\mathrm{L}(𝑉,𝑊)$ below, which transports the question to matrices. Be careful to transport only statements made of the linear operations: a property such as “every entry is positive” or “the polynomial has a root” is not preserved by isomorphisms.

To show that $𝐴$ and $𝐵$ are not similar, find a similarity invariant on which they differ: trace, rank, rank of a power ${𝐴}^{𝑘}$, rank of $𝐴-𝑐{𝐼}_{𝑛}$ for a well-chosen $𝑐$, and later the determinant and the characteristic polynomial. To show that they are similar, invariants are not enough: produce an $𝑆$ with $𝐴𝑆=𝑆𝐵$, usually by finding a basis in which the operator ${𝑇}_{𝐴}$ has matrix $𝐵$ (Theorem 4.5.25).

Reach for the cheapest invariants first. Trace and rank take seconds. If they agree, look for a structural difference: is one matrix nilpotent, or a scalar multiple of ${𝐼}_{𝑛}$, or does $𝐴-𝑐{𝐼}_{𝑛}$ drop rank for some $𝑐$ where $𝐵-𝑐{𝐼}_{𝑛}$ does not? The canonical example is Remark 4.5.28.

Many statements about a linear map $𝑇$ (or a matrix $𝐴$) are invariant under change of basis: they hold for one matrix of $𝑇$ if and only if they hold for all of them, or for $𝐴$ if and only if they hold for $𝐺𝐴𝐻$ (or for ${𝑆}^{-1}𝐴𝑆$). To prove such a statement, first check this invariance, then choose bases in which the matrix is as simple as possible, prove the statement there, and transport the conclusion back.

For maps between two spaces, the best possible matrix is the rank normal form ${𝑁}_{𝑟}$ (Corollary 4.5.22), and in matrix language this says: to prove something about $𝐴$ that survives $𝐴\mapsto 𝐺𝐴𝐻$, assume $𝐴={𝑁}_{𝑟}$. For operators, the bases must agree on both sides, and the convenient bases come from the operator itself: bases adapted to a subspace that $𝑇$ preserves (below), bases of the form $𝐯,𝑇𝐯,{𝑇}^2𝐯,\dots$ (Exercise 4.5.50, Exercise 4.5.43), and later bases of eigenvectors (Section 7.4) and triangularizing bases (Section 7.5).

If $𝑇$ maps a subspace $𝑈$ into itself, take a basis of $𝑈$ and extend it to a basis of $𝑉$ (Theorem 4.1.16). In this basis the matrix of $𝑇$ is block upper triangular (Proposition 4.5.35), the top left block is the matrix of $𝑇$ on $𝑈$, and a question about $𝑇$ splits into a question about $𝑇$ on $𝑈$ and one about the bottom right block. If $𝑉$ is assembled from several preserved subspaces, list bases of each in turn, and the matrix becomes block diagonal.

Reach for it when you can see a subspace that $𝑇$ preserves: a kernel or image of something commuting with $𝑇$, the span of a vector fixed or scaled by $𝑇$, or the span of $𝐯,𝑇𝐯,\dots ,{𝑇}^{𝑘}𝐯$. It is the first step of triangularization (Section 7.5) and of the Jordan form (Section 10.3).

Objects such as cosets are handled through representatives: a coset is named by any one of its elements, and a function on cosets is defined by a formula in that element, $𝑓(𝐯+𝑈)=𝑔(𝐯)$. Such a formula defines a function only if every name of the same coset gives the same value. So the first thing to prove about it is

which by Lemma 4.6.14 means: if $𝐯-{𝐯}^{\prime }\in 𝑈$, then $𝑔(𝐯)=𝑔({𝐯}^{\prime })$. One says that $𝑓$ is well defined.

Mind the direction. Equal inputs must give equal outputs. The converse, that equal outputs force equal inputs, is injectivity, which is a different property that $𝑓$ may or may not have (Exercise 4.6.43).

Reach for it whenever an object is defined through a choice: of a representative, a basis, a preimage, an extension. The canonical example is Theorem 4.6.22. The same check appeared in Exercise 2.6.43, where a map was defined on preimages, and in Proposition 4.2.15, which shows that the rank of a matrix of $𝑇$ does not depend on the bases. It returns when the determinant of an operator is defined through any one of its matrices (Section 5.4).

When a construction only depends on vectors up to elements of a subspace $𝑈$, replace $𝑉$ by $𝑉/𝑈$. By Theorem 4.6.30, a linear map that kills $𝑈$ is the same as a linear map on $𝑉/𝑈$, and by Theorem 4.6.27 and Proposition 4.6.28, dimensions split as $dim𝑉=$$dim𝑈+$$dim(𝑉/𝑈)$. Two typical uses:

• Make a map injective. Dividing out exactly the kernel turns $𝑇$ into an injective map with the same image. This is the first isomorphism theorem (Theorem 4.6.34), and it is the standard way to show that some space is isomorphic to an image.
• Split a problem in two. If an operator $𝑇$ maps $𝑈$ into itself, it acts on $𝑈$ and on $𝑉/𝑈$ (Proposition 4.6.32), and a statement about $𝑇$ often follows from the same statement for these two smaller operators, by induction on $dim𝑉$. Section 7.5 triangularizes operators this way.

The price is the well-definedness check (Technique 4.6.18) for every map defined on cosets.

An affine subspace has no origin of its own, but by Proposition 4.7.3(b) any of its points can serve as one. Once a point $𝐚\in 𝐸$ is fixed, $𝐱\mapsto 𝐱-𝐚$ carries $𝐸$ onto the subspace $𝑈=𝐸-𝐚$, and statements about $𝐸$ become statements about $𝑈$, where linear algebra applies. Every point of $𝐸$ works equally well, so choose the most convenient one, such as a point that two affine subspaces have in common, or a fixed point of a map.

Reach for it whenever an affine question has a linear counterpart that you already know how to answer. The canonical example is Proposition 4.7.10. The same move drives Theorem 4.7.14, Proposition 4.7.17, and Theorem 4.7.37.

To turn an affine problem into a linear one without choosing a base point, replace each point $𝐯$ by its lift $\widehat{𝐯}=(𝐯,1)$ in $𝑉\times 𝐹$, or in ${𝐹}^{𝑛+1}$ if $𝑉={𝐹}^{𝑛}$. Then

so the last coordinate records the coefficient sum. Affine combinations of points are the linear combinations of their lifts that land in the hyperplane “last coordinate $1$”, and affine dependences are the linear relations among the lifts. Row reduction, rank, and matrices then apply directly.

Reach for it when you want to treat all points symmetrically, or when you want affine maps to become matrix multiplication. The canonical example is the second approach to Proposition 4.7.20. Homogeneous coordinates (Section 4.7.6) apply the same idea to maps.

Suppose $𝐩={\sum }_{𝑖}{𝑐}_{𝑖}{𝐯}_{𝑖}$, where the coefficients are subject to constraints, such as ${𝑐}_{𝑖}\ge 0$ and ${\sum }_{𝑖}{𝑐}_{𝑖}=1$, and the ${𝐯}_{𝑖}$ satisfy a relation ${\sum }_{𝑖}{𝑑}_{𝑖}{𝐯}_{𝑖}=\mathrm{𝟎}$ that respects the equality constraints (here ${\sum }_{𝑖}{𝑑}_{𝑖}=0$). Then $𝐩=$${\sum }_{𝑖}({𝑐}_{𝑖}-𝜆{𝑑}_{𝑖}){𝐯}_{𝑖}$ for every scalar $𝜆$, and the equality constraints still hold. Increase $𝜆$ from $0$ until the first inequality constraint becomes tight. At that extremal $𝜆$ some coefficient is $0$, and its vector can be dropped. Repeat as long as a relation exists.

Reach for it to show that a representation can be chosen short, for instance using independent vectors only. It refines the argument of Theorem 1.6.10, where a redundant vector is simply discarded, to situations where the coefficients must keep their signs. The canonical example is Carathéodory’s theorem (Theorem 4.7.34).

If an argument of a multilinear function is a sum, split it: linearity in slot $𝑗$ turns $𝐷\left(\dots ,{\sum }_{𝑘}{𝑐}_{𝑘}{𝐱}_{𝑘},\dots \right)$ into ${\sum }_{𝑘}{𝑐}_{𝑘}𝐷(\dots ,{𝐱}_{𝑘},\dots )$. Doing this in several slots turns one value of $𝐷$ into a sum over all ways of choosing one term in each slot, so $𝑚$ terms in each of $𝑟$ slots give ${𝑚}^{𝑟}$ terms. Usually the terms are standard basis vectors, or other vectors on which $𝐷$ is known, and the expansion reduces $𝐷(𝐴)$ to finitely many known values. When $𝐷$ is also alternating, every term that uses the same vector in two slots vanishes, and typically most of the sum disappears.

Reach for it when you need a value of a multilinear function on general inputs and you know its values on special ones, much as a linear map is determined by its values on a basis (Technique 2.2.7). The canonical example is the $2\times 2$ determinant (Theorem 5.1.13). In Section 5.3 the same expansion, carried out in all $𝑛$ columns, produces a formula for $𝐷$ on ${𝐹}^{𝑛\times 𝑛}$.

To prove a statement $𝑃(𝑚)$ for every integer $𝑚\ge 0$, it suffices to prove $𝑃(𝑚)$ for each $𝑚$ under the assumption that $𝑃(𝑘)$ holds for every $𝑘<𝑚$. When $𝑚=0$ there is nothing to assume, so the argument must handle that case outright, but no separate base case is needed. Reach for strong induction when a reduction step replaces an object by a smaller one but you cannot say by how much it shrinks, so that induction from $𝑚-1$ to $𝑚$ does not apply. Often the main decision is the measure of size, such as the number of points a permutation moves or the degree of a polynomial.

An equivalent form is the well-ordering principle: every nonempty set of nonnegative integers has a least element. It justifies arguments that begin “let $𝑘$ be the least positive integer such that $\dots$”, and proofs by minimal counterexample. The canonical example is Proposition 5.2.13, by induction on the number of moved points. Section A.2 compares the forms of induction, and Section 7.1 uses strong induction on the degree to divide polynomials.

To show that the number of steps in a process has a determined parity, attach to each state a quantity that every step changes in a controlled way: it is multiplied by $-1$, or it changes by an odd integer. After $𝑟$ steps the quantity has been multiplied by ${(-1)}^{𝑟}$, or has changed by an amount of the same parity as $𝑟$, so the parity of $𝑟$ is determined by the initial and final states, whichever steps were taken. The same idea shows that a state cannot be reached: find a quantity that every allowed move preserves and that differs between the two states.

Reach for it when a statement is about parity, or about which configurations can be reached by repeating moves of one kind: swaps, slides, rotations. The canonical example is Lemma 5.2.20, where a product of differences ${𝑥}_{𝑗}-{𝑥}_{𝑖}$ changes sign under every transposition of the variables. Exercise 5.2.47 applies it to a classic puzzle, and Section 8.4 uses the sign of the determinant to separate rotations from reflections.

To show that a finite sum ${\sum }_{𝑥\in 𝑋}𝑡(𝑥)$ is $0$, find a bijection $𝜑:𝑋\to 𝑋$ with $𝜑(𝜑(𝑥))=𝑥$ and $𝜑(𝑥)\ne 𝑥$ for every $𝑥$, such that $𝑡(𝜑(𝑥))=$$-𝑡(𝑥)$. Then $𝑋$ splits into two-element sets $\{𝑥,𝜑(𝑥)\}$, and the two terms in each set cancel. To write this down, choose a set $𝑃\subseteq 𝑋$ containing exactly one element of each pair, so that $𝜑$ maps $𝑃$ bijectively onto $𝑋\setminus 𝑃$; then ${\sum }_{𝑥\in 𝑋}𝑡(𝑥)=$${\sum }_{𝑥\in 𝑃}(𝑡(𝑥)+𝑡(𝜑(𝑥)))=$$0$. If $𝜑$ has fixed points, and $𝑡(𝜑(𝑥))=$$-𝑡(𝑥)$ holds for the other $𝑥$, the same argument shows that the sum equals the sum over the fixed points, which is often easy to evaluate.

This is not the same as the shortcut “reindexing by $𝜑$ shows $𝑆=-𝑆$, so $𝑆=0$”. The shortcut divides by $1+1$, which is impossible in characteristic $2$, while pairing never divides. Reach for pairing when the terms of a sum come with signs and a natural operation flips the sign: for sums over ${𝑆}_{𝑛}$, composing with a fixed transposition. The canonical example is the alternation of the Leibniz formula in Theorem 5.3.4. Counting is a special case: an involution with no fixed points shows that a finite set has an even number of elements, and in general $|𝑋|$ has the same parity as the number of fixed points of $𝜑$ (Exercise 5.3.40).

A term of the Leibniz formula is $sgn(𝜎)$ times $𝑛$ entries of $𝐴$, one in each column and one in each row, and it vanishes if one of these entries is $0$. So to evaluate or analyze $det𝐴$ for a matrix with a pattern of zeros, ask which permutations $𝜎$ satisfy ${𝑎}_{𝜎(𝑗)𝑗}\ne 0$ for every $𝑗$. Often the pattern confines $𝜎$ to a small, explicit set, and only those terms need to be computed. The same question asked about entries that depend on a parameter, instead of entries that vanish, tells you how $det𝐴$ depends on the parameter (Technique 5.3.18).

Reach for it when the matrix is sparse or structured (triangular, block-diagonal, banded, mostly zeros), or when a question asks which products of entries can occur in $det𝐴$. Expect to prove a small lemma about permutations along the way, such as Lemma 5.3.14. The canonical example is Proposition 5.3.15, where only the identity survives.

By the Leibniz formula, $det𝐴$ is a polynomial in the ${𝑛}^2$ entries of $𝐴$ with integer coefficients $\pm 1$, each of whose monomials has degree $𝑛$ and uses one entry from each row and each column. So if the entries of a matrix depend polynomially on a parameter $𝑡$, then so does its determinant, and the degree and the leading coefficients can be read off the formula with Technique 5.3.12. Similarly, any map that respects sums and products can be applied to $det𝐴$ entry by entry: for example, complex conjugation (Exercise 5.3.28) and reduction modulo a prime (Technique 5.3.21).

Reach for it when a question asks how $det$ varies with a parameter, as for $det(𝐴+𝑡{𝐼}_{𝑛})$ or $det(𝐴+𝑡𝐵)$, for how many values of $𝑡$ a matrix can fail to be invertible, or how $det$ interacts with an operation on the entries. The canonical example is Proposition 5.3.19.

To show that a matrix with integer entries has nonzero determinant, and hence is invertible (Corollary 5.1.18), it is enough to find one prime $𝑝$ for which $det𝐴\ne 0$ in ${𝔽}_{𝑝}$: then $(det𝐴)mod𝑝\ne 0$ by Proposition 5.3.20, so $det𝐴\ne 0$. Choose $𝑝$ so that $𝐴$ is simple, for instance triangular with nonzero diagonal entries or a permutation matrix, and there is no need to compute $det𝐴$ itself. The converse inference is not available: $det𝐴=0$ only says that $𝑝$ divides $det𝐴$.

Reach for it when an integer matrix has a recognizable pattern modulo a small prime, most often modulo $2$, where the entries are just their parities and $sgn(𝜎)=1$ for every $𝜎$. The canonical example is Example 5.3.22.

Every invertible matrix is a product of elementary matrices (Theorem 3.5.19). So to prove a statement about all invertible matrices, it is often enough to

1. prove it for the three types of elementary matrices, by a direct computation; and
2. show that it survives multiplication: if it holds for $𝐴$ and $𝐸$ is elementary, then it holds for $𝐴𝐸$ (or for $𝐸𝐴$).

Induction on the number of factors then gives the statement for every invertible matrix. A statement about all square matrices needs a separate argument for the matrices that are not invertible. Often both sides of the claimed identity are $0$ there. Otherwise, write $𝐴={𝐺}^{-1}rref(𝐴)$ (Theorem 3.3.10) and use that $rref(𝐴)$ has a zero row.

Reach for it when a statement involves products, inverses, or transposes, and is easy to check on elementary matrices, which differ from ${𝐼}_{𝑛}$ in at most four entries. The fullest example is the first proof of Theorem 5.4.10; the first proof of Theorem 5.4.14 has the same shape. Remember the case split: a matrix that is not invertible is never a product of elementary matrices, since such products are invertible (Corollary 3.2.11). Forgetting this is a common error (Exercise 5.4.35).

By Theorem 5.3.4, every multilinear alternating function $𝐷:{𝐹}^{𝑛\times 𝑛}\to 𝐹$ equals $𝐷({𝐼}_{𝑛})det$. So to prove an identity of the form $𝐷(𝐵)=𝑐det𝐵$, where $𝐷(𝐵)$ is some expression built from $𝐵$, check two things about $𝐷$ as a function of the columns of $𝐵$: that it is linear in each column, and that it vanishes when two columns are equal. Then evaluate at ${𝐼}_{𝑛}$ to find $𝑐=𝐷({𝐼}_{𝑛})$. No formula for $det$ and no case analysis is needed.

Reach for it when an expression is visibly linear in each column of a matrix: $det(𝐴𝐵)$ for a fixed $𝐴$, $det\left(\begin{array}{cc}𝑋& 0\\ 0& 𝐵\end{array}\right)$ for a fixed $𝐵$, or a function of $𝑛$ vectors in a space with a basis. The canonical example is the second proof of Theorem 5.4.10. The same move proved Proposition 5.3.17, and Section 13.4 uses it to define the determinant of an operator without choosing a basis.

Row reduction works with blocks in place of entries, as long as the order of the factors in each product is respected. By Theorem 2.4.34, multiplying $\left(\begin{array}{cc}𝐴& 𝐵\\ 𝐶& 𝐷\end{array}\right)$ on the left by $\left(\begin{array}{cc}𝐼& 0\\ 𝑋& 𝐼\end{array}\right)$ adds $𝑋$ times the first block row to the second, giving $\left(\begin{array}{cc}𝐴& 𝐵\\ 𝑋𝐴+𝐶& 𝑋𝐵+𝐷\end{array}\right)$. Multiplying on the right by $\left(\begin{array}{cc}𝐼& 𝑌\\ 0& 𝐼\end{array}\right)$ adds the first block column times $𝑌$ to the second, giving $\left(\begin{array}{cc}𝐴& 𝐴𝑌+𝐵\\ 𝐶& 𝐶𝑌+𝐷\end{array}\right)$. Both multipliers have determinant $1$ by Theorem 5.4.26, so these operations do not change the determinant. Choose $𝑋$ or $𝑌$ to create a zero block, and finish with Theorem 5.4.26.

Reach for it when you want the determinant or the inverse of a $2\times 2$ block matrix and one of the blocks is invertible, or when two block matrices are related by such operations. The canonical example is Proposition 5.4.29.

Suppose a family of matrices ${𝑀}_1,{𝑀}_2,{𝑀}_3,\dots$, with ${𝑀}_{𝑛}\in {𝐹}^{𝑛\times 𝑛}$, has the property that expanding ${𝑀}_{𝑛}$ along a well-chosen row or column produces minors that are earlier members of the family, or are triangular, or are otherwise known. Then the expansion gives a recurrence for ${𝑑}_{𝑛}=det{𝑀}_{𝑛}$. Expand along the row or column with the fewest nonzero entries, identify each minor that appears, and write down the recurrence. Then either solve it, or compute ${𝑑}_1,{𝑑}_2,{𝑑}_3$, guess a closed form, and prove it by induction on $𝑛$.

Reach for it when a matrix has a pattern that repeats along the diagonal, so that deleting the last (or first) row and column gives the same kind of matrix. The canonical example is Proposition 5.5.18. Proposition 5.5.20 and the first proof of Theorem 5.5.21 induct in the same way, and Exercise 5.5.34 reproves Proposition 5.3.15.

When the entries of a matrix are polynomial expressions in some parameters and the determinant is expected to have a factor such as ${𝑐}_1-{𝑐}_0$, look for replacements that make this factor appear in every entry of one row (or column). Replacements do not change the determinant (Corollary 5.4.15, Lemma 5.1.8), and linearity in that row then pulls the factor out. Choose the replacements so that they also create zeros, so that a cofactor expansion reduces the size at the same step. Repeating this, usually by induction on the size, peels off the factors one at a time.

Reach for it when consecutive columns (or rows) are related by a common multiplier, as the powers ${𝑐}^{𝑘}$ and ${𝑐}^{𝑘+1}$ are related by $𝑐$, or when all rows have a common sum. The canonical example is the first proof of Theorem 5.5.21. Example 5.4.24 and Exercise 5.4.44 used the same idea with row sums.

To prove that two quantities depending on a scalar $𝑡$ are equal, show that both are values $𝑃(𝑡)$ and $𝑄(𝑡)$ of polynomials $𝑃,𝑄\in {𝐹[𝑥]}_{\le 𝑛}$, and then show $𝑃=𝑄$ by counting. Two polynomials of degree at most $𝑛$ that agree at $𝑛+1$ distinct points are equal, since their difference has $𝑛+1$ roots (Lemma 3.4.23). When zeros are easier to find than values, use Lemma 5.5.23 instead: a polynomial of degree at most $𝑛$ with $𝑛$ known distinct roots is determined by its coefficient of ${𝑥}^{𝑛}$. Then the proof splits into independent checks: a bound on the degree, the roots, and one coefficient.

Determinants are a rich source of such polynomials. If a parameter $𝑡$ occurs in only one row, the expansion along that row (Theorem 5.5.3) shows that the determinant is a polynomial in $𝑡$; if the top power of $𝑡$ occurs in only one entry of that row, as in $(1,𝑡,\dots ,{𝑡}^{𝑛})$, its coefficient is a single cofactor. More generally, see Technique 5.3.18. Roots come from coincidences: a value of $𝑡$ that makes two rows equal, or the rows dependent, is a root.

Reach for it when the expected answer is a product of linear factors, or when an identity is easy to check for many special values of a parameter. Two pitfalls: forgetting the leading coefficient (roots determine a polynomial only up to a scalar factor; see Exercise 5.5.42), and counting roots that are not distinct. Over an infinite field, an identity between polynomials in $𝑡$ that holds for all but finitely many $𝑡$ holds for all $𝑡$. This extends identities from invertible matrices to all matrices by way of $𝐴+𝑡{𝐼}_{𝑛}$ (Exercise 5.5.41). The canonical example is the second proof of Theorem 5.5.21. The technique returns in Section 7.3.

To compute $det𝑀$, write $𝑀$ as a product of matrices whose determinants are known, and multiply (Theorem 5.4.10). There are two common sources of factorizations. If every entry is a sum of products, ${𝑚}_{𝑖𝑗}=$${\sum }_{𝑘}{𝑥}_{𝑖𝑘}{𝑑}_{𝑘}{𝑦}_{𝑘𝑗}$, then $𝑀=𝑋𝐷𝑌$ with $𝐷=$$diag({𝑑}_1,\dots ,{𝑑}_{𝑟})$, and $𝑋$ and $𝑌$ are often triangular or Vandermonde matrices. If $𝑀$ is a block matrix, block row and column operations (Theorem 2.4.34) multiply it by matrices of determinant $1$ until it is block triangular. When the inner size $𝑟$ is smaller than the size of $𝑀$, the same factorization shows $det𝑀=0$ instead (Exercise 5.4.38). For instance, the matrix with entries $1+{𝑥}_{𝑖}{𝑦}_{𝑗}$ is $𝑋𝑌$ with rows $(1,{𝑥}_{𝑖})$ in $𝑋$ and columns $(1,{𝑦}_{𝑗})$ in $𝑌$. For two rows this gives $({𝑥}_2-{𝑥}_1)({𝑦}_2-{𝑦}_1)$, and for three or more rows it gives $0$.

Reach for it when the entries are power sums, binomial expansions, or sums over divisors, or when one block of a block matrix can be cleared. The chapter used it in Exercise 5.4.43, Exercise 5.4.46, and Exercise 5.5.47. The canonical example is the Hankel matrix of power sums, which is ${𝑉}^{\text{𝖳}}𝑉$ for a Vandermonde matrix $𝑉$ (Problem 5.9).

A sum of nonnegative real numbers is $0$ only if every term is $0$: if ${𝑡}_1,\dots ,{𝑡}_{𝑛}\ge 0$ and some ${𝑡}_{𝑗}>0$, then ${𝑡}_1+\cdots +{𝑡}_{𝑛}\ge {𝑡}_{𝑗}>0$. So to show that many quantities vanish, it suffices to exhibit them as squares, or squared moduli ${|{𝑧}_{𝑘}|}^2$, in a single sum, and to show that the sum is $0$.

Reach for it when a positivity or definiteness axiom must be verified for a concrete formula, and whenever one equation should force many. The canonical example is definiteness of the dot product (Proposition 6.1.10), where ${\sum }_{𝑘}{|{𝑣}_{𝑘}|}^2=0$ forces every ${𝑣}_{𝑘}=0$. Integrals of nonnegative continuous functions behave the same way (Lemma 6.1.14), and Technique 6.1.18 applies the idea to the entries of a matrix.

For every $𝐴\in {𝔽}^{𝑚\times 𝑛}$, $tr({𝐴}^{\ast }𝐴)=$${\sum }_{𝑖,𝑗}{|{𝑎}_{𝑖𝑗}|}^2$ (Proposition 6.1.16). So $tr({𝐴}^{\ast }𝐴)\ge 0$, with equality only for $𝐴=0$, and one scalar equation controls every entry of $𝐴$. To show that a matrix $𝐴$ is zero, it suffices to show $tr({𝐴}^{\ast }𝐴)=0$; in particular, it suffices to show ${𝐴}^{\ast }𝐴=0$.

Reach for it when a matrix identity involves ${𝐴}^{\ast }𝐴$ or $𝐴{𝐴}^{\ast }$ (or ${𝐴}^{\text{𝖳}}𝐴$ over $ℝ$) and the goal is a conclusion about $𝐴$ itself. It is Technique 6.1.9 applied to the entries of a matrix. The canonical example is Corollary 6.1.19.

An inner product is determined by its values $⟨𝐯,𝐯⟩$ on single vectors: by Proposition 6.1.32, $⟨𝐱,𝐲⟩$ is a combination of the numbers ${\Vert 𝐱+𝑐𝐲\Vert }^2$ with $𝑐\in \{\pm 1,\pm 𝑖\}$. So a statement about all pairs $(𝐱,𝐲)$ can often be reduced to a statement about single vectors, applied to $𝐱+𝑐𝐲$ for a few scalars $𝑐$.

Reach for it when the hypothesis or the conclusion involves only lengths, or only “quadratic” quantities such as $⟨𝑇𝐯,𝐯⟩$, and you need information about two different vectors at once. The canonical example is Proposition 6.1.32 itself. Over $ℝ$ there is a caveat: a symmetric function $𝐵(𝐱,𝐲)$ that is linear in each slot is determined by its diagonal values $𝐵(𝐯,𝐯)$, but without symmetry this fails. For instance, $𝐵(𝐱,𝐲)=$${𝑥}_1{𝑦}_2-$${𝑥}_2{𝑦}_1$ on ${ℝ}^2$ satisfies $𝐵(𝐯,𝐯)=0$ for all $𝐯$ without being $0$. Over $ℂ$ no symmetry is needed (Proposition 6.1.41).

By definiteness, $𝐯=\mathrm{𝟎}$ as soon as $⟨𝐯,𝐯⟩=0$. So to prove that a vector is zero, compute $⟨𝐯,𝐯⟩$, or ${\Vert 𝐯\Vert }^2$, and show that it vanishes. Often one knows that $⟨𝐯,𝐱⟩=0$ for many $𝐱$, and the move is to take $𝐱=𝐯$. To prove $𝐯=𝐰$, apply this to $𝐯-𝐰$, expanding ${\Vert 𝐯-𝐰\Vert }^2$ with Proposition 6.1.29 if necessary.

Reach for it when the hypotheses are statements about inner products and the conclusion is an equation between vectors. The canonical example is Proposition 6.1.37. In Section 6.5 the same move shows that ${𝐴}^{\ast }𝐴𝐱=\mathrm{𝟎}$ implies $𝐴𝐱=\mathrm{𝟎}$.

A hypothesis that holds for all vectors holds in particular for sums and multiples of the vectors you care about. Applying it to $𝐯=𝐱+𝐲$, $𝐱-𝐲$, $𝐱+𝑖𝐲$, or to the very vector you want to control, turns one identity into a system of equations, which can then be solved for the quantity you want.

Reach for it when a hypothesis is quantified over all vectors but involves each vector only quadratically, like $\Vert 𝐯\Vert$ or $⟨𝑇𝐯,𝐯⟩$, and you need information about pairs of vectors. Over $ℂ$, the pair $𝐱+𝐲$ and $𝐱+𝑖𝐲$ is usually the right choice, because together they separate real and imaginary parts. The canonical example is Proposition 6.1.41. The polarization identities (Proposition 6.1.32) and the choice $𝐱=𝐯-𝐰$ in Proposition 6.1.37 are instances of the same move.

To compare a vector $𝐱$ with a nonzero vector $𝐲$, split $𝐱$ into a part along $𝐲$ and a part perpendicular to $𝐲$:

This choice of $𝑐$ is exactly the one that makes $⟨𝐰,𝐲⟩=0$. Then the cross term in Proposition 6.1.29 vanishes, and ${\Vert 𝐱\Vert }^2=$${|𝑐|}^2{\Vert 𝐲\Vert }^2+$${\Vert 𝐰\Vert }^2$. So the length of $𝐱$ splits into a contribution from the direction $𝐲$ and a contribution from everything else. Dropping ${\Vert 𝐰\Vert }^2\ge 0$ gives a lower bound for $\Vert 𝐱\Vert$ that is sharp exactly when $𝐰=\mathrm{𝟎}$.

Reach for it when a statement compares $𝐱$ with one fixed direction, or asks how close $𝐱$ comes to the line through $𝐲$. The canonical example is the first proof of Theorem 6.2.1. In Section 6.4 the line is replaced by an arbitrary subspace, the part along $𝐲$ becomes the orthogonal projection, and the same computation solves best-approximation problems (Theorem 6.4.33) and least squares (Section 6.5).

If a real quadratic $𝑎{𝑡}^2-2𝑏𝑡+𝑐$ with $𝑎>0$ is nonnegative for every real $𝑡$, then ${𝑏}^2\le 𝑎𝑐$, with equality exactly when the quadratic has a real root (Lemma 6.2.6). So to prove an inequality of the shape ${𝑏}^2\le 𝑎𝑐$, look for an expression that is nonnegative for every real $𝑡$ for an obvious reason, usually a squared norm ${\Vert 𝐱-𝑡𝐲\Vert }^2$ or a sum of squares, and that expands to $𝑎{𝑡}^2-2𝑏𝑡+𝑐$. The equality case comes for free: it says that the nonnegative expression vanishes for some $𝑡$.

Reach for it when the target has the shape ${𝑏}^2\le 𝑎𝑐$ with $𝑎,𝑐\ge 0$, especially when no geometric picture suggests a decomposition. The parameter $𝑡$ must be real; over $ℂ$, first make the middle coefficient real (Technique 6.2.8). The canonical example is the second proof of Theorem 6.2.1.

Every $𝑧\in ℂ$ can be written $𝑧=\left|𝑧\right|𝜇$ with $|𝜇|=1$: take $𝜇=𝑧/|𝑧|$ if $𝑧\ne 0$, and $𝜇=1$ if $𝑧=0$. Then $𝜇𝑧=|𝑧|$, so multiplying by $𝜇$ rotates $𝑧$ onto the nonnegative real axis without changing its modulus. In an inner product space, replacing $𝐱$ by $𝜇𝐱$ changes no norm, since $|𝜇|=1$, and it turns $⟨𝐱,𝐲⟩$ into $𝜇⟨𝐱,𝐲⟩$. So in a statement that involves only $\Vert 𝐱\Vert$, $\Vert 𝐲\Vert$, and $|⟨𝐱,𝐲⟩|$, we may assume that $⟨𝐱,𝐲⟩$ is a nonnegative real number, and real-variable arguments apply. The same observation gives

since $Re(𝜆𝑧)\le$$\left|𝜆𝑧\right|=$$|𝑧|$ for $|𝜆|=1$, with equality at $𝜆=𝜇$.

Reach for it when a real-variable argument, such as a discriminant argument, must be run over $ℂ$, or when $Re⟨𝐱,𝐲⟩$ and $|⟨𝐱,𝐲⟩|$ must be compared. The canonical example is the second proof of Theorem 6.2.1.

To prove an inequality between sums or integrals, recognize one side as $|⟨𝐱,𝐲⟩|$ and the other as $\Vert 𝐱\Vert \Vert 𝐲\Vert$ for some inner product. The work is in the choices. Pick the space and the inner product (the dot product, a weighted dot product, an integral, the Frobenius inner product), and split each term of the quantity to be bounded as a product of two factors, one belonging to $𝐱$ and one to $𝐲$. A useful move is to insert weights: write ${𝑎}_{𝑘}{𝑏}_{𝑘}$ as $(\sqrt{{𝑤}_{𝑘}}{𝑎}_{𝑘})({𝑏}_{𝑘}/\sqrt{{𝑤}_{𝑘}})$ with ${𝑤}_{𝑘}>0$ chosen so that the resulting norms are quantities you control.

Then check the equality case. Equality holds exactly when one of $𝐱,𝐲$ is a multiple of the other, so it tells you whether the bound is sharp and which data attain it. If the data that would attain it violate your constraints, the bound is not sharp, and a different split may do better.

Reach for it when the target has the shape ${\left({\sum }_{𝑘}{𝑎}_{𝑘}{𝑏}_{𝑘}\right)}^2\le$$\left({\sum }_{𝑘}{𝑎}_{𝑘}^2\right)\left({\sum }_{𝑘}{𝑏}_{𝑘}^2\right)$ after renaming, when a linear quantity such as ${\sum }_{𝑘}{𝑎}_{𝑘}$ or $\int 𝑓$ must be bounded by a quadratic one such as ${\sum }_{𝑘}{𝑎}_{𝑘}^2$ or $\int {𝑓}^2$, or when a quadratic quantity must be minimized subject to a linear constraint. The canonical example is Proposition 6.2.22.

If a vector is written as a combination $𝐰=$${𝑎}_1{𝐯}_1+$$\cdots +$${𝑎}_{𝑘}{𝐯}_{𝑘}$ of an orthogonal list, take the inner product of both sides with ${𝐯}_{𝑗}$. Linearity in the first slot distributes it over the sum, and orthogonality removes every term except the $𝑗$th:

So each coefficient is determined by one inner product, with no reference to the other coefficients. Put ${𝐯}_{𝑗}$ in the second slot; in the first slot it produces $⟨{𝐯}_{𝑗},𝐰⟩=$${𝑎}_{𝑗}{\Vert {𝐯}_{𝑗}\Vert }^2$, the conjugate.

Reach for it when a vector or a linear relation is expressed through an orthogonal list and you need the coefficients, or need to show that they vanish. It is the inner-product form of Technique 4.1.25: the linear map $𝐱\mapsto ⟨𝐱,{𝐯}_{𝑗}⟩$ from $𝑉$ to $𝔽$ kills every ${𝐯}_{𝑙}$ with $𝑙\ne 𝑗$. The canonical example is Proposition 6.3.13. The coordinate formula Proposition 6.3.18, the Fourier inversion formula (Proposition 6.3.41), and Gram–Schmidt (Algorithm 6.4.14) use it again.

To study a list ${𝐯}_1,\dots ,{𝐯}_{𝑘}$ in an inner product space, record all the inner products $⟨{𝐯}_{𝑗},{𝐯}_{𝑖}⟩$ in its Gram matrix $𝐺$. Questions about the list become questions about one matrix: the list is orthonormal if and only if $𝐺=𝐼$, orthogonal if and only if $𝐺$ is diagonal, and independent if and only if $𝐺$ is invertible, and the combination with coefficient vector $𝐜$ has squared length ${𝐜}^{\ast }𝐺𝐜$. When the vectors are the columns of $𝐴\in {𝔽}^{𝑚\times 𝑛}$, $𝐺={𝐴}^{\ast }𝐴$, so these become statements about ${𝐴}^{\ast }𝐴$.

Reach for it when the hypotheses are about inner products among the vectors of a list (lengths, angles, orthogonality) and the conclusion is about the list itself, or when the product ${𝐴}^{\ast }𝐴$ appears. The canonical example is Proposition 6.3.30. In Section 6.5 the normal equations have the coefficient matrix ${𝐴}^{\ast }𝐴$, and Proposition 6.3.30 shows that they have a unique solution exactly when the columns of $𝐴$ are independent.

Suppose $𝐱=𝐩+𝐪$, where $𝐩$ lies in a subspace $𝑊$ and $𝐪⟂𝑊$, as for $𝐩={Pr}_{\mathrm{𝒪︀}}(𝐱)$ and $𝐪=𝐱-{Pr}_{\mathrm{𝒪︀}}(𝐱)$. By Pythagoras,

So each piece is at most as long as $𝐱$. Moreover $\Vert 𝐩\Vert =\Vert 𝐱\Vert$ exactly when $𝐪=\mathrm{𝟎}$, that is, when $𝐱\in 𝑊$, and $\Vert 𝐪\Vert =\Vert 𝐱\Vert$ exactly when $𝐩=\mathrm{𝟎}$.

Reach for it when you need an upper bound for a sum ${\sum }_{𝑗}{|⟨𝐱,{𝐮}_{𝑗}⟩|}^2$ over an orthonormal list, which is ${\Vert {Pr}_{\mathrm{𝒪︀}}(𝐱)\Vert }^2$, or more generally when the quantity to be bounded is the length of one orthogonal piece of a vector whose length you know. The equality case turns the bound into a test for membership in $𝑊$. The canonical example is Bessel’s inequality (Theorem 6.3.24). In Theorem 6.4.33 the error $𝐯-{Pr}_{𝑊}(𝐯)$ turns out to be the piece of $𝐯-𝐰$ orthogonal to $𝑊$, for every $𝐰\in 𝑊$; and in infinite dimensions (Section 15.3) Bessel’s inequality survives where Parseval’s identity needs more work.

To show that a vector $𝐩$ is the projection of $𝐯$ onto $𝑊$, do not compute the projection. Check the two conditions of Theorem 6.4.6: $𝐩\in 𝑊$, and $𝐯-𝐩⟂𝑊$. By Proposition 6.3.9(c), the second condition only has to be checked against a spanning list of $𝑊$. Uniqueness then does the rest, much as a two-sided inverse is recognized by checking two products (Technique 2.5.16).

Reach for it when a formula or a vector is proposed as a projection, when projections onto related subspaces are compared, and when you need to know that a projection does not depend on the choices made to compute it. The canonical example is Corollary 6.4.8. Later examples are the projection onto ${𝑊}^{⟂}$ (Proposition 6.4.29), the recognition of orthogonal projections among all linear maps (Proposition 6.4.30), and the projection formula of Section 6.5.

Suppose $\widehat{𝐱}$ minimizes a real-valued quantity $𝑓(𝐱)$ over a vector space. Then for every direction $𝐡$, the function $𝑡\mapsto 𝑓(\widehat{𝐱}+𝑡𝐡)$ of a real variable $𝑡$ has a minimum at $𝑡=0$. When $𝑓$ is the squared norm of a vector that depends linearly (or affinely) on $𝐱$, this function is a quadratic polynomial $𝛼+𝛽𝑡+𝛾{𝑡}^2$ with $𝛾\ge 0$, and a minimum at $𝑡=0$ forces the linear coefficient $𝛽$ to vanish: if $𝛽\ne 0$, a small $𝑡$ of the opposite sign makes $𝛽𝑡+𝛾{𝑡}^2<0$. Doing this for every $𝐡$ gives an equation that $\widehat{𝐱}$ must satisfy. Choosing $𝐡$ cleverly, usually equal to the vector you want to show is zero, turns “$𝛽=0$” into a statement ${\Vert 𝐬\Vert }^2=0$ (Technique 6.1.36). In the other direction, if the linear coefficient vanishes for every $𝐡$, the expansion shows that $𝑓(\widehat{𝐱}+𝐡)\ge$$𝑓(\widehat{𝐱})$, so $\widehat{𝐱}$ is a minimizer.

This is “the derivative vanishes at a minimum” without derivatives, and with the converse built in. Reach for it when a vector is defined as the minimizer (or maximizer) of something and you need an equation it satisfies. The canonical example is the second proof of Theorem 6.5.5. The same move gives the minimal-norm solution in Section 6.5.7, and in Section 12.3 it shows that a maximizer of $⟨𝑇𝐯,𝐯⟩$ over unit vectors is an eigenvector.

To compute ${𝑇}^{\ast }𝐰$, start from $⟨𝑇𝐯,𝐰⟩$, substitute the formula for $𝑇$, and rearrange until the expression reads $⟨𝐯,𝐮⟩$, with $𝐯$ alone in the first slot and $𝐮$ built from $𝐰$ only. Then ${𝑇}^{\ast }𝐰=𝐮$ by Proposition 6.6.9. Scalars that move into the second slot pick up a bar. The same move proves identities: to show that a given map $𝑆$ is ${𝑇}^{\ast }$, check $⟨𝑇𝐯,𝐰⟩=$$⟨𝐯,𝑆𝐰⟩$ for all $𝐯$ and $𝐰$, without ever writing a formula for ${𝑇}^{\ast }$. This is the analogue for adjoints of Technique 2.5.16 and Technique 6.4.7.

Reach for it when computing the adjoint of an explicit map, and when proving identities such as ${(𝑅𝑇)}^{\ast }={𝑇}^{\ast }{𝑅}^{\ast }$. The canonical example is Example 6.6.13.

When a map acts on one argument of an inner product, move it to the other argument as its adjoint: $⟨𝑇𝐯,𝐰⟩=$$⟨𝐯,{𝑇}^{\ast }𝐰⟩$ and $⟨𝐰,𝑇𝐯⟩=$$⟨{𝑇}^{\ast }𝐰,𝐯⟩$. Do this so that the map lands on the vector you know more about, or so that two vectors you want to compare end up in the same inner product. Typical outcomes: