3.1 Linear systems · Matrix Theory

The Fundamental Theorems (Section 2.7) are statements about the equation $𝐴 𝐱 = 𝐲$ : whether it has a solution for every $𝐲$ , and whether solutions are unique. They do not tell us how to settle either question for a particular matrix, let alone how to find the solutions. This chapter develops the tool that does, Gauss–Jordan elimination, and then uses it to finish the proofs of the theorems. This section sets up the problem. A linear system can be read as a list of equations, as one matrix equation, or as a question about linear combinations of columns, and its solution set always has the same shape: it is empty, or it is one solution plus the kernel of $𝑇_{𝐴}$ .

3.1.1Linear systems

Definition 3.1.1 (Linear system). Let $𝐹$ be a field. A linear equation in the unknowns $𝑥_{1}, \dots, 𝑥_{𝑛}$ over $𝐹$ is an equation

𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} + \dots + 𝑎_{𝑛} 𝑥_{𝑛} = 𝑏,

where the coefficients $𝑎_{1}, \dots, 𝑎_{𝑛}$ and the right-hand side $𝑏$ are fixed elements of $𝐹$ . A linear system (or system of linear equations) of $𝑚$ equations in $𝑛$ unknowns is a list of $𝑚$ linear equations in the same unknowns,

\begin{aligned} 𝑎_{11} 𝑥_{1} + 𝑎_{12} 𝑥_{2} + \dots + 𝑎_{1 𝑛} 𝑥_{𝑛} & = 𝑦_{1}, \\ 𝑎_{21} 𝑥_{1} + 𝑎_{22} 𝑥_{2} + \dots + 𝑎_{2 𝑛} 𝑥_{𝑛} & = 𝑦_{2}, \\ ⋮ \\ 𝑎_{𝑚 1} 𝑥_{1} + 𝑎_{𝑚 2} 𝑥_{2} + \dots + 𝑎_{𝑚 𝑛} 𝑥_{𝑛} & = 𝑦_{𝑚}, \end{aligned}

with all $𝑎_{𝑖 𝑗}$ and $𝑦_{𝑖}$ in $𝐹$ . A solution of the system is a vector $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑛}) \in$ $𝐹^{𝑛}$ that satisfies all $𝑚$ equations, and the solution set is the set of all solutions. The system is consistent if it has at least one solution and inconsistent otherwise. Two systems in the same unknowns are equivalent if they have the same solution set.

The word “linear” refers to the unknowns: each term is a scalar times a single unknown, and nothing else involves the unknowns. The coefficients can be any scalars. An equation such as $2 𝑥_{1} + 3 = 𝑥_{2} - 𝑥_{1}$ also counts, since adding $- 3 - 𝑥_{2} + 𝑥_{1}$ to both sides turns it into $3 𝑥_{1} - 𝑥_{2} = - 3$ without changing its solutions.

Example 3.1.2 (A system with a line of solutions). Over $ℝ$ , consider the system of three equations in three unknowns

\begin{aligned} 𝑥_{1} + 2 𝑥_{2} - 𝑥_{3} & = 1, \\ 2 𝑥_{1} + 5 𝑥_{2} + 𝑥_{3} & = 5, \\ 3 𝑥_{1} + 7 𝑥_{2} & = 6 . \end{aligned}

The vector $(2, 0, 1)$ is a solution, since $2 + 0 - 1 = 1$ , $4 + 0 + 1 = 5$ , and $6 + 0 = 6$ . So is $(- 5, 3, 0)$ . The vector $(1, 0, 0)$ satisfies the first equation but not the second, so it is not a solution. We will find the whole solution set in Example 3.1.13: it is a line in $ℝ^{3}$ . We call it the running system and return to it several times.

Non-example 3.1.3 (Equations that are not linear). Over

ℝ

, the equations

𝑥_{1} 𝑥_{2} = 1

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

, and

𝑥_{1} + sin 𝑥_{2} = 0

are not linear: the unknowns are multiplied together, squared, or fed into a function. Their solution sets in

ℝ^{2}

are a hyperbola, a circle, and a sine curve, and none of them contains a straight line. By Corollary 3.1.23, the solution set of a linear system contains the whole line through any two of its points, so none of these curves is the solution set of a linear system. On the other hand,

\sqrt{2} 𝑥_{1} + 𝜋 𝑥_{2} = 𝑒

is a linear equation; its coefficients are just unusual real numbers.

3.1.2Three faces of one problem

A linear system is determined by its coefficients $𝑎_{𝑖 𝑗}$ and its right-hand sides $𝑦_{𝑖}$ ; what we call the unknowns plays no role. Collecting the coefficients into a matrix and the right-hand sides into a vector turns the $𝑚$ equations into a single equation, and that equation can be read in two further ways.

Definition 3.1.4 (Coefficient matrix; matrix and vector forms). The coefficient matrix of the system in Definition 3.1.1 is the matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ whose $(𝑖, 𝑗)$ entry is $𝑎_{𝑖 𝑗}$ , the coefficient of $𝑥_{𝑗}$ in the $𝑖$ th equation. Write $𝐲 =$ $(𝑦_{1}, \dots, 𝑦_{𝑚}) \in$ $𝐹^{𝑚}$ for the vector of right-hand sides, and $𝐚_{1}, \dots, 𝐚_{𝑛} \in 𝐹^{𝑚}$ for the columns of $𝐴$ . The matrix form of the system is the equation

𝐴 𝐱 = 𝐲

in the unknown $𝐱 \in 𝐹^{𝑛}$ , and its vector form is the equation

𝑥_{1} 𝐚_{1} + 𝑥_{2} 𝐚_{2} + \dots + 𝑥_{𝑛} 𝐚_{𝑛} = 𝐲

in the unknown scalars $𝑥_{1}, \dots, 𝑥_{𝑛}$ . We refer to the system itself as “the system $𝐴 𝐱 = 𝐲$ ”.

For the running system (Example 3.1.2),

𝐴 = (\begin{matrix} 1 & 2 & - 1 \\ 2 & 5 & 1 \\ 3 & 7 & 0 \end{matrix}), 𝐲 = (\begin{matrix} 1 \\ 5 \\ 6 \end{matrix}), 𝑥_{1} (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) + 𝑥_{2} (\begin{matrix} 2 \\ 5 \\ 7 \end{matrix}) + 𝑥_{3} (\begin{matrix} - 1 \\ 1 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 5 \\ 6 \end{matrix}) .

The missing $𝑥_{3}$ in the third equation is a coefficient $0$ .

Proposition 3.1.5 (Three faces of a linear system). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

have columns

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

, let

𝐲 \in 𝐹^{𝑚}

, and let

𝐱 =

(𝑥_{1}, \dots, 𝑥_{𝑛}) \in

𝐹^{𝑛}

. The following are equivalent.

(i) $𝐱$ is a solution of the linear system with coefficient matrix $𝐴$ and right-hand sides $𝐲$ .
(ii) $𝐴 𝐱 = 𝐲$ .
(iii) $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛} =$ $𝐲$ .

Proof.routine

Uses. Definition 2.3.8 (Matrix–vector product), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Hint 1. Two of the three statements are the same equation by a definition. Which two?

Hint 2. For the remaining equivalence, compare the

𝑖

th entries of the two sides of (iii).

Sketch. By the definition of

𝐴 𝐱

as a combination of the columns of

𝐴

, (ii) and (iii) are the same equation. The

𝑖

th entry of

𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑛} 𝐚_{𝑛}

𝑎_{𝑖 1} 𝑥_{1} +

\dots +

𝑎_{𝑖 𝑛} 𝑥_{𝑛}

, the left side of the

𝑖

th equation, so (iii) holds exactly when all

𝑚

equations do.

By Definition 2.3.8, $𝐴 𝐱 =$ $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛}$ , so (ii) and (iii) are the same equation.

For (i) $\Leftrightarrow$ (iii), recall that vectors in $𝐹^{𝑚}$ are added and scaled entry by entry, and that two vectors in $𝐹^{𝑚}$ are equal exactly when their entries are (Definition 1.2.4). The $𝑖$ th entry of $𝐚_{𝑗}$ is $𝑎_{𝑖 𝑗}$ , so the $𝑖$ th entry of $𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑛} 𝐚_{𝑛}$ is

𝑥_{1} 𝑎_{𝑖 1} + 𝑥_{2} 𝑎_{𝑖 2} + \dots + 𝑥_{𝑛} 𝑎_{𝑖 𝑛} = 𝑎_{𝑖 1} 𝑥_{1} + 𝑎_{𝑖 2} 𝑥_{2} + \dots + 𝑎_{𝑖 𝑛} 𝑥_{𝑛} .

Hence (iii) holds if and only if, for each $𝑖 = 1, \dots, 𝑚$ , the left side of the $𝑖$ th equation equals $𝑦_{𝑖}$ . That is, (iii) holds if and only if $𝐱$ is a solution. □

Example 3.1.6 (Two pictures of one system). The system $2 𝑥_{1} - 𝑥_{2} = 1$ , $𝑥_{1} + 𝑥_{2} = 2$ over $ℝ$ has matrix form and vector form

(\begin{matrix} 2 & - 1 \\ 1 & 1 \end{matrix}) (\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \end{matrix}) = (\begin{matrix} 1 \\ 2 \end{matrix}), 𝑥_{1} (\begin{matrix} 2 \\ 1 \end{matrix}) + 𝑥_{2} (\begin{matrix} - 1 \\ 1 \end{matrix}) = (\begin{matrix} 1 \\ 2 \end{matrix}) .

Read as equations, it asks for the points of $ℝ^{2}$ that lie on two lines; the lines cross at $(1, 1)$ (Figure 3.1.1, left). Read as a vector equation, it asks how to reach $(1, 2)$ by scaling $𝐚_{1} = (2, 1)$ and $𝐚_{2} = (- 1, 1)$ and adding; the answer is one of each, since $(2, 1) +$ $(- 1, 1) =$ $(1, 2)$ (Figure 3.1.1, right).

Realize that the two pictures live in different spaces. The row picture is drawn in $𝐹^{𝑛}$ , the space where the unknown $𝐱$ lives, and has one line (in $ℝ^{3}$ , one plane) per equation. The column picture is drawn in $𝐹^{𝑚}$ , the space where the right-hand side $𝐲$ lives, and has one vector per unknown.

Figure 3.1.1. The system

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

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

. Left: the solution is the point where the two lines meet. Right: the same solution,

(𝑥_{1}, 𝑥_{2}) = (1, 1)

, gives the coefficients that combine the columns into

𝐲

Exercise 3.1.7.routine Write the system

𝑥_{1} - 𝑥_{3} = 2, 𝑥_{2} + 2 𝑥_{3} = - 1, 𝑥_{1} + 𝑥_{2} = 1

over $ℝ$ in matrix form and in vector form. Is $(2, - 1, 0)$ a solution? Is $(3, - 3, 1)$ ?

Solution.

Uses. Proposition 3.1.5 (Three faces of a linear system), Definition 3.1.4 (Coefficient matrix; matrix and vector forms)

Hint 1. Row

𝑖

𝐴

lists the coefficients of

𝑥_{1}, 𝑥_{2}, 𝑥_{3}

in equation

𝑖

, with

0

for a missing unknown.

Hint 2. To test a vector, substitute it into each equation, or compute

𝐴 𝐱

and compare with

𝐲

Sketch.

𝐴

has rows

(1, 0, - 1)

(0, 1, 2)

(1, 1, 0)

and

𝐲 = (2, - 1, 1)

. Then

𝐴 (2, - 1, 0) =

(2, - 1, 1)

, a solution, and

𝐴 (3, - 3, 1) =

(2, - 1, 0)

, not a solution.

The matrix and vector forms are

(\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & 2 \\ 1 & 1 & 0 \end{matrix}) (\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ 𝑥_{3} \end{matrix}) = (\begin{matrix} 2 \\ - 1 \\ 1 \end{matrix}), 𝑥_{1} (\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}) + 𝑥_{2} (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}) + 𝑥_{3} (\begin{matrix} - 1 \\ 2 \\ 0 \end{matrix}) = (\begin{matrix} 2 \\ - 1 \\ 1 \end{matrix}) .

For $𝐱 = (2, - 1, 0)$ , the left sides are $2 - 0 = 2$ , $- 1 + 0 = - 1$ , and $2 - 1 = 1$ , so $(2, - 1, 0)$ is a solution. For $𝐱 = (3, - 3, 1)$ , the first two equations hold ( $3 - 1 = 2$ and $- 3 + 2 = - 1$ ), but $3 + (- 3) = 0 \neq 1$ , so $(3, - 3, 1)$ is not a solution.

What each face is good for

Intuition (Three ways to read $𝐴 𝐱 = 𝐲$ ). The equations are what we manipulate. Adding a multiple of one equation to another, swapping two equations, or scaling one by a nonzero scalar does not change the solution set, and elimination is built from exactly these moves (Section 3.1.3). Geometrically, the solution set of a system is the intersection of the solution sets of its equations, which is the row picture.

The matrix equation brings in the linear map $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ , $𝐱 \mapsto 𝐴 𝐱$ (Definition 2.3.15). Solving the system means finding every $𝐱$ with $𝑇_{𝐴} (𝐱) = 𝐲$ , that is, the preimage of $𝐲$ under $𝑇_{𝐴}$ . Consistency asks whether $𝐲 \in im 𝑇_{𝐴}$ , and the solution set of $𝐴 𝐱 = 𝟎$ is $ker 𝑇_{𝐴}$ . Everything we know about kernels and images applies, and so does linearity: $𝐴 (𝐱 + 𝐱^{'}) =$ $𝐴 𝐱 +$ $𝐴 𝐱^{'}$ tells us how solutions of systems with the same coefficient matrix combine. This is the view in which the structure of the solution set (Proposition 3.1.19) is proved.

The vector equation asks whether $𝐲$ is a linear combination of the columns of $𝐴$ , and if so in how many ways. Read backwards, it says that every question about a span or about linear independence of a list in $𝐹^{𝑚}$ is a question about a linear system. So a procedure that solves linear systems also answers, by computation, the questions of Chapter 1.

The first two readings are related by the following proposition, which is little more than a translation of definitions.

Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , and let $𝐲 \in 𝐹^{𝑚}$ .

(a)The system $𝐴 𝐱 = 𝐲$ is consistent if and only if $𝐲 \in im 𝑇_{𝐴}$ , if and only if $𝐲 \in$ $span (𝐚_{1}, \dots, 𝐚_{𝑛})$ .
(b)The solution set of the homogeneous system $𝐴 𝐱 = 𝟎$ is $ker 𝑇_{𝐴}$ .

Proof.routine

Uses. Proposition 3.1.5 (Three faces of a linear system), Definition 2.3.15 (The linear map of a matrix), Definition 2.6.6 (Image), Definition 2.6.5 (Kernel), Definition 1.3.10 (Span)

Hint 1. Unwind the definitions: what does

𝐲 \in im 𝑇_{𝐴}

say? What does

𝐲 \in

span (𝐚_{1}, \dots, 𝐚_{𝑛})

say?

Hint 2. Each of them says that some

𝐱 \in 𝐹^{𝑛}

satisfies one of the forms in Proposition 3.1.5.

Sketch.

𝐲 \in im 𝑇_{𝐴}

means

𝐴 𝐱 = 𝐲

for some

𝐱

, and

𝐲 \in

span (𝐚_{1}, \dots, 𝐚_{𝑛})

means

𝑥_{1} 𝐚_{1} +

\dots +

𝑥_{𝑛} 𝐚_{𝑛} =

𝐲

for some scalars

𝑥_{𝑗}

. By Proposition 3.1.5, each says that the system has a solution. For (b),

𝐱

solves

𝐴 𝐱 = 𝟎

exactly when

𝑇_{𝐴} (𝐱) = 𝟎

(a) By Definition 2.6.6 and Definition 2.3.15, $𝐲 \in im 𝑇_{𝐴}$ means that $𝐴 𝐱 = 𝐲$ for some $𝐱 \in 𝐹^{𝑛}$ . By Definition 1.3.10, $𝐲 \in$ $span (𝐚_{1}, \dots, 𝐚_{𝑛})$ means that $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛} =$ $𝐲$ for some $𝑥_{1}, \dots, 𝑥_{𝑛} \in 𝐹$ . By Proposition 3.1.5, each of these says that the system has a solution $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑛})$ .

(b) By Proposition 3.1.5, $𝐱 \in 𝐹^{𝑛}$ solves $𝐴 𝐱 = 𝟎$ if and only if $𝑇_{𝐴} (𝐱) = 𝐴 𝐱 = 𝟎$ , that is, if and only if $𝐱 \in ker 𝑇_{𝐴}$ (Definition 2.6.5). □

Combining Proposition 3.1.8 with the Fundamental Theorems gives a dictionary between the three faces (Table 3.1.1). Each row says the same thing about $𝐴$ in three ways. Most of the questions we ask about a matrix in the next two chapters are entries of this table, and Gauss–Jordan elimination will answer each of them by inspecting a single matrix.

The system $𝐴 𝐱 = 𝐲$	The map $𝑇_{𝐴}$	The columns of $𝐴$
is consistent	$𝐲 \in im 𝑇_{𝐴}$	$𝐲$ is in their span
with $𝐲 = 𝟎$ has a solution $𝐱 \neq 𝟎$	$ker 𝑇_{𝐴} \neq {𝟎}$	they are linearly dependent
is consistent for every $𝐲 \in 𝐹^{𝑚}$	$𝑇_{𝐴}$ is surjective	they span $𝐹^{𝑚}$
has at most one solution for every $𝐲$	$𝑇_{𝐴}$ is injective	they are linearly independent
has exactly one solution for every $𝐲$	$𝑇_{𝐴}$ is bijective	they form a basis of $𝐹^{𝑚}$

Table 3.1.1. Three readings of the same property. The first two rows come from Proposition 3.1.8 and the definition of linear independence (Definition 1.5.1). The last three are parts of Theorem 2.7.4, Theorem 2.7.2, and Theorem 2.7.8.

The third reading turns questions about vectors into linear systems. This move is used so often that it deserves a name.

Technique 3.1.9 (Undetermined coefficients). 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} +$ $\dots +$ $𝑐_{𝑘} 𝐯_{𝑘} =$ $𝐰$ in the unknowns $𝑐_{𝑖}$ . Linear independence of $𝐯_{1}, \dots, 𝐯_{𝑘}$ asks whether the homogeneous system $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐯_{𝑘} =$ $𝟎$ has only the trivial solution. The canonical example is Example 3.1.10.

Used in 15 places and 9 practice exercises

Exercise 3.1.11, Exercise 3.1.29, Exercise 3.1.37, Exercise 3.1.38, Exercise 3.1.39, Exercise 3.1.40, Exercise 3.1.41, Theorem 3.4.24, Exercise 3.4.43, Exercise 3.6.12, Problem 3.9, Problem 3.11, Problem 3.13, Exercise 6.3.49, Exercise 6.6.48; 9 practice exercises.

Example 3.1.10 (Membership and independence over $ℝ$ and over $𝔽_{2}$ ). Let $𝐯_{1} = (1, 0, 1)$ , $𝐯_{2} = (1, 1, 0)$ , and $𝐯_{3} = (0, 1, 1)$ . Is $𝐰 = (1, 1, 1)$ a linear combination of $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ ? Writing $𝑐_{1} 𝐯_{1} +$ $𝑐_{2} 𝐯_{2} +$ $𝑐_{3} 𝐯_{3} =$ $𝐰$ and comparing entries gives the system

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

Adding the three equations shows that every solution satisfies $2 (𝑐_{1} + 𝑐_{2} + 𝑐_{3}) = 3$ .

Over $ℝ$ we may divide by $2$ , so every solution has $𝑐_{1} + 𝑐_{2} + 𝑐_{3} = 3 / 2$ . Subtracting each of the three equations from this one gives $𝑐_{3} = 1 / 2$ , $𝑐_{1} = 1 / 2$ , and $𝑐_{2} = 1 / 2$ . Conversely, $(1 / 2, 1 / 2, 1 / 2)$ satisfies all three equations. So $𝐰 =$ $\frac{1}{2} (𝐯_{1} + 𝐯_{2} + 𝐯_{3})$ , and this is the only way to write $𝐰$ as a combination of the $𝐯_{𝑖}$ . The same computation with right-hand side $𝟎$ shows that $𝑐_{1} +$ $𝑐_{2} =$ $𝑐_{2} +$ $𝑐_{3} =$ $𝑐_{1} +$ $𝑐_{3} =$ $0$ has only the trivial solution, so $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ is linearly independent over $ℝ$ .

Over $𝔽_{2}$ we have $2 = 0$ and $3 = 1$ , so every solution would satisfy $0 = 1$ . The system is inconsistent, and $𝐰 \notin$ $span (𝐯_{1}, 𝐯_{2}, 𝐯_{3})$ . The homogeneous system now has the nontrivial solution $(1, 1, 1)$ , because $𝐯_{1} +$ $𝐯_{2} +$ $𝐯_{3} =$ $(2, 2, 2) =$ $𝟎$ , so the list is linearly dependent over $𝔽_{2}$ .

The only step that distinguished the two fields was a division by $2$ . Elimination divides by nonzero scalars all the time, and which scalars are nonzero depends on the field.

Exercise 3.1.11.routine Set up a linear system whose solutions are exactly the triples $(𝑐_{1}, 𝑐_{2}, 𝑐_{3}) \in ℝ^{3}$ with

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

in $ℝ [𝑥]$ , and solve it.

Solution.

Uses. Technique 3.1.9 (Undetermined coefficients), Definition 1.2.13 (Polynomials)

Techniques. Undetermined coefficients (Technique 3.1.9)

Hint 1. Expand the right side and collect the coefficients of

𝑥^{2}

𝑥

, and

1

Hint 2. Two polynomials are equal exactly when their coefficients agree, which gives three equations.

Sketch. The right side is

(𝑐_{1} + 𝑐_{2}) 𝑥^{2} +

(2 𝑐_{1} - 2 𝑐_{2}) 𝑥 +

(𝑐_{1} + 𝑐_{2} + 𝑐_{3})

, so the system is

𝑐_{1} + 𝑐_{2} = 1

2 𝑐_{1} - 2 𝑐_{2} = 0

𝑐_{1} + 𝑐_{2} + 𝑐_{3} = 0

, with unique solution

(1 / 2, 1 / 2, - 1)

Expanding, $𝑐_{1} {(𝑥 + 1)}^{2} +$ $𝑐_{2} {(𝑥 - 1)}^{2} +$ $𝑐_{3} =$ $(𝑐_{1} + 𝑐_{2}) 𝑥^{2} +$ $(2 𝑐_{1} - 2 𝑐_{2}) 𝑥 +$ $(𝑐_{1} + 𝑐_{2} + 𝑐_{3})$ . Comparing coefficients with $𝑥^{2} = 1 𝑥^{2} + 0 𝑥 + 0$ gives the system

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

The second equation gives $𝑐_{1} = 𝑐_{2}$ , and then the first gives $𝑐_{1} = 𝑐_{2} = 1 / 2$ ; the third gives $𝑐_{3} = - 1$ . Conversely, $(1 / 2, 1 / 2, - 1)$ satisfies all three equations. So the system has exactly one solution, and

𝑥^{2} = \frac{1}{2} {(𝑥 + 1)}^{2} + \frac{1}{2} {(𝑥 - 1)}^{2} - 1 .

3.1.3Augmented matrices and elimination

Definition 3.1.12 (Augmented matrix). The augmented matrix of the system

𝐴 𝐱 = 𝐲

, where

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

𝐲 \in 𝐹^{𝑚}

, is the

𝑚 \times (𝑛 + 1)

matrix

(𝐴 | 𝐲)

obtained by adjoining

𝐲

𝐴

as a last column. A vertical bar separates the coefficients from the right-hand sides.

The augmented matrix of the running system (Example 3.1.2) is

(\begin{matrix} 1 & 2 & - 1 & 1 \\ 2 & 5 & 1 & 5 \\ 3 & 7 & 0 & 6 \end{matrix}) .

Row $𝑖$ of the augmented matrix records equation $𝑖$ , so operations on equations become operations on rows, and we can skip writing the unknowns.

Example 3.1.13 (Elimination on the running system). We solve the running system by eliminating unknowns. Subtract $2$ times the first equation from the second, and $3$ times the first from the third:

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

Now subtract the second equation from the third, and $2$ times the second from the first:

(\begin{matrix} 1 & 0 & - 7 & - 5 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 0 & 0 \end{matrix}) .

The last row is the equation $0 = 0$ , which every vector satisfies. The other two rows say $𝑥_{1} - 7 𝑥_{3} = - 5$ and $𝑥_{2} + 3 𝑥_{3} = 3$ . Whatever value $𝑡$ we give $𝑥_{3}$ , these determine $𝑥_{1} = - 5 + 7 𝑡$ and $𝑥_{2} = 3 - 3 𝑡$ . So the solution set is

{(- 5 + 7 𝑡, 3 - 3 𝑡, 𝑡) | 𝑡 \in ℝ} = {(- 5, 3, 0) + 𝑡 (7, - 3, 1) | 𝑡 \in ℝ},

the line through $(- 5, 3, 0)$ in the direction of $(7, - 3, 1)$ . The solutions $(- 5, 3, 0)$ and $(2, 0, 1)$ from Example 3.1.2 are the points with $𝑡 = 0$ and $𝑡 = 1$ .

If the third right-hand side were $7$ instead of $6$ , the same operations would end with the row $(0, 0, 0 | 1)$ , which is the equation $0 = 1$ . No vector satisfies it, so that system is inconsistent.

These moves never change the solution set. Each new equation is a combination of the old ones, so every solution of the old system also solves the new one. And each move can be undone by a move of the same kind: subtracting $2$ times the first equation from the second is undone by adding $2$ times the first equation back, which is possible because the first equation is still there. (In each step of the example, the equations we subtracted were themselves left unchanged in that step.) So the old equations are combinations of the new ones as well, and every solution of the new system solves the old one. The two systems are equivalent. Section 3.2 makes this precise by writing each move as left multiplication by an invertible matrix, and Exercise 3.1.35 shows what goes wrong when a move cannot be undone.

Intuition (Why we need an algorithm). Elimination by hand worked here, but each step was a choice, and we stopped when the answer looked readable. To prove theorems with elimination we need a precise procedure: one that always terminates, whose steps provably never change the solution set, and whose output has a standard shape from which the solution set, and every row of Table 3.1.1, can be read off directly. Gauss–Jordan elimination (Section 3.3) is that procedure. Section 3.2 sets up its bookkeeping, Section 3.4 reads solutions off its output, and Section 3.5 uses it to finish the Fundamental Theorems. It stays the computational engine through Chapter 4, where it computes bases, dimensions, and ranks.

3.1.4Homogeneous systems and the shape of the solution set

Definition 3.1.14 (Homogeneous system). A linear system

𝐴 𝐱 = 𝐲

is homogeneous if

𝐲 = 𝟎

. The associated homogeneous system of

𝐴 𝐱 = 𝐲

𝐴 𝐱 = 𝟎

. Every homogeneous system has the trivial solution

𝐱 = 𝟎

; any other solution is nontrivial.

Example 3.1.15 (The running system, made homogeneous). The associated homogeneous system of the running system is $𝑥_{1} + 2 𝑥_{2} - 𝑥_{3} = 0$ , $2 𝑥_{1} + 5 𝑥_{2} + 𝑥_{3} = 0$ , $3 𝑥_{1} + 7 𝑥_{2} = 0$ . The row operations of Example 3.1.13 never mix the last column into the others, and a last column of zeros stays zero, so they end with $𝑥_{1} - 7 𝑥_{3} = 0$ and $𝑥_{2} + 3 𝑥_{3} = 0$ . The solution set is

{𝑡 (7, - 3, 1) | 𝑡 \in ℝ} = span ((7, - 3, 1)),

a line through the origin, parallel to the solution line of the running system.

Corollary 3.1.16 (Homogeneous solution sets are subspaces). The solution set of a homogeneous system

𝐴 𝐱 = 𝟎

, where

𝐴 \in 𝐹^{𝑚 \times 𝑛}

, is the subspace

ker 𝑇_{𝐴}

𝐹^{𝑛}

Proof.routine

Uses. Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Proposition 2.6.8 (Kernels and images are subspaces)

Hint 1. Which subset of

𝐹^{𝑛}

is the solution set, by Proposition 3.1.8?

Hint 2. Kernels of linear maps are subspaces.

Sketch. By Proposition 3.1.8 the solution set is

ker 𝑇_{𝐴}

, and the kernel of a linear map is a subspace of its domain.

By part (b) of Proposition 3.1.8, the solution set is

ker 𝑇_{𝐴}

. Since

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

is linear,

ker 𝑇_{𝐴}

is a subspace of

𝐹^{𝑛}

by Proposition 2.6.8. □

Concretely: sums and scalar multiples of solutions of a homogeneous system are again solutions. A system with $𝐲 \neq 𝟎$ has no such luck. Its solution set never contains $𝟎$ , since $𝐴 𝟎 = 𝟎 \neq 𝐲$ , so it is never a subspace. The running system shows what it is instead: the line of solutions in Example 3.1.13 is the line of Example 3.1.15, moved over so that it passes through one solution. To say this in general we need a name for a moved-over subset.

Notation 3.1.17 (Translates). Let $𝑉$ be a vector space, $𝐯 \in 𝑉$ , and $𝑈 \subseteq 𝑉$ . The translate of $𝑈$ by $𝐯$ is

𝐯 + 𝑈 = {𝐯 + 𝐮 | 𝐮 \in 𝑈} .

Intuition. Suppose

𝐱

and

𝐱^{'}

both solve

𝐴 𝐱 = 𝐲

. Then

𝐴 (𝐱^{'} - 𝐱) =

𝐲 -

𝐲 =

𝟎

, so any two solutions differ by a solution of the homogeneous system. Conversely, adding a homogeneous solution

𝐳

to a solution

𝐱

gives another solution, since

𝐴 (𝐱 + 𝐳) = 𝐲 + 𝟎

. So once we know one solution, the others are exactly the ones we reach from it by adding elements of

ker 𝑇_{𝐴}

. Only linearity is involved, so the same holds for any linear map in place of

𝑇_{𝐴}

Technique 3.1.18 (Particular plus homogeneous). To find every solution of a linear equation $𝑇 (𝐱) = 𝐲$ , find one solution $𝐱_{0}$ , called a particular solution, and all solutions of the homogeneous equation $𝑇 (𝐳) = 𝟎$ . 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.

Used in 22 places and 8 practice exercises

Corollary 2.6.31, Exercise 2.6.33, Exercise 2.6.34, Proposition 3.1.19, Exercise 3.1.21, Corollary 3.1.22, Corollary 3.1.23, Exercise 3.1.29, Exercise 3.1.30, Exercise 3.1.31, Exercise 3.1.37, Exercise 3.1.38, Exercise 3.1.46, Exercise 3.1.47, Theorem 3.4.9, Exercise 3.6.12, Problem 3.1, Problem 3.5, Problem 3.9, Problem 3.16, Theorem 4.7.8, Corollary 7.1.30; 8 practice exercises.

Proposition 3.1.19 (Solution sets are translates of the kernel). Let $𝑇 : 𝑉 \to 𝑊$ be a linear map, let $𝐲 \in 𝑊$ , and let $𝑆 =$ ${𝐱 \in 𝑉 | 𝑇 (𝐱) = 𝐲}$ . If $𝐱_{0} \in 𝑆$ , then

𝑆 = 𝐱_{0} + ker 𝑇,

and the map $ker 𝑇 \to 𝑆$ , $𝐳 \mapsto 𝐱_{0} + 𝐳$ , is a bijection. In particular, the solution set of a linear system $𝐴 𝐱 = 𝐲$ is either empty or equal to $𝐱_{0} + ker 𝑇_{𝐴}$ , where $𝐱_{0}$ is any one solution.

Proof.routine

Uses. Definition 2.1.1 (Linear map), Definition 2.6.5 (Kernel), Notation 3.1.17 (Translates), Proposition 1.2.34 (Negatives and the scalar $- 1$ ), Proposition 3.1.5 (Three faces of a linear system)

Techniques. Double containment (Technique 1.3.14), Particular plus homogeneous (Technique 3.1.18)

Hint 1. Prove

𝐱_{0} + ker 𝑇 \subseteq 𝑆

and

𝑆 \subseteq 𝐱_{0} + ker 𝑇

separately.

Hint 2. For the first containment, apply

𝑇

𝐱_{0} + 𝐳

, where

𝐳 \in ker 𝑇

Hint 3. For the second, given

𝐱 \in 𝑆

, the only possible choice of

𝐳

𝐱 - 𝐱_{0}

. Show that it lies in

ker 𝑇

Sketch. If

𝑇 (𝐳) = 𝟎

, then

𝑇 (𝐱_{0} + 𝐳) =

𝐲 +

𝟎 =

𝐲

. If

𝑇 (𝐱) = 𝐲

, then

𝑇 (𝐱 - 𝐱_{0}) =

𝐲 -

𝐲 =

𝟎

, and

𝐱 = 𝐱_{0} + (𝐱 - 𝐱_{0})

. So

𝐳 \mapsto 𝐱_{0} + 𝐳

maps

ker 𝑇

onto

𝑆

, and it is injective by cancellation. For a system, take

𝑇 = 𝑇_{𝐴}

and use Proposition 3.1.5.

Suppose $𝐱_{0} \in 𝑆$ , so that $𝑇 (𝐱_{0}) = 𝐲$ . We prove the two containments.

$𝐱_{0} + ker 𝑇 \subseteq 𝑆$ . Let $𝐳 \in ker 𝑇$ . Since $𝑇$ is linear,

𝑇 (𝐱_{0} + 𝐳) = 𝑇 (𝐱_{0}) + 𝑇 (𝐳) = 𝐲 + 𝟎 = 𝐲,

so $𝐱_{0} + 𝐳 \in 𝑆$ .

$𝑆 \subseteq 𝐱_{0} + ker 𝑇$ . Let $𝐱 \in 𝑆$ , and put $𝐳 =$ $𝐱 -$ $𝐱_{0} =$ $𝐱 +$ $(- 1) 𝐱_{0}$ (Proposition 1.2.34). Since $𝑇$ is linear,

𝑇 (𝐳) = 𝑇 (𝐱) + (- 1) 𝑇 (𝐱_{0}) = 𝐲 - 𝐲 = 𝟎,

so $𝐳 \in ker 𝑇$ , and $𝐱 =$ $𝐱_{0} +$ $𝐳 \in$ $𝐱_{0} +$ $ker 𝑇$ .

Hence $𝑆 = 𝐱_{0} + ker 𝑇$ , which says exactly that $𝐳 \mapsto 𝐱_{0} + 𝐳$ maps $ker 𝑇$ onto $𝑆$ . This map is also injective: if $𝐱_{0} + 𝐳 = 𝐱_{0} + 𝐳^{'}$ , adding $- 𝐱_{0}$ to both sides gives $𝐳 = 𝐳^{'}$ . So it is a bijection.

For the last statement, let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ . By Proposition 3.1.5, the solution set of the system $𝐴 𝐱 = 𝐲$ is ${𝐱 \in 𝐹^{𝑛} | 𝑇_{𝐴} (𝐱) = 𝐲}$ . If it is nonempty, we apply what we proved to $𝑇 = 𝑇_{𝐴}$ and any solution $𝐱_{0}$ . □

So the solution set of a consistent system is $ker 𝑇_{𝐴}$ slid over to pass through any one solution, and which solution we slide it to does not matter. For the running system, Example 3.1.13 and Example 3.1.15 give

{𝐱 \in ℝ^{3} | 𝐴 𝐱 = 𝐲} = (- 5, 3, 0) + span ((7, - 3, 1)) = (2, 0, 1) + span ((7, - 3, 1)) .

The proof used nothing about $𝑉$ and $𝑊$ beyond the linearity of $𝑇$ , so the proposition applies to linear equations far from $𝐹^{𝑛}$ .

Example 3.1.20 (A linear equation in $ℝ [𝑥]$ ). Let $𝐷 : ℝ [𝑥] \to ℝ [𝑥]$ be differentiation, $𝐷 (𝑓) = 𝑓^{'}$ , which is linear (Section 2.1). Which polynomials $𝑓$ satisfy $𝑓^{'} = 2 𝑥 + 1$ ? One solution is $𝑥^{2} + 𝑥$ . The kernel of $𝐷$ consists of the constant polynomials: if $𝑓 =$ $𝑐_{0} +$ $𝑐_{1} 𝑥 +$ $\dots +$ $𝑐_{𝑑} 𝑥^{𝑑}$ and $𝑓^{'} =$ $𝑐_{1} +$ $2 𝑐_{2} 𝑥 +$ $\dots +$ $𝑑 𝑐_{𝑑} 𝑥^{𝑑 - 1} =$ $0$ , then $𝑘 𝑐_{𝑘} = 0$ , hence $𝑐_{𝑘} = 0$ , for every $𝑘 \geq 1$ . By Proposition 3.1.19, the solutions are exactly the polynomials $𝑥^{2} + 𝑥 + 𝑐$ with $𝑐 \in ℝ$ : the “ $+ 𝐶$ ” of an antiderivative is the kernel of $𝐷$ .

Over $𝔽_{𝑝}$ the step from $𝑘 𝑐_{𝑘} = 0$ to $𝑐_{𝑘} = 0$ fails when $𝑝$ divides $𝑘$ . For instance $𝐷 (𝑥^{𝑝}) =$ $𝑝 𝑥^{𝑝 - 1} =$ $0$ , so the kernel of $𝐷$ on $𝔽_{𝑝} [𝑥]$ is larger, and so is every nonempty solution set.

Aside (Linear differential equations). Proposition 3.1.19 is the reason behind the recipe “general solution = particular solution + complementary solution” for linear differential equations. For instance,

𝑓 \mapsto 𝑓^{″} + 𝑓

is a linear map on the space of twice-differentiable functions

ℝ \to ℝ

, its kernel consists of the functions

𝑎 cos 𝑥 + 𝑏 sin 𝑥

, and

𝑓 (𝑥) = 𝑥

is one solution of

𝑓^{″} + 𝑓 = 𝑥

. So every solution is

𝑥 +

𝑎 cos 𝑥 +

𝑏 sin 𝑥

. Identifying that kernel takes some analysis; the shape of the answer is linear algebra.

Exercise 3.1.21.routine Let

𝐴 \in ℝ^{2 \times 3}

, and suppose that

(1, 2, 0)

and

(0, 1, 1)

both solve

𝐴 𝐱 = (3, 1)

. Find a nonzero vector in

ker 𝑇_{𝐴}

, a solution of

𝐴 𝐱 = (6, 2)

, and infinitely many solutions of

𝐴 𝐱 = (3, 1)

Solution.

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Corollary 3.1.16 (Homogeneous solution sets are subspaces)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. The difference of two solutions of the same system lies in the kernel.

Hint 2. Use linearity of

𝑇_{𝐴}

for the second question, and Proposition 3.1.19 for the third.

Sketch.

𝐳 =

(1, 2, 0) -

(0, 1, 1) =

(1, 1, - 1) \in

ker 𝑇_{𝐴}

, and it is nonzero.

𝐴 (2, 4, 0) =

2 (3, 1) =

(6, 2)

. The vectors

(1, 2, 0) +

𝑡 (1, 1, - 1)

𝑡 \in ℝ

, all solve

𝐴 𝐱 = (3, 1)

Put

𝐳 =

(1, 2, 0) -

(0, 1, 1) =

(1, 1, - 1)

. Then

𝐴 𝐳 =

(3, 1) -

(3, 1) =

𝟎

, so

𝐳

is a nonzero vector of

ker 𝑇_{𝐴}

. Next,

𝐴 (2, 4, 0) =

2 𝐴 (1, 2, 0) =

2 (3, 1) =

(6, 2)

, so

(2, 4, 0)

solves

𝐴 𝐱 = (6, 2)

. Finally,

ker 𝑇_{𝐴}

is a subspace (Corollary 3.1.16), so

𝑡 𝐳 \in ker 𝑇_{𝐴}

for every

𝑡 \in ℝ

, and by Proposition 3.1.19 every vector

(1, 2, 0) +

𝑡 (1, 1, - 1) =

(1 + 𝑡, 2 + 𝑡, - 𝑡)

is a solution of

𝐴 𝐱 = (3, 1)

. These vectors are distinct for distinct

𝑡

(compare third entries), so there are infinitely many.

Consequences

Proposition 3.1.19 separates the two questions every system raises. Whether $𝐴 𝐱 = 𝐲$ has a solution depends on $𝐲$ . How many solutions it has, once it has one, depends only on $ker 𝑇_{𝐴}$ .

Corollary 3.1.22 (Uniqueness depends only on $𝐴$ ). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)A consistent system $𝐴 𝐱 = 𝐲$ has exactly one solution if and only if $ker 𝑇_{𝐴} = {𝟎}$ .
(b)If $𝐴 𝐱 = 𝐲$ has exactly one solution for some $𝐲 \in 𝐹^{𝑚}$ , then $𝐴 𝐱 = 𝐲^{'}$ has at most one solution for every $𝐲^{'} \in 𝐹^{𝑚}$ .

Proof.routine

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Proposition 2.1.4 (Linear maps preserve $𝟎$ and negatives)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. Proposition 3.1.19 gives a bijection between the solution set and

ker 𝑇_{𝐴}

. When does a set in bijection with

ker 𝑇_{𝐴}

have exactly one element?

Hint 2.

ker 𝑇_{𝐴}

always contains

𝟎

. For (b), apply (a) twice, and remember that

𝐴 𝐱 = 𝐲^{'}

might be inconsistent.

Sketch. The solution set of a consistent system is in bijection with

ker 𝑇_{𝐴}

, which contains

𝟎

, so it is a single vector exactly when

ker 𝑇_{𝐴} = {𝟎}

. For (b), (a) gives

ker 𝑇_{𝐴} = {𝟎}

, and then (a) again says that each consistent

𝐴 𝐱 = 𝐲^{'}

has one solution, while an inconsistent one has none.

(a) Let $𝑆$ be the solution set and $𝐱_{0} \in 𝑆$ . By Proposition 3.1.19, $𝐳 \mapsto 𝐱_{0} + 𝐳$ is a bijection from $ker 𝑇_{𝐴}$ onto $𝑆$ , so $𝑆$ has exactly one element if and only if $ker 𝑇_{𝐴}$ does. Since $𝟎 \in ker 𝑇_{𝐴}$ (Proposition 2.1.4), $ker 𝑇_{𝐴}$ has exactly one element if and only if $ker 𝑇_{𝐴} = {𝟎}$ .

(b) By (a), applied to the system with exactly one solution, $ker 𝑇_{𝐴} = {𝟎}$ . Let $𝐲^{'} \in 𝐹^{𝑚}$ . If $𝐴 𝐱 = 𝐲^{'}$ is inconsistent, it has no solutions. Otherwise it has exactly one solution, by (a) again. □

Part (a) recovers the implication “if $ker 𝑇_{𝐴} = {𝟎}$ , then $𝐴 𝐱 = 𝐲$ has at most one solution for every $𝐲$ ” of Theorem 2.7.2, now seen from the shape of the solution set. Part (b) cannot be improved to “exactly one solution for every $𝐲^{'}$ ”: see Exercise 3.1.34.

Over $ℝ$ , two solutions of a system determine a line, and the whole line consists of solutions. In general:

Corollary 3.1.23 (Lines through solutions). If

𝐮

and

𝐯

are solutions of the system

𝐴 𝐱 = 𝐲

over

𝐹

, then so is

𝐮 + 𝑡 (𝐯 - 𝐮)

for every

𝑡 \in 𝐹

Proof.routine

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Corollary 3.1.16 (Homogeneous solution sets are subspaces)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. Use Proposition 3.1.19 with

𝐱_{0} = 𝐮

. Where does

𝐯 - 𝐮

lie?

Hint 2.

ker 𝑇_{𝐴}

is a subspace, so it is closed under scalar multiplication.

Sketch.

𝐯 - 𝐮 \in ker 𝑇_{𝐴}

since both are solutions; hence

𝑡 (𝐯 - 𝐮) \in ker 𝑇_{𝐴}

, and

𝐮 +

𝑡 (𝐯 - 𝐮) \in

𝐮 +

ker 𝑇_{𝐴}

, which is the solution set.

Let

𝑆

be the solution set. By Proposition 3.1.19 with

𝐱_{0} = 𝐮

, we have

𝑆 = 𝐮 + ker 𝑇_{𝐴}

. Since

𝐯 \in 𝑆

𝐯 = 𝐮 + 𝐳

for some

𝐳 \in ker 𝑇_{𝐴}

, namely

𝐳 = 𝐯 - 𝐮

. As

ker 𝑇_{𝐴}

is a subspace (Corollary 3.1.16),

𝑡 𝐳 \in ker 𝑇_{𝐴}

for each

𝑡 \in 𝐹

, so

𝐮 +

𝑡 (𝐯 - 𝐮) =

𝐮 +

𝑡 𝐳 \in

𝑆

. □

Corollary 3.1.24 (No, one, or infinitely many solutions). Let

𝐹

be an infinite field, such as

ℚ

ℝ

, or

ℂ

. Every linear system over

𝐹

has no solutions, exactly one solution, or infinitely many solutions.

Proof.routine

Uses. Corollary 3.1.23 (Lines through solutions), Proposition 1.2.35 (Zero products)

Hint 1. Suppose the system has two different solutions

𝐮

and

𝐯

. Produce infinitely many more.

Hint 2. Use Corollary 3.1.23, and check that different values of

𝑡

give different points: if

𝐮 +

𝑡 (𝐯 - 𝐮) =

𝐮 +

𝑡^{'} (𝐯 - 𝐮)

, what can you say about

𝑡 - 𝑡^{'}

Sketch. If

𝐮 \neq 𝐯

are solutions, the points

𝐮 + 𝑡 (𝐯 - 𝐮)

are solutions, and they are distinct for distinct

𝑡

because

(𝑡 - 𝑡^{'}) (𝐯 - 𝐮) =

𝟎

with

𝐯 - 𝐮 \neq 𝟎

forces

𝑡 = 𝑡^{'}

. An infinite field gives infinitely many values of

𝑡

Suppose a system has at least two solutions; we show that it has infinitely many. Let

𝐮 \neq 𝐯

be solutions. By Corollary 3.1.23,

𝐮 + 𝑡 (𝐯 - 𝐮)

is a solution for every

𝑡 \in 𝐹

. These solutions are pairwise distinct: if

𝐮 +

𝑡 (𝐯 - 𝐮) =

𝐮 +

𝑡^{'} (𝐯 - 𝐮)

, then

(𝑡 - 𝑡^{'}) (𝐯 - 𝐮) =

𝟎

, and since

𝐯 - 𝐮 \neq 𝟎

, Proposition 1.2.35 gives

𝑡 - 𝑡^{'} = 0

. As

𝐹

is infinite, the system has infinitely many solutions. □

For a finite field the third option is impossible, and the right replacement is a count.

Corollary 3.1.25 (Counting solutions over a finite field). Let

𝐹

be a finite field and

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. Every consistent system

𝐴 𝐱 = 𝐲

has exactly as many solutions as the homogeneous system

𝐴 𝐱 = 𝟎

Proof.routine

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ )

Hint 1. What is the solution set of the homogeneous system, as a subset of

𝐹^{𝑛}

Hint 2. Proposition 3.1.19 gives a bijection from it onto the solution set of

𝐴 𝐱 = 𝐲

Sketch. The homogeneous solution set is

ker 𝑇_{𝐴}

, and

𝐳 \mapsto 𝐱_{0} + 𝐳

is a bijection from

ker 𝑇_{𝐴}

onto the solution set of

𝐴 𝐱 = 𝐲

. Finite sets in bijection have the same size.

By Proposition 3.1.8, the solution set of

𝐴 𝐱 = 𝟎

ker 𝑇_{𝐴}

. If

𝐴 𝐱 = 𝐲

is consistent with a solution

𝐱_{0}

, then by Proposition 3.1.19 the map

𝐳 \mapsto 𝐱_{0} + 𝐳

is a bijection from

ker 𝑇_{𝐴}

onto its solution set. Both sets are finite, as subsets of the finite set

𝐹^{𝑛}

, so they have the same number of elements. □

Example 3.1.26 (Exactly two solutions). Over

𝔽_{2}

, the equation

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

has exactly two solutions,

(1, 0)

and

(0, 1)

, and its homogeneous version

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

has exactly two,

(0, 0)

and

(1, 1)

. So Corollary 3.1.24 really needs

𝐹

to be infinite. The “line” through the two solutions,

𝐮 + 𝑡 (𝐯 - 𝐮)

with

𝑡 \in 𝔽_{2}

, consists of

𝐮

and

𝐯

alone, because

𝔽_{2}

has only two values of

𝑡

. Once we have dimension, Corollary 3.1.25 becomes a formula: over a field with

𝑞

elements, a consistent system has exactly

𝑞^{𝑘}

solutions, where

𝑘 = dim ker 𝑇_{𝐴}

(Section 4.1).

3.1.5Pictures in $ℝ^{2}$ and $ℝ^{3}$

Over $ℝ$ we can draw what the results of this section say.

The row picture

An equation $𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} = 𝑏$ with $(𝑎_{1}, 𝑎_{2}) \neq (0, 0)$ describes a line in $ℝ^{2}$ . An equation with $𝑎_{1} = 𝑎_{2} = 0$ reads $0 = 𝑏$ ; its solution set is all of $ℝ^{2}$ if $𝑏 = 0$ and empty otherwise. The solution set of a system is the intersection of the solution sets of its equations, so two equations in two unknowns, each with a nonzero coefficient, describe the intersection of two lines. There are three possibilities (Figure 3.1.2): the lines cross in one point, they are parallel and distinct, or they coincide.

Figure 3.1.2. Two equations in two unknowns over

ℝ

. Left:

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

𝑥_{1} - 𝑥_{2} = 0

, with the single solution

(1, 1)

. Middle:

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

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

, which is inconsistent. Right:

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

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

, two equations with the same solution set.

An equation in $𝑥_{1}, 𝑥_{2}, 𝑥_{3}$ with some nonzero coefficient describes a plane in $ℝ^{3}$ , and a system describes an intersection of planes. Two planes meet in a line, are parallel and distinct, or coincide. Three planes have more options. They can meet in a single point; pass through a common line, as the planes of the running system do (Example 3.1.13); coincide; or have no point in common. The last case occurs when two of the planes are parallel and distinct, but also in a less obvious way. Changing the right-hand side of the running system from $(1, 5, 6)$ to $(1, 5, 7)$ moves the third plane off the common line of the first two, but keeps it parallel to that line. The result is three planes, no two of them parallel, that meet in pairs along three parallel lines and have no point in common (Figure 3.1.3). Elimination detected this as the equation $0 = 1$ .

Figure 3.1.3. Three planes, no two of them parallel, with no common point. Each pair meets in a line (black), and the three lines are parallel. The planes of the running system with right-hand side

(1, 5, 7)

are arranged like this, with the three lines parallel to

(7, - 3, 1)

The column picture

The columns $(1, 2, 3)$ , $(2, 5, 7)$ , $(- 1, 1, 0)$ of the running system all satisfy $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ , and this condition is preserved by sums and scalar multiples, so every combination of the columns satisfies it too. Hence $𝐴 𝐱 = 𝐲$ can only be consistent if $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ . The right-hand side $(1, 5, 6)$ passes this test and $(1, 5, 7)$ fails it, which explains the inconsistency without any elimination. Conversely, every $𝐲$ with $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ is reached, since

(5 𝑦_{1} - 2 𝑦_{2}) (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) + (𝑦_{2} - 2 𝑦_{1}) (\begin{matrix} 2 \\ 5 \\ 7 \end{matrix}) = (\begin{matrix} 𝑦_{1} \\ 𝑦_{2} \\ 𝑦_{1} + 𝑦_{2} \end{matrix}) .

So $im 𝑇_{𝐴}$ is the plane $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ in $ℝ^{3}$ . The row picture lives in the space of unknowns and the column picture in the space of right-hand sides, and the two describe the same system from opposite ends.

Many right-hand sides

Proposition 3.1.19 adds the last piece. For a fixed $𝐴$ , the nonempty solution sets of $𝐴 𝐱 = 𝐲$ , as $𝐲$ varies, are all translates of the single subspace $ker 𝑇_{𝐴}$ , so they are parallel to each other (Figure 3.1.4).

Figure 3.1.4. The solution sets of

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

ℝ^{2}

for several values of

𝑐

. Each is a translate of

ker 𝑇_{𝐴}

, the solution set for

𝑐 = 0

(blue). For

𝑐 = 2

, the particular solution

𝐱_{0} = (1, 1)

plus any

𝐳 \in ker 𝑇_{𝐴}

is again a solution.

Remark 3.1.27 (What a solution set can look like). The subspaces of $ℝ^{2}$ are ${𝟎}$ , the lines through $𝟎$ , and $ℝ^{2}$ ; the subspaces of $ℝ^{3}$ are ${𝟎}$ , the lines and planes through $𝟎$ , and $ℝ^{3}$ . (This follows from the theory of dimension in Section 4.1.) So by Proposition 3.1.19, the solution set of a real linear system in two or three unknowns is empty, a point, a line, a plane, or the whole space. It is never a circle or a pair of points.

In any vector space, a translate $𝐯 + 𝑈$ of a subspace $𝑈$ is called an affine subspace (Definition 4.7.1). In this language, Proposition 3.1.19 says that the solution set of a consistent system is an affine subspace, and that it is a translate of $ker 𝑇_{𝐴}$ . Section 4.7 studies affine subspaces in their own right.

Exercises

Exercise 3.1.28.routine Which of the following are linear systems in the unknowns $𝑥_{1}, 𝑥_{2}, 𝑥_{3}$ over $ℝ$ ? For each one that is, write its coefficient matrix and its augmented matrix.

(a) $𝑥_{1} = 2 𝑥_{2} - 𝑥_{3} + 1$ and $𝑥_{3} = 4 𝑥_{1}$ .
(b) $𝑥_{1} 𝑥_{2} = 0$ and $𝑥_{3} = 1$ .
(c) $(sin 1) 𝑥_{1} +$ $𝑒 𝑥_{2} =$ $𝜋 𝑥_{3}$ .
(d) $2 𝑥_{1} + 3 = 𝑥_{2} - 𝑥_{1}$ and $𝑥_{2} + 𝑥_{3} = \sqrt{2}$ .

Solution.

Uses. Definition 3.1.1 (Linear system), Definition 3.1.4 (Coefficient matrix; matrix and vector forms), Definition 3.1.12 (Augmented matrix), Corollary 3.1.23 (Lines through solutions)

Hint 1. Move every term involving an unknown to the left and every constant to the right. Is each term then a scalar times a single unknown?

Hint 2. Coefficients may be any real numbers, including

sin 1

and

𝜋

. A product of two unknowns is not allowed.

Sketch. (a), (c), and (d) are linear; rearranged they read

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

- 4 𝑥_{1} + 𝑥_{3} = 0

; then

(sin 1) 𝑥_{1} +

𝑒 𝑥_{2} -

𝜋 𝑥_{3} =

0

; then

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

𝑥_{2} + 𝑥_{3} = \sqrt{2}

. (b) contains the product

𝑥_{1} 𝑥_{2}

Adding the same expression to both sides of an equation does not change its solutions, so we may move terms freely.

(a) Linear. Rearranged, the system is $𝑥_{1} - 2 𝑥_{2} + 𝑥_{3} = 1$ , $- 4 𝑥_{1} + 𝑥_{3} = 0$ , so

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

(b) Not linear: the term $𝑥_{1} 𝑥_{2}$ is a product of two unknowns. In fact its solution set, the points with $𝑥_{3} = 1$ and $𝑥_{1} = 0$ or $𝑥_{2} = 0$ , is not the solution set of any linear system: it contains $(1, 0, 1)$ and $(0, 1, 1)$ but not $(\frac{1}{2}, \frac{1}{2}, 1)$ , which lies on the line through them, contrary to Corollary 3.1.23.

(c) Linear: one equation $(sin 1) 𝑥_{1} +$ $𝑒 𝑥_{2} -$ $𝜋 𝑥_{3} =$ $0$ , so

𝐴 = (\begin{matrix} sin 1 & 𝑒 & - 𝜋 \end{matrix}), (𝐴 | 𝐲) = (\begin{matrix} sin 1 & 𝑒 & - 𝜋 & 0 \end{matrix}) .

(d) Linear. Rearranged, the system is $3 𝑥_{1} - 𝑥_{2} = - 3$ , $𝑥_{2} + 𝑥_{3} = \sqrt{2}$ , so

𝐴 = (\begin{matrix} 3 & - 1 & 0 \\ 0 & 1 & 1 \end{matrix}), (𝐴 | 𝐲) = (\begin{matrix} 3 & - 1 & 0 & - 3 \\ 0 & 1 & 1 & \sqrt{2} \end{matrix}) .

Exercise 3.1.29.routine Let $𝐚_{1} = (1, 2, 3)$ , $𝐚_{2} = (2, 1, 0)$ , and $𝐚_{3} = (3, 3, 3)$ in $ℝ^{3}$ .

(a)Write $(1, 5, 9)$ as a linear combination of $𝐚_{1}, 𝐚_{2}, 𝐚_{3}$ in every possible way.
(b)Show that $(1, 0, 0)$ is not a linear combination of $𝐚_{1}, 𝐚_{2}, 𝐚_{3}$ .

Solution.

Uses. Technique 3.1.9 (Undetermined coefficients), Proposition 3.1.5 (Three faces of a linear system), Proposition 3.1.19 (Solution sets are translates of the kernel)

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

Hint 1. The combinations

𝑐_{1} 𝐚_{1} +

𝑐_{2} 𝐚_{2} +

𝑐_{3} 𝐚_{3} =

𝐲

are the solutions of a linear system with augmented matrix

(𝐚_{1} 𝐚_{2} 𝐚_{3} | 𝐲)

. Eliminate.

Hint 2. Notice

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

. For (b), look for a linear condition that all three columns satisfy.

Sketch. Elimination reduces (a) to

𝑐_{1} + 𝑐_{3} = 3

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

, so the combinations are

(3 - 𝑡) 𝐚_{1} +

(- 1 - 𝑡) 𝐚_{2} +

𝑡 𝐚_{3}

. In (b) elimination produces

0 = 1

; equivalently, every column satisfies

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

and

(1, 0, 0)

does not.

(a) We want all $(𝑐_{1}, 𝑐_{2}, 𝑐_{3})$ with $𝑐_{1} 𝐚_{1} +$ $𝑐_{2} 𝐚_{2} +$ $𝑐_{3} 𝐚_{3} =$ $(1, 5, 9)$ . The augmented matrix is

(\begin{matrix} 1 & 2 & 3 & 1 \\ 2 & 1 & 3 & 5 \\ 3 & 0 & 3 & 9 \end{matrix}) .

Subtracting $2$ times row $1$ from row $2$ and $3$ times row $1$ from row $3$ gives rows $(0, - 3, - 3 | 3)$ and $(0, - 6, - 6 | 6)$ . Subtracting $2$ times the new row $2$ from the new row $3$ gives the zero row, and scaling row $2$ by $- 1 / 3$ gives $(0, 1, 1 | - 1)$ . Finally, subtracting $2$ times this row from row $1$ gives $(1, 0, 1 | 3)$ . So the system is equivalent to $𝑐_{1} + 𝑐_{3} = 3$ , $𝑐_{2} + 𝑐_{3} = - 1$ , and its solutions are $(𝑐_{1}, 𝑐_{2}, 𝑐_{3}) =$ $(3 - 𝑡, - 1 - 𝑡, 𝑡)$ for $𝑡 \in ℝ$ . That is,

(1, 5, 9) = (3 - 𝑡) 𝐚_{1} + (- 1 - 𝑡) 𝐚_{2} + 𝑡 𝐚_{3} (𝑡 \in ℝ),

and these are all the ways. This matches Proposition 3.1.19: $(3, - 1, 0)$ is one solution, and the homogeneous solutions are the multiples of $(- 1, - 1, 1)$ , reflecting $𝐚_{3} = 𝐚_{1} + 𝐚_{2}$ .

(b) The same row operations applied to $(𝐚_{1} 𝐚_{2} 𝐚_{3} | (1, 0, 0))$ give the rows $(1, 2, 3 | 1)$ , $(0, - 3, - 3 | - 2)$ , $(0, - 6, - 6 | - 3)$ , and then the last row becomes $(0, 0, 0 | 1)$ . So every solution would satisfy $0 = 1$ , and there is none. Here is a second argument, from the column picture. Each column satisfies $𝑦_{1} - 2 𝑦_{2} + 𝑦_{3} = 0$ : $1 - 4 + 3 = 0$ , $2 - 2 + 0 = 0$ , and $3 - 6 + 3 = 0$ . This condition is preserved by sums and scalar multiples, so every linear combination of the columns satisfies it. But $(1, 0, 0)$ gives $1 \neq 0$ .

Exercise 3.1.30.routine List all solutions of the system

𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 1, 𝑥_{1} + 2 𝑥_{2} = 0

over $𝔽_{3}$ , and check that their number agrees with Corollary 3.1.25. How many solutions does the same system have over $ℝ$ ?

Solution.

Uses. Corollary 3.1.25 (Counting solutions over a finite field), Corollary 3.1.24 (No, one, or infinitely many solutions)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. Solve the second equation for

𝑥_{1}

. In

𝔽_{3}

- 2 = 1

Hint 2. Then the first equation determines

𝑥_{3}

in terms of

𝑥_{2}

, and

𝑥_{2}

is free. For the count, also solve the homogeneous system.

Sketch. Over

𝔽_{3}

𝑥_{1} = 𝑥_{2}

and

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

, giving

(0, 0, 1)

(1, 1, 2)

(2, 2, 0)

. The homogeneous solutions are

(𝑡, 𝑡, 𝑡)

, also three. Over

ℝ

(- 2 𝑠, 𝑠, 1 + 𝑠)

, infinitely many.

Over $𝔽_{3}$ , the second equation says $𝑥_{1} = - 2 𝑥_{2} = 𝑥_{2}$ . Substituting into the first, $𝑥_{3} = 1 - 2 𝑥_{2} = 1 + 𝑥_{2}$ . Conversely, for each $𝑡 \in 𝔽_{3}$ the vector $(𝑡, 𝑡, 1 + 𝑡)$ satisfies both equations: $𝑡 +$ $𝑡 +$ $1 +$ $𝑡 =$ $1 +$ $3 𝑡 =$ $1$ and $𝑡 + 2 𝑡 = 3 𝑡 = 0$ . So the solutions are

(0, 0, 1), (1, 1, 2), (2, 2, 0) .

The homogeneous system $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0$ , $𝑥_{1} + 2 𝑥_{2} = 0$ gives $𝑥_{1} = 𝑥_{2}$ and $𝑥_{3} = - 2 𝑥_{2} = 𝑥_{2}$ in the same way, so its solutions are $(0, 0, 0)$ , $(1, 1, 1)$ , $(2, 2, 2)$ : three, as Corollary 3.1.25 predicts.

Over $ℝ$ , the same steps give $𝑥_{1} = - 2 𝑥_{2}$ and $𝑥_{3} =$ $1 -$ $𝑥_{1} -$ $𝑥_{2} =$ $1 +$ $𝑥_{2}$ , so the solutions are $(- 2 𝑠, 𝑠, 1 + 𝑠)$ for $𝑠 \in ℝ$ . There are infinitely many, in line with Corollary 3.1.24.

Exercise 3.1.31.standard Let $𝑝$ be a prime, $𝑛 \geq 1$ , and $𝑐 \in 𝔽_{𝑝}$ .

(a)Show that the equation $𝑥_{1} + 𝑥_{2} + \dots + 𝑥_{𝑛} = 𝑐$ has exactly $𝑝^{𝑛 - 1}$ solutions in $𝔽_{𝑝}^{𝑛}$ .
(b)Deduce that a set with $𝑛 \geq 1$ elements has exactly $2^{𝑛 - 1}$ subsets with an even number of elements.

Solution (solve for the last unknown).

Uses. Definition 3.1.1 (Linear system)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. Once

𝑥_{1}, \dots, 𝑥_{𝑛 - 1}

are chosen, how many choices of

𝑥_{𝑛}

work?

Hint 2. For (b), encode a subset

𝑋 \subseteq {1, \dots, 𝑛}

as the vector

𝐱 \in 𝔽_{2}^{𝑛}

with

𝑥_{𝑖} = 1

exactly when

𝑖 \in 𝑋

. What is

𝑥_{1} + \dots + 𝑥_{𝑛}

𝔽_{2}

Sketch. The map

𝐱 \mapsto (𝑥_{1}, \dots, 𝑥_{𝑛 - 1})

is a bijection from the solution set onto

𝔽_{𝑝}^{𝑛 - 1}

, since

𝑥_{𝑛} =

𝑐 -

𝑥_{1} -

\dots -

𝑥_{𝑛 - 1}

is forced. For (b),

𝑥_{1} + \dots + 𝑥_{𝑛}

𝔽_{2}

is the parity of

| 𝑋 |

, so the even subsets correspond to the solutions of

𝑥_{1} + \dots + 𝑥_{𝑛} = 0

over

𝔽_{2}

(a) If $𝐱$ is a solution, then $𝑥_{𝑛} =$ $𝑐 -$ $𝑥_{1} -$ $\dots -$ $𝑥_{𝑛 - 1}$ . Conversely, for any $𝑥_{1}, \dots, 𝑥_{𝑛 - 1} \in 𝔽_{𝑝}$ , this choice of $𝑥_{𝑛}$ gives a solution. So $𝐱 \mapsto (𝑥_{1}, \dots, 𝑥_{𝑛 - 1})$ is a bijection from the solution set onto $𝔽_{𝑝}^{𝑛 - 1}$ , which has $𝑝^{𝑛 - 1}$ elements.

(b) Encode $𝑋 \subseteq {1, \dots, 𝑛}$ as $𝐱 \in 𝔽_{2}^{𝑛}$ with $𝑥_{𝑖} = 1$ if $𝑖 \in 𝑋$ and $𝑥_{𝑖} = 0$ otherwise; this is a bijection between subsets and vectors. The sum $𝑥_{1} + \dots + 𝑥_{𝑛}$ computed in $𝔽_{2}$ is the remainder of $| 𝑋 |$ on division by $2$ (Lemma 1.1.21), so $| 𝑋 |$ is even exactly when $𝑥_{1} + \dots + 𝑥_{𝑛} = 0$ in $𝔽_{2}$ . By (a) with $𝑝 = 2$ and $𝑐 = 0$ , there are $2^{𝑛 - 1}$ such vectors.

Solution (translates).

Uses. Corollary 3.1.25 (Counting solutions over a finite field)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. Every

𝐱 \in 𝔽_{𝑝}^{𝑛}

solves exactly one of the

𝑝

equations

𝑥_{1} + \dots + 𝑥_{𝑛} = 𝑐

𝑐 \in 𝔽_{𝑝}

Hint 2. Each of these equations is consistent. What does Corollary 3.1.25 say about the sizes of their solution sets?

Sketch. The

𝑝

solution sets partition

𝔽_{𝑝}^{𝑛}

, and each has the size of the homogeneous solution set, since each equation is consistent (

𝑐 𝐞_{1}

is a solution). So each has

𝑝^{𝑛} / 𝑝 = 𝑝^{𝑛 - 1}

elements.

(a) Every $𝐱 \in 𝔽_{𝑝}^{𝑛}$ solves exactly one of the equations $𝑥_{1} + \dots + 𝑥_{𝑛} = 𝑐$ with $𝑐 \in 𝔽_{𝑝}$ , namely the one with $𝑐 = 𝑥_{1} + \dots + 𝑥_{𝑛}$ . So the $𝑝$ solution sets $𝑆_{𝑐}$ partition $𝔽_{𝑝}^{𝑛}$ . Each equation is consistent, since $𝑐 𝐞_{1} = (𝑐, 0, \dots, 0)$ is a solution, so by Corollary 3.1.25 every $𝑆_{𝑐}$ has as many elements as $𝑆_{0}$ . Hence $𝑝 | 𝑆_{0} | = 𝑝^{𝑛}$ , and $| 𝑆_{𝑐} | =$ $| 𝑆_{0} | =$ $𝑝^{𝑛 - 1}$ for every $𝑐$ .

(b) As in the first approach, the even subsets correspond to $𝑆_{0}$ over $𝔽_{2}$ , which has $2^{𝑛 - 1}$ elements. In this language the argument says something familiar: toggling whether $1 \in 𝑋$ (that is, adding $𝐞_{1}$ ) is a bijection between even and odd subsets.

Exercise 3.1.32.standard Consider the system $𝑥_{1} + 𝑘 𝑥_{2} = 1$ , $𝑘 𝑥_{1} + 𝑥_{2} = 1$ .

(a)Over $ℝ$ , for which $𝑘$ does it have no solution, exactly one solution, or infinitely many? Find the solution when it is unique.
(b)Over $𝔽_{3}$ , find the number of solutions for each $𝑘 \in 𝔽_{3}$ .

Solution.

Uses. Proposition 1.1.17 (No zero divisors), Corollary 3.1.24 (No, one, or infinitely many solutions)

Hint 1. Subtract the second equation from the first and factor:

(1 - 𝑘) (𝑥_{1} - 𝑥_{2}) = 0

Hint 2. Split into the cases

𝑘 = 1

and

𝑘 \neq 1

. In the second case

𝑥_{1} = 𝑥_{2}

; substitute back. Which value of

𝑘

is then special?

Sketch. Any solution satisfies

(1 - 𝑘) (𝑥_{1} - 𝑥_{2}) = 0

. If

𝑘 = 1

both equations are

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

. If

𝑘 \neq 1

, then

𝑥_{1} = 𝑥_{2}

and

(1 + 𝑘) 𝑥_{1} = 1

: no solution if

𝑘 = - 1

, else

𝑥_{1} = 𝑥_{2} = 1 / (1 + 𝑘)

. The argument works in any field; over

𝔽_{3}

𝑘 = 1

gives

3

solutions,

𝑘 = 2 = - 1

none,

𝑘 = 0

one.

The algebra below is valid over any field, so we do it once. Suppose $(𝑥_{1}, 𝑥_{2})$ is a solution. Subtracting the equations gives $(1 - 𝑘) 𝑥_{1} -$ $(1 - 𝑘) 𝑥_{2} =$ $0$ , that is, $(1 - 𝑘) (𝑥_{1} - 𝑥_{2}) = 0$ .

Case $𝑘 = 1$ . Both equations read $𝑥_{1} + 𝑥_{2} = 1$ , so the solution set is ${(1 - 𝑡, 𝑡) | 𝑡 \in 𝐹}$ , one solution for each $𝑡 \in 𝐹$ .

Case $𝑘 \neq 1$ . Then $1 - 𝑘 \neq 0$ , so $𝑥_{1} = 𝑥_{2}$ by Proposition 1.1.17, and either equation becomes $(1 + 𝑘) 𝑥_{1} = 1$ . If $𝑘 = - 1$ , this says $0 = 1$ , so there is no solution. If $𝑘 \neq - 1$ , then $𝑥_{1} = 𝑥_{2} = 1 / (1 + 𝑘)$ . Conversely, this pair is a solution, since $(1 + 𝑘) / (1 + 𝑘) = 1$ in both equations. So there is exactly one solution.

(a) Over $ℝ$ : infinitely many solutions for $𝑘 = 1$ , none for $𝑘 = - 1$ , and exactly one, $(1 / (1 + 𝑘), 1 / (1 + 𝑘))$ , otherwise.

(b) Over $𝔽_{3}$ : for $𝑘 = 1$ there are exactly $3$ solutions, $(1, 0)$ , $(0, 1)$ , $(2, 2)$ ; for $𝑘 = 2 = - 1$ there are none; for $𝑘 = 0$ there is exactly one, $(1, 1)$ .

Exercise 3.1.33.routine Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . Prove or disprove each statement.

(a)If $𝐴 𝐱 = 𝐲_{1}$ and $𝐴 𝐱 = 𝐲_{2}$ are consistent, then so are $𝐴 𝐱 = 𝐲_{1} + 𝐲_{2}$ and $𝐴 𝐱 = 𝑐 𝐲_{1}$ for every $𝑐 \in 𝐹$ .
(b)If $𝐴 𝐱 = 𝐲_{1}$ and $𝐴 𝐱 = 𝐲_{2}$ are inconsistent, then so is $𝐴 𝐱 = 𝐲_{1} + 𝐲_{2}$ .

Solution.

Uses. Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Definition 2.3.15 (The linear map of a matrix), Proposition 2.6.8 (Kernels and images are subspaces)

Hint 1. For (a), add solutions and scale them.

Hint 2. For (b), the set of

𝐲

for which the system is consistent is

im 𝑇_{𝐴}

, a subspace. Is its complement closed under addition? Try

𝐲_{2} = - 𝐲_{1}

Sketch. (a) True: if

𝐴 𝐮 = 𝐲_{1}

and

𝐴 𝐯 = 𝐲_{2}

, then

𝐴 (𝐮 + 𝐯) = 𝐲_{1} + 𝐲_{2}

and

𝐴 (𝑐 𝐮) = 𝑐 𝐲_{1}

. (b) False: with

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

, both

(0, 1)

and

(0, - 1)

are outside

im 𝑇_{𝐴}

, but their sum

𝟎

is not.

(a) True. Let $𝐴 𝐮 = 𝐲_{1}$ and $𝐴 𝐯 = 𝐲_{2}$ . Since $𝑇_{𝐴}$ is linear, $𝐴 (𝐮 + 𝐯) =$ $𝐴 𝐮 +$ $𝐴 𝐯 =$ $𝐲_{1} +$ $𝐲_{2}$ and $𝐴 (𝑐 𝐮) =$ $𝑐 𝐴 𝐮 =$ $𝑐 𝐲_{1}$ . In other words, by Proposition 3.1.8 the consistent right-hand sides form $im 𝑇_{𝐴}$ , which is a subspace (Proposition 2.6.8).

(b) False. Over any field, let $𝐴 = (\begin{matrix} 1 \\ 0 \end{matrix}) \in 𝐹^{2 \times 1}$ , $𝐲_{1} = (0, 1)$ , and $𝐲_{2} = (0, - 1)$ . For every $𝑥 \in 𝐹$ , $𝐴 𝑥 = (𝑥, 0)$ has second entry $0$ , so both systems are inconsistent. But $𝐲_{1} + 𝐲_{2} = 𝟎$ , and $𝐴 𝐱 = 𝟎$ is consistent.

Exercise 3.1.34.routine Find the error in the following argument, and show by an example that its conclusion is false.

Claim. If $𝐴 𝐱 = 𝟎$ has only the trivial solution, then $𝐴 𝐱 = 𝐲$ has exactly one solution for every $𝐲 \in 𝐹^{𝑚}$ .

Proof. Let $𝐲 \in 𝐹^{𝑚}$ . By Proposition 3.1.19, the solution set of $𝐴 𝐱 = 𝐲$ is $𝐱_{0} +$ $ker 𝑇_{𝐴} =$ $𝐱_{0} +$ ${𝟎} =$ ${𝐱_{0}}$ , a single vector.

Solution.

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Corollary 3.1.22 (Uniqueness depends only on $𝐴$ )

Hint 1. Reread the hypothesis of Proposition 3.1.19. What does it assume about

𝐱_{0}

Hint 2. Look for a matrix with more rows than columns.

Sketch. The proposition needs a solution

𝐱_{0}

to exist, and the argument never shows one does. For

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

𝐴 𝑥 = 0

forces

𝑥 = 0

, but

𝐴 𝑥 = (1, 0)

has no solution.

Proposition 3.1.19 describes the solution set given a solution $𝐱_{0}$ . The argument uses $𝐱_{0}$ without showing that the system is consistent, so it only proves that $𝐴 𝐱 = 𝐲$ has at most one solution, which is Corollary 3.1.22.

The claim itself is false. Let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix}) \in ℝ^{2 \times 1}$ . Then $𝐴 𝑥 = (𝑥, 𝑥)$ , so $𝐴 𝑥 = 𝟎$ only for $𝑥 = 0$ . But $𝐴 𝑥 = (1, 0)$ would need $𝑥 = 1$ and $𝑥 = 0$ , so it has no solution.

Exercise 3.1.35.standard A student solves

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

𝑥_{1} - 𝑥_{2} = 0

over

ℝ

as follows. “Replace the first equation by the first minus the second, and the second by the second minus the first. This gives

2 𝑥_{2} = 2

and

- 2 𝑥_{2} = - 2

. So

𝑥_{2} = 1

and

𝑥_{1}

is arbitrary, and the solution set is

{(𝑡, 1) | 𝑡 \in ℝ}

.” Find the error, and say exactly which solutions were gained or lost.

Solution.

Uses. Definition 3.1.1 (Linear system)

Hint 1. Is

(2, 1)

a solution of the original system?

Hint 2. Each new equation is a combination of the old ones, so no solution is lost. Can the old equations be recovered from the two new ones?

Sketch. The two replacements were made at the same time, and the second used the old first equation, which no longer appears in the new system. The new equations are negatives of each other and only say

𝑥_{2} = 1

; the original system cannot be recovered from them. The original solution set is

{(1, 1)}

, so the points

(𝑡, 1)

with

𝑡 \neq 1

were gained and nothing was lost.

The original system has the unique solution $(1, 1)$ : adding the equations gives $2 𝑥_{1} = 2$ , so $𝑥_{1} = 1$ , and then $𝑥_{2} = 1$ . The student’s answer contains $(2, 1)$ , which is not a solution, since $2 - 1 \neq 0$ .

Every solution of the old system satisfies both new equations, because each new equation is a combination of the old ones. So no solution is lost, and the student’s set does contain $(1, 1)$ . The problem is the other direction. The two new equations, $2 𝑥_{2} = 2$ and $- 2 𝑥_{2} = - 2$ , are negatives of each other and together say only $𝑥_{2} = 1$ . The equation $𝑥_{1} + 𝑥_{2} = 2$ cannot be recovered from them, so solutions are gained: all $(𝑡, 1)$ with $𝑡 \neq 1$ .

The error is performing two replacements simultaneously when the second one uses the equation that the first one replaces. Replacing an equation $𝐸_{𝑖}$ by $𝐸_{𝑖} - 𝐸_{𝑗}$ is reversible only while $𝐸_{𝑗}$ is still present: then $𝐸_{𝑖} =$ $(𝐸_{𝑖} - 𝐸_{𝑗}) +$ $𝐸_{𝑗}$ . Done one at a time, the operations are harmless. Replacing the first equation by the first minus the second gives $2 𝑥_{2} = 2$ , $𝑥_{1} - 𝑥_{2} = 0$ , and then subtracting the new first equation from the second gives $2 𝑥_{2} = 2$ , $𝑥_{1} - 3 𝑥_{2} = - 2$ , whose only solution is $(1, 1)$ .

Exercise 3.1.36.standard Call the planes $𝑎_{1} 𝑥_{1} +$ $𝑎_{2} 𝑥_{2} +$ $𝑎_{3} 𝑥_{3} =$ $𝑏$ and $𝑎_{1}^{'} 𝑥_{1} +$ $𝑎_{2}^{'} 𝑥_{2} +$ $𝑎_{3}^{'} 𝑥_{3} =$ $𝑏^{'}$ in $ℝ^{3}$ (with nonzero coefficient vectors) parallel if $(𝑎_{1}^{'}, 𝑎_{2}^{'}, 𝑎_{3}^{'}) =$ $𝑐 (𝑎_{1}, 𝑎_{2}, 𝑎_{3})$ for some $𝑐 \in ℝ$ . Find the error in the following argument, and give a counterexample to its conclusion.

Claim. Three planes in $ℝ^{3}$ , no two of them parallel, always have a common point.

Proof. The first two planes are not parallel, so they meet in a line $𝐿$ . The third plane is parallel to neither of the first two, so it is not parallel to $𝐿$ . Hence it meets $𝐿$ in a single point, which lies on all three planes.

Solution.

Uses. Definition 3.1.1 (Linear system)

Hint 1. A plane can contain lines in many directions. Must a plane that contains the direction of

𝐿

be parallel to one of the planes through

𝐿

Hint 2. Try three planes that all contain lines parallel to the

𝑥_{3}

-axis, for example planes whose equations do not involve

𝑥_{3}

Sketch. The step “parallel to neither plane, hence not parallel to

𝐿

” is unjustified. Counterexample:

𝑥_{1} = 0

𝑥_{2} = 0

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

. No two coefficient vectors are proportional, but a common point would have

0 + 0 = 1

The unjustified step is “the third plane is parallel to neither of the first two, so it is not parallel to $𝐿$ ”. Being parallel to a line is much weaker than being parallel to a plane: a plane is parallel to $𝐿$ when it contains lines in the direction of $𝐿$ , and many non-parallel planes do. If the third plane is parallel to $𝐿$ and does not contain it, it misses $𝐿$ entirely.

Counterexample: the planes $𝑥_{1} = 0$ , $𝑥_{2} = 0$ , and $𝑥_{1} + 𝑥_{2} = 1$ . Their coefficient vectors $(1, 0, 0)$ , $(0, 1, 0)$ , $(1, 1, 0)$ are pairwise not proportional, so no two of the planes are parallel. The first two meet in the $𝑥_{3}$ -axis $𝐿$ , and the third contains the lines ${(1, 0, 𝑡) | 𝑡 \in ℝ}$ and ${(0, 1, 𝑡) | 𝑡 \in ℝ}$ , both parallel to $𝐿$ . A common point would satisfy $𝑥_{1} = 0$ , $𝑥_{2} = 0$ , and $𝑥_{1} + 𝑥_{2} = 1$ , which gives $0 = 1$ . So there is none. This is the configuration of Figure 3.1.3.

Exercise 3.1.37.standard

(a)Find all polynomials $𝑝 \in {ℝ [𝑥]}_{\leq 2}$ with $𝑝 (- 1) = 2$ , $𝑝 (0) = 1$ , and $𝑝 (1) = 4$ .
(b)Find all $𝑞 \in {ℝ [𝑥]}_{\leq 3}$ with the same three values, and explain the form of the answer using Proposition 3.1.19.

Solution.

Uses. Technique 3.1.9 (Undetermined coefficients), Proposition 3.1.19 (Solution sets are translates of the kernel)

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

Hint 1. Write

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

. Each condition

𝑝 (𝑡) = 𝑣

is a linear equation in

𝑎, 𝑏, 𝑐

Hint 2. For (b), the answer to (a) is one particular solution. Find the cubics

𝑞

with

𝑞 (- 1) =

𝑞 (0) =

𝑞 (1) =

0

Sketch. (a)

𝑎 - 𝑏 + 𝑐 = 2

𝑎 = 1

𝑎 + 𝑏 + 𝑐 = 4

give

𝑝 = 1 + 𝑥 + 2 𝑥^{2}

, uniquely. (b) The homogeneous conditions force

𝑎 = 𝑐 = 0

and

𝑑 = - 𝑏

, so the solutions are

1 +

𝑥 +

2 𝑥^{2} +

𝑡 (𝑥^{3} - 𝑥)

(a) Write $𝑝 = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}$ . The conditions are the linear system

𝑎 - 𝑏 + 𝑐 = 2, 𝑎 = 1, 𝑎 + 𝑏 + 𝑐 = 4 .

With $𝑎 = 1$ , the first and third equations become $- 𝑏 + 𝑐 = 1$ and $𝑏 + 𝑐 = 3$ ; adding and subtracting gives $𝑐 = 2$ and $𝑏 = 1$ . Conversely $𝑝 = 1 + 𝑥 + 2 𝑥^{2}$ satisfies $𝑝 (- 1) = 2$ , $𝑝 (0) = 1$ , $𝑝 (1) = 4$ . So $𝑝 = 1 + 𝑥 + 2 𝑥^{2}$ is the only such polynomial.

(b) Write $𝑞 =$ $𝑎 +$ $𝑏 𝑥 +$ $𝑐 𝑥^{2} +$ $𝑑 𝑥^{3}$ . The conditions are linear in $(𝑎, 𝑏, 𝑐, 𝑑)$ , and $𝑞 = 1 + 𝑥 + 2 𝑥^{2}$ is one solution by (a). The homogeneous conditions $𝑞 (- 1) =$ $𝑞 (0) =$ $𝑞 (1) =$ $0$ read $𝑎 - 𝑏 + 𝑐 - 𝑑 = 0$ , $𝑎 = 0$ , $𝑎 + 𝑏 + 𝑐 + 𝑑 = 0$ . Then $- 𝑏 + 𝑐 - 𝑑 = 0$ and $𝑏 + 𝑐 + 𝑑 = 0$ ; adding gives $𝑐 = 0$ , and then $𝑑 = - 𝑏$ . So the homogeneous solutions are $𝑏 𝑥 -$ $𝑏 𝑥^{3} =$ $- 𝑏 (𝑥^{3} - 𝑥)$ , the multiples of $𝑥^{3} -$ $𝑥 =$ $(𝑥 + 1) 𝑥 (𝑥 - 1)$ . By Proposition 3.1.19, applied to the linear map $𝑞 \mapsto$ $(𝑞 (- 1), 𝑞 (0), 𝑞 (1))$ from ${ℝ [𝑥]}_{\leq 3}$ to $ℝ^{3}$ , the solutions are exactly

𝑞 = 1 + 𝑥 + 2 𝑥^{2} + 𝑡 (𝑥^{3} - 𝑥), 𝑡 \in ℝ .

The kernel consists of the cubics vanishing at the three points. Section 3.4 shows that through $𝑛 + 1$ points with distinct first coordinates there is always exactly one polynomial of degree at most $𝑛$ .

Exercise 3.1.38.standard Four one-way roads form a loop through the intersections $𝐴$ , $𝐵$ , $𝐶$ , $𝐷$ , carrying $𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}$ cars per hour as shown. In addition, $300$ cars per hour enter at $𝐴$ , $200$ leave at $𝐵$ , $100$ enter at $𝐶$ , and $200$ leave at $𝐷$ . At each intersection, the number of cars arriving per hour equals the number leaving.

Figure 3.1.5. The road network. Black arrows are the four one-way roads; blue arrows are cars entering or leaving the network.

(a) Write down the linear system for $𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}$ and find all its solutions.

(b) Explain why any one of the four equations follows from the other three.

(c) Since the roads are one-way, $𝑥_{𝑖} \geq 0$ for all $𝑖$ . What is the smallest possible flow on each road? Can all four minima occur at once?

Solution.

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Definition 3.1.14 (Homogeneous system)

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

Hint 1. At

𝐴

the arrivals are

300 + 𝑥_{4}

and the departures are

𝑥_{1}

. Write the other three balances similarly.

Hint 2. Solve for

𝑥_{1}, 𝑥_{2}, 𝑥_{3}

in terms of

𝑥_{4}

. For (b), add the four equations written as “arrivals minus departures

= 0

”.

Hint 3. The homogeneous solutions are the flows

(𝑡, 𝑡, 𝑡, 𝑡)

: cars circling the loop. For (c), which

𝑡

are allowed?

Sketch. The balances give

𝑥_{1} = 300 + 𝑥_{4}

𝑥_{2} = 𝑥_{1} - 200

𝑥_{3} = 𝑥_{2} + 100

𝑥_{3} = 𝑥_{4} + 200

, so the solutions are

(300 + 𝑡, 100 + 𝑡, 200 + 𝑡, 𝑡)

. The four balances sum to

0 = 0

because each road leaves one intersection and enters another and the external flows cancel. Nonnegativity means

𝑡 \geq 0

, so the minima

300, 100, 200, 0

all occur at

𝑡 = 0

(a) Balancing arrivals and departures at each intersection:

\begin{aligned} 𝐴 : & 300 + 𝑥_{4} = 𝑥_{1}, \\ 𝐵 : & 𝑥_{1} = 𝑥_{2} + 200, \\ 𝐶 : & 𝑥_{2} + 100 = 𝑥_{3}, \\ 𝐷 : & 𝑥_{3} = 𝑥_{4} + 200 . \end{aligned}

Suppose $(𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4})$ is a solution and put $𝑡 = 𝑥_{4}$ . Then $𝐴$ gives $𝑥_{1} = 300 + 𝑡$ , $𝐵$ gives $𝑥_{2} = 100 + 𝑡$ , and $𝐶$ gives $𝑥_{3} = 200 + 𝑡$ . Conversely, for every $𝑡 \in ℝ$ the vector $(300 + 𝑡, 100 + 𝑡, 200 + 𝑡, 𝑡)$ satisfies $𝐴$ , $𝐵$ , $𝐶$ by construction, and also $𝐷$ , since $200 + 𝑡 = 𝑡 + 200$ . So the solution set is

(300, 100, 200, 0) + span ((1, 1, 1, 1)) .

In the language of Proposition 3.1.19, the homogeneous solutions $(𝑡, 𝑡, 𝑡, 𝑡)$ are traffic circling the loop, which changes no balance.

(b) Write each balance as “arrivals minus departures $= 0$ ”. Each road variable $𝑥_{𝑖}$ appears once with a plus sign, at the intersection where the road ends, and once with a minus sign, where it starts. The external terms are $300 - 200 + 100 - 200 = 0$ . So the sum of the four equations is $0 = 0$ , and any one of them is the negative of the sum of the other three. (So the system is really three equations in four unknowns, and the computation in (a) shows that its homogeneous solutions form the line $span ((1, 1, 1, 1))$ .)

(c) The flows are nonnegative exactly when $𝑡 \geq 0$ , as then $300 + 𝑡$ , $100 + 𝑡$ , and $200 + 𝑡$ are positive too. So the smallest possible flows are $𝑥_{1} = 300$ , $𝑥_{2} = 100$ , $𝑥_{3} = 200$ , $𝑥_{4} = 0$ , and all four occur together at $𝑡 = 0$ , when no traffic uses the road from $𝐷$ to $𝐴$ .

Exercise 3.1.39.standard A chemical equation is balanced when each element occurs equally often on both sides. Unknown coefficients make balancing a homogeneous linear system.

(a)Find all balancings $𝑎 Cu +$ $𝑏 {HNO}_{3} \to$ $𝑐 {Cu(NO}_{3})_{2} +$ $𝑑 NO +$ $𝑒 H_{2} O$ , and the one with the smallest positive integer coefficients.
(b)Show that every balancing $𝑎 H_{2} +$ $𝑏 O_{2} \to$ $𝑐 H_{2} O +$ $𝑑 H_{2} O_{2}$ is a linear combination of $(2, 1, 2, 0)$ and $(1, 1, 0, 1)$ . What does this say chemically?

Solution.

Uses. Technique 3.1.9 (Undetermined coefficients), Corollary 3.1.16 (Homogeneous solution sets are subspaces)

Techniques. Undetermined coefficients (Technique 3.1.9)

Hint 1. Write one equation per element: for copper in (a),

𝑎 = 𝑐

. Count oxygen carefully:

{Cu(NO}_{3})_{2}

contains six oxygen atoms.

Hint 2. In (a), express everything in terms of

𝑎

. In (b) there are two equations in four unknowns; express

𝑎

and

𝑏

in terms of

𝑐

and

𝑑

Sketch. (a) Cu:

𝑎 = 𝑐

; H:

𝑏 = 2 𝑒

; N:

𝑏 = 2 𝑐 + 𝑑

; O:

3 𝑏 = 6 𝑐 + 𝑑 + 𝑒

. The solutions are the multiples of

(3, 8, 3, 2, 4)

. (b) H:

𝑎 = 𝑐 + 𝑑

; O:

2 𝑏 = 𝑐 + 2 𝑑

; so

(𝑎, 𝑏, 𝑐, 𝑑) =

(𝑐 / 2) (2, 1, 2, 0) +

𝑑 (1, 1, 0, 1)

(a) Counting atoms of each element on both sides gives the homogeneous system

Cu : 𝑎 = 𝑐, H : 𝑏 = 2 𝑒, N : 𝑏 = 2 𝑐 + 𝑑, O : 3 𝑏 = 6 𝑐 + 𝑑 + 𝑒 .

Suppose $(𝑎, 𝑏, 𝑐, 𝑑, 𝑒)$ is a solution. Then $𝑐 = 𝑎$ , and the nitrogen equation gives $𝑑 = 𝑏 - 2 𝑎 = 2 𝑒 - 2 𝑎$ . The oxygen equation becomes $6 𝑒 =$ $6 𝑎 +$ $(2 𝑒 - 2 𝑎) +$ $𝑒$ , that is, $3 𝑒 = 4 𝑎$ . So $𝑒 = 4 𝑎 / 3$ , $𝑏 = 8 𝑎 / 3$ , and $𝑑 = 2 𝑎 / 3$ , which means

(𝑎, 𝑏, 𝑐, 𝑑, 𝑒) = \frac{𝑎}{3} (3, 8, 3, 2, 4) .

Conversely, $(3, 8, 3, 2, 4)$ satisfies all four equations: $3 = 3$ , $8 = 8$ , $8 = 6 + 2$ , and $24 = 18 + 2 + 4$ . Since the solution set is a subspace (Corollary 3.1.16), all multiples are solutions too. So the balancings are the multiples of $(3, 8, 3, 2, 4)$ , and the smallest positive integer one is

3 Cu + 8 {HNO}_{3} \to 3 {Cu(NO}_{3})_{2} + 2 NO + 4 H_{2} O .

A balancing with positive integer entries is $(𝑎 / 3) (3, 8, 3, 2, 4)$ with $𝑎$ a positive integer. Its fourth entry $2 𝑎 / 3$ is an integer and $gcd (2, 3) = 1$ , so $3 ∣ 𝑎$ and $𝑎 \geq 3$ . Hence $𝑎 = 3$ gives the smallest one.

(b) The system is $2 𝑎 = 2 𝑐 + 2 𝑑$ (hydrogen) and $2 𝑏 = 𝑐 + 2 𝑑$ (oxygen). So any solution has $𝑎 = 𝑐 + 𝑑$ and $𝑏 = 𝑐 / 2 + 𝑑$ , and

(𝑎, 𝑏, 𝑐, 𝑑) = (𝑐 + 𝑑, \frac{𝑐}{2} + 𝑑, 𝑐, 𝑑) = \frac{𝑐}{2} (2, 1, 2, 0) + 𝑑 (1, 1, 0, 1) .

Conversely, $(2, 1, 2, 0)$ and $(1, 1, 0, 1)$ both satisfy the two equations, so all their combinations do. Chemically, every balanced version of this equation is a mixture of the two independent reactions $2 H_{2} + O_{2} \to 2 H_{2} O$ and $H_{2} + O_{2} \to H_{2} O_{2}$ . The solution set is a plane rather than a line, so balancing alone cannot determine the proportions.

Exercise 3.1.40.standard A $2 \times 2$ grid of lights is controlled by pressing lights: pressing a light toggles it and the lights directly next to it horizontally and vertically (not diagonally). Number the lights $1$ (top left), $2$ (top right), $3$ (bottom left), $4$ (bottom right).

(a)Explain why a set of presses can be recorded as $𝐱 \in 𝔽_{2}^{4}$ and a pattern of lit lights as $𝐲 \in 𝔽_{2}^{4}$ , and why pressing according to $𝐱$ switches off the pattern $𝐲$ exactly when $𝐴 𝐱 = 𝐲$ for a matrix $𝐴 \in 𝔽_{2}^{4 \times 4}$ . Find $𝐴$ .
(b)Show that $𝐴^{2} = 𝐼_{4}$ over $𝔽_{2}$ . Deduce that every pattern can be switched off, by exactly one set of presses.
(c)Which lights should be pressed to switch off a single lit corner?

Solution.

Uses. Proposition 3.1.5 (Three faces of a linear system), Definition 2.4.1 (Matrix product)

Techniques. Undetermined coefficients (Technique 3.1.9)

Hint 1. Pressing a light twice does nothing, and the order of presses does not matter. Why? So only the parity of the number of presses of each light matters.

Hint 2. Column

𝑗

𝐴

records which lights pressing

𝑗

toggles. For (b), entry

(𝑖, 𝑗)

𝐴^{2}

counts the lights toggled both by pressing

𝑖

and by pressing

𝑗

(

𝐴

is symmetric), modulo

2

Hint 3. If

𝐴^{2} = 𝐼

, then

𝐴 𝐱 = 𝐲

implies

𝐱 = 𝐴 𝐲

Sketch. Light

𝑖

ends in state

𝑦_{𝑖} +

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

, so all lights end off exactly when

𝐴 𝐱 = 𝐲

(over

𝔽_{2}

- 𝐲 = 𝐲

). Here

𝐴

has rows

(1, 1, 1, 0)

(1, 1, 0, 1)

(1, 0, 1, 1)

(0, 1, 1, 1)

; each row has three ones and any two rows share two, so

𝐴^{2} = 𝐼

. Then

𝐴 𝐱 = 𝐲

if and only if

𝐱 = 𝐴 𝐲

. For light

1

alone: press

1

2

3

(a) The final state of a light depends only on how many times it is toggled, and only on that number’s parity. So the order of presses is irrelevant, pressing a light twice is the same as not pressing it, and a strategy is the vector $𝐱 \in 𝔽_{2}^{4}$ with $𝑥_{𝑗} = 1$ exactly when light $𝑗$ is pressed (an odd number of times). Let $𝑎_{𝑖 𝑗} = 1$ if pressing light $𝑗$ toggles light $𝑖$ , and $𝑎_{𝑖 𝑗} = 0$ otherwise. Starting from the pattern $𝐲$ , light $𝑖$ ends in state $𝑦_{𝑖} +$ $𝑎_{𝑖 1} 𝑥_{1} +$ $\dots +$ $𝑎_{𝑖 4} 𝑥_{4}$ in $𝔽_{2}$ . All lights end off exactly when $𝐴 𝐱 + 𝐲 = 𝟎$ , that is, $𝐴 𝐱 = - 𝐲 = 𝐲$ , as $- 1 = 1$ in $𝔽_{2}$ . Light $1$ toggles lights $1, 2, 3$ , light $2$ toggles $1, 2, 4$ , light $3$ toggles $1, 3, 4$ , and light $4$ toggles $2, 3, 4$ , so

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

(b) $𝐴$ is symmetric, so entry $(𝑖, 𝑗)$ of $𝐴^{2}$ is $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑎_{𝑘 𝑗} =$ $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑎_{𝑗 𝑘}$ , the number of positions where rows $𝑖$ and $𝑗$ both have a $1$ , reduced mod $2$ . Each row has three $1$ s, so the diagonal entries are $3 = 1$ . Any two different rows have exactly two $1$ s in common (for instance, rows $1$ and $2$ share positions $1$ and $2$ ), so the off-diagonal entries are $2 = 0$ . Hence $𝐴^{2} = 𝐼_{4}$ .

Now let $𝐲$ be any pattern. If $𝐴 𝐱 = 𝐲$ , then $𝐱 = 𝐴^{2} 𝐱 = 𝐴 𝐲$ . Conversely, $𝐱 = 𝐴 𝐲$ satisfies $𝐴 𝐱 = 𝐴^{2} 𝐲 = 𝐲$ . So $𝐴 𝐱 = 𝐲$ has exactly one solution, $𝐱 = 𝐴 𝐲$ : every pattern can be switched off, in exactly one way.

(c) For light $1$ alone, $𝐲 = 𝐞_{1}$ and $𝐱 =$ $𝐴 𝐞_{1} =$ $(1, 1, 1, 0)$ : press lights $1$ , $2$ , and $3$ . Light $1$ is toggled three times and each other light twice. By symmetry, to switch off a single lit corner, press it and its two neighbors.

Exercise 3.1.41.standard

(a)Find a homogeneous linear system in $𝑥_{1}, 𝑥_{2}, 𝑥_{3}$ over $ℝ$ whose solution set is $span ((1, 2, 0), (0, 1, 1))$ .
(b)Find a linear system in $𝑥_{1}, 𝑥_{2}, 𝑥_{3}$ over $ℝ$ whose solution set is the line through $(1, 0, 2)$ and $(2, 1, 1)$ .

Solution.

Uses. Technique 3.1.9 (Undetermined coefficients), Corollary 3.1.16 (Homogeneous solution sets are subspaces), Proposition 1.4.14 (The span is the smallest subspace containing a list), Proposition 3.1.19 (Solution sets are translates of the kernel)

Techniques. Undetermined coefficients (Technique 3.1.9), Double containment (Technique 1.3.14)

Hint 1. For (a), look for an equation

𝑎_{1} 𝑥_{1} +

𝑎_{2} 𝑥_{2} +

𝑎_{3} 𝑥_{3} =

0

satisfied by both spanning vectors. That is a linear system in

𝑎_{1}, 𝑎_{2}, 𝑎_{3}

Hint 2. Having found a candidate, prove that its solution set equals the span by double containment.

Hint 3. For (b), the line is

(1, 0, 2) +

span ((1, 1, - 1))

. Find two equations whose left sides vanish at

(1, 1, - 1)

, and choose the right sides so that

(1, 0, 2)

is a solution.

Sketch. (a)

𝑎_{1} + 2 𝑎_{2} = 0

and

𝑎_{2} + 𝑎_{3} = 0

give

(2, - 1, 1)

; the solutions of

2 𝑥_{1} - 𝑥_{2} + 𝑥_{3} = 0

are

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

𝑥_{3} (0, 1, 1)

. (b)

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

𝑥_{2} + 𝑥_{3} = 2

; its solutions are

(1, 0, 2) +

𝑠 (1, 1, - 1)

(a) An equation $𝑎_{1} 𝑥_{1} +$ $𝑎_{2} 𝑥_{2} +$ $𝑎_{3} 𝑥_{3} =$ $0$ is satisfied by $(1, 2, 0)$ and $(0, 1, 1)$ exactly when $𝑎_{1} + 2 𝑎_{2} = 0$ and $𝑎_{2} + 𝑎_{3} = 0$ . One solution of this system is $(𝑎_{1}, 𝑎_{2}, 𝑎_{3}) =$ $(2, - 1, 1)$ . We claim that the solution set $𝑆$ of

2 𝑥_{1} - 𝑥_{2} + 𝑥_{3} = 0

is $𝑈 =$ $span ((1, 2, 0), (0, 1, 1))$ .

$𝑈 \subseteq 𝑆$ : both spanning vectors are solutions, since $2 - 2 + 0 = 0$ and $0 - 1 + 1 = 0$ , and $𝑆$ is a subspace (Corollary 3.1.16), so $𝑆$ contains their span (Proposition 1.4.14).

$𝑆 \subseteq 𝑈$ : if $2 𝑥_{1} - 𝑥_{2} + 𝑥_{3} = 0$ , then $𝑥_{2} = 2 𝑥_{1} + 𝑥_{3}$ , so

(𝑥_{1}, 𝑥_{2}, 𝑥_{3}) = (𝑥_{1}, 2 𝑥_{1} + 𝑥_{3}, 𝑥_{3}) = 𝑥_{1} (1, 2, 0) + 𝑥_{3} (0, 1, 1) \in 𝑈 .

(b) The line is $(1, 0, 2) +$ $span ((1, 1, - 1))$ , since $(2, 1, 1) -$ $(1, 0, 2) =$ $(1, 1, - 1)$ . By Proposition 3.1.19, it suffices to find a system that has $(1, 0, 2)$ as a solution and whose homogeneous solution set is $span ((1, 1, - 1))$ . The left sides $𝑥_{1} - 𝑥_{2}$ and $𝑥_{2} + 𝑥_{3}$ both vanish at $(1, 1, - 1)$ , and at $(1, 0, 2)$ they equal $1$ and $2$ . So consider

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

Any solution has $𝑥_{2} = 𝑥_{1} - 1$ and $𝑥_{3} = 2 - 𝑥_{2} = 3 - 𝑥_{1}$ , so

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

a point of the line. Conversely, $(1, 0, 2) +$ $𝑠 (1, 1, - 1) =$ $(1 + 𝑠, 𝑠, 2 - 𝑠)$ satisfies $(1 + 𝑠) - 𝑠 = 1$ and $𝑠 + (2 - 𝑠) = 2$ . So the solution set is exactly the line.

Exercise 3.1.42.standard For a field $𝐹$ , let $𝑆_{𝐹} =$ ${(𝑥_{1}, 𝑥_{2}) \in 𝐹^{2} | 𝑥_{1}^{2} + 𝑥_{2}^{2} = 𝑥_{1} + 𝑥_{2}}$ . Prove or disprove: $𝑆_{𝐹}$ is the solution set of some linear system in $𝑥_{1}, 𝑥_{2}$ over $𝐹$ , when

(a) $𝐹 = ℝ$ , (b) $𝐹 = 𝔽_{2}$ , (c) $𝐹 = 𝔽_{3}$ .

Solution.

Uses. Corollary 3.1.23 (Lines through solutions)

Hint 1. By Corollary 3.1.23, a solution set that contains

𝐮

and

𝐯

contains

𝐮 + 𝑡 (𝐯 - 𝐮)

for every

𝑡 \in 𝐹

. Find two points of

𝑆_{𝐹}

Hint 2. In

𝔽_{2}

, what is

𝑥^{2}

for each

𝑥

? In

𝔽_{3}

, list

𝑆_{𝐹}

by trying all nine points.

Sketch. (a) False:

(0, 0), (1, 0) \in 𝑆_{ℝ}

, but

(2, 0) \notin 𝑆_{ℝ}

. (b) True:

𝑥^{2} = 𝑥

for all

𝑥 \in 𝔽_{2}

, so

𝑆_{𝔽_{2}} = 𝔽_{2}^{2}

, the solution set of

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

. (c) False:

𝑆_{𝔽_{3}} = {0, 1}^{2}

contains

(0, 0)

and

(1, 0)

but not

(2, 0)

In all three cases $(0, 0)$ and $(1, 0)$ lie in $𝑆_{𝐹}$ , since $0 = 0$ and $1 = 1$ . If $𝑆_{𝐹}$ were the solution set of a linear system, then by Corollary 3.1.23 it would contain $(0, 0) +$ $𝑡 ((1, 0) - (0, 0)) =$ $(𝑡, 0)$ for every $𝑡 \in 𝐹$ .

(a) False. $(2, 0) \notin 𝑆_{ℝ}$ , since $4 \neq 2$ .

(b) True. In $𝔽_{2}$ , $0^{2} = 0$ and $1^{2} = 1$ , so $𝑥^{2} = 𝑥$ for every $𝑥$ , and every point of $𝔽_{2}^{2}$ satisfies the equation. So $𝑆_{𝔽_{2}} = 𝔽_{2}^{2}$ , which is the solution set of the linear equation $0 𝑥_{1} + 0 𝑥_{2} = 0$ .

(c) False. In $𝔽_{3}$ , $𝑥^{2} - 𝑥$ equals $0$ , $0$ , $2$ for $𝑥 = 0, 1, 2$ . So $(2, 0) \notin 𝑆_{𝔽_{3}}$ , since $(2^{2} - 2) + (0^{2} - 0) = 2 \neq 0$ . (In fact $𝑆_{𝔽_{3}} =$ ${(0, 0), (0, 1), (1, 0), (1, 1)}$ , as $2 + 2 = 4 = 1 \neq 0$ rules out $(2, 2)$ .)

Exercise 3.1.43.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , and suppose that for each $𝑖 = 1, \dots, 𝑚$ the system $𝐴 𝐱 = 𝐞_{𝑖}$ has a solution $𝐛_{𝑖} \in 𝐹^{𝑛}$ .

(a)Show that $𝐴 𝐱 = 𝐲$ is consistent for every $𝐲 \in 𝐹^{𝑚}$ , and give an explicit solution in terms of the $𝐛_{𝑖}$ .
(b)Let $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ be the matrix with columns $𝐛_{1}, \dots, 𝐛_{𝑚}$ . Show that $𝐴 𝐵 = 𝐼_{𝑚}$ , and conclude that $𝑇_{𝐴}$ has a right inverse.

Solution.

Uses. Definition 2.3.15 (The linear map of a matrix), Definition 2.3.8 (Matrix–vector product), Definition 2.4.1 (Matrix product), Definition 2.5.2 (Right inverse), Definition 1.6.8 (Standard bases)

Hint 1. Write

𝐲 =

𝑦_{1} 𝐞_{1} +

\dots +

𝑦_{𝑚} 𝐞_{𝑚}

and use linearity of

𝑇_{𝐴}

Hint 2. The

𝑗

th column of

𝐴 𝐵

𝐴 𝐛_{𝑗}

Sketch.

𝐴 (𝑦_{1} 𝐛_{1} + \dots + 𝑦_{𝑚} 𝐛_{𝑚}) =

𝑦_{1} 𝐞_{1} +

\dots +

𝑦_{𝑚} 𝐞_{𝑚} =

𝐲

. The columns of

𝐴 𝐵

are

𝐴 𝐛_{𝑗} = 𝐞_{𝑗}

, so

𝐴 𝐵 = 𝐼_{𝑚}

, and

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

since

𝐴 (𝐵 𝐲) = 𝐲

(a) Let $𝐲 =$ $(𝑦_{1}, \dots, 𝑦_{𝑚}) =$ $𝑦_{1} 𝐞_{1} +$ $\dots +$ $𝑦_{𝑚} 𝐞_{𝑚}$ . Since $𝑇_{𝐴}$ is linear,

𝐴 (𝑦_{1} 𝐛_{1} + \dots + 𝑦_{𝑚} 𝐛_{𝑚}) = 𝑦_{1} 𝐴 𝐛_{1} + \dots + 𝑦_{𝑚} 𝐴 𝐛_{𝑚} = 𝑦_{1} 𝐞_{1} + \dots + 𝑦_{𝑚} 𝐞_{𝑚} = 𝐲 .

So $𝐱 =$ $𝑦_{1} 𝐛_{1} +$ $\dots +$ $𝑦_{𝑚} 𝐛_{𝑚}$ is a solution.

(b) The $𝑗$ th column of $𝐴 𝐵$ is $𝐴 𝐛_{𝑗} = 𝐞_{𝑗}$ (Definition 2.4.1), which is the $𝑗$ th column of $𝐼_{𝑚}$ . So $𝐴 𝐵 = 𝐼_{𝑚}$ . The solution in (a) is $𝐱 = 𝐵 𝐲$ , by Definition 2.3.8, so $𝑇_{𝐴} (𝑇_{𝐵} (𝐲)) =$ $𝐴 (𝐵 𝐲) =$ $𝐲$ for every $𝐲 \in 𝐹^{𝑚}$ . That is, $𝑇_{𝐴} \circ 𝑇_{𝐵} = {id}_{𝐹^{𝑚}}$ , and the linear map $𝑇_{𝐵}$ is a right inverse of $𝑇_{𝐴}$ . This is one direction of the equivalence between solvability for every $𝐲$ and right invertibility in Theorem 2.7.4, with an explicit right inverse: it suffices to solve the $𝑚$ systems $𝐴 𝐱 = 𝐞_{𝑖}$ .

Exercise 3.1.44.standard

(a)Suppose that some linear system over a field $𝐹$ has exactly two solutions. Show that $𝐹$ has exactly two elements.
(b)More generally, suppose $𝐹$ is finite and a linear system over $𝐹$ has more than one solution. Show that it has at least $| 𝐹 |$ solutions.

Solution.

Uses. Corollary 3.1.23 (Lines through solutions), Proposition 1.2.35 (Zero products)

Hint 1. Let

𝐮 \neq 𝐯

be solutions. Corollary 3.1.23 gives a solution for each

𝑡 \in 𝐹

Hint 2. Show that

𝑡 \mapsto 𝐮 + 𝑡 (𝐯 - 𝐮)

is injective. Then compare sizes.

Sketch. If

𝐮 \neq 𝐯

are solutions,

𝑡 \mapsto 𝐮 + 𝑡 (𝐯 - 𝐮)

is an injective map from

𝐹

into the solution set, so the solution set has at least

| 𝐹 |

elements. With exactly two solutions this gives

| 𝐹 | \leq 2

, and

| 𝐹 | \geq 2

since

0 \neq 1

(b) Let $𝐮 \neq 𝐯$ be solutions, and define $𝜑 : 𝐹 \to 𝑆$ , where $𝑆$ is the solution set, by $𝜑 (𝑡) =$ $𝐮 +$ $𝑡 (𝐯 - 𝐮)$ . This lands in $𝑆$ by Corollary 3.1.23. It is injective: if $𝜑 (𝑡) = 𝜑 (𝑡^{'})$ , then $(𝑡 - 𝑡^{'}) (𝐯 - 𝐮) =$ $𝟎$ , and $𝐯 - 𝐮 \neq 𝟎$ gives $𝑡 = 𝑡^{'}$ by Proposition 1.2.35. So $| 𝑆 | \geq | 𝐹 |$ .

(a) If $𝑆$ has exactly two elements, then $𝐹$ is finite, since $𝜑 : 𝐹 \to 𝑆$ is injective, and $| 𝐹 | \leq | 𝑆 | = 2$ by the argument in (b). Every field has at least two elements, $0$ and $1$ , so $| 𝐹 | = 2$ .

Exercise 3.1.45.standard Let $𝑉$ be a vector space.

(a)Let $𝑈, 𝑈^{'}$ be subspaces of $𝑉$ and $𝐯, 𝐯^{'} \in 𝑉$ . Show that if $𝐯 + 𝑈 = 𝐯^{'} + 𝑈^{'}$ , then $𝑈 = 𝑈^{'}$ and $𝐯^{'} - 𝐯 \in 𝑈$ .
(b)Deduce that if two systems $𝐴 𝐱 = 𝐲$ and $𝐵 𝐱 = 𝐳$ in the same $𝑛$ unknowns have the same nonempty solution set, then $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ .
(c)Give an example of (b) with $𝐴 \neq 𝐵$ , both in $ℝ^{2 \times 2}$ .

Solution.

Uses. Notation 3.1.17 (Translates), Definition 1.4.1 (Subspace), Proposition 3.1.19 (Solution sets are translates of the kernel)

Techniques. Double containment (Technique 1.3.14)

Hint 1. Since

𝟎 \in 𝑈^{'}

, the vector

𝐯^{'}

lies in

𝐯 + 𝑈

. What does that say about

𝐯^{'} - 𝐯

Hint 2. Take

𝐮^{'} \in 𝑈^{'}

. Then

𝐯^{'} + 𝐮^{'} \in 𝐯 + 𝑈

; subtract

𝐯

and use that

𝑈

is closed under subtraction. Then swap the roles of the two translates.

Sketch.

𝐯^{'} = 𝐯^{'} + 𝟎 \in 𝐯 + 𝑈

, so

𝐰 = 𝐯^{'} - 𝐯 \in 𝑈

. For

𝐮^{'} \in 𝑈^{'}

𝐯^{'} + 𝐮^{'} = 𝐯 + 𝐮

with

𝐮 \in 𝑈

, so

𝐮^{'} = 𝐮 - 𝐰 \in 𝑈

. By symmetry

𝑈 \subseteq 𝑈^{'}

. For (b), write the common solution set as

𝐱_{0} +

ker 𝑇_{𝐴} =

𝐱_{0} +

ker 𝑇_{𝐵}

(a) Since $𝟎 \in 𝑈^{'}$ , we have $𝐯^{'} =$ $𝐯^{'} +$ $𝟎 \in$ $𝐯^{'} +$ $𝑈^{'} =$ $𝐯 +$ $𝑈$ , so $𝐯^{'} = 𝐯 + 𝐰$ for some $𝐰 \in 𝑈$ ; that is, $𝐯^{'} - 𝐯 = 𝐰 \in 𝑈$ . By the symmetric argument, $𝐯 - 𝐯^{'} \in 𝑈^{'}$ .

$𝑈^{'} \subseteq 𝑈$ : let $𝐮^{'} \in 𝑈^{'}$ . Then $𝐯^{'} +$ $𝐮^{'} \in$ $𝐯^{'} +$ $𝑈^{'} =$ $𝐯 +$ $𝑈$ , so $𝐯^{'} + 𝐮^{'} = 𝐯 + 𝐮$ for some $𝐮 \in 𝑈$ . Hence $𝐮^{'} =$ $𝐮 -$ $(𝐯^{'} - 𝐯) =$ $𝐮 -$ $𝐰$ , which lies in $𝑈$ because $𝑈$ is a subspace.

$𝑈 \subseteq 𝑈^{'}$ : the same argument with the roles of $(𝐯, 𝑈)$ and $(𝐯^{'}, 𝑈^{'})$ exchanged, using $𝐯 - 𝐯^{'} \in 𝑈^{'}$ .

(b) Let $𝑆$ be the common solution set and $𝐱_{0} \in 𝑆$ . By Proposition 3.1.19, $𝐱_{0} +$ $ker 𝑇_{𝐴} =$ $𝑆 =$ $𝐱_{0} +$ $ker 𝑇_{𝐵}$ , and $ker 𝑇_{𝐴}$ , $ker 𝑇_{𝐵}$ are subspaces of $𝐹^{𝑛}$ . By (a), $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ .

(c) Take $𝐴 = 𝐼_{2}$ , $𝐲 = (1, 1)$ , and $𝐵 = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$ , $𝐳 = (1, 2)$ . The first system says $𝑥_{1} = 1$ , $𝑥_{2} = 1$ . The second says $𝑥_{1} = 1$ and $𝑥_{1} + 𝑥_{2} = 2$ , which also forces $(𝑥_{1}, 𝑥_{2}) = (1, 1)$ , and $(1, 1)$ satisfies it. Both solution sets are ${(1, 1)}$ , and both kernels are ${𝟎}$ .

Exercise 3.1.46.standard Let $𝑛 \geq 3$ . Find all real solutions of the cyclic system

𝑥_{1} + 𝑥_{2} = 2, 𝑥_{2} + 𝑥_{3} = 2, \dots, 𝑥_{𝑛 - 1} + 𝑥_{𝑛} = 2, 𝑥_{𝑛} + 𝑥_{1} = 2 .

The answer depends on $𝑛$ . What are the solutions over $𝔽_{2}$ ?

Solution.

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ )

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1.

(1, 1, \dots, 1)

is a particular solution. Find the homogeneous solutions.

Hint 2. In the homogeneous system,

𝑥_{𝑖 + 1} = - 𝑥_{𝑖}

for each

𝑖

, so

𝑥_{𝑘 + 1} = {(- 1)}^{𝑘} 𝑥_{1}

. Go once around the cycle: what does

𝑥_{𝑛} + 𝑥_{1} = 0

say?

Sketch. The homogeneous solutions have

𝑥_{𝑘 + 1} = {(- 1)}^{𝑘} 𝑥_{1}

, and the last equation gives

({(- 1)}^{𝑛 - 1} + 1) 𝑥_{1} = 0

. For

𝑛

odd this forces

𝑥_{1} = 0

, so

(1, \dots, 1)

is the unique solution; for

𝑛

even the kernel is spanned by

(1, - 1, 1, \dots, - 1)

. Over

𝔽_{2}

2 = 0

and the equations say

𝑥_{1} = 𝑥_{2} = \dots = 𝑥_{𝑛}

: two solutions.

Over $ℝ$ , $(1, 1, \dots, 1)$ is a solution. By Proposition 3.1.19, we need the solutions of the homogeneous system $𝑥_{𝑖} + 𝑥_{𝑖 + 1} = 0$ ( $1 \leq 𝑖 \leq 𝑛 - 1$ ), $𝑥_{𝑛} + 𝑥_{1} = 0$ . In such a solution, $𝑥_{𝑖 + 1} = - 𝑥_{𝑖}$ for $𝑖 \leq 𝑛 - 1$ , so by induction $𝑥_{𝑘 + 1} = {(- 1)}^{𝑘} 𝑥_{1}$ for $0 \leq 𝑘 \leq 𝑛 - 1$ . The last equation then reads ${(- 1)}^{𝑛 - 1} 𝑥_{1} + 𝑥_{1} = 0$ . Conversely, a vector with $𝑥_{𝑘 + 1} = {(- 1)}^{𝑘} 𝑥_{1}$ satisfies the first $𝑛 - 1$ equations, and it satisfies the last one exactly when $({(- 1)}^{𝑛 - 1} + 1) 𝑥_{1} = 0$ .

If $𝑛$ is odd, this says $2 𝑥_{1} = 0$ , so $𝑥_{1} = 0$ and the kernel is ${𝟎}$ . The unique solution is $(1, 1, \dots, 1)$ .

If $𝑛$ is even, it says $0 = 0$ , so the kernel is spanned by $(1, - 1, 1, - 1, \dots, 1, - 1)$ , and the solutions are

(1 + 𝑡, 1 - 𝑡, 1 + 𝑡, 1 - 𝑡, \dots, 1 + 𝑡, 1 - 𝑡), 𝑡 \in ℝ .

Over $𝔽_{2}$ , the right-hand sides are $2 = 0$ and $- 𝑥_{𝑖} = 𝑥_{𝑖}$ , so the system says $𝑥_{𝑖 + 1} = 𝑥_{𝑖}$ for all $𝑖$ (and $𝑥_{1} = 𝑥_{𝑛}$ ). The solutions are $(0, \dots, 0)$ and $(1, \dots, 1)$ , for every $𝑛$ . Over $ℝ$ the parity of $𝑛$ mattered only through $2 𝑥_{1} = 0 \Rightarrow 𝑥_{1} = 0$ , which is exactly the step that fails in characteristic $2$ .

Exercise 3.1.47.hard A metal plate is modelled by a finite set $𝐺 \subseteq ℤ^{2}$ of interior grid points. The boundary $𝜕 𝐺$ is the set of points of $ℤ^{2} ∖ 𝐺$ that are adjacent (at distance $1$ , horizontally or vertically) to some point of $𝐺$ . The temperatures $𝑏_{𝑞}$ at the boundary points $𝑞 \in 𝜕 𝐺$ are fixed real numbers, and in equilibrium the temperature $𝑢_{𝑝}$ at each interior point is the average of the temperatures at its four neighbors. This is a linear system with one unknown $𝑢_{𝑝}$ for each $𝑝 \in 𝐺$ :

4 𝑢_{𝑝} - \sum_{𝑞 \sim 𝑝, 𝑞 \in 𝐺} 𝑢_{𝑞} = \sum_{𝑞 \sim 𝑝, 𝑞 \in 𝜕 𝐺} 𝑏_{𝑞} (𝑝 \in 𝐺),

where $𝑞 \sim 𝑝$ means that $𝑞$ and $𝑝$ are adjacent. Show that this system has at most one solution.

Solution.

Uses. Corollary 3.1.22 (Uniqueness depends only on $𝐴$ ), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ )

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. By Corollary 3.1.22, it suffices to show that the homogeneous system, with all

𝑏_{𝑞} = 0

, has only the trivial solution.

Hint 2. In a homogeneous solution, let

𝑀

be the largest

𝑢_{𝑝}

, and suppose

𝑀 > 0

. At a point where

𝑢_{𝑝} = 𝑀

, the average of four numbers that are all at most

𝑀

equals

𝑀

. What does that force?

Hint 3. Walk from a maximizing point to the right until you leave

𝐺

. The first point outside

𝐺

is a boundary point.

Sketch. Take a homogeneous solution, extended by

𝑢_{𝑞} = 0

𝜕 𝐺

, so each

𝑢_{𝑝}

is the average of its four neighbors. If

𝑀 = max 𝑢_{𝑝} > 0

is attained at

𝑝

, all four neighbors of

𝑝

equal

𝑀

. Walking right from

𝑝

, every point of

𝐺

along the way has value

𝑀

, and the first point outside

𝐺

is a boundary point adjacent to a point with value

𝑀

, so its value

0

equals

𝑀

, a contradiction. So

max \leq 0

; applying this to

- 𝑢

gives

min \geq 0

. Hence

𝑢 = 𝟎

, and Corollary 3.1.22 finishes.

By Corollary 3.1.22, it suffices to show that the homogeneous system, the one with every $𝑏_{𝑞} = 0$ , has only the trivial solution. Let ${(𝑢_{𝑝})}_{𝑝 \in 𝐺}$ be a solution of the homogeneous system, and set $𝑢_{𝑞} = 0$ for $𝑞 \in 𝜕 𝐺$ . Every neighbor of a point of $𝐺$ lies in $𝐺$ or in $𝜕 𝐺$ , so the equations say

𝑢_{𝑝} = \frac{1}{4} \sum_{𝑞 \sim 𝑝} 𝑢_{𝑞} for every 𝑝 \in 𝐺,

the sum running over all four neighbors of $𝑝$ .

Suppose, for contradiction, that $𝑀 = {max}_{𝑝 \in 𝐺} 𝑢_{𝑝} > 0$ (the maximum exists because $𝐺$ is finite and, being the index set of the unknowns, nonempty). Then every $𝑢_{𝑞}$ with $𝑞 \in 𝐺 \cup 𝜕 𝐺$ is at most $𝑀$ . We first show: if $𝑝 \in 𝐺$ and $𝑢_{𝑝} = 𝑀$ , then all four neighbors of $𝑝$ have value $𝑀$ . Indeed, $4 𝑀 =$ $4 𝑢_{𝑝} =$ $\sum_{𝑞 \sim 𝑝} 𝑢_{𝑞}$ is a sum of four numbers each at most $𝑀$ , so if one of them were less than $𝑀$ , the sum would be less than $4 𝑀$ .

Pick $𝑝_{0} \in 𝐺$ with $𝑢_{𝑝_{0}} = 𝑀$ , and consider the points $𝑝_{𝑘} = 𝑝_{0} + (𝑘, 0)$ for $𝑘 = 0, 1, 2, \dots$ . Since $𝐺$ is finite, some $𝑝_{𝑘}$ lies outside $𝐺$ ; let $𝑘$ be the smallest such index, so $𝑘 \geq 1$ and $𝑝_{0}, \dots, 𝑝_{𝑘 - 1} \in 𝐺$ . By the claim and induction, $𝑢_{𝑝_{0}} =$ $𝑢_{𝑝_{1}} =$ $\dots =$ $𝑢_{𝑝_{𝑘 - 1}} =$ $𝑀$ , and then $𝑢_{𝑝_{𝑘}} = 𝑀$ too, since $𝑝_{𝑘}$ is a neighbor of $𝑝_{𝑘 - 1}$ . But $𝑝_{𝑘} \notin 𝐺$ is adjacent to $𝑝_{𝑘 - 1} \in 𝐺$ , so $𝑝_{𝑘} \in 𝜕 𝐺$ and $𝑢_{𝑝_{𝑘}} = 0 < 𝑀$ . This contradiction shows $𝑢_{𝑝} \leq 0$ for all $𝑝 \in 𝐺$ .

The vector ${(- 𝑢_{𝑝})}_{𝑝 \in 𝐺}$ also solves the homogeneous system, so the same argument gives $- 𝑢_{𝑝} \leq 0$ for all $𝑝$ . Hence $𝑢_{𝑝} = 0$ for all $𝑝 \in 𝐺$ : the homogeneous system has only the trivial solution, and the original system has at most one solution.

The system has as many equations as unknowns. For such square systems, Section 3.5 shows that “at most one solution for every right-hand side” implies “exactly one”, so the equilibrium temperatures always exist and are unique.

Exercise 3.1.48.hardBeyond 21-242 Call a subset $𝑆 \subseteq 𝐹^{𝑛}$ line-closed if $𝐮 + 𝑡 (𝐯 - 𝐮) \in 𝑆$ for all $𝐮, 𝐯 \in 𝑆$ and $𝑡 \in 𝐹$ . By Corollary 3.1.23, solution sets of linear systems are line-closed.

(a)Suppose $1 + 1 \neq 0$ in $𝐹$ . Show that every nonempty line-closed set $𝑆$ is a translate $𝐯 + 𝑈$ of a subspace $𝑈$ of $𝐹^{𝑛}$ .
(b)Show that ${(0, 0), (1, 0), (0, 1)} \subseteq$ $𝔽_{2}^{2}$ is line-closed but is not a translate of any subspace.

Solution.

Uses. Definition 1.4.1 (Subspace), Theorem 1.4.3 (Subspace criterion), Notation 3.1.17 (Translates), Definition 1.1.28 (Characteristic)

Hint 1. Fix

𝐯 \in 𝑆

and let

𝑈 = {𝐬 - 𝐯 | 𝐬 \in 𝑆}

, so

𝑆 = 𝐯 + 𝑈

. Check the subspace conditions for

𝑈

Hint 2. Scalar multiples:

𝐯 + 𝑡 (𝐬 - 𝐯) \in 𝑆

. Sums are harder: first show that the midpoint

\frac{1}{2} 𝐬 + \frac{1}{2} 𝐬^{'}

of two points of

𝑆

lies in

𝑆

; this step needs

2 \neq 0

Hint 3. For (b), over

𝔽_{2}

the only values of

𝑡

are

0

and

1

. For the second part, a translate of a subspace by

𝐯

contains

𝐯

; subtract it and count.

Sketch. With

𝑈 = 𝑆 - 𝐯

𝟎 \in 𝑈

;

𝑡 (𝐬 - 𝐯) =

(𝐯 + 𝑡 (𝐬 - 𝐯)) -

𝐯 \in

𝑈

; the midpoint

𝐦 =

𝐬 +

\frac{1}{2} (𝐬^{'} - 𝐬) \in

𝑆

, and

(𝐬 - 𝐯) +

(𝐬^{'} - 𝐯) =

2 (𝐦 - 𝐯) \in

𝑈

. In (b), the line through two points of

𝔽_{2}^{2}

is just those two points; a translate

𝐯 + 𝑈

with three elements would make

𝑈

a subspace of

𝔽_{2}^{2}

with three elements, but

𝐮, 𝐮^{'} \in 𝑈

distinct and nonzero force a fourth element

𝐮 + 𝐮^{'}

(a) Fix $𝐯 \in 𝑆$ and put $𝑈 = {𝐬 - 𝐯 | 𝐬 \in 𝑆}$ , so that $𝑆 = 𝐯 + 𝑈$ . We check that $𝑈$ is a subspace.

$𝟎 \in 𝑈$ , as $𝟎 = 𝐯 - 𝐯$ .

Scalar multiples. Let $𝐬 \in 𝑆$ and $𝑡 \in 𝐹$ . By line-closedness with $𝐮 = 𝐯$ , the point $𝐯 + 𝑡 (𝐬 - 𝐯)$ lies in $𝑆$ , so $𝑡 (𝐬 - 𝐯) \in 𝑈$ .

Sums. Let $𝐬, 𝐬^{'} \in 𝑆$ . Since $2 = 1 + 1 \neq 0$ , the scalar $\frac{1}{2}$ exists, and $𝐦 = 𝐬 + \frac{1}{2} (𝐬^{'} - 𝐬)$ lies in $𝑆$ . Then $𝐦 - 𝐯 \in 𝑈$ , and by the previous step $2 (𝐦 - 𝐯) \in 𝑈$ . But

2 (𝐦 - 𝐯) = 2 𝐬 + (𝐬^{'} - 𝐬) - 2 𝐯 = (𝐬 - 𝐯) + (𝐬^{'} - 𝐯) .

So $𝑈$ is closed under addition, and $𝑈$ is a subspace by Theorem 1.4.3. Hence $𝑆 = 𝐯 + 𝑈$ is a translate of a subspace.

(b) Over $𝔽_{2}$ , $𝑡$ is $0$ or $1$ , and $𝐮 + 𝑡 (𝐯 - 𝐮)$ is then $𝐮$ or $𝐯$ . So every subset of $𝔽_{2}^{𝑛}$ is line-closed, in particular $𝑆 =$ ${(0, 0), (1, 0), (0, 1)}$ .

Suppose $𝑆 = 𝐯 + 𝑈$ for a subspace $𝑈$ . Then $𝑈 = {𝐬 - 𝐯 | 𝐬 \in 𝑆}$ has exactly three elements, since $𝐬 \mapsto 𝐬 - 𝐯$ is injective. One of them is $𝟎$ ; call the other two $𝐮 \neq 𝐮^{'}$ , both nonzero. Since $𝑈$ is a subspace, $𝐮 + 𝐮^{'} \in 𝑈$ . But $𝐮 + 𝐮^{'} \neq 𝟎$ , since otherwise $𝐮^{'} = - 𝐮 = 𝐮$ in characteristic $2$ ; and $𝐮 + 𝐮^{'} \neq 𝐮$ and $\neq 𝐮^{'}$ , since $𝐮^{'}$ and $𝐮$ are nonzero. So $𝑈$ has a fourth element, a contradiction.

Part (b) shows that line-closedness is too weak a condition in characteristic $2$ . The right notion uses combinations of more than two points; see Section 4.7.

Exercise 3.1.49.challenge Thirteen weights with integer masses have the following property: whichever one of them is removed, the remaining twelve can be split into two groups of six with equal total mass. Prove that all thirteen masses are equal.

Solution.

Uses. Corollary 3.1.16 (Homogeneous solution sets are subspaces), Proposition 3.1.5 (Three faces of a linear system)

Hint 1. Fix the masses

𝐰 = (𝑤_{1}, \dots, 𝑤_{13})

and, for each

𝑖

, one valid split. Encode the splits as a

13 \times 13

matrix

𝐴

with

𝐴 𝐰 = 𝟎

. What else lies in

ker 𝑇_{𝐴}

Hint 2.

(1, 1, \dots, 1) \in ker 𝑇_{𝐴}

, and

ker 𝑇_{𝐴}

is a subspace. Show that all entries of an integer vector in

ker 𝑇_{𝐴}

have the same parity.

Hint 3. Subtract the smallest mass from all masses, then keep dividing by

2

. Why must this stop, and what does that force?

Sketch. Row

𝑖

𝐴

has

0

in position

𝑖

+ 1

on one group and

- 1

on the other, so

𝐴 𝐰 = 𝟎

and

𝐴 𝟏 = 𝟎

. For an integer

𝐯 \in ker 𝑇_{𝐴}

, row

𝑖

gives

\sum_{𝑗 \neq 𝑖} 𝑣_{𝑗} \equiv 0 mod 2

, so every

𝑣_{𝑖}

has the parity of

\sum_{𝑗} 𝑣_{𝑗}

. Among nonzero integer vectors in

ker 𝑇_{𝐴}

with nonnegative entries and a zero entry, take one with the smallest maximum entry; its entries are all even, and halving it gives a smaller one. So

𝐰 -

({min}_{𝑗} 𝑤_{𝑗}) 𝟏 =

𝟎

Let $𝐰 =$ $(𝑤_{1}, \dots, 𝑤_{13}) \in$ $ℤ^{13}$ be the masses. For each $𝑖$ , fix a split of the other twelve weights into two groups of six with equal total mass, and let $𝐴 \in ℚ^{13 \times 13}$ have $(𝑖, 𝑗)$ entry $0$ if $𝑗 = 𝑖$ , $+ 1$ if weight $𝑗$ is in the first group of the split for $𝑖$ , and $- 1$ if it is in the second. Then row $𝑖$ of $𝐴 𝐰 = 𝟎$ says that the two groups balance, so $𝐰 \in ker 𝑇_{𝐴}$ . Each row of $𝐴$ has six entries $+ 1$ and six entries $- 1$ , so $𝟏 =$ $(1, \dots, 1) \in$ $ker 𝑇_{𝐴}$ as well. By Corollary 3.1.16, $ker 𝑇_{𝐴}$ is a subspace of $ℚ^{13}$ .

Parity. Let $𝐯 \in ker 𝑇_{𝐴}$ have integer entries, and let $𝑁 = 𝑣_{1} + \dots + 𝑣_{13}$ . Row $𝑖$ says $\sum_{𝑗 \neq 𝑖} \pm 𝑣_{𝑗} = 0$ . Since $- 𝑣_{𝑗} \equiv 𝑣_{𝑗}$ modulo $2$ , this gives $\sum_{𝑗 \neq 𝑖} 𝑣_{𝑗} \equiv 0$ , that is, $𝑁 - 𝑣_{𝑖} \equiv 0 mod 2$ . So every $𝑣_{𝑖}$ has the same parity as $𝑁$ , and all entries of $𝐯$ have the same parity.

Descent. Let $𝐾$ be the set of nonzero vectors $𝐯 \in ker 𝑇_{𝐴}$ with integer entries, all entries $\geq 0$ , and at least one entry equal to $0$ . Suppose $𝐾$ is nonempty, and choose $𝐯 \in 𝐾$ whose largest entry is as small as possible. Since $𝐯$ has a zero entry, all its entries are even by the parity step, so $\frac{1}{2} 𝐯$ has integer entries. It lies in $ker 𝑇_{𝐴}$ (a subspace), is nonzero, has nonnegative entries and a zero entry, so $\frac{1}{2} 𝐯 \in 𝐾$ . But its largest entry is half that of $𝐯$ , which is positive, so it is smaller. This contradicts the choice of $𝐯$ , so $𝐾$ is empty.

Conclusion. Let $𝑐 = {min}_{𝑗} 𝑤_{𝑗}$ and $𝐯 = 𝐰 - 𝑐 𝟏$ . Then $𝐯 \in ker 𝑇_{𝐴}$ , its entries are nonnegative integers, and at least one is $0$ . As $𝐾$ is empty, $𝐯 = 𝟎$ , so $𝑤_{1} = \dots = 𝑤_{13} = 𝑐$ .

The same holds for rational masses (multiply by a common denominator) and in fact for real masses, but the real case needs more: one shows that the kernel of $𝑇_{𝐴}$ over $ℝ$ is spanned by vectors with rational entries, which follows from Gauss–Jordan elimination never leaving the field of the entries (Section 3.4).

More practice

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