3.4 Solving linear systems

By Theorem 3.3.10, Gauss–Jordan elimination turns $𝐴$ into $rref (𝐴) = 𝐺 𝐴$ with $𝐺$ invertible, and by Proposition 3.2.14 the system $𝐴 𝐱 = 𝐲$ has the same solutions as the system $rref (𝐴) 𝐱 = 𝐺 𝐲$ . In Example 3.1.13 we read the solutions of one reduced system off by eye. This section does it in general. A reduced system says two things. Its zero rows decide whether there is a solution at all, and its other rows split the unknowns into free ones, which can take any values, and pivot ones, which the free ones then determine. From this we get a criterion for uniqueness and a criterion for existence, both in terms of pivots, and a first substantial application: through $𝑛 + 1$ points with distinct first coordinates there passes exactly one polynomial of degree at most $𝑛$ .

3.4.1Reducing to RREF

As in Definition 3.3.9, we write $𝐴_{𝑟} = rref (𝐴)$ .

Proposition 3.4.1 (Solving with the reduced matrix). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , and let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10). Then for all $𝐱 \in 𝐹^{𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ ,

𝐴 𝐱 = 𝐲 \Leftrightarrow 𝐴_{𝑟} 𝐱 = 𝐺 𝐲 .

Moreover, if $𝐺$ is the product of the elementary matrices of the run of Gauss–Jordan elimination on $𝐴$ (Theorem 3.3.10), then the run on the augmented matrix $(𝐴 | 𝐲)$ , with step 1 of Algorithm 3.3.1 restricted to the first $𝑛$ columns, ends at $(𝐴_{𝑟} | 𝐺 𝐲)$ .

Proof.routine

Uses. Proposition 3.2.14 (Invertible matrices preserve solution sets), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 3.3.11 (Carrying extra columns along)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. Which result of Section 3.2 says that multiplying a system on the left by an invertible matrix does not change its solutions?

Hint 2. For

\Leftarrow

, multiply

𝐴_{𝑟} 𝐱 = 𝐺 𝐲

on the left by

𝐺^{- 1}

and use

𝐺^{- 1} 𝐴_{𝑟} = 𝐴

. For the augmented matrix, apply Proposition 3.3.11 with

𝐵 = 𝐲

Sketch. If

𝐴 𝐱 = 𝐲

, then

𝐴_{𝑟} 𝐱 =

𝐺 𝐴 𝐱 =

𝐺 𝐲

. If

𝐴_{𝑟} 𝐱 = 𝐺 𝐲

, then

𝐴 𝐱 =

𝐺^{- 1} 𝐴_{𝑟} 𝐱 =

𝐺^{- 1} 𝐺 𝐲 =

𝐲

. The statement about

(𝐴 | 𝐲)

is Proposition 3.3.11(b) with

𝐵 = 𝐲

( $\Rightarrow$ ) If $𝐴 𝐱 = 𝐲$ , then $𝐴_{𝑟} 𝐱 =$ $(𝐺 𝐴) 𝐱 =$ $𝐺 (𝐴 𝐱) =$ $𝐺 𝐲$ .

( $\Leftarrow$ ) Since $𝐺 𝐴 = 𝐴_{𝑟}$ , we have $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ . So if $𝐴_{𝑟} 𝐱 = 𝐺 𝐲$ , then

𝐴 𝐱 = 𝐺^{- 1} (𝐴_{𝑟} 𝐱) = 𝐺^{- 1} (𝐺 𝐲) = 𝐲 .

(This is Proposition 3.2.14 for our particular $𝐺$ .) The last statement is Proposition 3.3.11(b), applied with $𝐵 = 𝐲 \in 𝐹^{𝑚 \times 1}$ ; it concerns the particular $𝐺$ produced by the run. (When $𝐴$ has fewer than $𝑚$ pivots, other invertible matrices $𝐺^{'}$ also satisfy $𝐺^{'} 𝐴 = 𝐴_{𝑟}$ , and the equivalence holds for each of them.) □

So the analysis of an arbitrary system reduces to that of a system whose coefficient matrix is in RREF. We never need $𝐺$ separately: we row reduce $(𝐴 | 𝐲)$ , and $𝐲$ rides along in the last column. To treat every right-hand side at once, we can let the last column hold the symbols $𝑦_{1}, \dots, 𝑦_{𝑚}$ , which amounts to carrying $𝐼_{𝑚}$ along and producing $𝐺$ (Proposition 3.3.11).

Definition 3.4.2 (Pivot and free variables). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

, and let

𝑝_{1} <

𝑝_{2} <

\dots <

𝑝_{𝑘}

be its pivot columns (Definition 3.3.9). The other columns,

𝑓_{1} <

𝑓_{2} <

\dots <

𝑓_{ℓ}

, are the free columns of

𝐴

; thus

𝑘 + ℓ = 𝑛

. In the system

𝐴 𝐱 = 𝐲

, the unknowns

𝑥_{𝑝_{1}}, \dots, 𝑥_{𝑝_{𝑘}}

are the pivot variables and

𝑥_{𝑓_{1}}, \dots, 𝑥_{𝑓_{ℓ}}

are the free variables.

These notions belong to $𝐴$ alone. They do not involve $𝐲$ , and they do not depend on how $𝐴$ was reduced (Corollary 3.3.18). In fact Corollary 3.3.19 describes them without any reduction: column $𝑗$ is free exactly when $𝐚_{𝑗}$ is a linear combination of $𝐚_{1}, \dots, 𝐚_{𝑗 - 1}$ . The $𝑘$ pivots lie in rows $1, \dots, 𝑘$ and in distinct columns (Proposition 3.3.8), so $𝑘 \leq min (𝑚, 𝑛)$ . The number $𝑘$ is the rank of $𝐴$ , the subject of Section 3.5. For the matrix of Example 3.3.3,

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

the pivot columns are $𝑝_{1} = 1$ and $𝑝_{2} = 3$ , and the free columns are $𝑓_{1} = 2$ and $𝑓_{2} = 4$ . In $𝐴 𝐱 = 𝐲$ the pivot variables are $𝑥_{1}, 𝑥_{3}$ , and the free variables are $𝑥_{2}, 𝑥_{4}$ .

3.4.2Reading off the solutions

Intuition (What a reduced system says). Let $𝑅 = 𝐴_{𝑟}$ , with entries $𝑟_{𝑖 𝑗}$ , and $𝐳 = 𝐺 𝐲$ . Row $𝑖 \leq 𝑘$ of $𝑅$ has its pivot, a $1$ , in column $𝑝_{𝑖}$ , and zeros in the other pivot columns, because the pivot columns of $𝑅$ are $𝐞_{1}, \dots, 𝐞_{𝑘}$ (Lemma 3.3.16(b)). So the $𝑖$ th equation of $𝑅 𝐱 = 𝐳$ contains exactly one pivot variable, with coefficient $1$ , plus some free variables:

𝑥_{𝑝_{𝑖}} + \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑥_{𝑓_{𝑗}} = 𝑧_{𝑖} .

The rows below row $𝑘$ are zero, so their equations read $0 = 𝑧_{𝑖}$ . These contain no unknowns at all: each one is either automatically true or impossible. For instance, a $4 \times 6$ matrix in RREF with pivot columns $1, 3, 6$ gives a system of the shape

\begin{aligned} 𝑥_{1} + 𝑟_{12} 𝑥_{2} + 𝑟_{14} 𝑥_{4} + 𝑟_{15} 𝑥_{5} & = 𝑧_{1}, \\ 𝑥_{3} + 𝑟_{24} 𝑥_{4} + 𝑟_{25} 𝑥_{5} & = 𝑧_{2}, \\ 𝑥_{6} & = 𝑧_{3}, \\ 0 & = 𝑧_{4} . \end{aligned}

If $𝑧_{4} \neq 0$ , there is nothing to be done. If $𝑧_{4} = 0$ , we may give the free variables $𝑥_{2}, 𝑥_{4}, 𝑥_{5}$ any values we like, and then each of the first three equations determines its own pivot variable.

Theorem 3.4.3 (Solving a system in reduced form). Let $𝑅 \in 𝐹^{𝑚 \times 𝑛}$ be in RREF, with entries $𝑟_{𝑖 𝑗}$ , pivot columns $𝑝_{1} < \dots < 𝑝_{𝑘}$ , and free columns $𝑓_{1} < \dots < 𝑓_{ℓ}$ . Let $𝐳 \in 𝐹^{𝑚}$ .

(a)If $𝑧_{𝑖} \neq 0$ for some $𝑖 > 𝑘$ , then $𝑅 𝐱 = 𝐳$ has no solution.
(b)If $𝑧_{𝑖} = 0$ for every $𝑖 > 𝑘$ , then $𝐱 \in 𝐹^{𝑛}$ solves $𝑅 𝐱 = 𝐳$ if and only if
$𝑥_{𝑝_{𝑖}} = 𝑧_{𝑖} - \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑥_{𝑓_{𝑗}} for 𝑖 = 1, \dots, 𝑘 .$
(3.4.1)
In particular, for every choice of $𝑡_{1}, \dots, 𝑡_{ℓ} \in 𝐹$ there is exactly one solution with $𝑥_{𝑓_{1}} =$ $𝑡_{1},$ $\dots,$ $𝑥_{𝑓_{ℓ}} =$ $𝑡_{ℓ}$ .

Proof.routine

Uses. Definition 2.3.8 (Matrix–vector product), Proposition 3.3.8 (Properties of the output), Theorem 3.3.12 (Matrices in RREF), Lemma 3.3.16 (Reading the columns of a matrix in RREF)

Hint 1. Write out the

𝑖

th entry of

𝑅 𝐱

, and split the sum over the columns into a sum over pivot columns and a sum over free columns.

Hint 2. Rows

𝑘 + 1, \dots, 𝑚

𝑅

are zero. For

𝑖 \leq 𝑘

, use that column

𝑝_{𝑠}

𝑅

𝐞_{𝑠}

Hint 3. For the last claim: every index

1, \dots, 𝑛

is exactly one of

𝑝_{1},

\dots,

𝑝_{𝑘},

𝑓_{1},

\dots,

𝑓_{ℓ}

. So the values

𝑡_{𝑗}

together with (3.4.1) specify each coordinate of

𝐱

exactly once.

Sketch. Split the

𝑖

th entry of

𝑅 𝐱

into a sum over the pivot columns and a sum over the free columns. For

𝑖 > 𝑘

row

𝑖

𝑅

is zero, so equation

𝑖

reads

0 = 𝑧_{𝑖}

, which is (a). For

𝑖 \leq 𝑘

𝑟_{𝑖 𝑝_{𝑠}}

1

𝑠 = 𝑖

and

0

otherwise, so equation

𝑖

involves the pivot variable

𝑥_{𝑝_{𝑖}}

with coefficient

1

and otherwise only free variables, which is (3.4.1). Free values plus (3.4.1) define one vector, and every solution with those free values is that vector.

Since $𝑅$ is in RREF, $𝑅 = rref (𝑅)$ is an output of Gauss–Jordan elimination, and its pivots are its leading entries (Theorem 3.3.12). By Proposition 3.3.8, rows $𝑘 + 1, \dots, 𝑚$ of $𝑅$ are zero, and by Lemma 3.3.16(b), column $𝑝_{𝑠}$ of $𝑅$ is $𝐞_{𝑠}$ for $𝑠 = 1, \dots, 𝑘$ .

By Definition 2.3.8, the $𝑖$ th entry of $𝑅 𝐱$ is $\sum_{𝑙 = 1}^{𝑛} 𝑟_{𝑖 𝑙} 𝑥_{𝑙}$ . Each index $𝑙 \in {1, \dots, 𝑛}$ is exactly one of $𝑝_{1},$ $\dots,$ $𝑝_{𝑘},$ $𝑓_{1},$ $\dots,$ $𝑓_{ℓ}$ , so

{(𝑅 𝐱)}_{𝑖} = \sum_{𝑠 = 1}^{𝑘} 𝑟_{𝑖 𝑝_{𝑠}} 𝑥_{𝑝_{𝑠}} + \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑥_{𝑓_{𝑗}} .

(3.4.2)

(a) If $𝑖 > 𝑘$ , row $𝑖$ of $𝑅$ is zero, so ${(𝑅 𝐱)}_{𝑖} = 0$ for every $𝐱$ . If moreover $𝑧_{𝑖} \neq 0$ , the $𝑖$ th equation fails for every $𝐱 \in 𝐹^{𝑛}$ .

(b) For $𝑖 > 𝑘$ , both sides of the $𝑖$ th equation are $0$ , so it holds for every $𝐱$ . For $𝑖 \leq 𝑘$ , the entry $𝑟_{𝑖 𝑝_{𝑠}}$ is the $𝑖$ th entry of $𝐞_{𝑠}$ , which is $1$ if $𝑠 = 𝑖$ and $0$ otherwise. So by (3.4.2),

{(𝑅 𝐱)}_{𝑖} = 𝑥_{𝑝_{𝑖}} + \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑥_{𝑓_{𝑗}},

and the $𝑖$ th equation ${(𝑅 𝐱)}_{𝑖} = 𝑧_{𝑖}$ holds if and only if (3.4.1) holds for this $𝑖$ . Hence $𝑅 𝐱 = 𝐳$ if and only if (3.4.1) holds for $𝑖 = 1, \dots, 𝑘$ .

For the last claim, let $𝑡_{1}, \dots, 𝑡_{ℓ} \in 𝐹$ . Define $𝐱 \in 𝐹^{𝑛}$ by $𝑥_{𝑓_{𝑗}} = 𝑡_{𝑗}$ for each $𝑗$ and

𝑥_{𝑝_{𝑖}} = 𝑧_{𝑖} - \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑡_{𝑗}

for each $𝑖$ . Since each index is exactly one pivot or free column, this specifies every coordinate exactly once, and $𝐱$ is a solution by what we just proved. Conversely, a solution with $𝑥_{𝑓_{𝑗}} = 𝑡_{𝑗}$ for all $𝑗$ has its pivot coordinates given by (3.4.1), so it is this $𝐱$ . □

The theorem is the lecture’s recipe, made precise: the free variables can be anything, and then the pivot variables are determined from the free variables and the corresponding $𝑧_{𝑖}$ . Applied to $𝑅 = 𝐴_{𝑟}$ and $𝐳 = 𝐺 𝐲$ , it settles consistency at once.

Corollary 3.4.4 (Consistency). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have $𝑘$ pivots, let $𝐺$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ , and let $𝐲 \in 𝐹^{𝑚}$ . Then $𝐴 𝐱 = 𝐲$ is consistent if and only if

{(𝐺 𝐲)}_{𝑖} = 0 for every 𝑖 with 𝑘 < 𝑖 \leq 𝑚 .

Equivalently, $𝐴 𝐱 = 𝐲$ is inconsistent exactly when the reduced augmented matrix $(𝐴_{𝑟} | 𝐺 𝐲)$ has a row $(0 \dots 0 | 𝑐)$ with $𝑐 \neq 0$ . In particular,

im 𝑇_{𝐴} = {𝐲 \in 𝐹^{𝑚} | {(𝐺 𝐲)}_{𝑖} = 0 for 𝑘 < 𝑖 \leq 𝑚} .

Proof.routine

Uses. Proposition 3.4.1 (Solving with the reduced matrix), Theorem 3.4.3 (Solving a system in reduced form), Proposition 3.3.8 (Properties of the output), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ )

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. By Proposition 3.4.1,

𝐴 𝐱 = 𝐲

has the same solutions as

𝐴_{𝑟} 𝐱 = 𝐺 𝐲

. Apply Theorem 3.4.3 to the latter.

Hint 2. Which rows of

𝐴_{𝑟}

are zero? The image of

𝑇_{𝐴}

is the set of

𝐲

for which the system is consistent.

Sketch. The system has the same solutions as

𝐴_{𝑟} 𝐱 = 𝐳

with

𝐳 = 𝐺 𝐲

. If some

𝑧_{𝑖} \neq 0

with

𝑖 > 𝑘

, there is no solution by Theorem 3.4.3(a); otherwise there is one, for instance with all free variables

0

, by Theorem 3.4.3(b). Rows

1, \dots, 𝑘

𝐴_{𝑟}

are nonzero and the others are zero, which gives the reformulation. The image of

𝑇_{𝐴}

consists of the

𝐲

for which the system is consistent.

Let $𝐳 = 𝐺 𝐲$ . By Proposition 3.4.1, $𝐴 𝐱 = 𝐲$ and $𝐴_{𝑟} 𝐱 = 𝐳$ have the same solutions. If $𝑧_{𝑖} \neq 0$ for some $𝑖 > 𝑘$ , the latter has no solution by Theorem 3.4.3(a). If $𝑧_{𝑖} = 0$ for all $𝑖 > 𝑘$ , it has a solution by Theorem 3.4.3(b), for instance the one whose free variables are all $0$ .

By Proposition 3.3.8, rows $1, \dots, 𝑘$ of $𝐴_{𝑟}$ are nonzero (they contain the pivots) and rows $𝑘 + 1, \dots, 𝑚$ are zero. So a row of $(𝐴_{𝑟} | 𝐳)$ of the form $(0 \dots 0 | 𝑐)$ with $𝑐 \neq 0$ is exactly a row $𝑖 > 𝑘$ with $𝑧_{𝑖} = 𝑐 \neq 0$ .

Finally, by Proposition 3.1.8(a), $𝐲 \in im 𝑇_{𝐴}$ if and only if $𝐴 𝐱 = 𝐲$ is consistent, which we have just characterized. □

The description of $im 𝑇_{𝐴}$ is worth a second look. The conditions ${(𝐺 𝐲)}_{𝑖} = 0$ for $𝑖 > 𝑘$ are $𝑚 - 𝑘$ homogeneous linear equations in $𝑦_{1}, \dots, 𝑦_{𝑚}$ , whose coefficients are the last $𝑚 - 𝑘$ rows of $𝐺$ . So the image of $𝑇_{𝐴}$ , which is defined as a set of outputs, is also the solution set of a homogeneous system, that is, a kernel. For the running system, the last row of $𝐺$ in Example 3.2.8 is $(- 1, - 1, 1)$ , and the single condition $- 𝑦_{1} - 𝑦_{2} + 𝑦_{3} = 0$ is the plane $𝑦_{3} = 𝑦_{1} + 𝑦_{2}$ that Section 3.1.5 found by inspecting the columns.

If we row reduce $(𝐴 | 𝐲)$ all the way, without restricting the scan, the test reads slightly differently, and it has a proof that never mentions $𝐺$ .

Corollary 3.4.5 (Consistency from the augmented matrix). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

𝐲 \in 𝐹^{𝑚}

. Then

𝐴 𝐱 = 𝐲

is consistent if and only if the last column of the augmented matrix

(𝐴 | 𝐲)

is not one of its pivot columns, that is, if and only if

rref ((𝐴 | 𝐲))

has no row

(0 \dots 0 | 1)

Proof.routine

Uses. Corollary 3.3.19 (Pivot columns, intrinsically), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Definition 3.3.9 (Reduced row echelon form), Proposition 3.3.8 (Properties of the output)

Hint 1. Apply Corollary 3.3.19(a) to the

𝑚 \times (𝑛 + 1)

matrix

(𝐴 | 𝐲)

and its last column.

Hint 2. When is

𝐲

a linear combination of the columns of

𝐴

Sketch. By Corollary 3.3.19(a), the last column

𝐲

is a pivot column exactly when it is not a combination of

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

, that is, by Proposition 3.1.8(a), exactly when the system is inconsistent. A pivot in the last column of a matrix in RREF is the leading

1

of a row that vanishes elsewhere, a row

(0 \dots 0 | 1)

The columns of $(𝐴 | 𝐲)$ are $𝐚_{1}, \dots, 𝐚_{𝑛}, 𝐲$ . By Corollary 3.3.19(a), applied to this matrix and its column $𝑛 + 1$ , the last column is a pivot column if and only if $𝐲$ is not a linear combination of $𝐚_{1}, \dots, 𝐚_{𝑛}$ . By Proposition 3.1.8(a), this happens if and only if $𝐴 𝐱 = 𝐲$ is inconsistent.

By Definition 3.3.9 and Proposition 3.3.8(b), the pivots of $(𝐴 | 𝐲)$ are the leading entries of the nonzero rows of $rref ((𝐴 | 𝐲))$ , and they are $1$ . So the last column is a pivot column if and only if some row has its leading entry, a $1$ , in the last column, that is, if and only if some row is $(0 \dots 0 | 1)$ . □

The two tests agree, as they must: by Exercise 3.3.44 the first $𝑛$ columns of $rref ((𝐴 | 𝐲))$ form $𝐴_{𝑟}$ , and the unrestricted run simply goes on to clear the last column once a row $(0 \dots 0 | 𝑐)$ with $𝑐 \neq 0$ appears.

Example 3.4.6 (A complete solution). We solve $𝐴 𝐱 = 𝐲$ for the matrix $𝐴$ of Example 3.3.3 and every $𝐲 \in ℚ^{3}$ . Carrying $𝐼_{3}$ along in Section 3.3.3 produced

𝐺 = (\begin{matrix} - 1 / 2 & 1 / 2 & 0 \\ 1 / 2 & 0 & 0 \\ - 1 & - 1 / 2 & 1 \end{matrix}),

so by Proposition 3.4.1 the system is equivalent to

(\begin{matrix} 1 & 2 & 0 & - 2 & (- 𝑦_{1} + 𝑦_{2}) / 2 \\ 0 & 0 & 1 & 2 & 𝑦_{1} / 2 \\ 0 & 0 & 0 & 0 & - 𝑦_{1} - 𝑦_{2} / 2 + 𝑦_{3} \end{matrix}) .

Here $𝑘 = 2$ , so there is one consistency condition. By Corollary 3.4.4, the system is consistent if and only if $𝑦_{3} = 𝑦_{1} + 𝑦_{2} / 2$ , and $im 𝑇_{𝐴}$ is the plane $2 𝑦_{3} = 2 𝑦_{1} + 𝑦_{2}$ in $ℚ^{3}$ . (Each column of $𝐴$ satisfies this, for example $2 \cdot 4 = 2 \cdot 4 + 0$ for $𝐚_{4} = (4, 0, 4)$ .)

Take $𝐲 = (4, 2, 5)$ . Then $𝐺 𝐲 = (- 1, 2, 0)$ , the condition holds, and by (3.4.1) the solutions are exactly the vectors with

𝑥_{1} = - 1 - 2 𝑥_{2} + 2 𝑥_{4}, 𝑥_{3} = 2 - 2 𝑥_{4}, 𝑥_{2}, 𝑥_{4} \in ℚ arbitrary .

For $𝐲 = (4, 2, 6)$ , instead, $𝐺 𝐲 = (- 1, 2, 1)$ , and the last equation of the reduced system reads $0 = 1$ : there is no solution.

The row reducer below carries out the reduction of $(𝐴 | 𝐲)$ for $𝐲 = (4, 2, 5)$ , scanning only the columns of $𝐴$ . At the end it reports the pivot and free columns and whether the system is consistent. Edit the last column to $(4, 2, 6)$ to see the row $(0, 0, 0, 0 | 1)$ appear.

(\begin{matrix} 0 & 0 & 2 & 4 & 4 \\ 2 & 4 & 2 & 0 & 2 \\ 1 & 2 & 3 & 4 & 5 \end{matrix}) ⇝ (\begin{matrix} 1 & 2 & 0 & - 2 & - 1 \\ 0 & 0 & 1 & 2 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})

Solving the system of Example 3.4.6. Pivots are boxed; the bar separates

𝐴

from

𝐲

Exercise 3.4.7.routine Let

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

Find $𝐴_{𝑟}$ and the pivot and free variables. For which $𝐲 \in ℝ^{3}$ is $𝐴 𝐱 = 𝐲$ consistent? Find all solutions for $𝐲 = (1, 2, 1)$ .

Solution.

Uses. Proposition 3.4.1 (Solving with the reduced matrix), Corollary 3.4.4 (Consistency), Theorem 3.4.3 (Solving a system in reduced form)

Hint 1. Reduce

(𝐴 | 𝐲)

with symbolic

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

. The first column is zero, so the first pivot is in column

2

Hint 2. The first column is a free column. Its variable

𝑥_{1}

appears in no equation at all.

Sketch.

𝐴_{𝑟}

has rows

(0, 1, 2, 0)

(0, 0, 0, 1)

𝟎

, so

𝑥_{2}, 𝑥_{4}

are pivot variables and

𝑥_{1}, 𝑥_{3}

are free. The last entry of

𝐺 𝐲

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

, so the system is consistent iff

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

. For

𝐲 = (1, 2, 1)

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

𝑥_{4} = 0

, with

𝑥_{1}, 𝑥_{3}

arbitrary.

We reduce $(𝐴 | 𝐲)$ . Column $1$ is zero, so pass $1$ uses the pivot in position $(1, 2)$ : add $- 2$ times row $1$ to row $2$ and $- 1$ times row $1$ to row $3$ . In pass $2$ , column $3$ vanishes in rows $2$ and $3$ , so the pivot is in position $(2, 4)$ ; add $- 1$ times row $2$ to row $1$ and row $2$ to row $3$ :

(\begin{matrix} 0 & 1 & 2 & 1 & 𝑦_{1} \\ 0 & 2 & 4 & 3 & 𝑦_{2} \\ 0 & 1 & 2 & 0 & 𝑦_{3} \end{matrix}) ⇝ (\begin{matrix} 0 & 1 & 2 & 1 & 𝑦_{1} \\ 0 & 0 & 0 & 1 & - 2 𝑦_{1} + 𝑦_{2} \\ 0 & 0 & 0 & - 1 & - 𝑦_{1} + 𝑦_{3} \end{matrix}) ⇝ (\begin{matrix} 0 & 1 & 2 & 0 & 3 𝑦_{1} - 𝑦_{2} \\ 0 & 0 & 0 & 1 & - 2 𝑦_{1} + 𝑦_{2} \\ 0 & 0 & 0 & 0 & - 3 𝑦_{1} + 𝑦_{2} + 𝑦_{3} \end{matrix}) .

So $𝐴_{𝑟}$ has rows $(0, 1, 2, 0)$ , $(0, 0, 0, 1)$ , $(0, 0, 0, 0)$ , the pivot variables are $𝑥_{2}$ and $𝑥_{4}$ , and the free variables are $𝑥_{1}$ and $𝑥_{3}$ . By Corollary 3.4.4 the system is consistent if and only if $- 3 𝑦_{1} + 𝑦_{2} + 𝑦_{3} = 0$ .

For $𝐲 = (1, 2, 1)$ the condition holds ( $- 3 + 2 + 1 = 0$ ), and the reduced system is $𝑥_{2} + 2 𝑥_{3} = 1$ , $𝑥_{4} = 0$ . By Theorem 3.4.3(b), the solutions are the vectors $(𝑥_{1}, 1 - 2 𝑥_{3}, 𝑥_{3}, 0)$ with $𝑥_{1}, 𝑥_{3} \in ℝ$ arbitrary. The unknown $𝑥_{1}$ multiplies the zero column, so it occurs in no equation, and it is free for the most obvious reason. As a check, $𝐴 (0, 1, 0, 0)$ is the second column $(1, 2, 1)$ .

3.4.3The shape of the solution set

Formula (3.4.1) expresses the pivot variables through the free ones. Collecting, for each free variable, the terms that involve it writes every solution as one fixed vector plus a combination of vectors that do not depend on $𝐲$ , which is the form Proposition 3.1.19 predicts.

Definition 3.4.8 (Basic solutions). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , with $𝐴_{𝑟} = 𝐺 𝐴$ as above, entries $𝑟_{𝑖 𝑗}$ of $𝐴_{𝑟}$ , pivot columns $𝑝_{1} < \dots < 𝑝_{𝑘}$ , and free columns $𝑓_{1} < \dots < 𝑓_{ℓ}$ .

(a)For $𝑗 = 1, \dots, ℓ$ , the $𝑗$ th basic solution of $𝐴$ is the vector $𝐬_{𝑗} \in 𝐹^{𝑛}$ with
${(𝐬_{𝑗})}_{𝑓_{𝑗}} = 1, {(𝐬_{𝑗})}_{𝑓_{𝑗^{'}}} = 0 for 𝑗^{'} \neq 𝑗, {(𝐬_{𝑗})}_{𝑝_{𝑖}} = - 𝑟_{𝑖 𝑓_{𝑗}} for 𝑖 = 1, \dots, 𝑘 .$
(b)If $𝐴 𝐱 = 𝐲$ is consistent, its particular solution $𝐱_{0} \in 𝐹^{𝑛}$ has ${(𝐱_{0})}_{𝑝_{𝑖}} =$ ${(𝐺 𝐲)}_{𝑖}$ for $𝑖 = 1, \dots, 𝑘$ , and ${(𝐱_{0})}_{𝑓_{𝑗}} = 0$ for $𝑗 = 1, \dots, ℓ$ .

In words: $𝐬_{𝑗}$ is the solution of $𝐴 𝐱 = 𝟎$ obtained by setting the free variable $𝑥_{𝑓_{𝑗}}$ to $1$ and the other free variables to $0$ , and $𝐱_{0}$ is the solution of $𝐴 𝐱 = 𝐲$ obtained by setting every free variable to $0$ . (Both are solutions by Theorem 3.4.3(b) and Proposition 3.4.1.) The $𝐬_{𝑗}$ depend only on $𝐴_{𝑟}$ , which depends only on $𝐴$ . The vector $𝐱_{0}$ is the only solution whose free variables all vanish, by Theorem 3.4.3(b), so it does not depend on which $𝐺$ we used either. Realize also that $𝐬_{𝑗}$ can be copied from column $𝑓_{𝑗}$ of $𝐴_{𝑟}$ : negate its first $𝑘$ entries and put them in the pivot positions $𝑝_{1}, \dots, 𝑝_{𝑘}$ , put a $1$ in position $𝑓_{𝑗}$ , and zeros elsewhere.

Theorem 3.4.9 (All solutions). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , and suppose $𝐴 𝐱 = 𝐲$ is consistent. Let $𝐱_{0}$ be its particular solution and $𝐬_{1}, \dots, 𝐬_{ℓ}$ the basic solutions of $𝐴$ (Definition 3.4.8).

(a)The solutions of $𝐴 𝐱 = 𝐲$ are exactly the vectors
$𝐱 = 𝐱_{0} + 𝑡_{1} 𝐬_{1} + 𝑡_{2} 𝐬_{2} + \dots + 𝑡_{ℓ} 𝐬_{ℓ} (𝑡_{1}, \dots, 𝑡_{ℓ} \in 𝐹),$
and each solution arises from exactly one choice of $𝑡_{1}, \dots, 𝑡_{ℓ}$ , namely $𝑡_{𝑗} = 𝑥_{𝑓_{𝑗}}$ .
(b) $ker 𝑇_{𝐴} =$ $span (𝐬_{1}, \dots, 𝐬_{ℓ})$ , and each vector of $ker 𝑇_{𝐴}$ is a linear combination of $𝐬_{1}, \dots, 𝐬_{ℓ}$ in exactly one way.

So the solution set of $𝐴 𝐱 = 𝐲$ is $𝐱_{0} +$ $span (𝐬_{1}, \dots, 𝐬_{ℓ}) =$ $𝐱_{0} +$ $ker 𝑇_{𝐴}$ .

Proof.standard

Uses. Theorem 3.4.3 (Solving a system in reduced form), Proposition 3.4.1 (Solving with the reduced matrix), Corollary 3.4.4 (Consistency), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Definition 1.3.10 (Span)

Techniques. Particular plus homogeneous (Technique 3.1.18), Reduce to RREF (Technique 3.3.22)

Hint 1. Fix

𝑡_{1}, \dots, 𝑡_{ℓ}

and compute the coordinates of

𝐰 =

𝐱_{0} +

\sum_{𝑗} 𝑡_{𝑗} 𝐬_{𝑗}

: first those in the free positions, then those in the pivot positions.

Hint 2. The

𝑓_{𝑗}

-coordinate of

𝐰

𝑡_{𝑗}

, and its

𝑝_{𝑖}

-coordinate is

𝑧_{𝑖} -

\sum_{𝑗} 𝑟_{𝑖 𝑓_{𝑗}} 𝑡_{𝑗}

, where

𝐳 = 𝐺 𝐲

. Compare with (3.4.1).

Hint 3. For (b), apply (a) with

𝐲 = 𝟎

. What is the particular solution then?

Sketch. With

𝐳 = 𝐺 𝐲

, the vector

𝐰 =

𝐱_{0} +

\sum_{𝑗} 𝑡_{𝑗} 𝐬_{𝑗}

has

𝑓_{𝑗}

-coordinate

𝑡_{𝑗}

and

𝑝_{𝑖}

-coordinate

𝑧_{𝑖} -

\sum_{𝑗} 𝑟_{𝑖 𝑓_{𝑗}} 𝑡_{𝑗}

. By Theorem 3.4.3(b),

𝐰

is a solution, and every solution

𝐱

equals the

𝐰

with

𝑡_{𝑗} = 𝑥_{𝑓_{𝑗}}

, because both have the same free coordinates and the pivot coordinates are determined by them. Reading off free coordinates gives uniqueness of the

𝑡_{𝑗}

. For

𝐲 = 𝟎

the particular solution is

𝟎

, which gives (b).

Let $𝐳 = 𝐺 𝐲$ . Since the system is consistent, $𝑧_{𝑖} = 0$ for $𝑖 > 𝑘$ (Corollary 3.4.4), and by Proposition 3.4.1 its solutions are those of $𝐴_{𝑟} 𝐱 = 𝐳$ .

(a) For $𝑡_{1}, \dots, 𝑡_{ℓ} \in 𝐹$ , let $𝐰 =$ $𝐱_{0} +$ $𝑡_{1} 𝐬_{1} +$ $\dots +$ $𝑡_{ℓ} 𝐬_{ℓ}$ . In position $𝑓_{𝑗}$ , the vector $𝐱_{0}$ has a $0$ , $𝐬_{𝑗}$ has a $1$ , and $𝐬_{𝑗^{'}}$ has a $0$ for $𝑗^{'} \neq 𝑗$ , so

𝑤_{𝑓_{𝑗}} = 𝑡_{𝑗} .

In position $𝑝_{𝑖}$ , $𝐱_{0}$ has $𝑧_{𝑖}$ and $𝐬_{𝑗}$ has $- 𝑟_{𝑖 𝑓_{𝑗}}$ , so

𝑤_{𝑝_{𝑖}} = 𝑧_{𝑖} - \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑡_{𝑗} = 𝑧_{𝑖} - \sum_{𝑗 = 1}^{ℓ} 𝑟_{𝑖 𝑓_{𝑗}} 𝑤_{𝑓_{𝑗}} .

This is (3.4.1) for $𝐰$ , so $𝐰$ solves $𝐴_{𝑟} 𝐱 = 𝐳$ by Theorem 3.4.3(b), and hence $𝐴 𝐱 = 𝐲$ .

Conversely, let $𝐱$ be a solution, and let $𝐰$ be the vector above with $𝑡_{𝑗} = 𝑥_{𝑓_{𝑗}}$ for each $𝑗$ . Then $𝐱$ and $𝐰$ are solutions with the same free coordinates, so by the uniqueness in Theorem 3.4.3(b) they are equal. Finally, if $𝐱 =$ $𝐱_{0} +$ $\sum_{𝑗} 𝑡_{𝑗} 𝐬_{𝑗}$ , then $𝑥_{𝑓_{𝑗}} = 𝑡_{𝑗}$ by the computation above, so $𝑡_{1}, \dots, 𝑡_{ℓ}$ are determined by $𝐱$ .

(b) By Proposition 3.1.8(b), $ker 𝑇_{𝐴}$ is the solution set of $𝐴 𝐱 = 𝟎$ , which is consistent. Its particular solution is $𝟎$ , since $𝐺 𝟎 = 𝟎$ . By (a), its solutions are exactly the vectors $𝑡_{1} 𝐬_{1} + \dots + 𝑡_{ℓ} 𝐬_{ℓ}$ , each for exactly one choice of the $𝑡_{𝑗}$ . By Definition 1.3.10, the set of these vectors is $span (𝐬_{1}, \dots, 𝐬_{ℓ})$ .

The last sentence of the theorem combines (a) and (b). □

This is Proposition 3.1.19 made explicit. That proposition said that once we know one solution, the others are obtained by adding elements of $ker 𝑇_{𝐴}$ ; the theorem produces the one solution, $𝐱_{0}$ , and describes $ker 𝑇_{𝐴}$ by $ℓ$ vectors, one for each free variable. It is the canonical instance of Technique 3.1.18. There is also a quick way to see that $𝐴 𝐬_{𝑗} = 𝟎$ without the theorem. By Corollary 3.3.19(b), column $𝑓_{𝑗}$ of $𝐴$ is $\sum_{𝑖} 𝑟_{𝑖 𝑓_{𝑗}} 𝐚_{𝑝_{𝑖}}$ (the terms with $𝑝_{𝑖} > 𝑓_{𝑗}$ are zero by Lemma 3.3.16(a)). Moving everything to one side gives a relation among the columns of $𝐴$ whose coefficient vector is exactly $𝐬_{𝑗}$ .

Example 3.4.10 (The complete solution, in vector form). In Example 3.4.6, with $𝐲 = (4, 2, 5)$ , we have $𝐺 𝐲 = (- 1, 2, 0)$ and

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

The particular solution has $- 1$ and $2$ in the pivot positions $1, 3$ , and $0$ in the free positions $2, 4$ . The basic solutions come from columns $2$ and $4$ of $𝐴_{𝑟}$ :

𝐱_{0} = (\begin{matrix} - 1 \\ 0 \\ 2 \\ 0 \end{matrix}), 𝐬_{1} = (\begin{matrix} - 2 \\ 1 \\ 0 \\ 0 \end{matrix}), 𝐬_{2} = (\begin{matrix} 2 \\ 0 \\ - 2 \\ 1 \end{matrix}) .

By Theorem 3.4.9, the solution set is

{(- 1, 0, 2, 0) + 𝑡_{1} (- 2, 1, 0, 0) + 𝑡_{2} (2, 0, - 2, 1) | 𝑡_{1}, 𝑡_{2} \in ℚ},

a plane in $ℚ^{4}$ , and $ker 𝑇_{𝐴} =$ $span ((- 2, 1, 0, 0), (2, 0, - 2, 1))$ . The relations among the columns behind $𝐬_{1}$ and $𝐬_{2}$ are $𝐚_{2} = 2 𝐚_{1}$ and $𝐚_{4} = - 2 𝐚_{1} + 2 𝐚_{3}$ , which we already read off in Section 3.3.4.

Remark 3.4.11 (A basis of the kernel). Part (b) of Theorem 3.4.9 says that every vector of

ker 𝑇_{𝐴}

is a linear combination of

𝐬_{1}, \dots, 𝐬_{ℓ}

in exactly one way. In the language of Section 1.5 and Section 1.6, the list

𝐬_{1}, \dots, 𝐬_{ℓ}

is linearly independent (Definition 1.5.1) and spans

ker 𝑇_{𝐴}

, so it is a basis of

ker 𝑇_{𝐴}

(Definition 1.6.1). It has one vector for each free variable, so

ℓ = 𝑛 - 𝑘

vectors. Once dimension is defined, this says that

dim ker 𝑇_{𝐴}

is the number of free columns of

𝐴

, which is the starting point of rank–nullity (Section 4.2).

Remark 3.4.12 (Checking a description of the solutions). Solutions are often written down by some other method, or the parameters are chosen differently. A description

𝐱_{0^{'}} +

span (𝐮_{1}, \dots, 𝐮_{𝑟})

is easy to test in one direction: if

𝐴 𝐱_{0^{'}} = 𝐲

and

𝐴 𝐮_{𝑖} = 𝟎

for every

𝑖

, then every vector in it is a solution. But this test cannot detect missing solutions: dropping one of the

𝐮_{𝑖}

still passes it. The description is complete exactly when

span (𝐮_{1}, \dots, 𝐮_{𝑟}) =

ker 𝑇_{𝐴}

, and by Theorem 3.4.9 this holds if and only if each basic solution

𝐬_{𝑗}

is a combination of the

𝐮_{𝑖}

. (Section 4.2 gives a quicker test:

𝑟 = ℓ

linearly independent vectors of

ker 𝑇_{𝐴}

always span it.) Exercise 3.4.34 is an example.

The whole procedure fits in a few lines.

Algorithm 3.4.13 (Solving a linear system)

Input: A matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and a vector $𝐲 \in 𝐹^{𝑚}$ .
Output: The solution set of $𝐴 𝐱 = 𝐲$ , in the form $𝐱_{0} +$ $span (𝐬_{1}, \dots, 𝐬_{ℓ})$ , or the conclusion that the system is inconsistent.

Row reduce

(𝐴 | 𝐲)

by Gauss–Jordan elimination, scanning only the first

𝑛

columns in step 1 of Algorithm 3.3.1. The result is

(𝐴_{𝑟} | 𝐳)

with

𝐳 = 𝐺 𝐲

. Record the pivot columns

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

and the free columns

𝑓_{1}, \dots, 𝑓_{ℓ}

𝑧_{𝑖} \neq 0

for some

𝑖 > 𝑘

, stop: the system is inconsistent.

Otherwise, let

𝐱_{0}

have

𝑧_{𝑖}

in position

𝑝_{𝑖}

for

𝑖 = 1, \dots, 𝑘

, and

0

in every free position.

For each

𝑗 = 1, \dots, ℓ

, let

𝐬_{𝑗}

have

1

in position

𝑓_{𝑗}

0

in the other free positions, and

- 𝑟_{𝑖 𝑓_{𝑗}}

in position

𝑝_{𝑖}

, where

𝑟_{𝑖 𝑓_{𝑗}}

is the

𝑖

th entry of column

𝑓_{𝑗}

𝐴_{𝑟}

Output

𝐱_{0} +

span (𝐬_{1}, \dots, 𝐬_{ℓ})

It is correct by Proposition 3.4.1, Corollary 3.4.4, and Theorem 3.4.9. The bijection $(𝑡_{1}, \dots, 𝑡_{ℓ}) \mapsto$ $𝐱_{0} +$ $\sum_{𝑗} 𝑡_{𝑗} 𝐬_{𝑗}$ of Theorem 3.4.9(a) also counts the solutions.

Corollary 3.4.14 (Counting solutions). Suppose $𝐴 𝐱 = 𝐲$ is consistent, where $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has $ℓ$ free columns.

(a)The system has exactly one solution if and only if $ℓ = 0$ , that is, if and only if every column of $𝐴$ is a pivot column.
(b)If $𝐹$ is finite with $𝑞$ elements, the system has exactly $𝑞^{ℓ}$ solutions.
(c)If $𝐹$ is infinite and $ℓ \geq 1$ , the system has infinitely many solutions.

Proof.routine

Uses. Theorem 3.4.9 (All solutions)

Hint 1. Theorem 3.4.9(a) sets up a bijection between the solution set and the set of lists

(𝑡_{1}, \dots, 𝑡_{ℓ})

of scalars.

Hint 2. For (a) with

ℓ \geq 1

, compare

𝐱_{0}

and

𝐱_{0} + 𝐬_{1}

Sketch. By Theorem 3.4.9(a),

(𝑡_{1}, \dots, 𝑡_{ℓ}) \mapsto

𝐱_{0} +

\sum_{𝑗} 𝑡_{𝑗} 𝐬_{𝑗}

is a bijection from

𝐹^{ℓ}

onto the solution set (for

ℓ = 0

, the solution set is

{𝐱_{0}}

). Count:

𝐹^{ℓ}

has

𝑞^{ℓ}

elements when

| 𝐹 | = 𝑞

, and infinitely many when

𝐹

is infinite and

ℓ \geq 1

. If

ℓ \geq 1

, the solutions

𝐱_{0}

and

𝐱_{0} + 𝐬_{1}

differ in position

𝑓_{1}

By Theorem 3.4.9(a), each solution is $𝐱_{0} + \sum_{𝑗} 𝑡_{𝑗} 𝐬_{𝑗}$ for exactly one list $(𝑡_{1}, \dots, 𝑡_{ℓ}) \in 𝐹^{ℓ}$ , and every such vector is a solution. So the solution set is in bijection with $𝐹^{ℓ}$ . If $ℓ = 0$ , there are no parameters and the only solution is $𝐱_{0}$ .

(a) If $ℓ = 0$ , the only solution is $𝐱_{0}$ . If $ℓ \geq 1$ , then $𝐱_{0}$ and $𝐱_{0} + 𝐬_{1}$ are solutions, and they differ, since their $𝑓_{1}$ -coordinates are $0$ and $1$ .

(b) $𝐹^{ℓ}$ has $𝑞^{ℓ}$ elements (and $𝑞^{0} = 1$ covers $ℓ = 0$ ).

(c) If $ℓ \geq 1$ and $𝐹$ is infinite, the vectors $𝐱_{0} + 𝑡 𝐬_{1}$ , $𝑡 \in 𝐹$ , are infinitely many distinct solutions. □

Part (b) is the formula promised after Example 3.1.26, where the equation $𝑥_{1} + 𝑥_{2} = 1$ over $𝔽_{2}$ has one free variable and $2^{1}$ solutions. We did not need dimension: the number of free variables does the counting. Part (c) recovers Corollary 3.1.24, and adds that the number of solutions of a consistent system is decided by $𝐴$ alone.

3.4.4Pivots in every column, pivots in every row

Intuition (Free variables and zero rows). Every system

𝐴 𝐱 = 𝐲

raises two questions: is there a solution, and is it unique? We have now located the source of each answer in

𝐴_{𝑟}

. Non-uniqueness comes from free variables, since each one can be varied independently. Inconsistency comes from zero rows, since each one produces an equation

0 = {(𝐺 𝐲)}_{𝑖}

, which fails for a suitable

𝐲

. A free variable is a column without a pivot, and a zero row is a row without a pivot. So we expect: a pivot in every column means uniqueness, and a pivot in every row means existence for every right-hand side. Uniqueness is a property of

ker 𝑇_{𝐴}

(Corollary 3.1.22), so the first statement is about the homogeneous system.

Proposition 3.4.15 (A pivot in every column). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝐴_{𝑟}$ has a pivot in every column.
(II)The equation $𝐴 𝐱 = 𝟎$ has only the trivial solution $𝐱 = 𝟎$ .

The homogeneous system is consistent, so this is the case $𝐲 = 𝟎$ of Corollary 3.4.14(a). The lecture proves it directly, and the direct argument is worth having: it constructs a nonzero solution whenever one exists.

Proof (set one free variable to $1$ ).routine

Uses. Proposition 3.4.1 (Solving with the reduced matrix), Theorem 3.4.3 (Solving a system in reduced form), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.3.8 (Matrix–vector product)

Techniques. Reduce to RREF (Technique 3.3.22), Contrapositive (Technique 1.5.4)

Hint 1. Reduce:

𝐴 𝐱 = 𝟎

if and only if

𝐴_{𝑟} 𝐱 = 𝟎

. If every column of

𝐴_{𝑟}

is a pivot column, what are its columns?

Hint 2. For (II)

\Rightarrow

(I), prove the contrapositive. If some column

𝑓

has no pivot,

𝑥_{𝑓}

is a free variable. Choose values of the free variables and solve for the pivot variables with Theorem 3.4.3.

Hint 3. Set

𝑥_{𝑓} = 1

and every other free variable to

0

Sketch.

𝐴 𝐱 = 𝟎

iff

𝐴_{𝑟} 𝐱 = 𝟎

, since

𝐺 𝟎 = 𝟎

. If every column is a pivot column, then

𝑘 = 𝑛

𝑝_{𝑠} = 𝑠

, and

𝐴_{𝑟}

has columns

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

, so

𝐴_{𝑟} 𝐱

lists

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

followed by zeros, and vanishes only for

𝐱 = 𝟎

. If column

𝑓

is free, Theorem 3.4.3(b) gives a solution with

𝑥_{𝑓} = 1

and the other free variables

0

; it is nonzero.

By Proposition 3.4.1 with $𝐲 = 𝟎$ , and since $𝐺 𝟎 = 𝟎$ , the equations $𝐴 𝐱 = 𝟎$ and $𝐴_{𝑟} 𝐱 = 𝟎$ have the same solutions.

(I) $\Rightarrow$ (II). Suppose every column of $𝐴_{𝑟}$ is a pivot column. Then $𝑘 = 𝑛$ , and $𝑝_{1} < \dots < 𝑝_{𝑛}$ are $𝑛$ increasing numbers in ${1, \dots, 𝑛}$ , so $𝑝_{𝑠} = 𝑠$ for every $𝑠$ . By Lemma 3.3.16(b), column $𝑠$ of $𝐴_{𝑟}$ is $𝐞_{𝑠}$ , so by Definition 2.3.8

𝐴_{𝑟} 𝐱 = 𝑥_{1} 𝐞_{1} + \dots + 𝑥_{𝑛} 𝐞_{𝑛},

the vector of $𝐹^{𝑚}$ whose first $𝑛$ entries are $𝑥_{1}, \dots, 𝑥_{𝑛}$ and whose remaining $𝑚 - 𝑛$ entries are $0$ . It is $𝟎$ only if $𝐱 = 𝟎$ .

(II) $\Rightarrow$ (I). We prove the contrapositive. Suppose some column of $𝐴_{𝑟}$ has no pivot, so it is a free column $𝑓_{𝑗}$ . The right-hand side $𝟎$ certainly has $𝑧_{𝑖} = 0$ for $𝑖 > 𝑘$ , so by Theorem 3.4.3(b) the system $𝐴_{𝑟} 𝐱 = 𝟎$ has a solution $𝐱$ with $𝑥_{𝑓_{𝑗}} = 1$ and every other free variable $0$ . This $𝐱$ is nonzero, as its $𝑓_{𝑗}$ -coordinate is $1$ , and $𝐴 𝐱 = 𝟎$ . So (II) fails. □

Proof (via relations among the columns).standard

Uses. Definition 2.3.8 (Matrix–vector product), Theorem 1.5.5 (Independence is decided at zero), Corollary 3.3.19 (Pivot columns, intrinsically), Lemma 1.5.10 (Linear dependence lemma)

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. By Definition 2.3.8, a solution of

𝐴 𝐱 = 𝟎

is a linear relation among the columns

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

. Restate (II) in terms of linear independence.

Hint 2. Corollary 3.3.19(a) restates (I): no column is a linear combination of the columns before it.

Hint 3. Connect the two restatements with the linear dependence lemma (Lemma 1.5.10).

Sketch. (II) says that

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

has only the trivial relation, that is, is linearly independent (Theorem 1.5.5). (I) says that no

𝐚_{𝑗}

lies in

span (𝐚_{1}, \dots, 𝐚_{𝑗 - 1})

(Corollary 3.3.19(a)). If some

𝐚_{𝑗} =

\sum_{𝑙 < 𝑗} 𝑐_{𝑙} 𝐚_{𝑙}

, then

\sum_{𝑙 < 𝑗} 𝑐_{𝑙} 𝐚_{𝑙} -

𝐚_{𝑗} =

𝟎

is a nontrivial relation; if the columns are dependent, Lemma 1.5.10 provides such a

𝑗

By Definition 2.3.8, $𝐴 𝐱 =$ $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛}$ . So (II) says that the only linear relation among $𝐚_{1}, \dots, 𝐚_{𝑛}$ is the trivial one, which by Theorem 1.5.5 means that the list $𝐚_{1}, \dots, 𝐚_{𝑛}$ is linearly independent. By Corollary 3.3.19(a), (I) says that for no $𝑗$ is $𝐚_{𝑗}$ a linear combination of $𝐚_{1}, \dots, 𝐚_{𝑗 - 1}$ .

If (I) fails, then $𝐚_{𝑗} =$ $𝑐_{1} 𝐚_{1} +$ $\dots +$ $𝑐_{𝑗 - 1} 𝐚_{𝑗 - 1}$ for some $𝑗$ and some scalars $𝑐_{𝑙}$ , and then

𝑐_{1} 𝐚_{1} + \dots + 𝑐_{𝑗 - 1} 𝐚_{𝑗 - 1} + (- 1) 𝐚_{𝑗} = 𝟎

is a linear relation with a nonzero coefficient, so (II) fails. If (II) fails, the columns are linearly dependent, and the linear dependence lemma (Lemma 1.5.10) gives an index $𝑗$ with $𝐚_{𝑗} \in$ $span (𝐚_{1}, \dots, 𝐚_{𝑗 - 1})$ , so (I) fails. □

The first proof is constructive: when (I) fails, it hands us a nonzero solution, namely a basic solution. The second explains what a missing pivot means: a column that depends on the columns before it. It also shows that a pivot in every column is the same as linear independence of the columns. By Theorem 2.6.11, (II) says that $𝑇_{𝐴}$ is injective, so a pivot in every column is a mechanical test for the equivalent conditions of Theorem 2.7.2. Section 3.5 adds it to that theorem.

Proposition 3.4.16 (A pivot in every row). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝐴_{𝑟}$ has a pivot in every row.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has a solution $𝐱 \in 𝐹^{𝑛}$ .

Proof.routine

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 3.3.8 (Properties of the output), Corollary 3.4.4 (Consistency), Theorem 3.4.3 (Solving a system in reduced form), Definition 2.5.12 (Invertible)

Techniques. Reduce to RREF (Technique 3.3.22), Contrapositive (Technique 1.5.4)

Hint 1. By Corollary 3.4.4, consistency is decided by the entries

{(𝐺 𝐲)}_{𝑖}

with

𝑖 > 𝑘

. How many such

𝑖

are there when every row has a pivot?

Hint 2. For (II)

\Rightarrow

(I), prove the contrapositive. It suffices to find

𝐳

such that

𝐴_{𝑟} 𝐱 = 𝐳

has no solution, and then take

𝐲 = 𝐺^{- 1} 𝐳

Hint 3. If some row has no pivot, the last row of

𝐴_{𝑟}

is zero. Try

𝐳 = 𝐞_{𝑚}

Sketch. The pivots lie in rows

1, \dots, 𝑘

, so (I) says

𝑘 = 𝑚

. If

𝑘 = 𝑚

, the consistency conditions of Corollary 3.4.4 are vacuous; explicitly,

𝑥_{𝑝_{𝑖}} = {(𝐺 𝐲)}_{𝑖}

with all free variables

0

is a solution. If

𝑘 < 𝑚

, the last row of

𝐴_{𝑟}

is zero. With

𝐲 = 𝐺^{- 1} 𝐞_{𝑚}

, the system

𝐴 𝐱 = 𝐲

is equivalent to

𝐴_{𝑟} 𝐱 = 𝐞_{𝑚}

, whose last equation reads

0 = 1

Let $𝐺$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10), and let $𝑘$ be the number of pivots. By Proposition 3.3.8 the pivots lie in rows $1, \dots, 𝑘$ , one in each, so (I) says exactly that $𝑘 = 𝑚$ .

(I) $\Rightarrow$ (II). Suppose $𝑘 = 𝑚$ , and let $𝐲 \in 𝐹^{𝑚}$ . There is no index $𝑖$ with $𝑘 < 𝑖 \leq 𝑚$ , so the condition in Corollary 3.4.4 holds trivially, and $𝐴 𝐱 = 𝐲$ is consistent. Explicitly, by Theorem 3.4.3(b) and Proposition 3.4.1, the vector with $𝑥_{𝑝_{𝑖}} = {(𝐺 𝐲)}_{𝑖}$ for $𝑖 = 1, \dots, 𝑚$ and all free variables $0$ is a solution.

(II) $\Rightarrow$ (I). We prove the contrapositive. Suppose $𝑘 < 𝑚$ , so that row $𝑚$ of $𝐴_{𝑟}$ is zero (Proposition 3.3.8(a)). Let $𝐲 = 𝐺^{- 1} 𝐞_{𝑚}$ . Then $𝐺 𝐲 = 𝐞_{𝑚}$ has $𝑚$ th entry $1 \neq 0$ , and $𝑚 > 𝑘$ , so $𝐴 𝐱 = 𝐲$ is inconsistent by Corollary 3.4.4. (Directly: $𝐴 𝐱 = 𝐲$ if and only if $𝐴_{𝑟} 𝐱 = 𝐞_{𝑚}$ , and the $𝑚$ th entry of $𝐴_{𝑟} 𝐱$ is $0$ for every $𝐱$ .) So (II) fails. □

Remark 3.4.17 (Why $𝐺^{- 1}$ ). It is tempting to take $𝐲 = 𝐞_{𝑚}$ itself in the last proof, but row operations move the image of $𝑇_{𝐴}$ (Non-example 3.2.19), and $𝐴 𝐱 = 𝐞_{𝑚}$ may well be consistent. For instance,

𝐴 = (\begin{matrix} 0 \\ 1 \end{matrix}), 𝐴_{𝑟} = (\begin{matrix} 1 \\ 0 \end{matrix}) = 𝐸_{12} 𝐴,

and $𝐴 𝐱 = 𝐞_{2}$ has the solution $𝑥 = 1$ . With $𝐺 = 𝐸_{12}$ , the bad right-hand side is $𝐺^{- 1} 𝐞_{2} = 𝐞_{1}$ : the equation $𝐴 𝐱 = 𝐞_{1}$ says $0 = 1$ .

By Proposition 3.1.8(a), (II) says that $𝑇_{𝐴}$ is surjective, equivalently that the columns of $𝐴$ span $𝐹^{𝑚}$ , so a pivot in every row is a mechanical test for the conditions of Theorem 2.7.4. For a $2 \times 2$ matrix both failures can be watched at once. The component below starts with

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

The columns $𝐚_{1} = (1, - 1)$ and $𝐚_{2} = (- 2, 2) = - 2 𝐚_{1}$ lie on one line, and $𝐴_{𝑟}$ has one pivot: its second column is free and its second row is zero. For $𝐲 = (1, 1)$ , off the line $span (𝐚_{1})$ , the two lines of the row picture are parallel and there is no solution. Drag $𝐲$ onto the line spanned by the columns and the two lines of the row picture coincide: now there are infinitely many solutions, one for each value of the free variable $𝑥_{2}$ . Drag $𝐚_{2}$ off that line and both defects disappear at once, as they must for a square matrix (Corollary 3.4.20).

The system

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

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

. Left: the row picture, with one line per equation. Right: the column picture, where

𝐲

must be reached as

𝑥_{1} 𝐚_{1} + 𝑥_{2} 𝐚_{2}

. Drag

𝐚_{1}

𝐚_{2}

𝐲

, or type new entries.

Exercise 3.4.18.routine Each matrix below is $𝐴_{𝑟}$ for some $𝐴$ . For each one, decide whether $𝐴 𝐱 = 𝟎$ has only the trivial solution, and whether $𝐴 𝐱 = 𝐲$ is consistent for every $𝐲$ .

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

Solution.

Uses. Proposition 3.4.15 (A pivot in every column), Proposition 3.4.16 (A pivot in every row)

Hint 1. Locate the pivots. Is there a column without one? A row without one?

Hint 2. A column without a pivot is a free variable, which gives a nontrivial solution of

𝐴 𝐱 = 𝟎

. A row without a pivot is a zero row, which makes some

𝐴 𝐱 = 𝐲

inconsistent.

Sketch.

𝑅_{1}

: a pivot in every row but not in column

3

, so always consistent, with nontrivial homogeneous solutions.

𝑅_{2}

: a pivot in every column but not in row

3

, so only the trivial solution, but not always consistent.

𝑅_{3}

: neither.

𝑅_{4}

: both.

By Proposition 3.4.15, $𝐴 𝐱 = 𝟎$ has only the trivial solution exactly when every column of $𝐴_{𝑟}$ has a pivot, and by Proposition 3.4.16, $𝐴 𝐱 = 𝐲$ is consistent for every $𝐲$ exactly when every row has a pivot.

$𝑅_{1}$ has pivots in columns $1, 2$ and in both rows. Column $3$ is free, so $𝐴 𝐱 = 𝟎$ has a nontrivial solution (for instance the basic solution $(- 3, 1, 1)$ ), and $𝐴 𝐱 = 𝐲$ is consistent for every $𝐲$ .
$𝑅_{2}$ has pivots in both columns but not in row $3$ . So $𝐴 𝐱 = 𝟎$ has only the trivial solution, but $𝐴 𝐱 = 𝐲$ is inconsistent for some $𝐲$ .
$𝑅_{3}$ has pivots in columns $1, 3$ and rows $1, 2$ . Column $2$ and row $3$ have none, so both properties fail.
$𝑅_{4} = 𝐼_{3}$ has a pivot in every row and every column, so both properties hold.

Since there are at most $min (𝑚, 𝑛)$ pivots, the shape of $𝐴$ alone can rule out one of the two properties.

Corollary 3.4.19 (More unknowns than equations). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)If $𝑛 > 𝑚$ , then $𝐴 𝐱 = 𝟎$ has a nontrivial solution.
(b)If $𝑚 > 𝑛$ , then $𝐴 𝐱 = 𝐲$ is inconsistent for some $𝐲 \in 𝐹^{𝑚}$ .

Proof.routine

Uses. Proposition 3.3.8 (Properties of the output), Proposition 3.4.15 (A pivot in every column), Proposition 3.4.16 (A pivot in every row)

Hint 1. How many pivots can

𝐴_{𝑟}

have?

Hint 2. If

𝑛 > 𝑚

, there are more columns than pivots.

Sketch. There are

𝑘 \leq min (𝑚, 𝑛)

pivots. If

𝑛 > 𝑚

, then

𝑘 \leq 𝑚 < 𝑛

, so some column has no pivot, and Proposition 3.4.15 applies. If

𝑚 > 𝑛

, then

𝑘 \leq 𝑛 < 𝑚

, so some row has no pivot, and Proposition 3.4.16 applies.

By Proposition 3.3.8,

𝐴_{𝑟}

has

𝑘 \leq min (𝑚, 𝑛)

pivots, in distinct rows and distinct columns. If

𝑛 > 𝑚

, then

𝑘 \leq 𝑚 < 𝑛

, so at least one of the

𝑛

columns has no pivot, and

𝐴 𝐱 = 𝟎

has a nontrivial solution by Proposition 3.4.15. If

𝑚 > 𝑛

, then

𝑘 \leq 𝑛 < 𝑚

, so at least one of the

𝑚

rows has no pivot, and some

𝐴 𝐱 = 𝐲

is inconsistent by Proposition 3.4.16. □

Part (a) has a geometric reading over $ℝ$ : two planes through the origin in $ℝ^{3}$ always share a line, since two homogeneous equations in three unknowns have a nontrivial solution. In terms of the Fundamental Theorems, (a) and (b) say that $𝑇_{𝐴}$ can be injective only if $𝑛 \leq 𝑚$ , and surjective only if $𝑚 \leq 𝑛$ . Section 3.5 draws the consequences, among them that every invertible matrix is square.

For square matrices the two properties cannot be separated.

Corollary 3.4.20 (Square systems). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

. The following are equivalent.

(i) $𝐴_{𝑟}$ has a pivot in every column.
(ii) $𝐴_{𝑟}$ has a pivot in every row.
(iii) $𝐴_{𝑟} = 𝐼_{𝑛}$ .
(iv) $𝐴 𝐱 = 𝟎$ has only the trivial solution.
(v) $𝐴 𝐱 = 𝐲$ has a solution for every $𝐲 \in 𝐹^{𝑛}$ .
(vi) $𝐴 𝐱 = 𝐲$ has exactly one solution for every $𝐲 \in 𝐹^{𝑛}$ .
(vii) $𝐴$ is invertible.

Proof.standard

Uses. Proposition 3.3.8 (Properties of the output), Proposition 3.4.15 (A pivot in every column), Proposition 3.4.16 (A pivot in every row), Corollary 3.1.22 (Uniqueness depends only on $𝐴$ ), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Theorem 3.3.23 (Invertibility and RREF)

Techniques. Proving TFAE (Technique 2.7.1), Reduce to RREF (Technique 3.3.22)

Hint 1. Each pivot occupies its own row and its own column. What do (i) and (ii) say about the number

𝑘

of pivots of a square matrix?

Hint 2. (i)

\Leftrightarrow

(iv) and (ii)

\Leftrightarrow

(v) are the two propositions. For (vi), combine existence with Corollary 3.1.22.

Hint 3. (iii)

\Leftrightarrow

(vii) is Theorem 3.3.23.

Sketch. With

𝑘

pivots in distinct rows and columns, (i) and (ii) both say

𝑘 = 𝑛

; and

𝑘 = 𝑛

forces

𝑝_{𝑠} = 𝑠

and

𝐴_{𝑟} = 𝐼_{𝑛}

, while

𝐼_{𝑛}

has

𝑛

pivots. The propositions give (i)

\Leftrightarrow

(iv) and (ii)

\Leftrightarrow

(v). (vi) implies (iv) (take

𝐲 = 𝟎

) and (v); conversely (iv) and (v) together give (vi) by Corollary 3.1.22. Finally (iii)

\Leftrightarrow

(vii) is Theorem 3.3.23.

Let $𝑘$ be the number of pivots of $𝐴$ . By Proposition 3.3.8 they lie in rows $1, \dots, 𝑘$ and in $𝑘$ distinct columns $𝑝_{1} < \dots < 𝑝_{𝑘}$ . So (i) says $𝑘 = 𝑛$ , and since $𝐴$ has $𝑛$ rows, (ii) also says $𝑘 = 𝑛$ . Hence (i) $\Leftrightarrow$ (ii).

(i) $\Leftrightarrow$ (iii). If $𝑘 = 𝑛$ , then $𝑝_{𝑠} = 𝑠$ for every $𝑠$ (as in the first proof of Proposition 3.4.15), and column $𝑠$ of $𝐴_{𝑟}$ is $𝐞_{𝑠}$ by Proposition 3.3.8(c), so $𝐴_{𝑟} = 𝐼_{𝑛}$ . Conversely, the pivots of $𝐼_{𝑛}$ are its diagonal entries (Example 3.3.13), one in each column.

(i) $\Leftrightarrow$ (iv) and (ii) $\Leftrightarrow$ (v) are Proposition 3.4.15 and Proposition 3.4.16.

(iv), (v) $\Leftrightarrow$ (vi). If (vi) holds, then (v) holds, and the unique solution of $𝐴 𝐱 = 𝟎$ is the trivial one, which is (iv). Conversely, suppose (iv) and (v) hold. By (iv) and Proposition 3.1.8(b), $ker 𝑇_{𝐴} = {𝟎}$ . Let $𝐲 \in 𝐹^{𝑛}$ . By (v), $𝐴 𝐱 = 𝐲$ is consistent, and by Corollary 3.1.22(a) it has exactly one solution. Since (iv) $\Leftrightarrow$ (i) $\Leftrightarrow$ (ii) $\Leftrightarrow$ (v), each of (iv) and (v) implies the other, so each is equivalent to (vi).

(iii) $\Leftrightarrow$ (vii) is Theorem 3.3.23. □

The equivalence of (iv) and (v) is the remarkable one. For a square system, knowing that the homogeneous system has only the trivial solution, a statement about uniqueness, gives a solution of $𝐴 𝐱 = 𝐲$ for every $𝐲$ , a statement about existence, and conversely. For non-square matrices both implications fail: $𝐴 = (\begin{matrix} 1 & 0 \end{matrix})$ has a pivot in every row but not in every column, and the $2 \times 1$ matrix with column $(1, 0)$ the reverse. The corollary also completes Exercise 3.1.47. That exercise showed that the equilibrium temperatures of a plate are unique, and its system has as many equations as unknowns, so they also exist, for every choice of boundary temperatures.

This is a proof strategy in its own right.

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

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

Used in 12 places

Theorem 3.4.24, Exercise 3.4.42, Exercise 3.5.39, Exercise 3.6.13, Exercise 3.6.14, Problem 3.13, Problem 3.15, Problem 3.16, Problem 3.19, Exercise 4.2.47, Theorem 7.1.14, Exercise 7.1.57.

3.4.5Polynomial interpolation

Two points in the plane with different first coordinates lie on exactly one line, the graph of a polynomial of degree at most $1$ . Three points with distinct first coordinates lie on exactly one graph of a polynomial of degree at most $2$ , as Exercise 3.1.37 found in one example. In general, through $𝑛 + 1$ points with distinct first coordinates there passes exactly one graph of a polynomial of degree at most $𝑛$ , and this holds over every field. The proof is an application of everything in this section.

Throughout, $𝑐_{0}, 𝑐_{1}, \dots, 𝑐_{𝑛} \in 𝐹$ are distinct (the nodes) and $𝑑_{0}, 𝑑_{1}, \dots, 𝑑_{𝑛} \in 𝐹$ are arbitrary (the values). We look for $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ with

𝑝 (𝑐_{0}) = 𝑑_{0}, 𝑝 (𝑐_{1}) = 𝑑_{1}, \dots, 𝑝 (𝑐_{𝑛}) = 𝑑_{𝑛} .

(3.4.3)

By Technique 3.1.9, write $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ with unknown coefficients. By Definition 1.2.17, the condition $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ reads

𝑎_{0} + 𝑎_{1} 𝑐_{𝑖} + 𝑎_{2} 𝑐_{𝑖}^{2} + \dots + 𝑎_{𝑛} 𝑐_{𝑖}^{𝑛} = 𝑑_{𝑖},

a linear equation in $𝑎_{0}, \dots, 𝑎_{𝑛}$ . So (3.4.3) is a linear system of $𝑛 + 1$ equations in $𝑛 + 1$ unknowns, with the following coefficient matrix.

Definition 3.4.22 (Vandermonde matrix). For $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ , the Vandermonde matrix $𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) \in$ $𝐹^{(𝑛 + 1) \times (𝑛 + 1)}$ is the matrix whose row $𝑖 + 1$ is $(1, 𝑐_{𝑖}, 𝑐_{𝑖}^{2}, \dots, 𝑐_{𝑖}^{𝑛})$ , for $𝑖 = 0, \dots, 𝑛$ :

𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) = (\begin{matrix} 1 & 𝑐_{0} & 𝑐_{0}^{2} & \dots & 𝑐_{0}^{𝑛} \\ 1 & 𝑐_{1} & 𝑐_{1}^{2} & \dots & 𝑐_{1}^{𝑛} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 𝑐_{𝑛} & 𝑐_{𝑛}^{2} & \dots & 𝑐_{𝑛}^{𝑛} \end{matrix}) .

With $𝐚 = (𝑎_{0}, \dots, 𝑎_{𝑛})$ and $𝐝 = (𝑑_{0}, \dots, 𝑑_{𝑛})$ in $𝐹^{𝑛 + 1}$ , the conditions (3.4.3) say exactly that $𝑉 𝐚 = 𝐝$ , where $𝑉 = 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})$ . The system is square, so by Technique 3.4.21 it is enough to show that $𝑉 𝐚 = 𝟎$ forces $𝐚 = 𝟎$ , that is, that a polynomial of degree at most $𝑛$ that vanishes at $𝑛 + 1$ distinct points is the zero polynomial.

Intuition (Splitting off a root). The familiar reason is that each root $𝑐$ of $𝑝$ contributes a factor $𝑥 - 𝑐$ , and a polynomial of degree at most $𝑛$ has room for at most $𝑛$ such factors. We cannot multiply polynomials until Section 7.1, but we can split off the factor by hand, because of an identity in the field:

𝑡^{𝑗} - 𝑐^{𝑗} = (𝑡 - 𝑐) (𝑡^{𝑗 - 1} + 𝑡^{𝑗 - 2} 𝑐 + \dots + 𝑐^{𝑗 - 1}) .

Summing these over the terms of $𝑝$ shows that $𝑝 (𝑡) - 𝑝 (𝑐)$ equals $𝑡 - 𝑐$ times the value at $𝑡$ of an explicit polynomial $𝑞$ of degree at most $𝑛 - 1$ . If $𝑝$ vanishes at $𝑐_{0}, \dots, 𝑐_{𝑛}$ , then $𝑞$ vanishes at $𝑐_{1}, \dots, 𝑐_{𝑛}$ , and induction on $𝑛$ takes over.

Lemma 3.4.23 (Too many roots). Let

𝑛 \geq 0

and

𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}

. If

𝑝 (𝑐_{0}) =

𝑝 (𝑐_{1}) =

\dots =

𝑝 (𝑐_{𝑛}) =

0

for distinct

𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹

, then

𝑝 = 𝟎

Proof.standard

Uses. Definition 1.2.16 (Degree), Definition 1.2.17 (Evaluation), Proposition 1.1.17 (No zero divisors), induction on $𝑛$

Hint 1. Induct on

𝑛

. For the inductive step, look for a polynomial

𝑞

of degree at most

𝑛 - 1

with

𝑝 (𝑡) -

𝑝 (𝑐_{0}) =

(𝑡 - 𝑐_{0}) 𝑞 (𝑡)

for every

𝑡 \in 𝐹

Hint 2. Use the telescoping identity for

𝑡^{𝑗} - 𝑐^{𝑗}

from the intuition above, and collect the coefficient of

𝑡^{𝑖}

. It is

𝑏_{𝑖} =

\sum_{𝑗 > 𝑖} 𝑎_{𝑗} 𝑐^{𝑗 - 1 - 𝑖}

Hint 3.

𝑞

vanishes at

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

, so

𝑞 = 𝟎

by induction. Recover

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

from

𝑏_{𝑛 - 1} = 𝑎_{𝑛}

and

𝑏_{𝑖} =

𝑎_{𝑖 + 1} +

𝑐_{0} 𝑏_{𝑖 + 1}

Sketch. Write

𝑝 = \sum_{𝑗} 𝑎_{𝑗} 𝑥^{𝑗}

and

𝑐 = 𝑐_{0}

. Telescoping gives

𝑝 (𝑡) -

𝑝 (𝑐) =

(𝑡 - 𝑐) 𝑞 (𝑡)

for all

𝑡

, where

𝑞 =

\sum_{𝑖 < 𝑛} 𝑏_{𝑖} 𝑥^{𝑖}

and

𝑏_{𝑖} =

\sum_{𝑗 > 𝑖} 𝑎_{𝑗} 𝑐^{𝑗 - 1 - 𝑖}

. For

𝑖 \geq 1

0 =

(𝑐_{𝑖} - 𝑐) 𝑞 (𝑐_{𝑖})

with

𝑐_{𝑖} - 𝑐 \neq 0

, so

𝑞

vanishes at the

𝑛

distinct points

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

, and

𝑞 = 𝟎

by induction. Since

𝑏_{𝑛 - 1} = 𝑎_{𝑛}

and

𝑏_{𝑖} =

𝑎_{𝑖 + 1} +

𝑐 𝑏_{𝑖 + 1}

, all of

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

vanish, and then

𝑎_{0} = 𝑝 (𝑐_{0}) = 0

We induct on $𝑛$ . If $𝑛 = 0$ , then $𝑝 = 𝑎_{0}$ is constant, and $𝑎_{0} = 𝑝 (𝑐_{0}) = 0$ .

Let $𝑛 \geq 1$ , and assume the lemma for $𝑛 - 1$ . Write $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ , and put $𝑐 = 𝑐_{0}$ . For $𝑗 \geq 1$ and $𝑡 \in 𝐹$ , the following sum telescopes:

(𝑡 - 𝑐) \sum_{𝑖 = 0}^{𝑗 - 1} 𝑡^{𝑖} 𝑐^{𝑗 - 1 - 𝑖} = \sum_{𝑖 = 0}^{𝑗 - 1} 𝑡^{𝑖 + 1} 𝑐^{𝑗 - 1 - 𝑖} - \sum_{𝑖 = 0}^{𝑗 - 1} 𝑡^{𝑖} 𝑐^{𝑗 - 𝑖} = 𝑡^{𝑗} - 𝑐^{𝑗} .

Multiplying by $𝑎_{𝑗}$ , summing over $𝑗 = 1, \dots, 𝑛$ , and collecting the terms with the same power $𝑡^{𝑖}$ (for a fixed $𝑖$ , the index $𝑗$ runs over $𝑖 + 1, \dots, 𝑛$ ), we get

𝑝 (𝑡) - 𝑝 (𝑐) = \sum_{𝑗 = 1}^{𝑛} 𝑎_{𝑗} (𝑡^{𝑗} - 𝑐^{𝑗}) = (𝑡 - 𝑐) \sum_{𝑖 = 0}^{𝑛 - 1} 𝑏_{𝑖} 𝑡^{𝑖}, where 𝑏_{𝑖} = \sum_{𝑗 = 𝑖 + 1}^{𝑛} 𝑎_{𝑗} 𝑐^{𝑗 - 1 - 𝑖} .

Let

𝑞 = 𝑏_{0} + 𝑏_{1} 𝑥 + \dots + 𝑏_{𝑛 - 1} 𝑥^{𝑛 - 1} \in {𝐹 [𝑥]}_{\leq 𝑛 - 1} .

We have shown that

𝑝 (𝑡) - 𝑝 (𝑐_{0}) = (𝑡 - 𝑐_{0}) 𝑞 (𝑡) for every 𝑡 \in 𝐹 .

(3.4.4)

For $𝑖 = 1, \dots, 𝑛$ , since $𝑝 (𝑐_{𝑖}) =$ $𝑝 (𝑐_{0}) =$ $0$ , (3.4.4) gives $(𝑐_{𝑖} - 𝑐_{0}) 𝑞 (𝑐_{𝑖}) =$ $0$ . Here $𝑐_{𝑖} - 𝑐_{0} \neq 0$ because the nodes are distinct, so $𝑞 (𝑐_{𝑖}) = 0$ by Proposition 1.1.17. Thus $𝑞$ has degree at most $𝑛 - 1$ and vanishes at the $𝑛$ distinct points $𝑐_{1}, \dots, 𝑐_{𝑛}$ , and by the induction hypothesis $𝑞 = 𝟎$ , that is, $𝑏_{0} =$ $𝑏_{1} =$ $\dots =$ $𝑏_{𝑛 - 1} =$ $0$ .

Now $𝑏_{𝑛 - 1} = 𝑎_{𝑛}$ , and for $0 \leq 𝑖 \leq 𝑛 - 2$ , splitting off the term $𝑗 = 𝑖 + 1$ ,

𝑏_{𝑖} = 𝑎_{𝑖 + 1} + 𝑐 \sum_{𝑗 = 𝑖 + 2}^{𝑛} 𝑎_{𝑗} 𝑐^{𝑗 - 2 - 𝑖} = 𝑎_{𝑖 + 1} + 𝑐 𝑏_{𝑖 + 1} .

Hence $𝑎_{𝑛} = 𝑏_{𝑛 - 1} = 0$ , and $𝑎_{𝑖 + 1} =$ $𝑏_{𝑖} -$ $𝑐 𝑏_{𝑖 + 1} =$ $0$ for $𝑖 = 𝑛 - 2, \dots, 0$ . So $𝑎_{1} = \dots = 𝑎_{𝑛} = 0$ , and finally $𝑎_{0} = 𝑝 (𝑐_{0}) = 0$ . Thus $𝑝 = 𝟎$ . □

The recursion $𝑏_{𝑖} =$ $𝑎_{𝑖 + 1} +$ $𝑐 𝑏_{𝑖 + 1}$ , started from $𝑏_{𝑛 - 1} = 𝑎_{𝑛}$ , is Horner’s scheme (or synthetic division) for dividing $𝑝$ by $𝑥 - 𝑐$ . Once polynomials can be multiplied, (3.4.4) becomes the factorization $𝑝 -$ $𝑝 (𝑐) =$ $(𝑥 - 𝑐) 𝑞$ , and the same induction shows that a nonzero polynomial has at most $deg 𝑝$ roots (Proposition 7.1.22).

Theorem 3.4.24 (Polynomial interpolation). Let

𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹

be distinct, and let

𝑑_{0}, \dots, 𝑑_{𝑛} \in 𝐹

. There is exactly one polynomial

𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}

with

𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}

for

𝑖 = 0, 1, \dots, 𝑛

. In particular, the Vandermonde matrix

𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})

is invertible.

Proof.standard

Uses. Definition 3.4.22 (Vandermonde matrix), Definition 1.2.17 (Evaluation), Definition 1.2.16 (Degree), Definition 2.3.8 (Matrix–vector product), Lemma 3.4.23 (Too many roots), Corollary 3.4.20 (Square systems)

Techniques. Undetermined coefficients (Technique 3.1.9), Uniqueness gives existence (Technique 3.4.21)

Hint 1. Write

𝑝 =

𝑎_{0} +

𝑎_{1} 𝑥 +

\dots +

𝑎_{𝑛} 𝑥^{𝑛}

, and translate the conditions

𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}

into a linear system for the

𝑎_{𝑗}

. What is its coefficient matrix?

Hint 2. The system is square. By Corollary 3.4.20 it is enough to show that the homogeneous system has only the trivial solution.

Hint 3. A solution of the homogeneous system gives a polynomial of degree at most

𝑛

that vanishes at

𝑛 + 1

distinct points.

Sketch. For

𝐚 \in 𝐹^{𝑛 + 1}

let

𝑝_{𝐚} = \sum_{𝑗} 𝑎_{𝑗} 𝑥^{𝑗}

. The entry of

𝑉 𝐚

in the row of

𝑐_{𝑖}

𝑝_{𝐚} (𝑐_{𝑖})

, so the interpolating polynomials correspond to the solutions of

𝑉 𝐚 = 𝐝

. If

𝑉 𝐚 = 𝟎

, then

𝑝_{𝐚}

vanishes at

𝑐_{0}, \dots, 𝑐_{𝑛}

, so

𝑝_{𝐚} = 𝟎

by Lemma 3.4.23 and

𝐚 = 𝟎

. Since

𝑉

is square, Corollary 3.4.20 gives exactly one solution of

𝑉 𝐚 = 𝐝

for each

𝐝

, and invertibility of

𝑉

Let $𝑉 = 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛})$ and $𝐝 = (𝑑_{0}, \dots, 𝑑_{𝑛})$ . For $𝐚 =$ $(𝑎_{0}, \dots, 𝑎_{𝑛}) \in$ $𝐹^{𝑛 + 1}$ , write $𝑝_{𝐚} =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ . By Definition 1.2.16, every $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ equals $𝑝_{𝐚}$ for exactly one $𝐚$ , namely its list of coefficients $𝑎_{0}, \dots, 𝑎_{𝑛}$ . By Definition 2.3.8 and Definition 1.2.17, the entry of $𝑉 𝐚$ in the row of $𝑐_{𝑖}$ is

𝑎_{0} + 𝑎_{1} 𝑐_{𝑖} + \dots + 𝑎_{𝑛} 𝑐_{𝑖}^{𝑛} = 𝑝_{𝐚} (𝑐_{𝑖}) .

So $𝑝_{𝐚}$ satisfies $𝑝_{𝐚} (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ if and only if $𝑉 𝐚 = 𝐝$ . Through $𝐚 \mapsto 𝑝_{𝐚}$ , the polynomials we want correspond exactly to the solutions of $𝑉 𝐚 = 𝐝$ .

Suppose $𝑉 𝐚 = 𝟎$ . Then $𝑝_{𝐚}$ has degree at most $𝑛$ and vanishes at the $𝑛 + 1$ distinct points $𝑐_{0}, \dots, 𝑐_{𝑛}$ , so $𝑝_{𝐚} = 𝟎$ by Lemma 3.4.23, that is, $𝐚 = 𝟎$ . So the homogeneous system $𝑉 𝐚 = 𝟎$ has only the trivial solution. Since $𝑉$ is square, Corollary 3.4.20 ((iv) $\Rightarrow$ (vi) and (vii)) shows that $𝑉 𝐚 = 𝐝$ has exactly one solution, and that $𝑉$ is invertible. Hence there is exactly one polynomial $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ with $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ . □

The proof never solved anything. Existence came from uniqueness: $𝑛 + 1$ conditions on $𝑛 + 1$ unknown coefficients form a square system, and the homogeneous version asks for a polynomial with too many roots. Both hypotheses are needed. If two nodes coincide, say $𝑐_{0} = 𝑐_{1}$ , then $𝑉$ has two equal rows, and for $𝑑_{0} \neq 𝑑_{1}$ there is no solution at all. And the degree bound $𝑛$ is exactly right. With degree at most $𝑛 - 1$ there are only $𝑛$ unknowns for $𝑛 + 1$ conditions, so by Corollary 3.4.19(b) some values cannot be interpolated. With degree at most $𝑛 + 1$ there are $𝑛 + 2$ unknowns, so by Corollary 3.4.19(a) the homogeneous system has a nontrivial solution and uniqueness fails (Figure 3.4.1; see also Exercise 3.4.39).

Example 3.4.25 (A cubic through four points). Find the polynomial $𝑝 \in {ℚ [𝑥]}_{\leq 3}$ with

𝑝 (- 1) = 2, 𝑝 (0) = 1, 𝑝 (1) = 0, 𝑝 (2) = 5 .

With $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2} +$ $𝑎_{3} 𝑥^{3}$ , the system $𝑉 𝐚 = 𝐝$ is

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

The second equation gives $𝑎_{0} = 1$ , and the others become $- 𝑎_{1} + 𝑎_{2} - 𝑎_{3} = 1$ , $𝑎_{1} + 𝑎_{2} + 𝑎_{3} = - 1$ , and $2 𝑎_{1} + 4 𝑎_{2} + 8 𝑎_{3} = 4$ . Adding the first two gives $𝑎_{2} = 0$ . Then $𝑎_{1} + 𝑎_{3} = - 1$ and $𝑎_{1} + 4 𝑎_{3} = 2$ , so $𝑎_{3} = 1$ and $𝑎_{1} = - 2$ . Hence

𝑝 = 1 - 2 𝑥 + 𝑥^{3} .

Check: $𝑝 (- 1) = 1 + 2 - 1 = 2$ , $𝑝 (0) = 1$ , $𝑝 (1) = 1 - 2 + 1 = 0$ , and $𝑝 (2) = 1 - 4 + 8 = 5$ .

(\begin{matrix} 1 & - 1 & 1 & - 1 & 2 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 2 & 4 & 8 & 5 \end{matrix}) ⇝ (\begin{matrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & - 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix})

The system

𝑉 𝐚 = 𝐝

of Example 3.4.25. The left block reduces to

𝐼_{4}

, and the last column becomes the coefficient vector

(1, - 2, 0, 1)

. Edit the last column to interpolate other values at the same nodes.

Figure 3.4.1. The cubic

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

of Example 3.4.25 (solid) is the only polynomial of degree at most

3

through the four points. The quartic

𝑞 =

1 -

𝑥 -

𝑥^{2} / 2 +

𝑥^{4} / 2

(dashed) passes through them too:

𝑞 -

𝑝 =

(𝑥^{4} - 2 𝑥^{3} - 𝑥^{2} + 2 𝑥) / 2

vanishes at

- 1, 0, 1, 2

. With degree at most

4

there are five unknown coefficients and only four conditions.

Lagrange’s formula

The theorem gives the interpolating polynomial for each list of values separately. Linearity lets us do all of them at once: it is enough to interpolate the simplest values, a single $1$ and zeros elsewhere.

Definition 3.4.26 (Lagrange polynomials). Let $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ be distinct. For $𝑖 = 0, \dots, 𝑛$ , the $𝑖$ th Lagrange polynomial $𝐿_{𝑖} \in {𝐹 [𝑥]}_{\leq 𝑛}$ is the unique polynomial of degree at most $𝑛$ with

𝐿_{𝑖} (𝑐_{𝑖}) = 1 and 𝐿_{𝑖} (𝑐_{𝑘}) = 0 for 𝑘 \neq 𝑖 .

It exists and is unique by Theorem 3.4.24.

Proposition 3.4.27 (Lagrange’s formula). Let $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ be distinct, and let $𝑑_{0}, \dots, 𝑑_{𝑛} \in 𝐹$ . The unique $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ with $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ is

𝑝 = 𝑑_{0} 𝐿_{0} + 𝑑_{1} 𝐿_{1} + \dots + 𝑑_{𝑛} 𝐿_{𝑛} .

Proof.routine

Uses. Definition 3.4.26 (Lagrange polynomials), Proposition 1.2.18 (Degree and evaluation versus the operations), Theorem 3.4.24 (Polynomial interpolation)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Evaluate the right side at

𝑐_{𝑘}

, using that evaluation is linear (Proposition 1.2.18(c)).

Hint 2. Conclude with the uniqueness in Theorem 3.4.24.

Sketch. The right side

𝑞

has degree at most

𝑛

, and

𝑞 (𝑐_{𝑘}) =

\sum_{𝑖} 𝑑_{𝑖} 𝐿_{𝑖} (𝑐_{𝑘}) =

𝑑_{𝑘}

by linearity of evaluation. By uniqueness in Theorem 3.4.24,

𝑞 = 𝑝

Let $𝑞 =$ $𝑑_{0} 𝐿_{0} +$ $\dots +$ $𝑑_{𝑛} 𝐿_{𝑛}$ . By Proposition 1.2.18(a) and (b), sums and nonzero scalar multiples of polynomials of degree at most $𝑛$ have degree at most $𝑛$ (and $0 𝐿_{𝑖} = 𝟎$ trivially does), so $𝑞 \in {𝐹 [𝑥]}_{\leq 𝑛}$ . By Proposition 1.2.18(c), for each $𝑘$ ,

𝑞 (𝑐_{𝑘}) = \sum_{𝑖 = 0}^{𝑛} 𝑑_{𝑖} 𝐿_{𝑖} (𝑐_{𝑘}) = 𝑑_{𝑘} \cdot 1 + \sum_{𝑖 \neq 𝑘} 𝑑_{𝑖} \cdot 0 = 𝑑_{𝑘} .

So $𝑞$ satisfies the same conditions as $𝑝$ , and $𝑞 = 𝑝$ by the uniqueness in Theorem 3.4.24. □

Example 3.4.28 (Lagrange polynomials for the nodes $- 1, 0, 1, 2$ ). For the nodes of Example 3.4.25, the Lagrange polynomials are

\begin{aligned} 𝐿_{0} & = - \frac{1}{3} 𝑥 + \frac{1}{2} 𝑥^{2} - \frac{1}{6} 𝑥^{3}, & 𝐿_{1} & = 1 - \frac{1}{2} 𝑥 - 𝑥^{2} + \frac{1}{2} 𝑥^{3}, \\ 𝐿_{2} & = 𝑥 + \frac{1}{2} 𝑥^{2} - \frac{1}{2} 𝑥^{3}, & 𝐿_{3} & = - \frac{1}{6} 𝑥 + \frac{1}{6} 𝑥^{3} . \end{aligned}

Each claim is checked by evaluating at the four nodes; for instance $𝐿_{3} (2) = - \frac{1}{3} + \frac{8}{6} = 1$ and $𝐿_{3} (- 1) = \frac{1}{6} - \frac{1}{6} = 0$ . By Proposition 3.4.27, the cubic of Example 3.4.25 is

2 𝐿_{0} + 𝐿_{1} + 0 𝐿_{2} + 5 𝐿_{3} = 1 + (- \frac{2}{3} - \frac{1}{2} - \frac{5}{6}) 𝑥 + (1 - 1) 𝑥^{2} + (- \frac{1}{3} + \frac{1}{2} + \frac{5}{6}) 𝑥^{3} = 1 - 2 𝑥 + 𝑥^{3},

as before. Once polynomials can be multiplied (Section 7.1), each $𝐿_{𝑖}$ has the closed form

𝐿_{𝑖} = \prod_{𝑗 \neq 𝑖} \frac{𝑥 - 𝑐_{𝑗}}{𝑐_{𝑖} - 𝑐_{𝑗}},

because the product has degree $𝑛$ and takes the right values, so it is $𝐿_{𝑖}$ by uniqueness. For instance

𝐿_{3} = \frac{(𝑥 + 1) 𝑥 (𝑥 - 1)}{3 \cdot 2 \cdot 1} = \frac{𝑥^{3} - 𝑥}{6} .

Section 7.1 revisits interpolation from this side.

The Lagrange polynomials also describe $𝑉^{- 1}$ . The coefficient vector $𝐥_{𝑖}$ of $𝐿_{𝑖}$ solves $𝑉 𝐚 = 𝐞_{𝑖 + 1}$ , since $𝐿_{𝑖}$ takes the value $1$ at $𝑐_{𝑖}$ and $0$ at the other nodes. So the columns of $𝑉^{- 1}$ are the coefficient vectors of $𝐿_{0}, \dots, 𝐿_{𝑛}$ , and Lagrange’s formula is the equation $𝑉^{- 1} 𝐝 =$ $𝑑_{0} 𝐥_{0} +$ $\dots +$ $𝑑_{𝑛} 𝐥_{𝑛}$ . For the nodes $- 1, 0, 1, 2$ , the first column of $𝑉^{- 1}$ is $(0, - 1 / 3, 1 / 2, - 1 / 6)$ , the coefficients of $𝐿_{0}$ .

Finally, $𝑉$ is a square matrix, so its invertibility can also be decided by a determinant. Section 5.5 computes

det 𝑉 (𝑐_{0}, \dots, 𝑐_{𝑛}) = \prod_{𝑖 < 𝑗} (𝑐_{𝑗} - 𝑐_{𝑖})

(Theorem 5.5.21), which is nonzero exactly when the nodes are distinct; by Theorem 5.4.7 this gives a second proof that $𝑉$ is invertible.

Exercise 3.4.29.routine

(a)Over $ℚ$ , find the Lagrange polynomials for the nodes $0, 1, 3$ , and use them to find the $𝑝 \in {ℚ [𝑥]}_{\leq 2}$ with $𝑝 (0) = 2$ , $𝑝 (1) = - 1$ , and $𝑝 (3) = 5$ .
(b)Find the $𝑝 \in 𝔽_{5} {[𝑥]}_{\leq 2}$ with the same three values, read in $𝔽_{5}$ .

Solution.

Uses. Definition 3.4.26 (Lagrange polynomials), Proposition 3.4.27 (Lagrange’s formula), Theorem 3.4.24 (Polynomial interpolation)

Hint 1. Each

𝐿_{𝑖}

is the solution of a

3 \times 3

system. Alternatively, guess

𝐿_{𝑖}

(for instance from the closed form previewed in Example 3.4.28) and check its values at the three nodes.

Hint 2. For (b), check whether the answer to (a) still makes sense with coefficients in

𝔽_{5}

, and quote uniqueness.

Sketch.

𝐿_{0} = 1 - \frac{4}{3} 𝑥 + \frac{1}{3} 𝑥^{2}

𝐿_{1} = \frac{3}{2} 𝑥 - \frac{1}{2} 𝑥^{2}

𝐿_{2} = - \frac{1}{6} 𝑥 + \frac{1}{6} 𝑥^{2}

, and

𝑝 =

2 𝐿_{0} -

𝐿_{1} +

5 𝐿_{2} =

2 -

5 𝑥 +

2 𝑥^{2}

. Over

𝔽_{5}

2 - 5 𝑥 + 2 𝑥^{2} = 2 + 2 𝑥^{2}

takes the values

2, 4 = - 1, 20 = 0 = 5

, so it is the answer by uniqueness.

(a) Expanding the closed form of Example 3.4.28 suggests the candidates

𝐿_{0} = 1 - \frac{4}{3} 𝑥 + \frac{1}{3} 𝑥^{2}, 𝐿_{1} = \frac{3}{2} 𝑥 - \frac{1}{2} 𝑥^{2}, 𝐿_{2} = - \frac{1}{6} 𝑥 + \frac{1}{6} 𝑥^{2} .

We check the values directly. $𝐿_{0} (0) = 1$ , $𝐿_{0} (1) = 1 - \frac{4}{3} + \frac{1}{3} = 0$ , $𝐿_{0} (3) = 1 - 4 + 3 = 0$ ; $𝐿_{1} (0) = 0$ , $𝐿_{1} (1) = \frac{3}{2} - \frac{1}{2} = 1$ , $𝐿_{1} (3) = \frac{9}{2} - \frac{9}{2} = 0$ ; $𝐿_{2} (0) = 0$ , $𝐿_{2} (1) = 0$ , $𝐿_{2} (3) = - \frac{1}{2} + \frac{3}{2} = 1$ . Each has degree at most $2$ , so by the uniqueness in Theorem 3.4.24 these are the Lagrange polynomials. By Proposition 3.4.27,

𝑝 = 2 𝐿_{0} - 𝐿_{1} + 5 𝐿_{2} = 2 + (- \frac{8}{3} - \frac{3}{2} - \frac{5}{6}) 𝑥 + (\frac{2}{3} + \frac{1}{2} + \frac{5}{6}) 𝑥^{2} = 2 - 5 𝑥 + 2 𝑥^{2} .

Check: $𝑝 (0) = 2$ , $𝑝 (1) = 2 - 5 + 2 = - 1$ , $𝑝 (3) = 2 - 15 + 18 = 5$ .

(b) In $𝔽_{5}$ the nodes $0, 1, 3$ are still distinct, so there is exactly one such $𝑝$ by Theorem 3.4.24. The polynomial $2 - 5 𝑥 + 2 𝑥^{2} = 2 + 2 𝑥^{2}$ has coefficients in $𝔽_{5}$ , and its values are $2$ , $4 = - 1$ , and $2 + 18 = 20 = 0 = 5$ in $𝔽_{5}$ . So $𝑝 = 2 + 2 𝑥^{2}$ . (Reducing the answer over $ℚ$ worked because the computation only divided by $2$ , $3$ , and $6$ , which are invertible in $𝔽_{5}$ .)

Exercises

Exercise 3.4.30.routine Let

𝐴 = (\begin{matrix} 1 & 2 & 0 & 1 & 3 \\ 2 & 4 & 1 & 4 & 7 \\ - 1 & - 2 & 1 & 1 & - 2 \end{matrix}) \in ℚ^{3 \times 5} .

(a) Find all $𝐲 \in ℚ^{3}$ for which $𝐴 𝐱 = 𝐲$ is consistent.

(b) For $𝐲 = (1, 3, 0)$ , write the solution set in the form $𝐱_{0} +$ $span (𝐬_{1}, \dots, 𝐬_{ℓ})$ of Theorem 3.4.9.

Solution.

Uses. Algorithm 3.4.13 (Solving a linear system), Corollary 3.4.4 (Consistency), Theorem 3.4.9 (All solutions)

Hint 1. Row reduce

(𝐴 | 𝐲)

with symbolic

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

. No swaps or scalings are needed.

Hint 2. The pivot columns are

1

and

3

. The basic solutions come from columns

2

4

5

𝐴_{𝑟}

Sketch. The reduction gives rows

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

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

(𝟎 | 3 𝑦_{1} - 𝑦_{2} + 𝑦_{3})

. (a) Consistent iff

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

. (b)

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

𝐬_{1} = (- 2, 1, 0, 0, 0)

𝐬_{2} = (- 1, 0, - 2, 1, 0)

𝐬_{3} = (- 3, 0, - 1, 0, 1)

(a) Add $- 2$ times row $1$ to row $2$ and row $1$ to row $3$ . Then column $2$ vanishes below row $1$ , so the next pivot is in position $(2, 3)$ ; add $- 1$ times row $2$ to row $3$ . Row $1$ already has a $0$ in column $3$ . The result is

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

So $𝑘 = 2$ , and by Corollary 3.4.4 the system is consistent if and only if $3 𝑦_{1} - 𝑦_{2} + 𝑦_{3} = 0$ , that is, $𝑦_{2} = 3 𝑦_{1} + 𝑦_{3}$ .

(b) For $𝐲 = (1, 3, 0)$ the last entry is $3 - 3 + 0 = 0$ , and the last column becomes $(1, 1, 0)$ . The pivot columns are $1, 3$ and the free columns $2, 4, 5$ . Following Algorithm 3.4.13: $𝐱_{0}$ has $1, 1$ in positions $1, 3$ , and the basic solutions come from columns $2$ , $4$ , $5$ of $𝐴_{𝑟}$ , which are $(2, 0, 0)$ , $(1, 2, 0)$ , $(3, 1, 0)$ . So

𝐱_{0} = (\begin{matrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}), 𝐬_{1} = (\begin{matrix} - 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}), 𝐬_{2} = (\begin{matrix} - 1 \\ 0 \\ - 2 \\ 1 \\ 0 \end{matrix}), 𝐬_{3} = (\begin{matrix} - 3 \\ 0 \\ - 1 \\ 0 \\ 1 \end{matrix}),

and the solution set is $𝐱_{0} +$ $span (𝐬_{1}, 𝐬_{2}, 𝐬_{3})$ . As a check,

\begin{aligned} 𝐴 𝐱_{0} & = 𝐚_{1} + 𝐚_{3} = (1, 2, - 1) + (0, 1, 1) = (1, 3, 0), \\ 𝐴 𝐬_{3} & = - 3 𝐚_{1} - 𝐚_{3} + 𝐚_{5} = (- 3, - 6, 3) - (0, 1, 1) + (3, 7, - 2) = 𝟎 . \end{aligned}

Exercise 3.4.31.routine Let $𝐴$ be the matrix of Exercise 3.3.40,

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

Solve $𝐴 𝐱 = (1, 0, 1)$ over $ℚ$ and over $𝔽_{2}$ . Over $𝔽_{2}$ , list all solutions, and compare their number with Corollary 3.4.14.

Solution.

Uses. Algorithm 3.4.13 (Solving a linear system), Theorem 3.4.9 (All solutions), Corollary 3.4.14 (Counting solutions)

Hint 1. Reduce

(𝐴 | 𝐲)

; the first two passes are the same over both fields. Over

𝔽_{2}

, remember that

- 1 = 1

and

2 = 0

Hint 2. Over

ℚ

there are three pivots and one free variable; over

𝔽_{2}

there are two of each.

Sketch. Over

ℚ

(𝐴 | 𝐲)

reduces to rows

(1, 0, 0, 0 | 1)

(0, 1, 0, 1 | 0)

(0, 0, 1, 0 | 0)

, so the solutions are

(1, 0, 0, 0) +

𝑡 (0, - 1, 0, 1)

. Over

𝔽_{2}

it reduces to

(1, 0, 1, 0 | 1)

(0, 1, 1, 1 | 0)

(𝟎 | 0)

, and there are

2^{2} = 4

solutions:

(1, 0, 0, 0)

(0, 1, 1, 0)

(1, 1, 0, 1)

(0, 0, 1, 1)

Pass $1$ adds $- 1$ times row $1$ to row $3$ , and pass $2$ adds $- 1$ times row $2$ to row $1$ and row $2$ to row $3$ :

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

Over $ℚ$ . Pass $3$ scales row $3$ by $1 / 2$ , then adds row $3$ to row $1$ and $- 1$ times row $3$ to row $2$ , giving

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

The pivot columns are $1, 2, 3$ and $𝑥_{4}$ is free. So $𝐱_{0} = (1, 0, 0, 0)$ , $𝐬_{1} = (0, - 1, 0, 1)$ , and the solutions are $(1, - 𝑡, 0, 𝑡)$ for $𝑡 \in ℚ$ : infinitely many.

Over $𝔽_{2}$ . Here $- 1 = 1$ and $2 = 0$ , so the last matrix above is

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

which is in RREF. The last entry of the right side is $0$ , so the system is consistent. The pivot variables are $𝑥_{1}, 𝑥_{2}$ and the free variables $𝑥_{3}, 𝑥_{4}$ , with $𝑥_{1} = 1 + 𝑥_{3}$ and $𝑥_{2} = 𝑥_{3} + 𝑥_{4}$ (again since $- 1 = 1$ ). The four choices of $(𝑥_{3}, 𝑥_{4})$ give the solutions

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

That is $2^{2}$ solutions, as Corollary 3.4.14(b) predicts with $𝑞 = 2$ and $ℓ = 2$ .

Exercise 3.4.32.routine Over $ℂ$ , consider

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

(a) Find all solutions in $ℂ^{3}$ .

(b) For which $𝐲 \in ℂ^{3}$ is the system with these left sides and right side $𝐲$ consistent?

Solution.

Uses. Algorithm 3.4.13 (Solving a linear system), Corollary 3.4.4 (Consistency), Theorem 3.4.9 (All solutions)

Hint 1. Pass

1

adds

- 𝑖

times row

1

to row

2

. Remember

𝑖^{2} = - 1

Hint 2. The coefficient matrix has pivot columns

1, 3

. For (c), when is

1 - 𝑖 𝑡

real for

𝑡 \in ℂ

with

𝑡

itself real?

Sketch. The reduction gives rows

(1, 𝑖, 0 | 𝑦_{1})

(0, 0, 1 | - 𝑖 𝑦_{1} + 𝑦_{2})

(0, 0, 0 | 𝑖 𝑦_{1} - 𝑦_{2} + 𝑦_{3})

. (a)

(1, 0, 2) +

𝑡 (- 𝑖, 1, 0)

𝑡 \in ℂ

. (b)

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

. (c) Only

(1, 0, 2)

Pass $1$ adds $- 𝑖$ times row $1$ to row $2$ : the new row $2$ is

(𝑖, - 1, 1) - 𝑖 (1, 𝑖, 0) = (0, - 1 - 𝑖^{2}, 1) = (0, 0, 1),

with right side $𝑦_{2} - 𝑖 𝑦_{1}$ . Then column $2$ vanishes below row $1$ , so pass $2$ uses the pivot in position $(2, 3)$ and adds $- 1$ times row $2$ to row $3$ :

(\begin{matrix} 1 & 𝑖 & 0 & 𝑦_{1} \\ 0 & 0 & 1 & - 𝑖 𝑦_{1} + 𝑦_{2} \\ 0 & 0 & 0 & 𝑖 𝑦_{1} - 𝑦_{2} + 𝑦_{3} \end{matrix}) .

(a) For $𝐲 = (1, 2 + 𝑖, 2)$ the right side is $(1, - 𝑖 + 2 + 𝑖, 𝑖 - 2 - 𝑖 + 2) =$ $(1, 2, 0)$ . The pivot variables are $𝑥_{1}, 𝑥_{3}$ and $𝑥_{2}$ is free, with $𝑥_{1} = 1 - 𝑖 𝑥_{2}$ and $𝑥_{3} = 2$ . So the solutions are

(1, 0, 2) + 𝑡 (- 𝑖, 1, 0), 𝑡 \in ℂ .

Check: the left sides at $(- 𝑖, 1, 0)$ are $- 𝑖 + 𝑖 = 0$ , $1 - 1 + 0 = 0$ , and $0$ .

(b) By Corollary 3.4.4, exactly when $𝑖 𝑦_{1} - 𝑦_{2} + 𝑦_{3} = 0$ .

(c) The solution with parameter $𝑡$ is $(1 - 𝑖 𝑡, 𝑡, 2)$ . If it is real, then $𝑡 = 𝑥_{2}$ is real, and then $1 - 𝑖 𝑡$ is real only if $𝑡 = 0$ . So $(1, 0, 2)$ is the only real solution. The complex solution set is a line in $ℂ^{3}$ , and it meets $ℝ^{3}$ in a single point.

Exercise 3.4.33.standard For $𝑎, 𝑏$ in a field $𝐹$ , consider the system

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

(a) For $𝐹 = ℝ$ , find all $(𝑎, 𝑏)$ for which the system has no solution, exactly one solution, and infinitely many solutions.

(b) Answer the same question for $𝐹 = 𝔽_{3}$ , and count the solutions in each case.

Solution.

Uses. Algorithm 3.4.13 (Solving a linear system), Corollary 3.4.4 (Consistency), Corollary 3.4.14 (Counting solutions)

Hint 1. Subtract row

1

from row

2

and

𝑎

times row

1

from row

3

. When can you use the

(2, 2)

entry

𝑎 - 1

as a pivot?

Hint 2. For

𝑎 \neq 1

, after clearing column

2

the last row is

(0, 0, (1 - 𝑎) (2 + 𝑎) | 𝑏 - 𝑎)

. Treat

𝑎 = 1

and

𝑎 = - 2

separately. In

𝔽_{3}

- 2 = 1

Sketch. For

𝑎 \neq 1

the reduction reaches rows

(1, 1, 𝑎 | 1)

(0, 1, - 1 | 0)

(0, 0, (1 - 𝑎) (2 + 𝑎) | 𝑏 - 𝑎)

. Over

ℝ

: one solution if

𝑎 \neq 1, - 2

; for

𝑎 = - 2

, none if

𝑏 \neq - 2

and infinitely many if

𝑏 = - 2

; for

𝑎 = 1

, none if

𝑏 \neq 1

and infinitely many if

𝑏 = 1

. Over

𝔽_{3}

𝑎 = - 2

𝑎 = 1

: for

𝑎 = 1

there are

9

solutions if

𝑏 = 1

and none otherwise; for

𝑎 = 0, 2

exactly one.

Adding $- 1$ times row $1$ to row $2$ and $- 𝑎$ times row $1$ to row $3$ gives

(\begin{matrix} 1 & 1 & 𝑎 & 1 \\ 0 & 𝑎 - 1 & 1 - 𝑎 & 0 \\ 0 & 1 - 𝑎 & 1 - 𝑎^{2} & 𝑏 - 𝑎 \end{matrix}) .

Case $𝑎 = 1$ . Rows $2$ and $3$ become $(0, 0, 0 | 0)$ and $(0, 0, 0 | 𝑏 - 1)$ , and the left block is in RREF with one pivot. If $𝑏 \neq 1$ , the system is inconsistent. If $𝑏 = 1$ , it is consistent with $ℓ = 2$ free variables $𝑥_{2}, 𝑥_{3}$ .

Case $𝑎 \neq 1$ . Scale row $2$ by ${(𝑎 - 1)}^{- 1}$ to get $(0, 1, - 1 | 0)$ , and add $- (1 - 𝑎)$ times it to row $3$ , which becomes

(0, 0, 1 - 𝑎^{2} + (1 - 𝑎) | 𝑏 - 𝑎) = (0, 0, (1 - 𝑎) (2 + 𝑎) | 𝑏 - 𝑎) .

If $(1 - 𝑎) (2 + 𝑎) \neq 0$ , this entry is a third pivot, and there are pivots in every column and every row; by Corollary 3.4.20 the system has exactly one solution. If $(1 - 𝑎) (2 + 𝑎) = 0$ , then since $𝑎 \neq 1$ we have $2 + 𝑎 = 0$ , and the last row is $(0, 0, 0 | 𝑏 - 𝑎)$ : the system is inconsistent if $𝑏 \neq 𝑎$ , and consistent with one free variable $𝑥_{3}$ if $𝑏 = 𝑎$ .

(a) Over $ℝ$ , $2 + 𝑎 = 0$ means $𝑎 = - 2$ . So the system has exactly one solution if $𝑎 \neq 1$ and $𝑎 \neq - 2$ ; no solution if $𝑎 = 1, 𝑏 \neq 1$ or $𝑎 = - 2, 𝑏 \neq - 2$ ; and infinitely many (by Corollary 3.4.14(c)) if $(𝑎, 𝑏) = (1, 1)$ or $(𝑎, 𝑏) = (- 2, - 2)$ .

(b) Over $𝔽_{3}$ , $- 2 = 1$ , so the case $2 + 𝑎 = 0$ with $𝑎 \neq 1$ never occurs. For $𝑎 = 1$ : if $𝑏 = 1$ there are $3^{2} = 9$ solutions by Corollary 3.4.14(b), and if $𝑏 \neq 1$ there are none. For $𝑎 = 0$ and $𝑎 = 2$ , $(1 - 𝑎) (2 + 𝑎)$ equals $2$ and $(- 1) (4) = - 1 = 2$ , both nonzero, so there is exactly one solution for every $𝑏$ . The two exceptional values $1$ and $- 2$ of the real case collide in $𝔽_{3}$ .

Exercise 3.4.34.standard Let $𝐴$ be the matrix of Example 3.4.6, and $𝐲 = (4, 2, 5)$ . Two students describe the solution set of $𝐴 𝐱 = 𝐲$ .

Student 1. “The solution set is $(- 1, 0, 2, 0) +$ $span ((0, 1, - 2, 1))$ . Proof: $𝐴 (- 1, 0, 2, 0) =$ $(4, 2, 5)$ and $𝐴 (0, 1, - 2, 1) = 𝟎$ , so every vector of this form is a solution, by Proposition 3.1.19.”

Student 2. The solution set is

(1, - 1, 2, 0) + span ((0, 1, - 2, 1), (4, - 1, - 2, 1)) .

(a)Find the error in Student 1′s argument, and a solution that Student 1 has missed.
(b)Decide whether Student 2 is right.

Solution.

Uses. Theorem 3.4.9 (All solutions), Remark 3.4.12 (Checking a description of the solutions), Proposition 3.1.19 (Solution sets are translates of the kernel)

Hint 1. Student 1 proved one containment. Which one? Compare the description with Example 3.4.10.

Hint 2. Every solution is

𝐱_{0} + 𝑡_{1} 𝐬_{1} + 𝑡_{2} 𝐬_{2}

. Is

𝐱_{0} + 𝐬_{1}

in Student 1′s set? For Student 2, express the new vectors through

𝐱_{0}

𝐬_{1}

𝐬_{2}

Sketch. (a) The check shows only that the line consists of solutions, not that it contains all of them; the solution set is a plane. The solution

(- 3, 1, 2, 0) =

𝐱_{0} +

𝐬_{1}

is missing: its second and fourth coordinates would force

𝑡 = 1

and

𝑡 = 0

. (b) Right:

(1, - 1, 2, 0) =

𝐱_{0} -

𝐬_{1}

is a solution,

(0, 1, - 2, 1) =

𝐬_{1} +

𝐬_{2}

and

(4, - 1, - 2, 1) =

𝐬_{2} -

𝐬_{1}

lie in

ker 𝑇_{𝐴}

, and

𝐬_{1}, 𝐬_{2}

are combinations of these two vectors.

By Example 3.4.10, the solution set is $𝐱_{0} + span (𝐬_{1}, 𝐬_{2})$ with $𝐱_{0} = (- 1, 0, 2, 0)$ , $𝐬_{1} = (- 2, 1, 0, 0)$ , and $𝐬_{2} = (2, 0, - 2, 1)$ .

(a) Student 1 showed that every vector of the line $(- 1, 0, 2, 0) +$ $span ((0, 1, - 2, 1))$ is a solution. That is one containment; the claim “the solution set is” needs the other one too, and it is false (Remark 3.4.12). For instance $𝐱_{0} +$ $𝐬_{1} =$ $(- 3, 1, 2, 0)$ is a solution. If it were $(- 1, 0, 2, 0) +$ $𝑡 (0, 1, - 2, 1)$ , comparing second coordinates would give $𝑡 = 1$ and comparing fourth coordinates $𝑡 = 0$ . So Student 1 has missed it. The solution set is a plane, with two free variables, and a line cannot be all of it.

(b) Student 2 is right. First, $(1, - 1, 2, 0) =$ $𝐱_{0} -$ $𝐬_{1}$ is a solution, and $(0, 1, - 2, 1) =$ $𝐬_{1} +$ $𝐬_{2}$ and $(4, - 1, - 2, 1) =$ $𝐬_{2} -$ $𝐬_{1}$ lie in $ker 𝑇_{𝐴}$ . Since $ker 𝑇_{𝐴}$ is a subspace, Student 2′s set is contained in the solution set. Conversely, with $𝐮_{1} = 𝐬_{1} + 𝐬_{2}$ and $𝐮_{2} = 𝐬_{2} - 𝐬_{1}$ , we have

𝐬_{1} = \frac{1}{2} (𝐮_{1} - 𝐮_{2}), 𝐬_{2} = \frac{1}{2} (𝐮_{1} + 𝐮_{2}),

so $𝐬_{1},$ $𝐬_{2} \in$ $span (𝐮_{1}, 𝐮_{2})$ , and every solution

𝐱_{0} + 𝑡_{1} 𝐬_{1} + 𝑡_{2} 𝐬_{2} = (𝐱_{0} - 𝐬_{1}) + (𝑡_{1} + 1) 𝐬_{1} + 𝑡_{2} 𝐬_{2}

lies in $(1, - 1, 2, 0) +$ $span (𝐮_{1}, 𝐮_{2})$ . (This uses $1 + 1 \neq 0$ , which holds in $ℚ$ . In characteristic $2$ we would have $𝐮_{1} = 𝐮_{2}$ , and Student 2′s set would only be a line.)

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

(a)If $𝐴 𝐱 = 𝐲$ has exactly one solution for some $𝐲 \in 𝐹^{𝑚}$ , then $𝐴_{𝑟}$ has a pivot in every column.
(b)If $𝐴 𝐱 = 𝟎$ has only the trivial solution, then $𝐴 𝐱 = 𝐲$ is consistent for every $𝐲$ .
(c)If $𝐴_{𝑟}$ has a pivot in every column, and $𝐵$ is obtained from $𝐴$ by deleting some of its columns, then $𝐵_{𝑟}$ has a pivot in every column.
(d)If $𝐴_{𝑟}$ has a pivot in every row, and $𝐵$ is obtained from $𝐴$ by deleting some of its columns, then $𝐵_{𝑟}$ has a pivot in every row.

Solution.

Uses. Corollary 3.1.22 (Uniqueness depends only on $𝐴$ ), Proposition 3.4.15 (A pivot in every column), Proposition 3.4.16 (A pivot in every row), Definition 2.3.8 (Matrix–vector product)

Hint 1. (a): uniqueness for one right-hand side is a statement about

ker 𝑇_{𝐴}

(Corollary 3.1.22).

Hint 2. For (c), translate both statements into homogeneous systems with Proposition 3.4.15, and pad a solution for

𝐵

with zeros. For (b) and (d), look at

1 \times 2

and

2 \times 1

matrices.

Sketch. (a) True: by Corollary 3.1.22,

ker 𝑇_{𝐴} = {𝟎}

, then Proposition 3.4.15. (b) False: the

2 \times 1

matrix with column

(1, 0)

, and

𝐲 = 𝐞_{2}

. (c) True: a nontrivial solution of

𝐵 𝐱 = 𝟎

, padded with zeros in the deleted positions, is a nontrivial solution of

𝐴 𝐱 = 𝟎

. (d) False:

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

, delete column

2

(a) True. By Corollary 3.1.22(a), applied to the consistent system with exactly one solution, $ker 𝑇_{𝐴} = {𝟎}$ ; that is, $𝐴 𝐱 = 𝟎$ has only the trivial solution. By Proposition 3.4.15, $𝐴_{𝑟}$ has a pivot in every column.

(b) False. Let $𝐴 \in 𝐹^{2 \times 1}$ be the matrix with the single column $(1, 0)$ . Then $𝐴 𝑥 = (𝑥, 0)$ is $𝟎$ only for $𝑥 = 0$ , but $𝐴 𝑥 = (0, 1)$ has no solution.

(c) True. By Proposition 3.4.15, we must show: if $𝐵 𝐱 = 𝟎$ has a nontrivial solution, so does $𝐴 𝐱 = 𝟎$ . Let $𝐵$ consist of the columns $𝐚_{𝑙_{1}}, \dots, 𝐚_{𝑙_{𝑟}}$ of $𝐴$ , and let $𝐵 𝐮 = 𝟎$ with $𝐮 \neq 𝟎$ . Define $𝐱 \in 𝐹^{𝑛}$ by $𝑥_{𝑙_{𝑞}} = 𝑢_{𝑞}$ for $𝑞 = 1, \dots, 𝑟$ and $𝑥_{𝑙} = 0$ for the deleted columns $𝑙$ . By Definition 2.3.8,

𝐴 𝐱 = \sum_{𝑞 = 1}^{𝑟} 𝑢_{𝑞} 𝐚_{𝑙_{𝑞}} = 𝐵 𝐮 = 𝟎,

and $𝐱 \neq 𝟎$ . (In terms of columns: a sublist of a linearly independent list is linearly independent.)

(d) False. Let $𝐴 = (\begin{matrix} 0 & 1 \end{matrix}) \in 𝐹^{1 \times 2}$ , which is in RREF with a pivot in its only row. Deleting the second column leaves $𝐵 = (\begin{matrix} 0 \end{matrix})$ , which has no pivot.

Exercise 3.4.36.standard Let $𝐹$ be a finite field with $𝑞$ elements, and let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have $𝑘$ pivots.

(a)Show that $𝐴 𝐱 = 𝐲$ is consistent for exactly $𝑞^{𝑘}$ vectors $𝐲 \in 𝐹^{𝑚}$ .
(b)Each consistent system $𝐴 𝐱 = 𝐲$ has $𝑞^{𝑛 - 𝑘}$ solutions. Explain why $𝑞^{𝑘} \cdot 𝑞^{𝑛 - 𝑘} = 𝑞^{𝑛}$ is no coincidence.

Solution.

Uses. Corollary 3.4.4 (Consistency), Corollary 3.4.14 (Counting solutions), Definition 2.5.12 (Invertible)

Hint 1. By Corollary 3.4.4,

𝐲

works exactly when

𝐺 𝐲

has zeros in positions

𝑘 + 1, \dots, 𝑚

. How many vectors

𝐳

have this property, and how are they related to the good

𝐲

Hint 2. For (b), count the pairs

(𝐱, 𝐲)

with

𝐴 𝐱 = 𝐲

in two ways.

Sketch. (a)

𝐲 \mapsto 𝐺 𝐲

is a bijection of

𝐹^{𝑚}

(inverse

𝐳 \mapsto 𝐺^{- 1} 𝐳

), and it maps the good

𝐲

onto the

𝐳

with

𝑧_{𝑘 + 1} = \dots = 𝑧_{𝑚} = 0

, of which there are

𝑞^{𝑘}

. (b) Each

𝐱 \in 𝐹^{𝑛}

determines

𝐲 = 𝐴 𝐱

, so the

𝑞^{𝑛}

vectors

𝐱

are split among the

𝑞^{𝑘}

consistent

𝐲

, each receiving

𝑞^{𝑛 - 𝑘}

of them.

(a) Let $𝐺$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ , and let $𝑍 =$ ${𝐳 \in 𝐹^{𝑚} | 𝑧_{𝑘 + 1} = \dots = 𝑧_{𝑚} = 0}$ . By Corollary 3.4.4, $𝐴 𝐱 = 𝐲$ is consistent if and only if $𝐺 𝐲 \in 𝑍$ . The map $𝐲 \mapsto 𝐺 𝐲$ is a bijection $𝐹^{𝑚} \to 𝐹^{𝑚}$ , with inverse $𝐳 \mapsto 𝐺^{- 1} 𝐳$ , so it restricts to a bijection from the set of good $𝐲$ onto $𝑍$ . A vector of $𝑍$ is determined by its first $𝑘$ entries, which are arbitrary, so $| 𝑍 | = 𝑞^{𝑘}$ .

(b) By Corollary 3.4.14(b), each consistent system has $𝑞^{ℓ} = 𝑞^{𝑛 - 𝑘}$ solutions. Now count the pairs $(𝐱, 𝐲) \in 𝐹^{𝑛} \times 𝐹^{𝑚}$ with $𝐴 𝐱 = 𝐲$ . Each $𝐱$ belongs to exactly one pair, namely $(𝐱, 𝐴 𝐱)$ , so there are $𝑞^{𝑛}$ pairs. On the other hand, grouping the pairs by $𝐲$ , only the $𝑞^{𝑘}$ consistent $𝐲$ occur, each in $𝑞^{𝑛 - 𝑘}$ pairs. So $𝑞^{𝑛} = 𝑞^{𝑘} \cdot 𝑞^{𝑛 - 𝑘}$ , and the identity just says that the solution sets of the consistent systems partition $𝐹^{𝑛}$ .

Exercise 3.4.37.standard Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

1 \leq 𝑗 \leq 𝑛

. Show that

𝑥_{𝑗}

is a free variable of

𝐴

if and only if there is a solution

𝐱

𝐴 𝐱 = 𝟎

with

𝑥_{𝑗} = 1

and

𝑥_{𝑙} = 0

for every

𝑙 > 𝑗

Solution.

Uses. Definition 3.4.8 (Basic solutions), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Corollary 3.3.19 (Pivot columns, intrinsically), Definition 2.3.8 (Matrix–vector product)

Hint 1. If

𝑗 = 𝑓_{𝑡}

is free, try the basic solution

𝐬_{𝑡}

. Which of its coordinates beyond position

𝑗

could be nonzero?

Hint 2. A pivot coordinate

{(𝐬_{𝑡})}_{𝑝_{𝑖}} =

- 𝑟_{𝑖 𝑓_{𝑡}}

with

𝑝_{𝑖} > 𝑓_{𝑡}

vanishes by Lemma 3.3.16(a). For the converse, rewrite

𝐴 𝐱 = 𝟎

as an expression for

𝐚_{𝑗}

Sketch. If

𝑗 = 𝑓_{𝑡}

, then

𝐬_{𝑡}

has

1

in position

𝑗

0

in the other free positions, and

- 𝑟_{𝑖 𝑗}

in position

𝑝_{𝑖}

; for

𝑝_{𝑖} > 𝑗

𝑟_{𝑖 𝑗} = 0

by Lemma 3.3.16(a). Conversely, such an

𝐱

gives

𝐚_{𝑗} =

- \sum_{𝑙 < 𝑗} 𝑥_{𝑙} 𝐚_{𝑙}

, so column

𝑗

is not a pivot column by Corollary 3.3.19(a).

Suppose $𝑥_{𝑗}$ is free, say $𝑗 = 𝑓_{𝑡}$ , and consider the basic solution $𝐬_{𝑡}$ , which solves $𝐴 𝐱 = 𝟎$ (Theorem 3.4.9). It has a $1$ in position $𝑗$ , and $0$ in every other free position. In a pivot position $𝑝_{𝑖} > 𝑗$ it has the entry $- 𝑟_{𝑖 𝑗}$ of $𝐴_{𝑟}$ , where $𝑟_{𝑖 𝑗}$ is the entry in row $𝑖$ of column $𝑗 < 𝑝_{𝑖}$ ; this is $0$ by Lemma 3.3.16(a), since column $𝑗$ lies to the left of the $𝑖$ th pivot. So ${(𝐬_{𝑡})}_{𝑙} = 0$ for all $𝑙 > 𝑗$ .

Conversely, suppose $𝐴 𝐱 = 𝟎$ with $𝑥_{𝑗} = 1$ and $𝑥_{𝑙} = 0$ for $𝑙 > 𝑗$ . By Definition 2.3.8,

𝟎 = 𝐴 𝐱 = 𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑗 - 1} 𝐚_{𝑗 - 1} + 𝐚_{𝑗},

so $𝐚_{𝑗} =$ $- 𝑥_{1} 𝐚_{1} -$ $\dots -$ $𝑥_{𝑗 - 1} 𝐚_{𝑗 - 1}$ is a linear combination of the earlier columns. By Corollary 3.3.19(a), column $𝑗$ is not a pivot column, so $𝑥_{𝑗}$ is free.

So the basic solutions are the “staircase” solutions: $𝐬_{𝑡}$ ends with a $1$ in position $𝑓_{𝑡}$ , followed only by zeros.

Exercise 3.4.38.standard Let $𝐹$ be a subfield of a field $𝐾$ (for example $ℚ \subseteq ℝ$ or $ℝ \subseteq ℂ$ ). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ .

(a)Show that if $𝐴 𝐱 = 𝐲$ has a solution $𝐱 \in 𝐾^{𝑛}$ , then it has a solution in $𝐹^{𝑛}$ .
(b)Show that if $𝐴 𝐱 = 𝐲$ has exactly one solution in $𝐾^{𝑛}$ , then that solution lies in $𝐹^{𝑛}$ .
(c)Show that if $𝐴 𝐱 = 𝟎$ has a nontrivial solution in $𝐾^{𝑛}$ , then it has one in $𝐹^{𝑛}$ .

Solution.

Uses. Exercise 3.3.54, Corollary 3.4.4 (Consistency), Theorem 3.4.9 (All solutions), Proposition 3.4.15 (A pivot in every column)

Hint 1. By Exercise 3.3.54, Gauss–Jordan elimination on

(𝐴 | 𝐲)

performs the same operations over

𝐹

and over

𝐾

. What does that say about the reduced augmented matrix?

Hint 2. The particular and basic solutions are built from the entries of

(𝐴_{𝑟} | 𝐺 𝐲)

Sketch. Row reducing

(𝐴 | 𝐲)

uses only field operations on entries of

𝐹

, so

(𝐴_{𝑟} | 𝐺 𝐲)

, the pivots,

𝐱_{0}

, and the

𝐬_{𝑗}

are the same over

𝐹

and over

𝐾

, and have entries in

𝐹

. (a) Consistency over

𝐾

is consistency over

𝐹

, and then

𝐱_{0} \in 𝐹^{𝑛}

. (b) If the solution over

𝐾

is unique, it is

𝐱_{0}

. (c) A free column exists, and

𝐬_{1} \in 𝐹^{𝑛}

is nonzero.

Run Gauss–Jordan elimination on $(𝐴 | 𝐲)$ , scanning only the first $𝑛$ columns. Every step uses only additions, multiplications, and inverses of nonzero entries, all of which stay in $𝐹$ , and whether an entry is $0$ does not depend on whether we regard it in $𝐹$ or in $𝐾$ . So the run is the same over $𝐹$ and over $𝐾$ (this is the argument of Exercise 3.3.54), and it produces the same matrix $(𝐴_{𝑟} | 𝐳)$ , with entries in $𝐹$ , and the same pivot and free columns. Hence the particular solution $𝐱_{0}$ (when the system is consistent) and the basic solutions $𝐬_{𝑗}$ are the same over both fields, and lie in $𝐹^{𝑛}$ .

(a) By Corollary 3.4.4, consistency over either field means $𝑧_{𝑖} = 0$ for $𝑖 > 𝑘$ , the same condition. If the system has a solution in $𝐾^{𝑛}$ , this condition holds, so $𝐱_{0} \in 𝐹^{𝑛}$ is a solution.

(b) If the solution in $𝐾^{𝑛}$ is unique, it is $𝐱_{0}$ (which is a solution over $𝐾$ ), and $𝐱_{0} \in 𝐹^{𝑛}$ .

(c) If $𝐴 𝐱 = 𝟎$ has a nontrivial solution in $𝐾^{𝑛}$ , then by Proposition 3.4.15 (over $𝐾$ ) some column of $𝐴_{𝑟}$ is free, so $ℓ \geq 1$ , and $𝐬_{1} \in 𝐹^{𝑛}$ is a nonzero solution.

Exercise 3.4.39.standard Let $𝑚 \geq 1$ , let $𝑐_{1}, \dots, 𝑐_{𝑚} \in 𝐹$ be distinct, let $𝑑 \geq 0$ , and let $𝑊 \in 𝐹^{𝑚 \times (𝑑 + 1)}$ be the matrix with rows $(1, 𝑐_{𝑖}, 𝑐_{𝑖}^{2}, \dots, 𝑐_{𝑖}^{𝑑})$ , $𝑖 = 1, \dots, 𝑚$ . Show that:

(a) $𝑊_{𝑟}$ has a pivot in every column if and only if $𝑚 \geq 𝑑 + 1$ ;
(b) $𝑊_{𝑟}$ has a pivot in every row if and only if $𝑚 \leq 𝑑 + 1$ .

Interpret both statements as statements about polynomials of degree at most $𝑑$ with prescribed values at $𝑐_{1}, \dots, 𝑐_{𝑚}$ .

Solution.

Uses. Lemma 3.4.23 (Too many roots), Theorem 3.4.24 (Polynomial interpolation), Proposition 3.4.15 (A pivot in every column), Proposition 3.4.16 (A pivot in every row), Corollary 3.4.19 (More unknowns than equations)

Hint 1. As in Theorem 3.4.24,

𝑊 𝐚

lists the values of

𝑎_{0} +

𝑎_{1} 𝑥 +

\dots +

𝑎_{𝑑} 𝑥^{𝑑}

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

Hint 2. For (a) with

𝑚 \geq 𝑑 + 1

, use Lemma 3.4.23 with

𝑑 + 1

of the nodes. For (b) with

𝑚 \leq 𝑑 + 1

, interpolate with a polynomial of degree at most

𝑚 - 1

. The other directions are Corollary 3.4.19.

Sketch.

𝑊 𝐚

lists the values of

𝑝_{𝐚}

at the nodes. (a) If

𝑚 \geq 𝑑 + 1

and

𝑊 𝐚 = 𝟎

, then

𝑝_{𝐚}

vanishes at

𝑑 + 1

distinct points, so

𝐚 = 𝟎

. If

𝑚 < 𝑑 + 1

, there are more unknowns than equations. (b) If

𝑚 \leq 𝑑 + 1

, Theorem 3.4.24 gives

𝑝

of degree at most

𝑚 - 1 \leq 𝑑

with any values. If

𝑚 > 𝑑 + 1

, there are more equations than unknowns. Interpretation: interpolating polynomials of degree at most

𝑑

are unique when they exist iff

𝑚 \geq 𝑑 + 1

, and always exist iff

𝑚 \leq 𝑑 + 1

For $𝐚 = (𝑎_{0}, \dots, 𝑎_{𝑑})$ let $𝑝_{𝐚} =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑑} 𝑥^{𝑑}$ . As in the proof of Theorem 3.4.24, $𝑊 𝐚 =$ $(𝑝_{𝐚} (𝑐_{1}), \dots, 𝑝_{𝐚} (𝑐_{𝑚}))$ .

(a) Suppose $𝑚 \geq 𝑑 + 1$ , and $𝑊 𝐚 = 𝟎$ . Then $𝑝_{𝐚}$ has degree at most $𝑑$ and vanishes at the $𝑑 + 1$ distinct points $𝑐_{1}, \dots, 𝑐_{𝑑 + 1}$ , so $𝑝_{𝐚} = 𝟎$ by Lemma 3.4.23, and $𝐚 = 𝟎$ . By Proposition 3.4.15, $𝑊_{𝑟}$ has a pivot in every column. If $𝑚 < 𝑑 + 1$ , then $𝑊$ has more columns than rows, and by Corollary 3.4.19(a) $𝑊 𝐚 = 𝟎$ has a nontrivial solution, so some column of $𝑊_{𝑟}$ has no pivot.

(b) Suppose $𝑚 \leq 𝑑 + 1$ , and let $𝐯 \in 𝐹^{𝑚}$ . By Theorem 3.4.24 (with $𝑛 = 𝑚 - 1$ and the nodes $𝑐_{1}, \dots, 𝑐_{𝑚}$ ) there is a polynomial $𝑝$ of degree at most $𝑚 - 1 \leq 𝑑$ with $𝑝 (𝑐_{𝑖}) = 𝑣_{𝑖}$ for all $𝑖$ . Its coefficients, padded with zeros up to $𝑎_{𝑑}$ , form a solution of $𝑊 𝐚 = 𝐯$ . So $𝑊 𝐚 = 𝐯$ is consistent for every $𝐯$ , and by Proposition 3.4.16 $𝑊_{𝑟}$ has a pivot in every row. If $𝑚 > 𝑑 + 1$ , then $𝑊$ has more rows than columns, and by Corollary 3.4.19(b) some system $𝑊 𝐚 = 𝐯$ is inconsistent, so some row of $𝑊_{𝑟}$ has no pivot.

In terms of polynomials: prescribing values at $𝑚$ distinct points, a polynomial of degree at most $𝑑$ with those values is unique (if it exists) exactly when $𝑚 \geq 𝑑 + 1$ , and exists for all choices of values exactly when $𝑚 \leq 𝑑 + 1$ . Both hold exactly when $𝑚 = 𝑑 + 1$ , which is Theorem 3.4.24.

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

(a)Show that every function $𝑔 : 𝔽_{𝑝} \to 𝔽_{𝑝}$ is the polynomial function of exactly one polynomial $𝑓 \in 𝔽_{𝑝} {[𝑥]}_{\leq 𝑝 - 1}$ . Check this by counting both sides.
(b)Find that polynomial for the function $𝑔$ with $𝑔 (0) = 1$ and $𝑔 (𝑐) = 0$ for $𝑐 \neq 0$ .

Solution.

Uses. Theorem 3.4.24 (Polynomial interpolation), Exercise 1.1.51, Definition 1.2.17 (Evaluation)

Hint 1.

𝔽_{𝑝}

has exactly

𝑝

elements. Use them all as nodes.

Hint 2. For (b), Fermat’s little theorem (Exercise 1.1.51) says

𝑐^{𝑝 - 1} = 1

for

𝑐 \neq 0

Sketch. (a) The

𝑝

elements

0, 1, \dots, 𝑝 - 1

𝔽_{𝑝}

are distinct nodes, so Theorem 3.4.24 with

𝑛 = 𝑝 - 1

gives exactly one

𝑓

of degree at most

𝑝 - 1

with

𝑓 (𝑐) = 𝑔 (𝑐)

for all

𝑐

. Count:

𝑝^{𝑝}

functions and

𝑝^{𝑝}

polynomials (one for each list of

𝑝

coefficients). (b)

𝑓 = 1 - 𝑥^{𝑝 - 1}

, by Fermat.

(a) The elements $0, 1, \dots, 𝑝 - 1$ of $𝔽_{𝑝}$ are $𝑝$ distinct nodes. By Theorem 3.4.24 with $𝑛 = 𝑝 - 1$ and $𝑑_{𝑐} = 𝑔 (𝑐)$ , there is exactly one $𝑓 \in 𝔽_{𝑝} {[𝑥]}_{\leq 𝑝 - 1}$ with $𝑓 (𝑐) = 𝑔 (𝑐)$ for all $𝑐 \in 𝔽_{𝑝}$ , that is, whose polynomial function is $𝑔$ . Counting: there are $𝑝^{𝑝}$ functions $𝔽_{𝑝} \to 𝔽_{𝑝}$ (a value for each of $𝑝$ inputs), and $𝑝^{𝑝}$ polynomials $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑝 - 1} 𝑥^{𝑝 - 1}$ (a coefficient for each of $𝑝$ positions). The map sending a polynomial to its function is therefore a bijection between two sets with $𝑝^{𝑝}$ elements, consistent with what we proved.

(b) Let $𝑓 = 1 - 𝑥^{𝑝 - 1}$ , which has degree at most $𝑝 - 1$ . Then $𝑓 (0) = 1$ , and for $𝑐 \neq 0$ Fermat’s little theorem (Exercise 1.1.51) gives $𝑐^{𝑝 - 1} = 1$ , so $𝑓 (𝑐) = 0$ . By the uniqueness in (a), $𝑓$ is the polynomial.

Polynomials of degree at least $𝑝$ are not needed to describe functions, and indeed $𝑥^{𝑝} - 𝑥$ has the zero function (Exercise 1.2.51); this does not contradict Lemma 3.4.23, since $𝑥^{𝑝} - 𝑥$ has degree $𝑝$ and only $𝑝$ roots are available.

Exercise 3.4.41.standard For each prime $𝑝$ , find the number of $(𝑎_{0}, 𝑎_{1}, 𝑎_{2}) \in$ $𝔽_{𝑝}^{3}$ with

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

Solution.

Uses. Theorem 3.4.24 (Polynomial interpolation), Definition 3.4.22 (Vandermonde matrix), Corollary 3.4.4 (Consistency)

Hint 1. The coefficient matrix is

𝑉 (1, 2, 3)

: the system asks for a polynomial of degree at most

2

with values

1, 2, 4

1, 2, 3

. When are the nodes distinct in

𝔽_{𝑝}

Hint 2. For

𝑝 = 2

two nodes coincide. Compare the corresponding equations.

Sketch. For

𝑝 \geq 3

, the nodes

1, 2, 3

are distinct in

𝔽_{𝑝}

(

3 - 1 = 2

3 - 2 = 1

2 - 1 = 1

are nonzero), so there is exactly one solution by Theorem 3.4.24. For

𝑝 = 2

, the first and third equations read

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

and

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

: no solution.

The coefficient matrix has rows $(1, 𝑐, 𝑐^{2})$ for $𝑐 = 1, 2, 3$ , so it is $𝑉 (1, 2, 3)$ , and the system asks for $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2}$ with $𝑝 (1) = 1$ , $𝑝 (2) = 2$ , $𝑝 (3) = 4$ .

If $𝑝 \geq 3$ , the differences $2 - 1 = 1$ , $3 - 2 = 1$ , and $3 - 1 = 2$ are nonzero in $𝔽_{𝑝}$ , so the nodes are distinct, and by Theorem 3.4.24 there is exactly one solution. (Over $ℚ$ it is $(1, - 1 / 2, 1 / 2)$ , and the same computation works in $𝔽_{𝑝}$ for $𝑝 \geq 3$ , where $2$ is invertible.)

If $𝑝 = 2$ , then $3 = 1$ and $9 = 1$ in $𝔽_{2}$ , so the third equation reads $𝑎_{0} + 𝑎_{1} + 𝑎_{2} = 4 = 0$ , while the first reads $𝑎_{0} + 𝑎_{1} + 𝑎_{2} = 1$ . Subtracting gives $0 = 1$ , so there is no solution. (In the language of Corollary 3.4.4: the reduced augmented matrix has a row $(0, 0, 0 | 1)$ .)

So the number of solutions is $1$ for every odd prime, and $0$ for $𝑝 = 2$ .

Exercise 3.4.42.standard For $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $𝑎_{2} 𝑥^{2} +$ $𝑎_{3} 𝑥^{3} \in$ $ℝ [𝑥]$ , write $𝑝^{'} =$ $𝑎_{1} +$ $2 𝑎_{2} 𝑥 +$ $3 𝑎_{3} 𝑥^{2}$ .

(a)Show that for all $𝑢_{0}, 𝑣_{0}, 𝑢_{1}, 𝑣_{1} \in ℝ$ there is exactly one $𝑝 \in {ℝ [𝑥]}_{\leq 3}$ with
$𝑝 (0) = 𝑢_{0}, 𝑝^{'} (0) = 𝑣_{0}, 𝑝 (1) = 𝑢_{1}, 𝑝^{'} (1) = 𝑣_{1} .$
(b)Find the four polynomials $ℎ_{1}, ℎ_{2}, ℎ_{3}, ℎ_{4}$ obtained when one of $𝑢_{0}, 𝑣_{0}, 𝑢_{1}, 𝑣_{1}$ is $1$ and the others are $0$ , and write the general $𝑝$ in terms of them.

Solution.

Uses. Corollary 3.4.20 (Square systems), Definition 1.2.17 (Evaluation), Proposition 1.2.18 (Degree and evaluation versus the operations)

Techniques. Uniqueness gives existence (Technique 3.4.21)

Hint 1. The four conditions are linear in

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

, so this is a square system. By Technique 3.4.21 it is enough to treat

𝑢_{0} = 𝑣_{0} = 𝑢_{1} = 𝑣_{1} = 0

Hint 2. For (b), solve each system directly; then use that the conditions are linear in

𝑝

Sketch. The conditions are

𝑎_{0} = 𝑢_{0}

𝑎_{1} = 𝑣_{0}

𝑎_{0} +

𝑎_{1} +

𝑎_{2} +

𝑎_{3} =

𝑢_{1}

𝑎_{1} + 2 𝑎_{2} + 3 𝑎_{3} = 𝑣_{1}

. With zero data,

𝑎_{0} = 𝑎_{1} = 0

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

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

force

𝐚 = 𝟎

, so Corollary 3.4.20 applies.

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

ℎ_{2} = 𝑥 - 2 𝑥^{2} + 𝑥^{3}

ℎ_{3} = 3 𝑥^{2} - 2 𝑥^{3}

ℎ_{4} = - 𝑥^{2} + 𝑥^{3}

, and

𝑝 =

𝑢_{0} ℎ_{1} +

𝑣_{0} ℎ_{2} +

𝑢_{1} ℎ_{3} +

𝑣_{1} ℎ_{4}

(a) By Definition 1.2.17, the four conditions are

𝑎_{0} = 𝑢_{0}, 𝑎_{1} = 𝑣_{0}, 𝑎_{0} + 𝑎_{1} + 𝑎_{2} + 𝑎_{3} = 𝑢_{1}, 𝑎_{1} + 2 𝑎_{2} + 3 𝑎_{3} = 𝑣_{1},

a square linear system in $𝑎_{0}, 𝑎_{1}, 𝑎_{2}, 𝑎_{3}$ . By Corollary 3.4.20 it suffices to show that the homogeneous system has only the trivial solution. If all data are $0$ , then $𝑎_{0} = 𝑎_{1} = 0$ , so $𝑎_{2} + 𝑎_{3} = 0$ and $2 𝑎_{2} + 3 𝑎_{3} = 0$ ; subtracting twice the first from the second gives $𝑎_{3} = 0$ , and then $𝑎_{2} = 0$ . So for all data there is exactly one solution.

(b) Solving the four systems:

$𝑢_{0} = 1$ : $𝑎_{0} = 1$ , $𝑎_{1} = 0$ , $𝑎_{2} + 𝑎_{3} = - 1$ , $2 𝑎_{2} + 3 𝑎_{3} = 0$ , so $𝑎_{3} = 2$ , $𝑎_{2} = - 3$ : $ℎ_{1} = 1 - 3 𝑥^{2} + 2 𝑥^{3}$ .
$𝑣_{0} = 1$ : $𝑎_{0} = 0$ , $𝑎_{1} = 1$ , $𝑎_{2} + 𝑎_{3} = - 1$ , $2 𝑎_{2} + 3 𝑎_{3} = - 1$ , so $𝑎_{3} = 1$ , $𝑎_{2} = - 2$ : $ℎ_{2} = 𝑥 - 2 𝑥^{2} + 𝑥^{3}$ .
$𝑢_{1} = 1$ : $𝑎_{0} = 𝑎_{1} = 0$ , $𝑎_{2} + 𝑎_{3} = 1$ , $2 𝑎_{2} + 3 𝑎_{3} = 0$ , so $𝑎_{3} = - 2$ , $𝑎_{2} = 3$ : $ℎ_{3} = 3 𝑥^{2} - 2 𝑥^{3}$ .
$𝑣_{1} = 1$ : $𝑎_{0} = 𝑎_{1} = 0$ , $𝑎_{2} + 𝑎_{3} = 0$ , $2 𝑎_{2} + 3 𝑎_{3} = 1$ , so $𝑎_{3} = 1$ , $𝑎_{2} = - 1$ : $ℎ_{4} = - 𝑥^{2} + 𝑥^{3}$ .

The four conditions depend linearly on $𝑝$ : values by Proposition 1.2.18(c), and $𝑝^{'}$ because its coefficients are linear in those of $𝑝$ . So $𝑢_{0} ℎ_{1} +$ $𝑣_{0} ℎ_{2} +$ $𝑢_{1} ℎ_{3} +$ $𝑣_{1} ℎ_{4}$ satisfies the conditions with data $𝑢_{0}, 𝑣_{0}, 𝑢_{1}, 𝑣_{1}$ , and by uniqueness it is $𝑝$ . (These are the cubic Hermite polynomials, used in computer graphics to join curve segments smoothly.)

Exercise 3.4.43.standard

(a)Find all $𝑤_{0}, 𝑤_{1}, 𝑤_{2} \in ℝ$ such that
$\int_{- 1}^{1} 𝑝 (𝑡) d 𝑡 = 𝑤_{0} 𝑝 (- 1) + 𝑤_{1} 𝑝 (0) + 𝑤_{2} 𝑝 (1)$
for every $𝑝 \in {ℝ [𝑥]}_{\leq 2}$ .
(b)Show that the resulting rule is exact for every $𝑝 \in {ℝ [𝑥]}_{\leq 3}$ as well, but not for $𝑥^{4}$ .

Solution.

Uses. Proposition 1.2.18 (Degree and evaluation versus the operations), Corollary 3.4.20 (Square systems), Definition 1.2.16 (Degree)

Techniques. Undetermined coefficients (Technique 3.1.9)

Hint 1. Both sides depend linearly on

𝑝

. So it is enough to require the equation for

𝑝 = 1

𝑝 = 𝑥

, and

𝑝 = 𝑥^{2}

Hint 2. This gives a

3 \times 3

system for

𝑤_{0}, 𝑤_{1}, 𝑤_{2}

whose coefficient matrix is the transpose of

𝑉 (- 1, 0, 1)

Sketch. For

𝑝 = 1, 𝑥, 𝑥^{2}

the conditions are

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

- 𝑤_{0} + 𝑤_{2} = 0

𝑤_{0} + 𝑤_{2} = 2 / 3

, with the unique solution

(1 / 3, 4 / 3, 1 / 3)

. These three conditions suffice by linearity. For

𝑥^{3}

both sides are

0

; for

𝑥^{4}

the integral is

2 / 5

and the rule gives

2 / 3

(a) The integral and the right side both depend linearly on $𝑝$ : the right side by Proposition 1.2.18(c), and the integral because $\int (𝑓 + 𝑔) = \int 𝑓 + \int 𝑔$ and $\int 𝑐 𝑓 = 𝑐 \int 𝑓$ . So if the equation holds for $𝑝 = 1$ , $𝑥$ , and $𝑥^{2}$ , it holds for every $𝑎_{0} + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2}$ ; conversely it must hold for these three. Since $\int_{- 1}^{1} 1 = 2$ , $\int_{- 1}^{1} 𝑡 d 𝑡 = 0$ , and $\int_{- 1}^{1} 𝑡^{2} d 𝑡 = 2 / 3$ , the conditions are

𝑤_{0} + 𝑤_{1} + 𝑤_{2} = 2, - 𝑤_{0} + 𝑤_{2} = 0, 𝑤_{0} + 𝑤_{2} = \frac{2}{3} .

The last two give $𝑤_{0} = 𝑤_{2} = 1 / 3$ , and the first gives $𝑤_{1} = 4 / 3$ . So the only rule is

\int_{- 1}^{1} 𝑝 (𝑡) d 𝑡 = \frac{1}{3} 𝑝 (- 1) + \frac{4}{3} 𝑝 (0) + \frac{1}{3} 𝑝 (1),

Simpson’s rule. (The coefficient matrix of the system is the transpose of $𝑉 (- 1, 0, 1)$ , which is invertible because $𝑉 (- 1, 0, 1)$ is (Theorem 3.4.24, Proposition 2.4.23). This is why the weights exist and are unique for any three distinct nodes.)

(b) By linearity it is enough to check $𝑥^{3}$ : the integral is $0$ , and the rule gives $\frac{1}{3} (- 1) + 0 + \frac{1}{3} (1) = 0$ . For $𝑥^{4}$ the integral is $2 / 5$ , while the rule gives $\frac{1}{3} + \frac{1}{3} = 2 / 3$ .

Exercise 3.4.44.hard Let $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲, 𝐰 \in 𝐹^{𝑚}$ .

(a)Show that if the systems $𝐴 𝐱 = 𝐲$ and $𝐵 𝐱 = 𝐰$ have the same solution set, and it is nonempty, then the augmented matrices $(𝐴 | 𝐲)$ and $(𝐵 | 𝐰)$ are row equivalent.
(b)Show by an example that (a) fails without the word “nonempty”.

Solution.

Uses. Proposition 3.1.19 (Solution sets are translates of the kernel), Corollary 3.3.20 (The kernel is a complete invariant), Definition 3.2.21 (Row equivalence), Definition 2.5.12 (Invertible)

Hint 1. Two systems with the same nonempty solution set have the same homogeneous solution set. Why?

Hint 2. So

ker 𝑇_{𝐴} = ker 𝑇_{𝐵}

. What does Corollary 3.3.20 give? Then use a common solution

𝐱_{0}

to compare

𝐲

and

𝐰

Hint 3. For (b), two inconsistent systems have the same (empty) solution set.

Sketch. If

𝑆

is the common solution set and

𝐱_{0} \in 𝑆

, then

𝑆 =

𝐱_{0} +

ker 𝑇_{𝐴} =

𝐱_{0} +

ker 𝑇_{𝐵}

, so

ker 𝑇_{𝐴} = ker 𝑇_{𝐵}

, and Corollary 3.3.20 gives

𝐵 = 𝐻 𝐴

with

𝐻

a product of elementary matrices. Then

𝐰 =

𝐵 𝐱_{0} =

𝐻 𝐴 𝐱_{0} =

𝐻 𝐲

, so

(𝐵 | 𝐰) = 𝐻 (𝐴 | 𝐲)

. (b) The inconsistent systems

0 𝑥 = 1, 0 𝑥 = 0

and

𝑥 = 0, 𝑥 = 1

have the same (empty) solution set, but their augmented matrices have different reduced forms.

(a) Let $𝑆$ be the common solution set and $𝐱_{0} \in 𝑆$ . By Proposition 3.1.19, $𝑆 = 𝐱_{0} + ker 𝑇_{𝐴}$ and $𝑆 = 𝐱_{0} + ker 𝑇_{𝐵}$ . So $𝐳 \in ker 𝑇_{𝐴}$ if and only if $𝐱_{0} + 𝐳 \in 𝑆$ if and only if $𝐳 \in ker 𝑇_{𝐵}$ ; that is, $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ . By Corollary 3.3.20, $𝐴 \sim 𝐵$ , so $𝐵 = 𝐻 𝐴$ for a product $𝐻$ of elementary matrices (Definition 3.2.21). Then

𝐰 = 𝐵 𝐱_{0} = 𝐻 𝐴 𝐱_{0} = 𝐻 𝐲,

(b) Take $𝑚 = 2$ , $𝑛 = 1$ , and the systems

0 𝑥 = 1, 0 𝑥 = 0 and 𝑥 = 0, 𝑥 = 1 .

Both are inconsistent, so they have the same (empty) solution set. Their augmented matrices are $(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$ . The first is in RREF, and the second reduces to $𝐼_{2}$ , so their reduced row echelon forms differ and they are not row equivalent (Corollary 3.3.18(b)).

Exercise 3.4.45.hard Let $𝐱_{0},$ $𝐮_{1},$ $\dots,$ $𝐮_{𝑟} \in$ $𝐹^{𝑛}$ .

(a)Describe a procedure that produces a linear system whose solution set is exactly $𝐱_{0} +$ $span (𝐮_{1}, \dots, 𝐮_{𝑟})$ , and prove that it works.
(b)Carry it out over $ℝ$ for $𝐱_{0} = (1, 0, 2, 0)$ , $𝐮_{1} = (1, 1, 0, 0)$ , and $𝐮_{2} = (0, 0, 1, 1)$ .

Solution.

Uses. Corollary 3.4.4 (Consistency), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Proposition 3.1.19 (Solution sets are translates of the kernel), Proposition 3.3.11 (Carrying extra columns along), Definition 2.4.1 (Matrix product)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. Let

𝑈

be the

𝑛 \times 𝑟

matrix with columns

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

, so that the span is

im 𝑇_{𝑈}

. By Corollary 3.4.4,

im 𝑇_{𝑈}

is cut out by linear equations. Which ones?

Hint 2. If

𝐺 𝑈 = rref (𝑈)

has

𝑘

pivots, let

𝐵

consist of the last

𝑛 - 𝑘

rows of

𝐺

. Then

ker 𝑇_{𝐵} = im 𝑇_{𝑈}

. Now choose the right-hand side so that

𝐱_{0}

is a solution.

Sketch. Row reduce

(𝑈 | 𝐼_{𝑛})

(rref (𝑈) | 𝐺)

, with

𝑘

pivots, and let

𝐵

be the last

𝑛 - 𝑘

rows of

𝐺

. By Corollary 3.4.4,

𝐵 𝐲 = 𝟎

if and only if

𝐲 \in

im 𝑇_{𝑈} =

span (𝐮_{1}, \dots, 𝐮_{𝑟})

. The system

𝐵 𝐱 = 𝐵 𝐱_{0}

has the solution

𝐱_{0}

and homogeneous solution set

ker 𝑇_{𝐵}

, so its solution set is

𝐱_{0} +

span (𝐮_{1}, \dots, 𝐮_{𝑟})

. In (b),

𝐵

has rows

(- 1, 1, 0, 0)

and

(0, 0, - 1, 1)

, and the system is

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

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

(a) Let $𝑈 \in 𝐹^{𝑛 \times 𝑟}$ have columns $𝐮_{1}, \dots, 𝐮_{𝑟}$ , so that $span (𝐮_{1}, \dots, 𝐮_{𝑟}) =$ $im 𝑇_{𝑈}$ by Proposition 3.1.8(a). The procedure:

Row reduce $(𝑈 | 𝐼_{𝑛})$ , scanning only the first $𝑟$ columns, to $(rref (𝑈) | 𝐺)$ (Proposition 3.3.11). Let $𝑘$ be the number of pivots.
If $𝑘 = 𝑛$ , output the empty system (or $0 𝑥_{1} = 0$ ): its solution set is $𝐹^{𝑛}$ .
Otherwise, let $𝐵 \in 𝐹^{(𝑛 - 𝑘) \times 𝑛}$ consist of the last $𝑛 - 𝑘$ rows of $𝐺$ , and output the system $𝐵 𝐱 = 𝐵 𝐱_{0}$ .

Correctness. The $𝑗$ th entry of $𝐵 𝐲$ is the $(𝑘 + 𝑗)$ th entry of $𝐺 𝐲$ (Definition 2.4.1), so $𝐵 𝐲 = 𝟎$ if and only if ${(𝐺 𝐲)}_{𝑖} = 0$ for all $𝑖 > 𝑘$ . By Corollary 3.4.4, applied to $𝑈$ , this holds if and only if $𝐲 \in im 𝑇_{𝑈}$ . So $ker 𝑇_{𝐵} =$ $span (𝐮_{1}, \dots, 𝐮_{𝑟})$ . (If $𝑘 = 𝑛$ , the conditions are vacuous and $im 𝑇_{𝑈} = 𝐹^{𝑛}$ .) The system $𝐵 𝐱 = 𝐵 𝐱_{0}$ has the solution $𝐱_{0}$ , so by Proposition 3.1.19 its solution set is $𝐱_{0} +$ $ker 𝑇_{𝐵} =$ $𝐱_{0} +$ $span (𝐮_{1}, \dots, 𝐮_{𝑟})$ .

(b) Here $𝑈$ has rows $(1, 0)$ , $(1, 0)$ , $(0, 1)$ , $(0, 1)$ . Pass $1$ adds $- 1$ times row $1$ to row $2$ , which becomes $(0, 0 | - 1, 1, 0, 0)$ . In pass $2$ , column $2$ has a $0$ in row $2$ , so rows $2$ and $3$ are swapped, and then $- 1$ times the new row $2$ , which is $(0, 1 | 0, 0, 1, 0)$ , is added to row $4$ :

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

So $𝑘 = 2$ , and $𝐵$ has rows $(- 1, 1, 0, 0)$ and $(0, 0, - 1, 1)$ . Since $𝐵 𝐱_{0} = (- 1, - 2)$ , the system is

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

Check: $𝐱_{0}$ satisfies both equations, and $𝐮_{1}$ and $𝐮_{2}$ satisfy the homogeneous ones. Its solution set has two free variables, $𝑥_{2}$ and $𝑥_{4}$ , matching the two parameters of $𝐱_{0} + 𝑠 𝐮_{1} + 𝑡 𝐮_{2}$ . Part (a) of Exercise 3.1.41 found such a system by inspection; the procedure always works.

Exercise 3.4.47.challenge For

𝑛 \geq 0

, let

𝑝_{𝑛} \in {ℚ [𝑥]}_{\leq 𝑛}

be the polynomial with

𝑝_{𝑛} (𝑘) = 2^{𝑘}

for

𝑘 = 0, 1, \dots, 𝑛

. Show that

𝑝_{𝑛} (𝑛 + 1) =

2^{𝑛 + 1} -

1

Solution.

Uses. Theorem 3.4.24 (Polynomial interpolation), Definition 1.2.17 (Evaluation), Definition 1.2.16 (Degree), induction on $𝑛$

Hint 1. Compute

𝑝_{0}

𝑝_{1}

𝑝_{2}

and look for a pattern. Then consider the differences

𝑝_{𝑛} (𝑥 + 1) -

𝑝_{𝑛} (𝑥)

Hint 2. Show that there is a polynomial

𝑞

of degree at most

𝑛 - 1

with

𝑞 (𝑡) =

𝑝_{𝑛} (𝑡 + 1) -

𝑝_{𝑛} (𝑡)

for all

𝑡 \in ℚ

. What are its values at

0, 1, \dots, 𝑛 - 1

Hint 3. By uniqueness,

𝑞 = 𝑝_{𝑛 - 1}

. Now induct.

Sketch. Induction on

𝑛

;

𝑝_{0} = 1

gives

𝑝_{0} (1) = 1

. Expanding

{(𝑡 + 1)}^{𝑗}

by the binomial theorem,

𝑝_{𝑛} (𝑡 + 1) -

𝑝_{𝑛} (𝑡) =

𝑞 (𝑡)

for a polynomial

𝑞

of degree at most

𝑛 - 1

(the

𝑡^{𝑛}

terms cancel). Then

𝑞 (𝑘) =

2^{𝑘 + 1} -

2^{𝑘} =

2^{𝑘}

for

𝑘 = 0, \dots, 𝑛 - 1

, so

𝑞 = 𝑝_{𝑛 - 1}

by Theorem 3.4.24. Hence

𝑝_{𝑛} (𝑛 + 1) =

2^{𝑛} +

𝑝_{𝑛 - 1} (𝑛)

, and induction gives

2^{𝑛} + 2^{𝑛} - 1

The polynomials $𝑝_{𝑛}$ exist and are unique by Theorem 3.4.24, since $0, 1, \dots, 𝑛$ are distinct in $ℚ$ . We induct on $𝑛$ . For $𝑛 = 0$ , $𝑝_{0} = 1$ and $𝑝_{0} (1) = 1 = 2^{1} - 1$ .

Let $𝑛 \geq 1$ and write $𝑝_{𝑛} =$ $\sum_{𝑗 = 0}^{𝑛} 𝑎_{𝑗} 𝑥^{𝑗}$ . For $𝑡 \in ℚ$ , the binomial theorem gives

𝑝_{𝑛} (𝑡 + 1) - 𝑝_{𝑛} (𝑡) = \sum_{𝑗 = 0}^{𝑛} 𝑎_{𝑗} ({(𝑡 + 1)}^{𝑗} - 𝑡^{𝑗}) = \sum_{𝑗 = 1}^{𝑛} 𝑎_{𝑗} \sum_{𝑖 = 0}^{𝑗 - 1} (\binom{𝑗}{𝑖}) 𝑡^{𝑖} = \sum_{𝑖 = 0}^{𝑛 - 1} 𝑏_{𝑖} 𝑡^{𝑖},

where $𝑏_{𝑖} =$ $\sum_{𝑗 = 𝑖 + 1}^{𝑛} (\binom{𝑗}{𝑖}) 𝑎_{𝑗}$ . So with

𝑞 = 𝑏_{0} + 𝑏_{1} 𝑥 + \dots + 𝑏_{𝑛 - 1} 𝑥^{𝑛 - 1} \in {ℚ [𝑥]}_{\leq 𝑛 - 1}

we have $𝑞 (𝑡) =$ $𝑝_{𝑛} (𝑡 + 1) -$ $𝑝_{𝑛} (𝑡)$ for every $𝑡 \in ℚ$ . In particular, for $𝑘 = 0, 1, \dots, 𝑛 - 1$ ,

𝑞 (𝑘) = 𝑝_{𝑛} (𝑘 + 1) - 𝑝_{𝑛} (𝑘) = 2^{𝑘 + 1} - 2^{𝑘} = 2^{𝑘} .

By the uniqueness in Theorem 3.4.24 (with the $𝑛$ nodes $0, \dots, 𝑛 - 1$ ), $𝑞 = 𝑝_{𝑛 - 1}$ . Therefore, using the induction hypothesis $𝑝_{𝑛 - 1} (𝑛) = 2^{𝑛} - 1$ ,

𝑝_{𝑛} (𝑛 + 1) = 𝑝_{𝑛} (𝑛) + 𝑞 (𝑛) = 2^{𝑛} + 𝑝_{𝑛 - 1} (𝑛) = 2^{𝑛} + 2^{𝑛} - 1 = 2^{𝑛 + 1} - 1,

as desired. (For instance $𝑝_{2} = 1 + 𝑥 / 2 + 𝑥^{2} / 2$ takes the values $1, 2, 4$ at $0, 1, 2$ , and $𝑝_{2} (3) =$ $1 +$ $3 / 2 +$ $9 / 2 =$ $7$ .)

More practice

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