3.2 Gaussian Elimination

Every reader of this book has solved a system of equations by eliminating unknowns: subtract a multiple of one equation from another, and a variable disappears. Done by hand on small systems, this feels like common sense. Done on a system of 50 equations, or over $\mathbb{F}_2$ , or in a proof about all systems at once, it needs to be an algorithm, and we need to know that it never changes the answer. This section makes elimination precise, proves that it always reaches a standard shape, and shows how to read every solution from that shape.

3.2.1. Three moves that do not change the answer

Here is a system over $\mathbb{R}$ , solved the way one would solve it on paper: $\begin{aligned} x + 2y + z &= 4, \\ 2x + 4y + 3z &= 9, \\ x + 3y + z &= 5 . \end{aligned}$ Subtract twice the first equation from the second: $z = 1$ . Subtract the first from the third: $y = 1$ . Then the first equation gives $x = 4 - 2 - 1 = 1$ .

Only three kinds of move were used, or could reasonably be used: reorder the equations, multiply an equation by a nonzero number, and add a multiple of one equation to another. None of them looks at the names $x, y, z$ . Each acts on the coefficients and the right-hand side of whole equations, that is, on the rows of the augmented matrix. The first step above, for instance, replaces row 2, $(2, 4, 3 \mid 9)$ , by row 2 minus twice row 1, $(0, 0, 1 \mid 1)$ .

Not every move that looks harmless is safe. Multiplying an equation by $0$ turns it into $0 = 0$ , and a constraint silently disappears. So we list the allowed moves carefully.

An elementary row operation is a reversible move on the rows of a matrix: swap two rows, rescale one row by a nonzero scalar, or add a multiple of one row to a different row.

Definition 3.2.1 (Elementary row operations)

Let $F$ be a field and let $\mathbf{M} \in M_{m \times k}(F)$ have rows $\mathbf{r}_1, \dots, \mathbf{r}_m$ . An elementary row operation on $\mathbf{M}$ is one of the following.

(1) Swap two rows: for $i \neq j$ , exchange $\mathbf{r}_i$ and $\mathbf{r}_j$ . Notation: $R_i \leftrightarrow R_j$ .
(2) Scale a row: for an index $i$ and a scalar $c \in F$ with $c \neq 0$ , replace $\mathbf{r}_i$ by $c\mathbf{r}_i$ . Notation: $R_i \to cR_i$ .
(3) Replace a row by adding a multiple of another row: for indices $i \neq j$ and any $c \in F$ , replace $\mathbf{r}_i$ by $\mathbf{r}_i + c\mathbf{r}_j$ . Notation: $R_i \to R_i + cR_j$ .

In each case the rows not mentioned are left unchanged.

In words: (1) reorders, (2) rescales one row by a nonzero scalar, and (3) changes one row, row $i$ , using a different row $j$ , which itself stays as it was. We write $R_i \to R_i - cR_j$ for $R_i \to R_i + (-c)R_j$ . The notation $R_i$ refers to the current row $i$ at the moment the operation is performed.

Take $\mathbf{M} = \begin{pmatrix} 1 & 2 & 0 \\ 3 & 1 & 1 \end{pmatrix}$ over $\mathbb{R}$ . Then $R_1 \leftrightarrow R_2$ gives $\begin{pmatrix} 3 & 1 & 1 \\ 1 & 2 & 0 \end{pmatrix}$ , $R_1 \to -2R_1$ gives $\begin{pmatrix} -2 & -4 & 0 \\ 3 & 1 & 1 \end{pmatrix}$ , and $R_2 \to R_2 - 3R_1$ gives $\begin{pmatrix} 1 & 2 & 0 \\ 0 & -5 & 1 \end{pmatrix}$ . The degenerate case $m = 1$ is worth a glance: a one-row matrix admits no swap and no replacement, since both need two different rows, so its only elementary row operations are the scalings.

The minimal change that breaks the definition is to drop “ $c \neq 0$ ”. The move $R_2 \to 0R_2$ still replaces one row by a multiple of itself, but it sends $\begin{pmatrix} 1 & 2 & 0 \\ 3 & 1 & 1 \end{pmatrix}$ to $\begin{pmatrix} 1 & 2 & 0 \\ 0 & 0 & 0 \end{pmatrix}$ , and no move of any kind can recover the lost row $(3, 1, 1)$ from that matrix. The failing clause is $c \neq 0$ , and the damage is exactly irreversibility.

Warning. Perform operations one at a time. It is tempting to write “ $R_1 \to R_1 - R_2$ and $R_2 \to R_2 - R_1$ ” as one step, using the old rows in both. That is not a sequence of elementary row operations, and it can destroy information. On the system $x = 1$ , $x = 1$ it produces $0 = 0$ , $0 = 0$ , whose solution set is all of $F$ , not $\{ 1 \}$ . Done in order, the second operation uses the new row 1, $(0 \mid 0)$ , and leaves row 2 unchanged, so no information is lost.

Why these three and no others? They are exactly the moves of hand elimination, and each can be undone by a move of the same kind, which is what the theorem below needs. The condition $i \neq j$ in (3) is not fussiness: “add $c$ times row $i$ to row $i$ ” would be scaling by $1 + c$ , which is illegal when $c = -1$ (Exercise C1).

An elementary row operation acts on the rows, but it treats each column separately: the new entry in position $(i, l)$ is computed only from entries of column $l$ . We record this, because it will be used again and again.

Lemma 3.2.1 (Row operations act column by column)

Let $\mathbf{M} = [\, \mathbf{M}_1 \mid \mathbf{M}_2 \,] \in M_{m \times k}(F)$ be split into its first $k_1$ columns $\mathbf{M}_1$ and its remaining columns $\mathbf{M}_2$ . If an elementary row operation turns $\mathbf{M}$ into $\mathbf{M}' = [\, \mathbf{M}'_1 \mid \mathbf{M}'_2 \,]$ (split in the same place), then the same operation turns $\mathbf{M}_1$ into $\mathbf{M}'_1$ and $\mathbf{M}_2$ into $\mathbf{M}'_2$ . In particular, an elementary row operation turns a zero column into a zero column.

Proof. Let $m_{hl}$ be the entries of $\mathbf{M}$ and $m'_{hl}$ those of $\mathbf{M}'$ . For a swap $R_i \leftrightarrow R_j$ : $m'_{il} = m_{jl}$ , $m'_{jl} = m_{il}$ , and $m'_{hl} = m_{hl}$ for $h \neq i, j$ . For a scaling $R_i \to cR_i$ : $m'_{il} = c\,m_{il}$ , and other rows are unchanged. For a replacement $R_i \to R_i + cR_j$ : $m'_{il} = m_{il} + c\,m_{jl}$ , and other rows are unchanged. In each case, every entry of column $l$ of $\mathbf{M}'$ is computed from column $l$ of $\mathbf{M}$ alone, by the same rule for every $l$ . Hence applying the operation to $\mathbf{M}_1$ or to $\mathbf{M}_2$ separately gives $\mathbf{M}'_1$ and $\mathbf{M}'_2$ . If column $l$ of $\mathbf{M}$ is zero, each formula gives $0$ , since $c \cdot 0 = 0$ and $0 + c \cdot 0 = 0$ (Theorem 0.7.1).

For an augmented matrix, the lemma says: operating on $[\, \mathbf{A} \mid \mathbf{b} \,]$ is the same as operating on $\mathbf{A}$ and on $\mathbf{b}$ with the same moves. Now we name what sequences of moves produce.

Definition 3.2.2 (Row equivalence)

Let $\mathbf{A}, \mathbf{B} \in M_{m \times k}(F)$ . We say $\mathbf{A}$ is row equivalent to $\mathbf{B}$ if $\mathbf{B}$ can be obtained from $\mathbf{A}$ by a finite sequence of elementary row operations. The empty sequence is allowed, so every matrix is row equivalent to itself.

In Example (Row equivalence) of Chapter 0 we met a definition that looks different: $\mathbf{B} = \mathbf{E}\mathbf{A}$ for an invertible matrix $\mathbf{E}$ . In section 4 of this chapter we prove that the two definitions agree (Theorem 3.4.8), by writing each elementary row operation as multiplication by an invertible matrix. Until then, “row equivalent” means the definition above.

3.2.2. Row operations preserve solutions

Here is the promise from the start of the section, now as a theorem.

Theorem 3.2.2 (Row operations preserve solutions)

Let $F$ be a field.

(a) (Reversibility) If an elementary row operation turns $\mathbf{M}$ into $\mathbf{M}'$ , then an elementary row operation of the same type turns $\mathbf{M}'$ back into $\mathbf{M}$ .
(b) Row equivalence is an equivalence relation on $M_{m \times k}(F)$ .
(c) If $[\, \mathbf{A} \mid \mathbf{b} \,]$ and $[\, \mathbf{A}' \mid \mathbf{b}' \,]$ in $M_{m \times (n + 1)}(F)$ are row equivalent, then the systems $\mathbf{A}\mathbf{x} = \mathbf{b}$ and $\mathbf{A}'\mathbf{x} = \mathbf{b}'$ have the same solution set.

Idea. Reversibility is checked type by type, and the check for scaling is the only place where $c \neq 0$ is used. For (c), every equation of the new system is a combination of equations of the old one, so an old solution satisfies the new system. That gives one inclusion. Instead of repeating the argument backwards, reversibility gives the other inclusion for free.

Proof.

(a) A swap $R_i \leftrightarrow R_j$ is undone by the same swap. A scaling $R_i \to cR_i$ is undone by $R_i \to c^{-1}R_i$ , which is a legal scaling because $c \neq 0$ has an inverse $c^{-1} \neq 0$ in $F$ (Definition 0.7.1): the row becomes $c^{-1}(c\mathbf{r}_i) = \mathbf{r}_i$ . A replacement $R_i \to R_i + cR_j$ is undone by $R_i \to R_i - cR_j$ . Here we use $i \neq j$ : row $j$ was not changed by the first operation, so the second one gives $(\mathbf{r}_i + c\mathbf{r}_j) - c\mathbf{r}_j = \mathbf{r}_i$ .
(b) Reflexivity holds via the empty sequence. For symmetry, suppose operations $O_1, \dots, O_s$ , in this order, turn $\mathbf{A}$ into $\mathbf{B}$ . By (a), each $O_t$ has an undoing operation $O'_t$ . Then $O'_s, O'_{s-1}, \dots, O'_1$ , in this order, turn $\mathbf{B}$ back into $\mathbf{A}$ . For transitivity, if a sequence turns $\mathbf{A}$ into $\mathbf{B}$ and another turns $\mathbf{B}$ into $\mathbf{C}$ , performing the first and then the second turns $\mathbf{A}$ into $\mathbf{C}$ , and this is still a finite sequence.
(c) First suppose a single operation turns $[\, \mathbf{A} \mid \mathbf{b} \,]$ into $[\, \mathbf{A}' \mid \mathbf{b}' \,]$ . Let $S$ and $S'$ be the two solution sets. Write $\mathbf{r}_h$ for row $h$ of $\mathbf{A}$ , so that equation $h$ says $\mathbf{r}_h\mathbf{x} = b_h$ , where $\mathbf{r}_h\mathbf{x}$ is a $1 \times 1$ product. Let $\mathbf{s} \in S$ , so $\mathbf{r}_h\mathbf{s} = b_h$ for every $h$ . Each equation of the new system holds at $\mathbf{s}$ :

after $R_i \leftrightarrow R_j$ , the new equations are the old ones in another order;
after $R_i \to cR_i$ , the new equation $i$ is $(c\mathbf{r}_i)\mathbf{x} = cb_i$ , and $(c\mathbf{r}_i)\mathbf{s} = c(\mathbf{r}_i\mathbf{s}) = cb_i$ ;
after $R_i \to R_i + cR_j$ , the new equation $i$ is $(\mathbf{r}_i + c\mathbf{r}_j)\mathbf{x} = b_i + cb_j$ , and $(\mathbf{r}_i + c\mathbf{r}_j)\mathbf{s} = \mathbf{r}_i\mathbf{s} + c(\mathbf{r}_j\mathbf{s}) = b_i + cb_j$ , by Theorem 0.9.4.

The other equations are unchanged. Hence $\mathbf{s} \in S'$ , and $S \subseteq S'$ . By (a), a single operation turns $[\, \mathbf{A}' \mid \mathbf{b}' \,]$ back into $[\, \mathbf{A} \mid \mathbf{b} \,]$ , so the same argument gives $S' \subseteq S$ . Therefore $S = S'$ .

For a sequence of $s$ operations, the intermediate augmented matrices all have the same solution set, by the single-operation case applied $s$ times (formally, by induction on $s$ ). This proves (c).

This theorem is the license for everything that follows: we may transform a system as much as we like by row operations, and the solutions of the final system are the solutions of the original one. What it does not license is just as important.

Warning. Scaling by $0$ is not a row operation, and it changes the solution set. Over $\mathbb{R}$ , the system $x + y = 2$ , $x - y = 0$ has exactly one solution, $(1, 1)$ . Applying the illegal move $R_2 \to 0R_2$ gives $x + y = 2$ , $0 = 0$ , whose solutions $(2 - t, t)$ form a whole line. The inclusion $S \subseteq S'$ in the proof above still holds; what fails is reversibility, and with it $S' \subseteq S$ .

Warning. Column operations are not allowed. Operations on the columns of $[\, \mathbf{A} \mid \mathbf{b} \,]$ mix up the unknowns. The system $x + y = 3$ , $x - y = 1$ has the unique solution $(2, 1)$ . Adding column 1 to column 2 of its augmented matrix gives $\left[ \begin{array}{cc|c} 1 & 2 & 3 \\ 1 & 0 & 1 \end{array} \right]$ , the system $x + 2y = 3$ , $x = 1$ , whose only solution is $(1, 1)$ . Even swapping two columns of $\mathbf{A}$ swaps the corresponding entries of every solution.

3.2.3. Echelon forms

Row operations can change a system a great deal. We now choose a target: a shape of matrix from which the solutions can be read off with no further work. Look at the finished computation from the start of the section. After eliminating, the augmented matrix could be brought to $\left[ \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right],$ which says $x = 1$ , $y = 1$ , $z = 1$ outright. Not every system can be brought to this shape, since not every system has exactly one solution. The general target is a staircase.

For a nonzero row of a matrix, its leading entry is its first nonzero entry, reading from the left.

A matrix is in row echelon form when its nonzero rows come first and their leading entries step strictly to the right as we go down.

Definition 3.2.3 (Row echelon form)

A matrix $\mathbf{R} \in M_{m \times k}(F)$ is in row echelon form if:

(E1) there is an integer $r$ with $0 \le r \le m$ such that rows $1, \dots, r$ are nonzero and rows $r + 1, \dots, m$ are zero; and
(E2) if the leading entry of row $i$ lies in column $j_i$ , for $i = 1, \dots, r$ , then $j_1 < j_2 < \dots < j_r$ , strictly.

The leading entries of rows $1, \dots, r$ are the pivots of $\mathbf{R}$ , and the columns $j_1, \dots, j_r$ are its pivot columns.

In words: (E1) says zero rows sit at the bottom, and (E2) says each pivot lies strictly to the right of the pivot above it. Two consequences are used constantly. Each row contains at most one pivot, so there are at most $m$ pivots. And every entry below a pivot is zero: if $h > i$ , then row $h$ is zero or has its leading entry in column $j_h > j_i$ , so its entry in column $j_i$ is $0$ .

Definition 3.2.4 (Reduced row echelon form)

A matrix $\mathbf{R} \in M_{m \times k}(F)$ is in reduced row echelon form (RREF) if it is in row echelon form, with pivot columns $j_1 < \dots < j_r$ , and moreover:

(E3) every pivot equals $1$ : $r_{i j_i} = 1$ for $i = 1, \dots, r$ ; and
(E4) every pivot is the only nonzero entry in its column: $r_{h j_i} = 0$ for all $h \neq i$ .

In words: (E3) normalizes the pivots, and (E4) clears the entries above each pivot as well as below. Together they say that the pivot column $j_i$ is the standard basis vector $\mathbf{e}_i \in F^m$ .

Example (Echelon or not?)

Decide which of the following real matrices are in row echelon form, and which are in reduced row echelon form. Give the pivot columns where they exist. $\mathbf{P} = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 0 & -1 \\ 0 & 0 & 0 \end{pmatrix}, \quad \mathbf{Q} = \begin{pmatrix} 1 & 5 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{pmatrix}, \quad \mathbf{T} = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}, \quad \mathbf{Z} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}.$

Solution. $\mathbf{P}$ is in row echelon form: rows 1 and 2 are nonzero, row 3 is zero, and the leading entries lie in columns $1 < 3$ . The pivot columns are 1 and 3. It is not reduced: the pivot $2$ is not $1$ , failing (E3), and column 3 has the nonzero entry $3$ above the pivot $-1$ , failing (E4).

$\mathbf{Q}$ is in reduced row echelon form, with pivot columns 1 and 3. Both pivots are $1$ , and columns 1 and 3 are $\mathbf{e}_1$ and $\mathbf{e}_2$ . The entries $5, 2, 3$ in the nonpivot columns 2 and 4 are allowed to be anything.

$\mathbf{T}$ is not in row echelon form. Its leading entries lie in columns $1, 3, 2$ , and $3 < 2$ fails, so (E2) fails. Swapping rows 2 and 3 would repair it.

$\mathbf{Z}$ is in reduced row echelon form, with $r = 0$ : there are no pivots, and (E2)–(E4) hold vacuously. This degenerate case matters, because the zero matrix must have an RREF too, and it is itself.

For $\mathbf{Q}$ , a minimal change gives a nonexample: replacing the $0$ in position $(1, 3)$ by $4$ keeps (E1)–(E3), but column 3 now has the nonzero entry $4$ above its pivot, so (E4) fails.

Why insist on the reduced form, when row echelon form already allows back substitution? Because a system in reduced form needs no substitution: each pivot variable appears in exactly one equation. More importantly, the reduced form turns out to be unique: a matrix is row equivalent to exactly one matrix in RREF, however the operations are chosen. That is proved in the next section, and it is what makes later definitions, such as the rank, independent of choices. Row echelon form is not unique, as the warning after the worked example shows.

Quick check. Is $\begin{pmatrix} 1 & 2 & 0 & -1 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 \end{pmatrix}$ in reduced row echelon form? If it is the coefficient matrix of a homogeneous system in $x_1, x_2, x_3, x_4$ , which unknowns correspond to pivot columns?

Solution. Yes. Row 3 is the only zero row and it is last; the leading entries lie in columns $1 < 3$ ; both are $1$ ; and columns 1 and 3 are $\mathbf{e}_1$ and $\mathbf{e}_2$ . The pivot columns are 1 and 3, so the unknowns $x_1$ and $x_3$ correspond to pivots, and $x_2, x_4$ do not.

3.2.4. Gauss–Jordan elimination

We now show that every matrix can be brought to reduced row echelon form. The procedure works through the columns from left to right, keeping a count $r$ of the pivots found so far.

Algorithm. Gauss–Jordan elimination. Input: $\mathbf{M} \in M_{m \times k}(F)$ . Set $r = 0$ . For $l = 1, 2, \dots, k$ in turn:

Look for a row $h$ with $h > r$ whose entry in column $l$ is nonzero. If there is none, column $l$ gets no pivot; go on to the next $l$ .
Otherwise choose such an $h$ . If $h \neq r + 1$ , perform $R_{r+1} \leftrightarrow R_h$ .
Let $a \neq 0$ be the entry now in position $(r + 1, l)$ . Perform $R_{r+1} \to a^{-1}R_{r+1}$ , so that this entry becomes $1$ .
For every row $g \neq r + 1$ whose entry $c$ in column $l$ is nonzero, perform $R_g \to R_g - cR_{r+1}$ .
Increase $r$ by $1$ .

Output: the final matrix, which is in reduced row echelon form, with $r$ pivots.

Step 2 involves a choice: any nonzero entry will do. By hand, we choose one that avoids fractions. If we skip the scaling in step 3 and clear only the entries below the pivot $a$ , by $R_g \to R_g - ca^{-1}R_{r+1}$ for the rows $g > r + 1$ , the output is a row echelon form instead; this cheaper variant is Gaussian elimination, and it is followed by back substitution.

Theorem 3.2.3 (Existence of the reduced row echelon form)

Let $F$ be a field. Every matrix $\mathbf{M} \in M_{m \times k}(F)$ is row equivalent to a matrix in reduced row echelon form.

Idea. We prove that the algorithm works, by induction on the number $l$ of columns processed. The invariant is: the first $l$ columns of the current matrix form a matrix in RREF. When a new column is processed, all the operations involve only rows below the pivots found so far, or add multiples of the new pivot row, which is zero in the first $l$ columns. So the part already built is never disturbed. After all $k$ columns, the whole matrix is in RREF.

Proof. For $0 \le l \le k$ , let $P(l)$ be the statement: there is a matrix $\mathbf{M}_l$ row equivalent to $\mathbf{M}$ and an integer $r \ge 0$ such that the $m \times l$ matrix $\mathbf{L}$ formed by the first $l$ columns of $\mathbf{M}_l$ is in reduced row echelon form with exactly $r$ nonzero rows. We prove $P(l)$ for all $l$ by induction (Theorem 0.2.7). For $l = 0$ take $\mathbf{M}_0 = \mathbf{M}$ and $r = 0$ ; there are no columns, so there is nothing to check.

Suppose $P(l)$ holds for some $l < k$ , with $\mathbf{M}_l$ , $\mathbf{L}$ , and $r$ as described, and let $j_1 < \dots < j_r \le l$ be the pivot columns of $\mathbf{L}$ . By (E1) for $\mathbf{L}$ , rows $r + 1, \dots, m$ of $\mathbf{M}_l$ are zero in columns $1, \dots, l$ . Let $\mathbf{L}'$ denote the first $l + 1$ columns of the matrix we are about to construct.

Case 1: every entry of column $l + 1$ of $\mathbf{M}_l$ in rows $h > r$ is zero (this includes the case $r = m$ ). Put $\mathbf{M}_{l+1} = \mathbf{M}_l$ . Rows $r + 1, \dots, m$ of $\mathbf{L}'$ are zero, and rows $1, \dots, r$ are nonzero with the same leading entries as in $\mathbf{L}$ , which lie in columns $\le l$ . So (E1)–(E3) hold for $\mathbf{L}'$ with the same $r$ and pivot columns, and so does (E4), since the pivot columns of $\mathbf{L}'$ are those of $\mathbf{L}$ and are unchanged. Hence $\mathbf{L}'$ is in RREF and $P(l + 1)$ holds.

Case 2: some row $h > r$ has a nonzero entry in column $l + 1$ . Then $r + 1 \le h \le m$ . Perform steps 2, 3, and 4 of the algorithm with this $h$ and with column $l + 1$ ; call the result $\mathbf{M}_{l+1}$ . It is row equivalent to $\mathbf{M}_l$ , hence to $\mathbf{M}$ , by Theorem 3.2.2 (b).

These operations do not change columns $1, \dots, l$ . Indeed, the swap in step 2 and the scaling in step 3 only move or rescale rows $h$ and $r + 1$ , which are both zero in those columns. Each replacement $R_g \to R_g - cR_{r+1}$ in step 4 adds a multiple of row $r + 1$ , which is still zero in columns $1, \dots, l$ . So the first $l$ columns of $\mathbf{M}_{l+1}$ form the matrix $\mathbf{L}$ . In column $l + 1$ , step 3 makes the entry in row $r + 1$ equal to $1$ , and each replacement in step 4 makes the entry of row $g$ equal to $c - c \cdot 1 = 0$ without changing any other row. So column $l + 1$ of $\mathbf{M}_{l+1}$ is $\mathbf{e}_{r+1}$ .

We check that $\mathbf{L}'$ is in RREF with $r + 1$ nonzero rows. Rows $1, \dots, r$ of $\mathbf{L}'$ have the same leading entries as in $\mathbf{L}$ , in columns $j_1 < \dots < j_r \le l$ . Row $r + 1$ is zero in columns $1, \dots, l$ and has a $1$ in column $l + 1$ , so its leading entry is in column $j_{r+1} \mathrel{:=} l + 1 > j_r$ . Rows $r + 2, \dots, m$ are zero in columns $1, \dots, l$ and in column $l + 1$ , so they are zero. This gives (E1) and (E2). The pivots are $1$ , by (E3) for $\mathbf{L}$ and the construction, so (E3) holds. For (E4), the columns $j_1, \dots, j_r$ are unchanged from $\mathbf{L}$ , and column $l + 1$ is $\mathbf{e}_{r+1}$ . Hence $P(l + 1)$ holds.

By induction $P(k)$ holds: $\mathbf{M}_k$ is row equivalent to $\mathbf{M}$ , and its first $k$ columns, which are all of $\mathbf{M}_k$ , form a matrix in reduced row echelon form. This proves the theorem.

The proof is also the correctness proof of the algorithm: the matrix $\mathbf{M}_l$ is the state of the computation after column $l$ . Note where the field axioms were used. Step 3 divides by $a \neq 0$ , which needs (F8), and nothing else in the argument depends on which field we work over.

Example (Gauss–Jordan on a

3 \times 4

system)

Solve the following system over $\mathbb{R}$ by Gauss–Jordan elimination, naming each operation: $\begin{aligned} 2x_2 - 2x_3 + x_4 &= 3, \\ x_1 + x_2 + x_3 \phantom{{} + x_4} &= 3, \\ 2x_1 + x_2 + 3x_3 + x_4 &= 3 . \end{aligned}$

Solution. We work on the augmented matrix. Column 1. Row 1 has a $0$ there, so we bring up row 2, whose entry is already $1$ . Then we clear the rest of column 1. $\begin{aligned} \left[ \begin{array}{cccc|c} 0 & 2 & -2 & 1 & 3 \\ 1 & 1 & 1 & 0 & 3 \\ 2 & 1 & 3 & 1 & 3 \end{array} \right] &\xrightarrow{R_1 \leftrightarrow R_2} \left[ \begin{array}{cccc|c} 1 & 1 & 1 & 0 & 3 \\ 0 & 2 & -2 & 1 & 3 \\ 2 & 1 & 3 & 1 & 3 \end{array} \right] \\ &\xrightarrow{R_3 \to R_3 - 2R_1} \left[ \begin{array}{cccc|c} 1 & 1 & 1 & 0 & 3 \\ 0 & 2 & -2 & 1 & 3 \\ 0 & -1 & 1 & 1 & -3 \end{array} \right] \end{aligned}$ Column 2. The candidates below row 1 are $2$ and $-1$ . Choosing $-1$ avoids fractions, so we swap it up and scale. $\xrightarrow{R_2 \leftrightarrow R_3} \left[ \begin{array}{cccc|c} 1 & 1 & 1 & 0 & 3 \\ 0 & -1 & 1 & 1 & -3 \\ 0 & 2 & -2 & 1 & 3 \end{array} \right] \xrightarrow{R_2 \to -R_2} \left[ \begin{array}{cccc|c} 1 & 1 & 1 & 0 & 3 \\ 0 & 1 & -1 & -1 & 3 \\ 0 & 2 & -2 & 1 & 3 \end{array} \right]$ Now clear column 2 above and below the pivot. $\xrightarrow{R_1 \to R_1 - R_2} \left[ \begin{array}{cccc|c} 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & -1 & -1 & 3 \\ 0 & 2 & -2 & 1 & 3 \end{array} \right] \xrightarrow{R_3 \to R_3 - 2R_2} \left[ \begin{array}{cccc|c} 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & -1 & -1 & 3 \\ 0 & 0 & 0 & 3 & -3 \end{array} \right]$ Column 3. The only entry below row 2 is $0$ , so column 3 gets no pivot. Column 4. The entry $3$ in row 3 becomes the pivot. $\begin{aligned} &\xrightarrow{R_3 \to \frac13 R_3} \left[ \begin{array}{cccc|c} 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & -1 & -1 & 3 \\ 0 & 0 & 0 & 1 & -1 \end{array} \right] \\ &\xrightarrow{R_1 \to R_1 - R_3} \left[ \begin{array}{cccc|c} 1 & 0 & 2 & 0 & 1 \\ 0 & 1 & -1 & -1 & 3 \\ 0 & 0 & 0 & 1 & -1 \end{array} \right] \\ &\xrightarrow{R_2 \to R_2 + R_3} \left[ \begin{array}{cccc|c} 1 & 0 & 2 & 0 & 1 \\ 0 & 1 & -1 & 0 & 2 \\ 0 & 0 & 0 & 1 & -1 \end{array} \right] \end{aligned}$ Column 5. No rows remain below row 3, so we stop. The final matrix is in RREF, with pivot columns 1, 2, and 4. It is the system $x_1 + 2x_3 = 1, \qquad x_2 - x_3 = 2, \qquad x_4 = -1,$ which by Theorem 3.2.2 has the same solutions as the original. The unknown $x_3$ is unconstrained; writing $x_3 = t$ , the solutions are $(1 - 2t,\ 2 + t,\ t,\ -1) = (1, 2, 0, -1) + t(-2, 1, 1, 0), \qquad t \in \mathbb{R} .$ Check: $(1, 2, 0, -1)$ gives $4 + 0 - 1 = 3$ , $1 + 2 + 0 = 3$ , and $2 + 2 + 0 - 1 = 3$ ; and $(-2, 1, 1, 0)$ gives $2 - 2 + 0 = 0$ , $-2 + 1 + 1 = 0$ , and $-4 + 1 + 3 + 0 = 0$ . This is the “particular plus homogeneous” form of Theorem 3.1.3.

The same computation can be carried out in exact arithmetic. In the online version the cell below can be edited and run, which is a good way to check a hand computation.

from sympy import Matrix

M = Matrix([
    [0, 2, -2, 1, 3],
    [1, 1,  1, 0, 3],
    [2, 1,  3, 1, 3],
])
R, pivots = M.rref()   # the RREF and the (0-based) pivot columns
print(R)
print("pivot columns:", [j + 1 for j in pivots])

Warning. Echelon forms are not unique; only the reduced form is. Different choices in step 2 give different intermediate matrices. For $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ over $\mathbb{R}$ , the operation $R_2 \to R_2 - 3R_1$ gives the row echelon form $\begin{pmatrix} 1 & 2 \\ 0 & -2 \end{pmatrix}$ . Starting instead with $R_1 \leftrightarrow R_2$ and then $R_2 \to R_2 - \frac13 R_1$ gives the row echelon form $\begin{pmatrix} 3 & 4 \\ 0 & \frac23 \end{pmatrix}$ . Both continue to the same RREF, $\mathbf{I}_2$ . That this always happens is the theorem of the next section; until it is proved, “the” RREF of a matrix is not yet justified.

3.2.5. Reading off the solutions

Once $[\, \mathbf{A} \mid \mathbf{b} \,]$ is in reduced row echelon form, the example shows what to do: a pivot in the last column signals a contradiction, and otherwise the unknowns without pivots can be chosen freely. We name the two kinds of unknowns.

Suppose $[\, \mathbf{A} \mid \mathbf{b} \,]$ , with $\mathbf{A} \in M_{m \times n}(F)$ , is row equivalent to a matrix $[\, \mathbf{R} \mid \mathbf{c} \,]$ in reduced row echelon form, where $\mathbf{R}$ is $m \times n$ . For $l \le n$ , the unknown $x_l$ is a pivot variable if $l$ is a pivot column of $[\, \mathbf{R} \mid \mathbf{c} \,]$ , and a free variable otherwise. (By the uniqueness theorem of the next section, this does not depend on which sequence of operations was used.)

Theorem 3.2.4 (Reading solutions from the RREF)

Let $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{b} \in F^m$ , and suppose $[\, \mathbf{A} \mid \mathbf{b} \,]$ is row equivalent to a matrix $[\, \mathbf{R} \mid \mathbf{c} \,]$ in reduced row echelon form. Let $r_{il}$ be the entries of $\mathbf{R}$ and $\mathbf{c} = (c_1, \dots, c_m)$ .

(a) $\mathbf{A}\mathbf{x} = \mathbf{b}$ is inconsistent if and only if the last column, column $n + 1$ , is a pivot column of $[\, \mathbf{R} \mid \mathbf{c} \,]$ , that is, some row of $[\, \mathbf{R} \mid \mathbf{c} \,]$ is $(0 \ \cdots \ 0 \mid 1)$ .
(b) Suppose there is no pivot in the last column. Let $j_1 < \dots < j_r$ be the pivot columns. Then for every choice of scalars $t_l \in F$ , one for each free variable $x_l$ , there is exactly one solution with $x_l = t_l$ for all free $l$ , namely the one with $x_{j_i} = c_i - \sum_{l \text{ free}} r_{il}\, t_l \qquad (i = 1, \dots, r).$ In particular, setting every free variable to $0$ gives the solution $\mathbf{p}$ with $p_{j_i} = c_i$ and all other entries $0$ .
(c) A consistent system $\mathbf{A}\mathbf{x} = \mathbf{b}$ has exactly one solution if and only if it has no free variables, that is, each of the columns $1, \dots, n$ is a pivot column.

Proof. By Theorem 3.2.2 (c), $\mathbf{A}\mathbf{x} = \mathbf{b}$ has the same solution set as $\mathbf{R}\mathbf{x} = \mathbf{c}$ , so we work with the latter.

(a, $\Leftarrow$ ) If row $i$ of $[\, \mathbf{R} \mid \mathbf{c} \,]$ has its pivot in column $n + 1$ , then its first $n$ entries are $0$ and $c_i = 1$ by (E3). Equation $i$ reads $0 = 1$ , which is false in any field (Definition 0.7.1). So there is no solution.

(b) Suppose no pivot lies in column $n + 1$ . Then all pivots of $[\, \mathbf{R} \mid \mathbf{c} \,]$ lie in columns $j_1, \dots, j_r \le n$ . By (E1), rows $r + 1, \dots, m$ of $[\, \mathbf{R} \mid \mathbf{c} \,]$ are zero, so the corresponding equations read $0 = 0$ and hold for every $\mathbf{x}$ . For $i \le r$ , row $i$ of $\mathbf{R}$ has $r_{i j_i} = 1$ by (E3) and $r_{i j_h} = 0$ for $h \neq i$ by (E4). So equation $i$ reads $x_{j_i} + \sum_{l \text{ free}} r_{il}\, x_l = c_i .$ Hence $\mathbf{x}$ is a solution if and only if $x_{j_i} = c_i - \sum_{l \text{ free}} r_{il} x_l$ for $i = 1, \dots, r$ . Each unknown is either a pivot variable or a free variable, not both. So once the free variables are given the values $t_l$ , these equations determine every pivot variable uniquely, and the resulting vector is a solution. This proves (b).
(a, $\Rightarrow$ ) This is the contrapositive of what (b) just showed: if there is no pivot in the last column, then choosing all $t_l = 0$ produces a solution, so the system is consistent.
(c) By (a), a consistent system has no pivot in the last column, so (b) applies. If there are no free variables, (b) gives exactly one solution. If $x_l$ is free, the choices $t_l = 0$ and $t_l = 1$ , with all other free variables $0$ , give two solutions whose $l$ -th entries differ, since $0 \neq 1$ . This proves (c).

In Example (Gauss–Jordan on a $3 \times 4$ system) the pivot columns were 1, 2, 4, the free variable was $x_3$ , and (b) gave $x_1 = 1 - 2t$ , $x_2 = 2 + t$ , $x_4 = -1$ , with $\mathbf{p} = (1, 2, 0, -1)$ . The same recipe works over any field, and over a finite field the free variables can take only finitely many values.

Example (Elimination over

\mathbb{F}_2

)

Solve the following system over $\mathbb{F}_2$ : $x_1 + x_2 + x_4 = 1, \qquad x_2 + x_3 + x_4 = 0, \qquad x_1 + x_3 + x_4 = 1 .$ How many solutions are there? What changes if the same equations are read over $\mathbb{R}$ ?

Solution. In $\mathbb{F}_2$ , $-1 = 1$ , so $R_i \to R_i - R_j$ is the same operation as $R_i \to R_i + R_j$ , and every nonzero pivot is already $1$ . Column 1 has its pivot in row 1; clear row 3. Column 2 has its pivot in row 2; clear rows 3 and 1. $\left[ \begin{array}{cccc|c} 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \end{array} \right] \xrightarrow{R_3 \to R_3 + R_1} \left[ \begin{array}{cccc|c} 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{array} \right] \xrightarrow{R_3 \to R_3 + R_2} \left[ \begin{array}{cccc|c} 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$ $\xrightarrow{R_1 \to R_1 + R_2} \left[ \begin{array}{cccc|c} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$ In the row $R_3 + R_1$ , the entries $1 + 1$ became $0$ , and in $R_3 + R_2$ the entry in column 3 is $1 + 1 = 0$ . Column 3 has only a $0$ below row 2, so no pivot. Column 4 has its pivot in row 3; row 1 already has a $0$ there, so only row 2 needs clearing. $\xrightarrow{R_2 \to R_2 + R_3} \left[ \begin{array}{cccc|c} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right]$ This is in RREF, with pivot columns 1, 2, 4 and no pivot in the last column, so the system is consistent by Theorem 3.2.4 (a). The free variable is $x_3 = t$ , and part (b) gives $x_1 = 1 - t = 1 + t$ , $x_2 = -t = t$ , $x_4 = 0$ . Since $t \in \mathbb{F}_2 = \{ 0, 1 \}$ , there are exactly two solutions: $(1, 0, 0, 0) \quad \text{and} \quad (0, 1, 1, 0).$ Check the second: $0 + 1 + 0 = 1$ , $1 + 1 + 0 = 0$ , $0 + 1 + 0 = 1$ in $\mathbb{F}_2$ .

Over $\mathbb{R}$ the first step is $R_3 \to R_3 - R_1$ , giving row 3 $= (0, -1, 1, 0 \mid 0)$ , and adding row 2 then gives $(0, 0, 2, 1 \mid 0)$ . The entry $2$ is nonzero in $\mathbb{R}$ , so column 3 now gets a pivot. Completing the reduction gives pivot columns 1, 2, 3, free variable $x_4$ , and infinitely many real solutions. The same equations lead to different pivot patterns over different fields, because $1 + 1 = 0$ in one and not in the other.

When a coefficient depends on a parameter, whether a column gets a pivot can depend on the parameter too. Then the reduction splits into cases, one for each answer to “is this entry zero?”.

Example (A system with a parameter)

For which $k \in \mathbb{R}$ does the system $x + ky = 1$ , $kx + y = 1$ have no solution, exactly one solution, or infinitely many? Find the solutions when they exist.

Solution. The entry in position $(1, 1)$ is $1$ for every $k$ , so it is a pivot with no case distinction: $\left[ \begin{array}{cc|c} 1 & k & 1 \\ k & 1 & 1 \end{array} \right] \xrightarrow{R_2 \to R_2 - kR_1} \left[ \begin{array}{cc|c} 1 & k & 1 \\ 0 & 1 - k^2 & 1 - k \end{array} \right].$ (For $k = 0$ this operation changes nothing, which is allowed.) Column 2 gets a pivot in row 2 exactly when $1 - k^2 = (1 - k)(1 + k)$ is nonzero, and only then may we scale by its inverse. So we split into cases.

Case $k \neq \pm 1$ . Then $1 - k^2 \neq 0$ , and $R_2 \to (1 - k^2)^{-1}R_2$ turns row 2 into $(0, 1 \mid \tfrac{1}{1 + k})$ , since $\tfrac{1 - k}{(1 - k)(1 + k)} = \tfrac{1}{1 + k}$ . Then $R_1 \to R_1 - kR_2$ turns row 1 into $(1, 0 \mid 1 - \tfrac{k}{1 + k}) = (1, 0 \mid \tfrac{1}{1 + k})$ . The RREF is $[\, \mathbf{I}_2 \mid \mathbf{c} \,]$ with $\mathbf{c} = (\tfrac{1}{1 + k}, \tfrac{1}{1 + k})$ , and by Theorem 3.2.4 (c) this is the only solution. Check: $\tfrac{1}{1 + k} + \tfrac{k}{1 + k} = 1$ for both equations.

Case $k = 1$ . Row 2 is $(0, 0 \mid 0)$ , and $\left[ \begin{array}{cc|c} 1 & 1 & 1 \\ 0 & 0 & 0 \end{array} \right]$ is in RREF with pivot column 1. The free variable is $y = t$ , and Theorem 3.2.4 (b) gives the solutions $(1 - t, t)$ , $t \in \mathbb{R}$ : infinitely many.

Case $k = -1$ . Row 2 is $(0, 0 \mid 2)$ , and $R_2 \to \tfrac12 R_2$ makes it $(0, 0 \mid 1)$ . The last column is a pivot column, so the system is inconsistent by Theorem 3.2.4 (a). Directly: $x - y = 1$ and $-x + y = 1$ add up to $0 = 2$ .

Hence there is no solution for $k = -1$ , there are infinitely many for $k = 1$ , and there is exactly one otherwise. The trap is to scale by $(1 - k^2)^{-1}$ before asking whether $1 - k^2$ is zero: that step silently assumes $k \neq \pm 1$ , and loses exactly the two interesting cases.

3.2.6. More unknowns than equations

Counting pivots gives a first general theorem. A matrix with $m$ rows has at most $m$ pivots, one per nonzero row. If there are more unknowns than that, some unknown must be free.

Corollary 3.2.5 (More unknowns than equations)

Let $\mathbf{A} \in M_{m \times n}(F)$ with $n > m$ .

(a) The homogeneous system $\mathbf{A}\mathbf{x} = \mathbf{0}$ has a nontrivial solution.
(b) Consequently, every list of $n$ vectors in $F^m$ with $n > m$ is linearly dependent.

Proof.

(a) By Theorem 3.2.3, $[\, \mathbf{A} \mid \mathbf{0} \,]$ is row equivalent to a matrix $[\, \mathbf{R} \mid \mathbf{c} \,]$ in RREF. By Lemma 3.2.1, each operation keeps the last column zero, so $\mathbf{c} = \mathbf{0}$ , and the last column is not a pivot column. Each pivot is the leading entry of a different row, so there are at most $m$ pivots, hence at most $m < n$ pivot columns among the first $n$ columns. So some $x_l$ is a free variable. By Theorem 3.2.4 (b), with $t_l = 1$ and every other free variable $0$ , there is a solution whose $l$ -th entry is $1 \neq 0$ . This solution is nontrivial.
(b) Let $\mathbf{v}_1, \dots, \mathbf{v}_n \in F^m$ and let $\mathbf{A} \in M_{m \times n}(F)$ have these columns. By (a) there is $\mathbf{x} \neq \mathbf{0}$ with $\mathbf{A}\mathbf{x} = \mathbf{0}$ , and by Theorem 0.9.3 this says $x_1\mathbf{v}_1 + \dots + x_n\mathbf{v}_n = \mathbf{0}$ with $x_1, \dots, x_n$ not all zero. So the list is linearly dependent.

Part (b) is not new: since $\dim F^m = m$ , it is also a case of Theorem 1.6.3, which rests on the Steinitz Exchange Theorem (Theorem 1.6.1). The proof here is independent of that one. It uses nothing from Chapter 1 beyond the definition of independence, only elimination and a count of pivots. Two proofs by different routes give some confidence that the dimension theory of Chapter 1 and the computations of this chapter will fit together, and the rest of the chapter makes that fit exact.

3.2.7. Exercises

A. Check your understanding

Exercise (A1)

(a) List the three types of elementary row operation, including the conditions on the scalar and on the indices.
(b) Determine whether the following statement is true: “every matrix in row echelon form is in reduced row echelon form.” Justify your answer.
(c) Determine whether the following statement is true: “if the RREF of $[\, \mathbf{A} \mid \mathbf{b} \,]$ has a zero row, then $\mathbf{A}\mathbf{x} = \mathbf{b}$ is inconsistent.” Justify your answer.
(d) Determine whether the following statement is true: “a homogeneous system of 3 equations in 5 unknowns over $\mathbb{R}$ has infinitely many solutions.” Justify your answer.
(e) Explain why swapping two columns of $\mathbf{A}$ in $[\, \mathbf{A} \mid \mathbf{b} \,]$ is not a safe step when solving $\mathbf{A}\mathbf{x} = \mathbf{b}$ .

Solution.

(a) $R_i \leftrightarrow R_j$ with $i \neq j$ ; $R_i \to cR_i$ with $c \neq 0$ ; $R_i \to R_i + cR_j$ with $i \neq j$ and any $c \in F$ .
(b) False. $\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$ is in row echelon form, but its first pivot is $2 \neq 1$ , so (E3) fails; its second column also has a nonzero entry above the pivot, so (E4) fails.
(c) False. A zero row is the equation $0 = 0$ , which every vector satisfies. Inconsistency means a row $(0 \ \cdots \ 0 \mid 1)$ (Theorem 3.2.4 (a)). For example $\left[ \begin{array}{c|c} 1 & 1 \\ 0 & 0 \end{array} \right]$ is the consistent system $x = 1$ , $0 = 0$ .
(d) True. By Corollary 3.2.5 ( $5 > 3$ ) there is a nontrivial solution $\mathbf{h}$ , and since $\mathbb{R}$ is infinite, the multiples $c\mathbf{h}$ ( $c \in \mathbb{R}$ ) are infinitely many distinct solutions, as in Exercise (C1: How many solutions?).
(e) It swaps the roles of two unknowns: $\mathbf{s}$ solves the new system exactly when the vector obtained from $\mathbf{s}$ by swapping those two entries solves the old one. So the solution set changes, unless the swap happens to fix it. For instance $x = 1$ , $y = 2$ becomes $y = 1$ , $x = 2$ .

B. Practice

Exercise (B1: Reduce and solve)

Reduce the augmented matrix of each system over $\mathbb{R}$ to reduced row echelon form, naming each operation. Hence decide whether the system is consistent, and if so, describe all solutions.

(a) $x_1 + 2x_2 - x_3 = 1$ , $2x_1 + 5x_2 + x_3 = 4$ , $x_1 + 3x_2 + 2x_3 = 4$ .
(b) $x_1 + x_2 + 2x_3 = 3$ , $2x_1 + 3x_2 + 5x_3 = 7$ , $x_1 + 2x_2 + 4x_3 = 5$ .
(c) $x_1 - x_2 + 2x_3 + x_4 = 2$ , $2x_1 - 2x_2 + 5x_3 + 4x_4 = 5$ , $-x_1 + x_2 - x_3 + x_4 = -1$ .

Solution.

(a) $\left[ \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 2 & 5 & 1 & 4 \\ 1 & 3 & 2 & 4 \end{array} \right] \xrightarrow{R_2 \to R_2 - 2R_1} \left[ \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 1 & 3 & 2 \\ 1 & 3 & 2 & 4 \end{array} \right] \xrightarrow{R_3 \to R_3 - R_1} \left[ \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 1 & 3 & 2 \\ 0 & 1 & 3 & 3 \end{array} \right]$ $\xrightarrow{R_1 \to R_1 - 2R_2} \left[ \begin{array}{ccc|c} 1 & 0 & -7 & -3 \\ 0 & 1 & 3 & 2 \\ 0 & 1 & 3 & 3 \end{array} \right] \xrightarrow{R_3 \to R_3 - R_2} \left[ \begin{array}{ccc|c} 1 & 0 & -7 & -3 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 1 \end{array} \right]$ Column 3 gets no pivot. Column 4 has its pivot in row 3: $\xrightarrow{R_1 \to R_1 + 3R_3} \left[ \begin{array}{ccc|c} 1 & 0 & -7 & 0 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 1 \end{array} \right] \xrightarrow{R_2 \to R_2 - 2R_3} \left[ \begin{array}{ccc|c} 1 & 0 & -7 & 0 \\ 0 & 1 & 3 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right].$ The last column is a pivot column, so by Theorem 3.2.4 (a) the system is inconsistent. (Row 3 already said $0 = 1$ before the last two operations.)
(b) $\left[ \begin{array}{ccc|c} 1 & 1 & 2 & 3 \\ 2 & 3 & 5 & 7 \\ 1 & 2 & 4 & 5 \end{array} \right] \xrightarrow{R_2 \to R_2 - 2R_1} \left[ \begin{array}{ccc|c} 1 & 1 & 2 & 3 \\ 0 & 1 & 1 & 1 \\ 1 & 2 & 4 & 5 \end{array} \right] \xrightarrow{R_3 \to R_3 - R_1} \left[ \begin{array}{ccc|c} 1 & 1 & 2 & 3 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 2 & 2 \end{array} \right]$ $\begin{aligned} &\xrightarrow{R_1 \to R_1 - R_2} \left[ \begin{array}{ccc|c} 1 & 0 & 1 & 2 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 2 & 2 \end{array} \right] \\ &\xrightarrow{R_3 \to R_3 - R_2} \left[ \begin{array}{ccc|c} 1 & 0 & 1 & 2 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right] \\ &\xrightarrow{R_1 \to R_1 - R_3} \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right] \\ &\xrightarrow{R_2 \to R_2 - R_3} \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right]. \end{aligned}$ Columns 1, 2, 3 are pivot columns and the last column is not, so by Theorem 3.2.4 (c) there is exactly one solution, $(1, 0, 1)$ . Check: $1 + 0 + 2 = 3$ , $2 + 0 + 5 = 7$ , $1 + 0 + 4 = 5$ .
(c) $\begin{aligned} \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2 \\ 2 & -2 & 5 & 4 & 5 \\ -1 & 1 & -1 & 1 & -1 \end{array} \right] &\xrightarrow{R_2 \to R_2 - 2R_1} \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2 \\ 0 & 0 & 1 & 2 & 1 \\ -1 & 1 & -1 & 1 & -1 \end{array} \right] \\ &\xrightarrow{R_3 \to R_3 + R_1} \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 & 1 \end{array} \right] \end{aligned}$ Column 2 has only zeros below row 1, so no pivot. Column 3 has its pivot in row 2: $\xrightarrow{R_1 \to R_1 - 2R_2} \left[ \begin{array}{cccc|c} 1 & -1 & 0 & -3 & 0 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 & 1 \end{array} \right] \xrightarrow{R_3 \to R_3 - R_2} \left[ \begin{array}{cccc|c} 1 & -1 & 0 & -3 & 0 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right].$ Columns 4 and 5 have only a $0$ in row 3, so this is the RREF. The pivot columns are 1 and 3; the free variables are $x_2 = s$ and $x_4 = t$ . By Theorem 3.2.4 (b), $x_1 = s + 3t$ and $x_3 = 1 - 2t$ . Hence the solution set is $\{ (0, 0, 1, 0) + s(1, 1, 0, 0) + t(3, 0, -2, 1) : s, t \in \mathbb{R} \}.$

Exercise (B2: A parameter)

For which $k \in \mathbb{R}$ is the system $x + y - z = 2, \qquad x + 2y + z = 3, \qquad x + y + (k^2 - 5)z = k$ inconsistent, which give exactly one solution, and which give infinitely many? Justify your answer, and find the solutions when they exist.

Solution. $\begin{aligned} \left[ \begin{array}{ccc|c} 1 & 1 & -1 & 2 \\ 1 & 2 & 1 & 3 \\ 1 & 1 & k^2 - 5 & k \end{array} \right] &\xrightarrow{R_2 \to R_2 - R_1} \left[ \begin{array}{ccc|c} 1 & 1 & -1 & 2 \\ 0 & 1 & 2 & 1 \\ 1 & 1 & k^2 - 5 & k \end{array} \right] \\ &\xrightarrow{R_3 \to R_3 - R_1} \left[ \begin{array}{ccc|c} 1 & 1 & -1 & 2 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & k^2 - 4 & k - 2 \end{array} \right] \\ &\xrightarrow{R_1 \to R_1 - R_2} \left[ \begin{array}{ccc|c} 1 & 0 & -3 & 1 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & k^2 - 4 & k - 2 \end{array} \right]. \end{aligned}$ Whether column 3 gets a pivot depends on whether $k^2 - 4 = (k - 2)(k + 2)$ is zero.

Case $k \neq \pm 2$ . Then $k^2 - 4 \neq 0$ , and $R_3 \to (k^2 - 4)^{-1}R_3$ turns row 3 into $(0, 0, 1 \mid \tfrac{1}{k + 2})$ , since $\tfrac{k - 2}{(k - 2)(k + 2)} = \tfrac{1}{k + 2}$ . Then $R_1 \to R_1 + 3R_3$ and $R_2 \to R_2 - 2R_3$ give the RREF $[\, \mathbf{I}_3 \mid \mathbf{c} \,]$ with $\mathbf{c} = \left( \frac{k + 5}{k + 2},\ \frac{k}{k + 2},\ \frac{1}{k + 2} \right),$ using $1 + \tfrac{3}{k + 2} = \tfrac{k + 5}{k + 2}$ and $1 - \tfrac{2}{k + 2} = \tfrac{k}{k + 2}$ . By Theorem 3.2.4 (c) there is exactly one solution, $\mathbf{c}$ .

Case $k = 2$ . Row 3 is zero, and the matrix is in RREF with pivot columns 1, 2 and free variable $z = t$ . The solutions are $(1 + 3t, 1 - 2t, t)$ , $t \in \mathbb{R}$ : infinitely many.

Case $k = -2$ . Row 3 is $(0, 0, 0 \mid -4)$ , and $R_3 \to -\tfrac14 R_3$ makes it $(0, 0, 0 \mid 1)$ . The last column is a pivot column, so the system is inconsistent.

Hence: inconsistent for $k = -2$ , infinitely many solutions for $k = 2$ , and exactly one solution otherwise.

Exercise (B3: Over

\mathbb{F}_3

)

Solve each system over $\mathbb{F}_3$ by reducing to RREF, naming each operation, and list all solutions.

(a) $x + 2y + z = 1$ , $2x + y + z = 0$ , $x + z = 2$ .
(b) $x + y + 2z = 1$ , $2x + z = 2$ .

Solution. In $\mathbb{F}_3$ the inverses are $1^{-1} = 1$ and $2^{-1} = 2$ , since $2 \cdot 2 = 4 = 1$ , and $-1 = 2$ , $-2 = 1$ .

(a) $\left[ \begin{array}{ccc|c} 1 & 2 & 1 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 0 & 1 & 2 \end{array} \right] \xrightarrow{R_2 \to R_2 - 2R_1} \left[ \begin{array}{ccc|c} 1 & 2 & 1 & 1 \\ 0 & 0 & 2 & 1 \\ 1 & 0 & 1 & 2 \end{array} \right] \xrightarrow{R_3 \to R_3 - R_1} \left[ \begin{array}{ccc|c} 1 & 2 & 1 & 1 \\ 0 & 0 & 2 & 1 \\ 0 & 1 & 0 & 1 \end{array} \right]$ Here $1 - 4 = -3 = 0$ , $1 - 2 = -1 = 2$ , $0 - 2 = 1$ , and $0 - 2 = 1$ , $2 - 1 = 1$ . Column 2 has entries $0, 1$ below row 1, so we swap: $\begin{aligned} &\xrightarrow{R_2 \leftrightarrow R_3} \left[ \begin{array}{ccc|c} 1 & 2 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 \end{array} \right] \\ &\xrightarrow{R_1 \to R_1 - 2R_2} \left[ \begin{array}{ccc|c} 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 \end{array} \right] \\ &\xrightarrow{R_3 \to 2R_3} \left[ \begin{array}{ccc|c} 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{array} \right] \\ &\xrightarrow{R_1 \to R_1 - R_3} \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{array} \right]. \end{aligned}$ There are no free variables, so the unique solution is $(0, 1, 2)$ . Check: $0 + 2 + 2 = 4 = 1$ , $0 + 1 + 2 = 3 = 0$ , $0 + 2 = 2$ .
(b) $\left[ \begin{array}{ccc|c} 1 & 1 & 2 & 1 \\ 2 & 0 & 1 & 2 \end{array} \right] \xrightarrow{R_2 \to R_2 - 2R_1} \left[ \begin{array}{ccc|c} 1 & 1 & 2 & 1 \\ 0 & 1 & 0 & 0 \end{array} \right] \xrightarrow{R_1 \to R_1 - R_2} \left[ \begin{array}{ccc|c} 1 & 0 & 2 & 1 \\ 0 & 1 & 0 & 0 \end{array} \right],$ using $0 - 2 = 1$ , $1 - 4 = 0$ , $2 - 2 = 0$ . The free variable is $z = t$ , and $x = 1 - 2t = 1 + t$ , $y = 0$ . As $t$ runs through $0, 1, 2$ , the solutions are $(1, 0, 0)$ , $(2, 0, 1)$ , $(0, 0, 2)$ : exactly three.

C. Going deeper

Exercise (C1: Why

i \neq j

Consider the move “ $R_i \to R_i + cR_i$ ”, which the definition does not allow.

(a) Show that for $c = -1$ this move is not reversible: give a matrix on which its effect cannot be undone by any sequence of elementary row operations and moves of this kind, and a system whose solution set it changes.
(b) Show that for $c \neq -1$ the move is an elementary row operation of another type. Explain why the condition $i \neq j$ in type (3) therefore loses nothing.

Solution.

(a) The move replaces $\mathbf{r}_i$ by $\mathbf{r}_i + (-1)\mathbf{r}_i = \mathbf{0}$ . Apply it to the $1 \times 2$ augmented matrix $[\, 1 \mid 1 \,]$ of the equation $x = 1$ over any field $F$ : the result is $[\, 0 \mid 0 \,]$ , the equation $0 = 0$ . The solution set changes from $\{ 1 \}$ to all of $F$ . No sequence of moves can return to $[\, 1 \mid 1 \,]$ : every elementary row operation, and every move “ $R_i \to R_i + cR_i$ ”, sends a zero matrix to a zero matrix, by the formulas in the proof of Lemma 3.2.1 and $c \cdot 0 = 0$ .
(b) The move replaces $\mathbf{r}_i$ by $(1 + c)\mathbf{r}_i$ . If $c \neq -1$ , then $1 + c \neq 0$ , and this is the scaling $R_i \to (1 + c)R_i$ , an operation of type (2). So allowing $i = j$ in type (3) would add only moves that are already available (when $c \neq -1$ ) and one move that destroys information ( $c = -1$ ). Requiring $i \neq j$ excludes exactly the bad case.

Exercise (C2: The cost of elimination)

Let $\mathbf{A} \in M_n(F)$ and $\mathbf{b} \in F^n$ , and suppose that Gauss–Jordan elimination on $[\, \mathbf{A} \mid \mathbf{b} \,]$ finds, for each $l = 1, \dots, n$ , a nonzero entry in position $(l, l)$ and so never swaps. Count as one operation each multiplication or division of two scalars, under these conventions: scaling row $l$ costs one division for each entry in columns $l + 1, \dots, n + 1$ (the pivot is simply set to $1$ ), and each replacement $R_g \to R_g - cR_l$ costs one multiplication for each entry in columns $l + 1, \dots, n + 1$ (the entry in column $l$ is simply set to $0$ ).

(a) Show that processing column $l$ costs at most $n(n + 1 - l)$ operations.
(b) Hence show that the whole elimination costs at most $\tfrac12 (n^3 + n^2)$ operations.
(c) Roughly how many times more work is a system of $2n$ equations than one of $n$ equations, for large $n$ ?

Solution.

(a) Scaling row $l$ costs $n + 1 - l$ divisions. At most $n - 1$ other rows need a replacement, each costing $n + 1 - l$ multiplications. The total is at most $(n + 1 - l) + (n - 1)(n + 1 - l) = n(n + 1 - l)$ .
(b) Summing (a) over $l = 1, \dots, n$ , and substituting $q = n + 1 - l$ , which runs through $1, \dots, n$ , $\sum_{l=1}^{n} n(n + 1 - l) = n \sum_{q=1}^{n} q = n \cdot \frac{n(n + 1)}{2} = \frac{n^3 + n^2}{2},$ using the formula for $1 + \dots + n$ (Proposition 0.2.8).
(c) The bound is dominated by $\tfrac12 n^3$ for large $n$ , since $\tfrac12 n^2$ is small compared with it. Replacing $n$ by $2n$ multiplies $n^3$ by $8$ , so doubling the size of the system costs roughly eight times as much.

Exercise (C3: Solvable for every right-hand side)

Let $\mathbf{A} \in M_{m \times n}(F)$ , and suppose that $\mathbf{A}\mathbf{x} = \mathbf{b}$ is consistent for every $\mathbf{b} \in F^m$ . Prove that $m \le n$ .

Hint: suppose $m > n$ , reduce $\mathbf{A}$ to its RREF $\mathbf{R}$ , and run the operations backwards on $[\, \mathbf{R} \mid \mathbf{e}_m \,]$ .

Solution. Suppose, for a contradiction, that $m > n$ . By Theorem 3.2.3, some sequence of operations $O_1, \dots, O_s$ turns $\mathbf{A}$ into a matrix $\mathbf{R}$ in RREF. By (E2), $\mathbf{R}$ has at most $n$ pivots, one in each pivot column, so at most $n < m$ nonzero rows, and by (E1) its last row is zero. Therefore the last row of $[\, \mathbf{R} \mid \mathbf{e}_m \,]$ is $(0 \ \cdots \ 0 \mid 1)$ , so the system $\mathbf{R}\mathbf{x} = \mathbf{e}_m$ has no solution.

By Theorem 3.2.2 (a), each $O_t$ is undone by an operation $O'_t$ , and $O'_s, \dots, O'_1$ turn $\mathbf{R}$ back into $\mathbf{A}$ . Apply them to $[\, \mathbf{R} \mid \mathbf{e}_m \,]$ . By Lemma 3.2.1 they act on the two blocks separately, so the result is $[\, \mathbf{A} \mid \mathbf{b} \,]$ for some $\mathbf{b} \in F^m$ . By Theorem 3.2.2 (c), $\mathbf{A}\mathbf{x} = \mathbf{b}$ has the same solutions as $\mathbf{R}\mathbf{x} = \mathbf{e}_m$ , namely none. This contradicts the hypothesis, so $m \le n$ .