Reduced Echelon Form

After developing the mechanics of Gauss’s Method, we observed that it can be done in more than one way. For example, from this matrix

$(\begin{matrix} 2 & 2 \\ 4 & 3 \end{matrix})$

we could derive any of these three echelon form matrices.

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

The first results from $- 2 ρ_{1} + ρ_{2}$ . The second comes from doing $(1 / 2) ρ_{1}$ and then $- 4 ρ_{1} + ρ_{2}$ . The third comes from $- 2 ρ_{1} + ρ_{2}$ followed by $2 ρ_{2} + ρ_{1}$ (after the first row combination the matrix is already in echelon form but it is nonetheless a legal row operation).

In this chapter’s first section we noted that this raises questions. Will any two echelon form versions of a linear system have the same number of free variables? If yes, will the two have exactly the same free variables? In this section we will give a way to decide if one linear system can be derived from another by row operations. The answers to both questions, both “yes,” will follow from that.

Gauss-Jordan Reduction

Here is an extension of Gauss’s Method that has some advantages.

Example 1.1 To solve

$\begin{array}{rcrcrcr} x & + & y & - & 2 z & = & - 2 \\ y & + & 3 z & = & 7 \\ x & - & z & = & - 1 \end{array}$

we can start as usual by reducing it to echelon form.

$⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{3}} (\begin{array}{cccr} 1 & 1 & - 2 & - 2 \\ 0 & 1 & 3 & 7 \\ 0 & - 1 & 1 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} + ρ_{3}} (\begin{array}{cccr} 1 & 1 & - 2 & - 2 \\ 0 & 1 & 3 & 7 \\ 0 & 0 & 4 & 8 \end{array})$

We can keep going to a second stage by making the leading entries into $1$ ’s

$⟶_{\begin{array}{l} \end{array}}^{(1 / 4) ρ_{3}} (\begin{array}{cccr} 1 & 1 & - 2 & - 2 \\ 0 & 1 & 3 & 7 \\ 0 & 0 & 1 & 2 \end{array})$

and then to a third stage that uses the leading entries to eliminate all of the other entries in each column by combining upwards.

$⟶_{\begin{array}{l} 2 ρ_{3} + ρ_{1} \end{array}}^{- 3 ρ_{3} + ρ_{2}} (\begin{array}{cccr} 1 & 1 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{array}{cccr} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{array})$

The answer is $x = 1$ , $y = 1$ , and $z = 2$ .

Using one entry to clear out the rest of a column is pivoting on that entry.

Notice that the row combination operations in the first stage move left to right while the combination operations in the third stage move right to left.

Example 1.2 The middle stage operations that turn the leading entries into $1$ ’s don’t interact so we can combine multiple ones into a single step.

$\begin{aligned} (\begin{array}{ccr} 2 & 1 & 7 \\ 4 & - 2 & 6 \end{array}) & ⟶_{\begin{matrix} \end{matrix}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{ccr} 2 & 1 & 7 \\ 0 & - 4 & - 8 \end{array}) \\ ⟶_{\begin{matrix} (- 1 / 4) ρ_{2} \end{matrix}}^{(1 / 2) ρ_{1}} (\begin{array}{ccr} 1 & 1 / 2 & 7 / 2 \\ 0 & 1 & 2 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 2) ρ_{2} + ρ_{1}} (\begin{array}{ccr} 1 & 0 & 5 / 2 \\ 0 & 1 & 2 \end{array}) \end{aligned}$

The answer is $x = 5 / 2$ and $y = 2$ .

This extension of Gauss’s Method is the Gauss-Jordan Method or Gauss-Jordan reduction.

Definition 1.3 A matrix or linear system is in reduced echelon form if, in addition to being in echelon form, each leading entry is a $1$ and is the only nonzero entry in its column.

The cost of using Gauss-Jordan reduction to solve a system is the additional arithmetic. The benefit is that we can just read off the solution set description.

In any echelon form system, reduced or not, we can read off when the system has an empty solution set because there is a contradictory equation. We can read off when the system has a one-element solution set because there is no contradiction and every variable is the leading variable in some row. And, we can read off when the system has an infinite solution set because there is no contradiction and at least one variable is free.

However, in reduced echelon form we can read off not just the size of the solution set but also its description. We have no trouble describing the solution set when it is empty, of course. Example 1.1 and 1.2 show how in a single element solution set case the single element is in the column of constants. The next example shows how to read the parametrization of an infinite solution set.

Example 1.4 $\begin{matrix} (\begin{array}{ccccr} 2 & 6 & 1 & 2 & 5 \\ 0 & 3 & 1 & 4 & 1 \\ 0 & 3 & 1 & 2 & 5 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{array}{ccccr} 2 & 6 & 1 & 2 & 5 \\ 0 & 3 & 1 & 4 & 1 \\ 0 & 0 & 0 & - 2 & 4 \end{array}) \\ ⟶_{\begin{array}{l} (1 / 3) ρ_{2} \\ - (1 / 2) ρ_{3} \end{array}}^{(1 / 2) ρ_{1}} ⟶_{\begin{array}{l} - ρ_{3} + ρ_{1} \end{array}}^{- (4 / 3) ρ_{3} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 3 ρ_{2} + ρ_{1}} (\begin{array}{ccccr} 1 & 0 & - 1 / 2 & 0 & - 9 / 2 \\ 0 & 1 & 1 / 3 & 0 & 3 \\ 0 & 0 & 0 & 1 & - 2 \end{array}) \end{matrix}$

As a linear system this is

$\begin{array}{rcrcrcrcr} x_{1} & - & 1 / 2 x_{3} & = & - 9 / 2 \\ x_{2} & + & 1 / 3 x_{3} & = & 3 \\ x_{4} & = & - 2 \end{array}$

so a solution set description is this.

$S = {(\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}) = (\begin{matrix} - 9 / 2 \\ 3 \\ 0 \\ - 2 \end{matrix}) + (\begin{matrix} 1 / 2 \\ - 1 / 3 \\ 1 \\ 0 \end{matrix}) x_{3} ∣ x_{3} \in ℝ}$

Thus, echelon form isn’t some kind of one best form for systems. Other forms, such as reduced echelon form, have advantages and disadvantages. Instead of picturing linear systems (and the associated matrices) as things we operate on, always directed toward the goal of echelon form, we can think of them as interrelated, where we can get from one to another by row operations. The rest of this subsection develops this thought.

Lemma 1.5 Elementary row operations are reversible.

Proof For any matrix $A$ , the effect of swapping rows is reversed by swapping them back, multiplying a row by a nonzero $k$ is undone by multiplying by $1 / k$ , and adding a multiple of row $i$ to row $j$ (with $i \neq j$ ) is undone by subtracting the same multiple of row $i$ from row $j$ .

$A ⟶_{\begin{array}{l} \end{array}}^{ρ_{i} \leftrightarrow ρ_{j}} ⟶_{\begin{array}{l} \end{array}}^{ρ_{j} \leftrightarrow ρ_{i}} A A ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i}} ⟶_{\begin{array}{l} \end{array}}^{(1 / k) ρ_{i}} A A ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i} + ρ_{j}} ⟶_{\begin{array}{l} \end{array}}^{- k ρ_{i} + ρ_{j}} A$

(We need the $i \neq j$ condition; see Exercise 1.18.)

QED

Again, the point of view that we are developing, supported now by the lemma, is that the term ‘reduces to’ is misleading: where $A ⟶ B$ , we shouldn’t think of $B$ as after $A$ or simpler than $A$ . Instead we should think of the two matrices as interrelated. Below is a picture. It shows the matrices from the start of this section and their reduced echelon form version in a cluster, as interreducible.

Five two-by-two row-equivalent matrices are linked by reversible row-operation arrows, including the identity matrix and matrices (2,2;4,3), (2,0;0,-1), (1,1;0,-1), and (2,2;0,-1).

We say that matrices that reduce to each other are equivalent with respect to the relationship of row reducibility. The next result justifies this, using the definition of an equivalence.¹

Lemma 1.6 Between matrices, ‘reduces to’ is an equivalence relation.

Proof We must check the conditions (i) reflexivity, that any matrix reduces to itself, (ii) symmetry, that if $A$ reduces to $B$ then $B$ reduces to $A$ , and (iii) transitivity, that if $A$ reduces to $B$ and $B$ reduces to $C$ then $A$ reduces to $C$ .

Reflexivity is easy; any matrix reduces to itself in zero-many operations.

The relationship is symmetric by the prior lemma—if $A$ reduces to $B$ by some row operations then also $B$ reduces to $A$ by reversing those operations.

For transitivity, suppose that $A$ reduces to $B$ and that $B$ reduces to $C$ . Following the reduction steps from $A \to \dots \to B$ with those from $B \to \dots \to C$ gives a reduction from $A$ to $C$ .

QED

Definition 1.7 Two matrices that are interreducible by elementary row operations are row equivalent.

The diagram below shows the collection of all matrices as a box. Inside that box each matrix lies in a class. Matrices are in the same class if and only if they are interreducible. The classes are disjoint—no matrix is in two distinct classes. We have partitioned the collection of matrices into row equivalence classes.²

The set of matrices is partitioned into row-equivalence classes. Points A and B lie in the same region, so they are row equivalent.

One of the classes is the cluster of interrelated matrices from the start of this section sketched above (it includes all of the nonsingular $2 \times 2$ matrices).

The next subsection proves that the reduced echelon form of a matrix is unique. Rephrased in terms of the row-equivalence relationship, we shall prove that every matrix is row equivalent to one and only one reduced echelon form matrix. In terms of the partition what we shall prove is: every equivalence class contains one and only one reduced echelon form matrix. So each reduced echelon form matrix serves as a representative of its class.

Exercises

Exercise 1.8 Worked answer

Recommended. Use Gauss-Jordan reduction to solve each system.
1. $\begin{array}{rcrcr} x & + & y & = & 2 \\ x & - & y & = & 0 \end{array}$
2. $\begin{array}{rcrcrcr} x & - & z & = & 4 \\ 2 x & + & 2 y & = & 1 \end{array}$
3. $\begin{array}{rcrcr} 3 x & - & 2 y & = & 1 \\ 6 x & + & y & = & 1 / 2 \end{array}$
4. $\begin{array}{rcrcrcr} 2 x & - & y & = & - 1 \\ x & + & 3 y & - & z & = & 5 \\ y & + & 2 z & = & 5 \end{array}$
Back to Exercise 1.8

Answer. These answers show only the Gauss-Jordan reduction. With it, describing the solution set is easy.
1. The solution set contains only a single element.
  
  $\begin{matrix} (\begin{array}{ccr} 1 & 1 & 2 \\ 1 & - 1 & 0 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{2}} (\begin{array}{ccr} 1 & 1 & 2 \\ 0 & - 2 & - 2 \end{array}) \\ ⟶_{\begin{array}{l} \end{array}}^{- (1 / 2) ρ_{2}} (\begin{array}{ccr} 1 & 1 & 2 \\ 0 & 1 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{array}{ccr} 1 & 0 & 1 \\ 0 & 1 & 1 \end{array}) \end{matrix}$
2. The solution set has one parameter.
  
  $(\begin{array}{cccr} 1 & 0 & - 1 & 4 \\ 2 & 2 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{cccr} 1 & 0 & - 1 & 4 \\ 0 & 2 & 2 & - 7 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{(1 / 2) ρ_{2}} (\begin{array}{cccr} 1 & 0 & - 1 & 4 \\ 0 & 1 & 1 & - 7 / 2 \end{array})$
3. There is a unique solution.
  
  $\begin{matrix} (\begin{array}{ccr} 3 & - 2 & 1 \\ 6 & 1 & 1 / 2 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{ccr} 3 & - 2 & 1 \\ 0 & 5 & - 3 / 2 \end{array}) \\ ⟶_{\begin{array}{l} (1 / 5) ρ_{2} \end{array}}^{(1 / 3) ρ_{1}} (\begin{array}{ccr} 1 & - 2 / 3 & 1 / 3 \\ 0 & 1 & - 3 / 10 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{(2 / 3) ρ_{2} + ρ_{1}} (\begin{array}{ccr} 1 & 0 & 2 / 15 \\ 0 & 1 & - 3 / 10 \end{array}) \end{matrix}$
4. A row swap in the second step makes the arithmetic easier.
  
  $\begin{matrix} (\begin{array}{cccr} 2 & - 1 & 0 & - 1 \\ 1 & 3 & - 1 & 5 \\ 0 & 1 & 2 & 5 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- (1 / 2) ρ_{1} + ρ_{2}} (\begin{array}{cccr} 2 & - 1 & 0 & - 1 \\ 0 & 7 / 2 & - 1 & 11 / 2 \\ 0 & 1 & 2 & 5 \end{array}) \\ \begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{ρ_{2} \leftrightarrow ρ_{3}} (\begin{array}{cccr} 2 & - 1 & 0 & - 1 \\ 0 & 1 & 2 & 5 \\ 0 & 7 / 2 & - 1 & 11 / 2 \end{array}) ⟶_{\begin{matrix} \end{matrix}}^{- (7 / 2) ρ_{2} + ρ_{3}} (\begin{array}{cccr} 2 & - 1 & 0 & - 1 \\ 0 & 1 & 2 & 5 \\ 0 & 0 & - 8 & - 12 \end{array}) \\ ⟶_{\begin{matrix} - (1 / 8) ρ_{2} \end{matrix}}^{(1 / 2) ρ_{1}} (\begin{array}{cccr} 1 & - 1 / 2 & 0 & - 1 / 2 \\ 0 & 1 & 2 & 5 \\ 0 & 0 & 1 & 3 / 2 \end{array}) ⟶_{\begin{matrix} \end{matrix}}^{- 2 ρ_{3} + ρ_{2}} (\begin{array}{cccr} 1 & - 1 / 2 & 0 & - 1 / 2 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 / 2 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{(1 / 2) ρ_{2} + ρ_{1}} (\begin{array}{cccr} 1 & 0 & 0 & 1 / 2 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 / 2 \end{array}) \end{aligned} \end{matrix}$
Exercise 1.9 Worked answer

Do Gauss-Jordan reduction.
1. $\begin{array}{rcrcrcr} x & + & y & - & z & = & 3 \\ 2 x & - & y & - & z & = & 1 \\ 3 x & + & y & + & 2 z & = & 0 \end{array}$
2. $\begin{array}{rcrcrcr} x & + & y & + & 2 z & = & 0 \\ 2 x & - & y & + & z & = & 1 \\ 4 x & + & y & + & 5 z & = & 1 \end{array}$
Back to Exercise 1.9

Answer.
1. $\begin{matrix} (\begin{array}{cccc} 1 & 1 & - 1 & 3 \\ 2 & - 1 & - 1 & 1 \\ 3 & 1 & 2 & 0 \end{array}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{cccc} 1 & 1 & - 1 & 3 \\ 0 & - 3 & 1 & - 5 \\ 0 & - 2 & 5 & - 9 \end{array}) \\ \begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{- (2 / 3) ρ_{2} + ρ_{3}} (\begin{array}{cccc} 1 & 1 & - 1 & 3 \\ 0 & - 3 & 1 & - 5 \\ 0 & 0 & 13 / 3 & - 17 / 3 \end{array}) ⟶_{\begin{matrix} (3 / 13) ρ_{3} \end{matrix}}^{- (1 / 3) ρ_{2}} (\begin{array}{cccc} 1 & 1 & - 1 & 3 \\ 0 & 1 & - 1 / 3 & 5 / 3 \\ 0 & 0 & 1 & - 17 / 13 \end{array}) \\ ⟶_{\begin{matrix} (1 / 3) ρ_{3} + ρ_{2} \end{matrix}}^{ρ_{3} + ρ_{1}} (\begin{array}{cccc} 1 & 1 & 0 & 22 / 13 \\ 0 & 1 & 0 & 16 / 13 \\ 0 & 0 & 1 & - 17 / 13 \end{array}) ⟶_{\begin{matrix} \end{matrix}}^{- ρ_{2} + ρ_{1}} (\begin{array}{cccc} 1 & 0 & 0 & 6 / 13 \\ 0 & 1 & 0 & 16 / 13 \\ 0 & 0 & 1 & - 17 / 13 \end{array}) \end{aligned} \end{matrix}$
2. $\begin{matrix} (\begin{array}{cccc} 1 & 1 & 2 & 0 \\ 2 & - 1 & 1 & 1 \\ 4 & 1 & 5 & 1 \end{array}) ⟶_{\begin{array}{l} - 4 ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{cccc} 1 & 1 & 2 & 0 \\ 0 & - 3 & - 3 & 1 \\ 0 & - 3 & - 3 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{array}{cccc} 1 & 1 & 2 & 0 \\ 0 & - 3 & - 3 & 1 \\ 0 & 0 & 0 & 0 \end{array}) \\ ⟶_{\begin{array}{l} \end{array}}^{- (1 / 3) ρ_{2}} (\begin{array}{cccc} 1 & 1 & 2 & 0 \\ 0 & 1 & 1 & - 1 / 3 \\ 0 & 0 & 0 & 0 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{array}{cccc} 1 & 0 & 1 & 1 / 3 \\ 0 & 1 & 1 & - 1 / 3 \\ 0 & 0 & 0 & 0 \end{array}) \end{matrix}$
Exercise 1.10 Worked answer

Recommended. Find the reduced echelon form of each matrix.
1. $(\begin{matrix} 2 & 1 \\ 1 & 3 \end{matrix})$
2. $(\begin{matrix} 1 & 3 & 1 \\ 2 & 0 & 4 \\ - 1 & - 3 & - 3 \end{matrix})$
3. $(\begin{matrix} 1 & 0 & 3 & 1 & 2 \\ 1 & 4 & 2 & 1 & 5 \\ 3 & 4 & 8 & 1 & 2 \end{matrix})$
4. $(\begin{matrix} 0 & 1 & 3 & 2 \\ 0 & 0 & 5 & 6 \\ 1 & 5 & 1 & 5 \end{matrix})$
Back to Exercise 1.10

Answer. Use Gauss-Jordan reduction.
1. The reduced echelon form is all zeroes except for a diagonal of ones.
  
  $⟶_{\begin{array}{l} \end{array}}^{- (1 / 2) ρ_{1} + ρ_{2}} (\begin{matrix} 2 & 1 \\ 0 & 5 / 2 \end{matrix}) ⟶_{\begin{array}{l} (2 / 5) ρ_{2} \end{array}}^{(1 / 2) ρ_{1}} (\begin{matrix} 1 & 1 / 2 \\ 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- (1 / 2) ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
2. As in the prior problem, the reduced echelon form is all zeroes but for a diagonal of ones.
  
  $\begin{matrix} ⟶_{\begin{array}{l} ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 3 & 1 \\ 0 & - 6 & 2 \\ 0 & 0 & - 2 \end{matrix}) ⟶_{\begin{array}{l} - (1 / 2) ρ_{3} \end{array}}^{- (1 / 6) ρ_{2}} (\begin{matrix} 1 & 3 & 1 \\ 0 & 1 & - 1 / 3 \\ 0 & 0 & 1 \end{matrix}) \\ ⟶_{\begin{array}{l} - ρ_{3} + ρ_{1} \end{array}}^{(1 / 3) ρ_{3} + ρ_{2}} (\begin{matrix} 1 & 3 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- 3 ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \end{matrix}$
3. There are more columns than rows so we must get more than just a diagonal of ones.
  
  $\begin{matrix} ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 0 & 3 & 1 & 2 \\ 0 & 4 & - 1 & 0 & 3 \\ 0 & 4 & - 1 & - 2 & - 4 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 0 & 3 & 1 & 2 \\ 0 & 4 & - 1 & 0 & 3 \\ 0 & 0 & 0 & - 2 & - 7 \end{matrix}) \\ ⟶_{\begin{array}{l} - (1 / 2) ρ_{3} \end{array}}^{(1 / 4) ρ_{2}} (\begin{matrix} 1 & 0 & 3 & 1 & 2 \\ 0 & 1 & - 1 / 4 & 0 & 3 / 4 \\ 0 & 0 & 0 & 1 & 7 / 2 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{3} + ρ_{1}} (\begin{matrix} 1 & 0 & 3 & 0 & - 3 / 2 \\ 0 & 1 & - 1 / 4 & 0 & 3 / 4 \\ 0 & 0 & 0 & 1 & 7 / 2 \end{matrix}) \end{matrix}$
4. As in the prior item, this is not a square matrix.
  
  $\begin{matrix} ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{3}} (\begin{matrix} 1 & 5 & 1 & 5 \\ 0 & 0 & 5 & 6 \\ 0 & 1 & 3 & 2 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} \leftrightarrow ρ_{3}} (\begin{matrix} 1 & 5 & 1 & 5 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 5 & 6 \end{matrix}) \\ \begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{(1 / 5) ρ_{3}} (\begin{array}{c} 1 & 5 & 1 & 5 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 1 & 6 / 5 \end{array}) ⟶_{\begin{matrix} - ρ_{3} + ρ_{1} \end{matrix}}^{- 3 ρ_{3} + ρ_{2}} (\begin{array}{c} 1 & 5 & 0 & 19 / 5 \\ 0 & 1 & 0 & - 8 / 5 \\ 0 & 0 & 1 & 6 / 5 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- 5 ρ_{2} + ρ_{1}} (\begin{array}{c} 1 & 0 & 0 & 59 / 5 \\ 0 & 1 & 0 & - 8 / 5 \\ 0 & 0 & 1 & 6 / 5 \end{array}) \end{aligned} \end{matrix}$
Exercise 1.11 Worked answer

Get the reduced echelon form of each.
1. $(\begin{matrix} 0 & 2 & 1 \\ 2 & - 1 & 1 \\ - 2 & - 1 & 0 \end{matrix})$
2. $(\begin{matrix} 1 & 3 & 1 \\ 2 & 6 & 2 \\ - 1 & 0 & 0 \end{matrix})$
Back to Exercise 1.11

Answer.
1. Swap first.
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} + ρ_{3}} ⟶_{\begin{array}{l} (1 / 2) ρ_{2} \\ (1 / 2) ρ_{3} \end{array}}^{(1 / 2) ρ_{1}} ⟶_{\begin{array}{l} (- 1 / 2) ρ_{3} + ρ_{2} \end{array}}^{(- 1 / 2) ρ_{3} + ρ_{1}} ⟶_{\begin{array}{l} \end{array}}^{(1 / 2) ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$
2. Here the swap is in the middle.
  
  $⟶_{\begin{array}{l} ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} \leftrightarrow ρ_{3}} ⟶_{\begin{array}{l} \end{array}}^{(1 / 3) ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 3 ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 / 3 \\ 0 & 0 & 0 \end{matrix})$
Exercise 1.12 Worked answer

Recommended. Find each solution set by using Gauss-Jordan reduction and then reading off the parametrization.
1. $\begin{array}{rcrcrcr} 2 x & + & y & - & z & = & 1 \\ 4 x & - & y & = & 3 \end{array}$
2. $\begin{array}{rcrcrcrcr} x & - & z & = & 1 \\ y & + & 2 z & - & w & = & 3 \\ x & + & 2 y & + & 3 z & - & w & = & 7 \end{array}$
3. $\begin{array}{rcrcrcrcr} x & - & y & + & z & = & 0 \\ y & + & w & = & 0 \\ 3 x & - & 2 y & + & 3 z & + & w & = & 0 \\ - y & - & w & = & 0 \end{array}$
4. $\begin{array}{rcrcrcrcrcr} a & + & 2 b & + & 3 c & + & d & - & e & = & 1 \\ 3 a & - & b & + & c & + & d & + & e & = & 3 \end{array}$
Back to Exercise 1.12

Answer. For the Gauss’s halves, see the answers to Chapter One’s section I.2 question Exercise 2.19.
1. The “Jordan” half goes this way.
  
  $⟶_{\begin{array}{l} - (1 / 3) ρ_{2} \end{array}}^{(1 / 2) ρ_{1}} (\begin{array}{cccr} 1 & 1 / 2 & - 1 / 2 & 1 / 2 \\ 0 & 1 & - 2 / 3 & - 1 / 3 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- (1 / 2) ρ_{2} + ρ_{1}} (\begin{array}{cccr} 1 & 0 & - 1 / 6 & 2 / 3 \\ 0 & 1 & - 2 / 3 & - 1 / 3 \end{array})$
  
  The solution set is this
  
  ${(\begin{matrix} 2 / 3 \\ - 1 / 3 \\ 0 \end{matrix}) + (\begin{matrix} 1 / 6 \\ 2 / 3 \\ 1 \end{matrix}) z ∣ z \in ℝ}$
2. The second half is
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{3} + ρ_{2}} (\begin{array}{ccccr} 1 & 0 & - 1 & 0 & 1 \\ 0 & 1 & 2 & 0 & 3 \\ 0 & 0 & 0 & 1 & 0 \end{array})$
  
  so the solution is this.
  
  ${(\begin{matrix} 1 \\ 3 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 1 \\ - 2 \\ 1 \\ 0 \end{matrix}) z ∣ z \in ℝ}$
3. This Jordan half
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{2} + ρ_{1}} (\begin{array}{ccccr} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array})$
  
  gives
  
  ${(\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} - 1 \\ 0 \\ 1 \\ 0 \end{matrix}) z + (\begin{matrix} - 1 \\ - 1 \\ 0 \\ 1 \end{matrix}) w ∣ z, w \in ℝ}$
  
  (of course, we could omit the zero vector from the description).
4. The “Jordan” half
  
  $\begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 7) ρ_{2}} (\begin{array}{cccccr} 1 & 2 & 3 & 1 & - 1 & 1 \\ 0 & 1 & 8 / 7 & 2 / 7 & - 4 / 7 & 0 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- 2 ρ_{2} + ρ_{1}} (\begin{array}{cccccr} 1 & 0 & 5 / 7 & 3 / 7 & 1 / 7 & 1 \\ 0 & 1 & 8 / 7 & 2 / 7 & - 4 / 7 & 0 \end{array}) \end{aligned}$
  
  ends with this solution set.
  
  ${(\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} - 5 / 7 \\ - 8 / 7 \\ 1 \\ 0 \\ 0 \end{matrix}) c + (\begin{matrix} - 3 / 7 \\ - 2 / 7 \\ 0 \\ 1 \\ 0 \end{matrix}) d + (\begin{matrix} - 1 / 7 \\ 4 / 7 \\ 0 \\ 0 \\ 1 \end{matrix}) e ∣ c, d, e \in ℝ}$
Exercise 1.13 Worked answer

Give two distinct echelon form versions of this matrix.

$(\begin{matrix} 2 & 1 & 1 & 3 \\ 6 & 4 & 1 & 2 \\ 1 & 5 & 1 & 5 \end{matrix})$

Back to Exercise 1.13

Answer. Routine Gauss’s Method gives one:

$⟶_{\begin{array}{l} - (1 / 2) ρ_{1} + ρ_{3} \end{array}}^{- 3 ρ_{1} + ρ_{2}} (\begin{matrix} 2 & 1 & 1 & 3 \\ 0 & 1 & - 2 & - 7 \\ 0 & 9 / 2 & 1 / 2 & 7 / 2 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- (9 / 2) ρ_{2} + ρ_{3}} (\begin{matrix} 2 & 1 & 1 & 3 \\ 0 & 1 & - 2 & - 7 \\ 0 & 0 & 19 / 2 & 35 \end{matrix})$

and any cosmetic change, such as multiplying the bottom row by $2$ ,

$(\begin{matrix} 2 & 1 & 1 & 3 \\ 0 & 1 & - 2 & - 7 \\ 0 & 0 & 19 & 70 \end{matrix})$

gives another.
Exercise 1.14 Worked answer

Recommended. List the reduced echelon forms possible for each size.
1. $2 \times 2$
2. $2 \times 3$
3. $3 \times 2$
4. $3 \times 3$
Back to Exercise 1.14

Answer. In the cases listed below, we take $a, b \in ℝ$ . Thus, some canonical forms listed below actually include infinitely many cases. In particular, they includes the cases $a = 0$ and $b = 0$ .
1. $(\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & a \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
2. $(\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & a & b \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 1 & a \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & 0 & a \\ 0 & 1 & b \end{matrix})$ , $(\begin{matrix} 1 & a & 0 \\ 0 & 0 & 1 \end{matrix})$ , $(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$
3. $(\begin{matrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & a \\ 0 & 0 \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix})$
4. $(\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & a & b \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 1 & a \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & a & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix})$ , $(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$
Exercise 1.15 Worked answer

Recommended. What results from applying Gauss-Jordan reduction to a nonsingular matrix?

Back to Exercise 1.15

Answer. A nonsingular homogeneous linear system has a unique solution. So a nonsingular matrix must reduce to a (square) matrix that is all $0$ ’s except for $1$ ’s down the upper-left to lower-right diagonal, such as these.

$(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$
Exercise 1.16 Worked answer

Decide whether each relation is an equivalence on the set of $2 \times 2$ matrices.
1. two matrices are related if they have the same entry in the first row and first column
2. two matrices are related if they have the same entry in the first row and first column, or the same entry in the second row and second column
Back to Exercise 1.16

Answer.
1. This is an equivalence.
  
  We can write $M_{1} \sim M_{2}$ if they are related. The $\sim$ relation is reflexive because any matrix has the same $1, 1$ entry as itself. The relation is symmetric because if $M_{1}$ has the same $1, 1$ entry as $M_{2}$ then clearly also $M_{2}$ has the same $1, 1$ entry as $M_{1}$ . Finally, the relation is transitive because if $M_{1} \sim M_{2}$ so they have the same $1, 1$ entry as each other, and $M_{2} \sim M_{3}$ so they have the same as each other, then all three have the same $1, 1$ entry, and $M_{1} \sim M_{3}$ .
2. This is not an equivalence because it is not transitive. The first and second matrix below are related by their $1, 1$ entries, and the second and third are related by their $2, 2$ entries. But the first and third are not related.
  
  $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}) (\begin{matrix} 0 & 0 \\ 0 & - 1 \end{matrix})$
Exercise 1.17 Worked answer

[Cleary] Consider the following relationship on the set of $2 \times 2$ matrices: we say that $A$ is sum-what like $B$ if the sum of all of the entries in $A$ is the same as the sum of all the entries in $B$ . For instance, the zero matrix would be sum-what like the matrix whose first row had two sevens, and whose second row had two negative sevens. Prove or disprove that this is an equivalence relation on the set of $2 \times 2$ matrices.

Back to Exercise 1.17

Answer. It is an equivalence relation. To prove that we must check that the relation is reflexive, symmetric, and transitive.

Assume that all matrices are $2 \times 2$ . For reflexive, we note that a matrix has the same sum of entries as itself. For symmetric, we assume $A$ has the same sum of entries as $B$ and obviously then $B$ has the same sum of entries as $A$ . Transitivity is no harder—if $A$ has the same sum of entries as $B$ and $B$ has the same sum of entries as $C$ then $A$ has the same as $C$ .
Exercise 1.18 Worked answer

The proof of Lemma 1.5 contains a reference to the $i \neq j$ condition on the row combination operation.
1. Write down a $2 \times 2$ matrix with nonzero entries, and show that the $- 1 \cdot ρ_{1} + ρ_{1}$ operation is not reversed by $1 \cdot ρ_{1} + ρ_{1}$ .
2. Expand the proof of that lemma to make explicit exactly where it uses the $i \neq j$ condition on combining.
Back to Exercise 1.18

Answer.
1. For instance,
  
  $(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{1}} (\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{1}} (\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix})$
  
  leaves the matrix changed.
2. This operation
  
  $(\begin{matrix} ⋮ \\ a_{i, 1} & \dots & a_{i, n} \\ ⋮ \\ a_{j, 1} & \dots & a_{j, n} \\ ⋮ \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i} + ρ_{j}} (\begin{matrix} ⋮ \\ a_{i, 1} & \dots & a_{i, n} \\ ⋮ \\ k a_{i, 1} + a_{j, 1} & \dots & k a_{i, n} + a_{j, n} \\ ⋮ \end{matrix})$
  
  leaves the $i$ -th row unchanged because of the $i \neq j$ restriction. Because the $i$ -th row is unchanged, this operation
  
  $⟶_{\begin{array}{l} \end{array}}^{- k ρ_{i} + ρ_{j}} (\begin{matrix} ⋮ \\ a_{i, 1} & \dots & a_{i, n} \\ ⋮ \\ - k a_{i, 1} + k a_{i, 1} + a_{j, 1} & \dots & - k a_{i, n} + k a_{i, n} + a_{j, n} \\ ⋮ \end{matrix})$
  
  returns the $j$ -th row to its original state.
Exercise 1.19 Worked answer

Recommended. [Cleary] Consider the set of students in a class. Which of the following relationships are equivalence relations? Explain each answer in at least a sentence.
1. Two students $x, y$ are related if $x$ has taken at least as many math classes as $y$ .
2. Students $x, y$ are related if they have names that start with the same letter.
Back to Exercise 1.19

Answer. To be an equivalence, each relation must be reflexive, symmetric, and transitive.
1. This relation is not symmetric because if $x$ has taken $4$ classes and $y$ has taken $3$ then $x$ is related to $y$ but $y$ is not related to $x$ .
2. This is reflexive because $x$ ’s name starts with the same letter as does $x$ ’s. It is symmetric because if $x$ ’s name starts with the same letter as $y$ ’s then $y$ ’s starts with the same letter as does $x$ ’s. And it is transitive because if $x$ ’s name starts with the same letter as does $y$ ’s and $y$ ’s name starts with the same letter as does $z$ ’s then $x$ ’s starts with the same letter as does $z$ ’s. So it is an equivalence.
Exercise 1.20 Worked answer

Show that each of these is an equivalence on the set of $2 \times 2$ matrices. Describe the equivalence classes.
1. Two matrices are related if they have the same product down the diagonal, that is, if the product of the entries in the upper left and lower right are equal.
2. Two matrices are related if they both have at least one entry that is a $1$ , or if neither does.
Back to Exercise 1.20

Answer. For each we must check the three conditions of reflexivity, symmetry, and transitivity.
1. Any matrix clearly has the same product down the diagonal as itself, so the relation is reflexive. The relation is symmetric because if $A$ has the same product down its diagonal as does $B$ , if $a_{1, 1} \cdot a_{2, 2} = b_{1, 1} \cdot b_{2, 2}$ , then $B$ has the same product as does $A$ .
  
  Transitivity is similar: suppose that $A$ ’s product is $r$ and that it equals $B$ ’s product. Suppose also that $B$ ’s product equals $C$ ’s. Then all three have a product of $r$ , and $A$ ’s equals $C$ ’s.
  
  There is an equivalence class for each real number, namely the class contains all $2 \times 2$ matrices whose product down the diagonal is that real.
2. For reflexivity, if the matrix $A$ has a $1$ entry then it is related to itself while if it does not then it is also related to itself. Symmetry also has two cases: suppose that $A$ and $B$ are related. If $A$ has a $1$ entry then so does $B$ , and thus $B$ is related to $A$ . If $A$ has no $1$ then neither does $B$ , and again $B$ is related to $A$ .
  
  For transitivity, suppose that $A$ is related to $B$ and $B$ to $C$ . If $A$ has a $1$ entry then so does $B$ , and because $B$ is related to $C$ , therefore so does $C$ , and hence $A$ is related to $C$ . Likewise, if $A$ has no $1$ then neither does $B$ , and consequently neither does $C$ , giving the conclusion that $A$ is related to $C$ .
  
  There are exactly two equivalence classes, one containing any $2 \times 2$ matrix that has at least one entry that is a $1$ , and the other containing all the matrices that have no $1$ ’s.
Exercise 1.21 Worked answer

Show that each is not an equivalence on the set of $2 \times 2$ matrices.
1. Two matrices $A, B$ are related if $a_{1, 1} = - b_{1, 1}$ .
2. Two matrices are related if the sum of their entries are within $5$ , that is, $A$ is related to $B$ if $| (a_{1, 1} + \dots + a_{2, 2}) - (b_{1, 1} + \dots + b_{2, 2}) | < 5$ .
Back to Exercise 1.21

Answer.
1. This relation is not reflexive. For instance, any matrix with an upper-left entry of $1$ is not related to itself.
2. This relation is not transitive. For these three, $A$ is related to $B$ , and $B$ is related to $C$ , but $A$ is not related to $C$ .
  
  $A = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}), B = (\begin{matrix} 4 & 0 \\ 0 & 0 \end{matrix}), C = (\begin{matrix} 8 & 0 \\ 0 & 0 \end{matrix}),$

The Linear Combination Lemma

We will close this chapter by proving that every matrix is row equivalent to one and only one reduced echelon form matrix. The ideas here will reappear, and be further developed, in the next chapter.

The crucial observation concerns how row operations act to transform one matrix into another: the new rows are linear combinations of the old.

Example 2.1 Consider this Gauss-Jordan reduction.

$\begin{aligned} (\begin{array}{ccc} 2 & 1 & 0 \\ 1 & 3 & 5 \end{array}) & ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 2) ρ_{1} + ρ_{2}} (\begin{array}{ccc} 2 & 1 & 0 \\ 0 & 5 / 2 & 5 \end{array}) \\ ⟶_{\begin{matrix} (2 / 5) ρ_{2} \end{matrix}}^{(1 / 2) ρ_{1}} (\begin{array}{ccc} 1 & 1 / 2 & 0 \\ 0 & 1 & 2 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 2) ρ_{2} + ρ_{1}} (\begin{array}{ccc} 1 & 0 & - 1 \\ 0 & 1 & 2 \end{array}) \end{aligned}$

Denoting those matrices $A \to D \to G \to B$ and writing the rows of $A$ as $α_{1}$ and $α_{2}$ , etc., we have this.

$\begin{aligned} (\begin{array}{l} α_{1} \\ α_{2} \end{array}) & ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 2) ρ_{1} + ρ_{2}} (\begin{matrix} δ_{1} = α_{1} \\ δ_{2} = - (1 / 2) α_{1} + α_{2} \end{matrix}) \\ ⟶_{\begin{matrix} (2 / 5) ρ_{2} \end{matrix}}^{(1 / 2) ρ_{1}} (\begin{matrix} γ_{1} = (1 / 2) α_{1} \\ γ_{2} = - (1 / 5) α_{1} + (2 / 5) α_{2} \end{matrix}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 2) ρ_{2} + ρ_{1}} (\begin{matrix} β_{1} = (3 / 5) α_{1} - (1 / 5) α_{2} \\ β_{2} = - (1 / 5) α_{1} + (2 / 5) α_{2} \end{matrix}) \end{aligned}$

Example 2.2 The fact that Gaussian operations combine rows linearly also holds if there is a row swap. With this $A$ , $D$ , $G$ , and $B$

$(\begin{matrix} 0 & 2 \\ 1 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{matrix} 1 & 1 \\ 0 & 2 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{(1 / 2) ρ_{2}} (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$

we get these linear relationships.

$\begin{matrix} (\begin{array}{l} {\vec{α}}_{1} \\ {\vec{α}}_{2} \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{array}{l} {\vec{δ}}_{1} = {\vec{α}}_{2} \\ {\vec{δ}}_{2} = {\vec{α}}_{1} \end{array}) ⟶_{\begin{array}{l} \end{array}}^{(1 / 2) ρ_{2}} (\begin{array}{l} {\vec{γ}}_{1} = {\vec{α}}_{2} \\ {\vec{γ}}_{2} = (1 / 2) {\vec{α}}_{1} \end{array}) \\ ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{array}{l} {\vec{β}}_{1} = (- 1 / 2) {\vec{α}}_{1} + 1 \cdot {\vec{α}}_{2} \\ {\vec{β}}_{2} = (1 / 2) {\vec{α}}_{1} \end{array}) \end{matrix}$

In summary, Gauss’s Method systematically finds a suitable sequence of linear combinations of the rows.

Lemma 2.3 (Linear Combination Lemma) A linear combination of linear combinations is a linear combination.

Proof Given the set $c_{1, 1} x_{1} + \dots + c_{1, n} x_{n}$ through $c_{m, 1} x_{1} + \dots + c_{m, n} x_{n}$ of linear combinations of the $x$ ’s, consider a combination of those

$d_{1} (c_{1, 1} x_{1} + \dots + c_{1, n} x_{n}) + \dots + d_{m} (c_{m, 1} x_{1} + \dots + c_{m, n} x_{n})$

where the $d$ ’s are scalars along with the $c$ ’s. Distributing those $d$ ’s and regrouping gives

$= (d_{1} c_{1, 1} + \dots + d_{m} c_{m, 1}) x_{1} + \dots + (d_{1} c_{1, n} + \dots + d_{m} c_{m, n}) x_{n}$

which is also a linear combination of the $x$ ’s.

QED

Corollary 2.4 Where one matrix reduces to another, each row of the second is a linear combination of the rows of the first.

Proof For any two interreducible matrices $A$ and $B$ there is some minimum number of row operations that will take one to the other. We proceed by induction on that number.

In the base step, that we can go from one matrix to another using zero reduction operations, the two are equal. Then each row of $B$ is trivially a combination of $A$ ’s rows ${\vec{β}}_{i} = 0 \cdot {\vec{α}}_{1} + \dots + 1 \cdot {\vec{α}}_{i} + \dots + 0 \cdot {\vec{α}}_{m}$ .

For the inductive step assume the inductive hypothesis: with $k \geq 0$ , any matrix that can be derived from $A$ in $k$ or fewer operations has rows that are linear combinations of $A$ ’s rows. Consider a matrix $B$ such that reducing $A$ to $B$ requires $k + 1$ operations. In that reduction there is a next-to-last matrix $G$ , so that $A ⟶ \dots ⟶ G ⟶ B$ . The inductive hypothesis applies to this $G$ because it is only $k$ steps away from $A$ . That is, each row of $G$ is a linear combination of the rows of $A$ .

We will verify that the rows of $B$ are linear combinations of the rows of $G$ . Then the Linear Combination Lemma, Lemma 2.3, applies to show that the rows of $B$ are linear combinations of the rows of $A$ .

If the row operation taking $G$ to $B$ is a swap then the rows of $B$ are just the rows of $G$ reordered and each row of $B$ is a linear combination of the rows of $G$ . If the operation taking $G$ to $B$ is multiplication of a row by a scalar $c ρ_{i}$ then ${\vec{β}}_{i} = c {\vec{γ}}_{i}$ and the other rows are unchanged. Finally, if the row operation is adding a multiple of one row to another $r ρ_{i} + ρ_{j}$ then only row $j$ of $B$ differs from the matching row of $G$ , and ${\vec{β}}_{j} = r γ_{i} + γ_{j}$ , which is indeed a linear combinations of the rows of $G$ .

Because we have proved both a base step and an inductive step, the proposition follows by the principle of mathematical induction.

QED

We now have the insight that Gauss’s Method builds linear combinations of the rows. But of course its goal is to end in echelon form, since that is a particularly basic version of a linear system, as it has isolated the variables. For instance, in this matrix

$R = (\begin{matrix} 2 & 3 & 7 & 8 & 0 & 0 \\ 0 & 0 & 1 & 5 & 1 & 1 \\ 0 & 0 & 0 & 3 & 3 & 0 \\ 0 & 0 & 0 & 0 & 2 & 1 \end{matrix})$

$x_{1}$ has been removed from $x_{5}$ ’s equation. That is, Gauss’s Method has made $x_{5}$ ’s row in some way independent of $x_{1}$ ’s row.

The following result makes this intuition precise. We sometimes refer to Gauss’s Method as Gaussian elimination. What it eliminates is linear relationships among the rows.

Lemma 2.5 In an echelon form matrix, no nonzero row is a linear combination of the other nonzero rows.

Proof Let $R$ be an echelon form matrix and consider its non- $\vec{0}$ rows. First observe that if we have a row written as a combination of the others ${\vec{ρ}}_{i} = c_{1} {\vec{ρ}}_{1} + \dots + c_{i - 1} {\vec{ρ}}_{i - 1} + c_{i + 1} {\vec{ρ}}_{i + 1} + \dots + c_{m} {\vec{ρ}}_{m}$ then we can rewrite that equation as

$\begin{matrix} \vec{0} = c_{1} {\vec{ρ}}_{1} + \dots + c_{i - 1} {\vec{ρ}}_{i - 1} + c_{i} {\vec{ρ}}_{i} + c_{i + 1} {\vec{ρ}}_{i + 1} + \dots + c_{m} {\vec{ρ}}_{m} & (*) \end{matrix}$

where not all the coefficients are zero; specifically, $c_{i} = - 1$ . The converse holds also: given equation ( $*$ ) where some $c_{i} \neq 0$ we could express ${\vec{ρ}}_{i}$ as a combination of the other rows by moving $c_{i} {\vec{ρ}}_{i}$ to the left and dividing by $- c_{i}$ . Therefore we will have proved the theorem if we show that in ( $*$ ) all of the coefficients are $0$ . For that we use induction on the row number $i$ .

The base case is the first row $i = 1$ (if there is no such nonzero row, so that $R$ is the zero matrix, then the lemma holds vacuously). Let $ℓ_{i}$ be the column number of the leading entry in row $i$ . Consider the entry of each row that is in column $ℓ_{1}$ . Equation ( $*$ ) gives this.

$\begin{matrix} 0 = c_{1} r_{1, ℓ_{1}} + c_{2} r_{2, ℓ_{1}} + \dots + c_{m} r_{m, ℓ_{1}} & (* *) \end{matrix}$

The matrix is in echelon form so every row after the first has a zero entry in that column $r_{2, ℓ_{1}} = \dots = r_{m, ℓ_{1}} = 0$ . Thus equation ( $* *$ ) shows that $c_{1} = 0$ , because $r_{1, ℓ_{1}} \neq 0$ as it leads the row.

The inductive step is much the same as the base step. Again consider equation ( $*$ ). We will prove that if the coefficient $c_{i}$ is $0$ for each row index $i \in {1, \dots, k}$ then $c_{k + 1}$ is also $0$ . We focus on the entries from column $ℓ_{k + 1}$ .

$0 = c_{1} r_{1, ℓ_{k + 1}} + \dots + c_{k + 1} r_{k + 1, ℓ_{k + 1}} + \dots + c_{m} r_{m, ℓ_{k + 1}}$

By the inductive hypothesis $c_{1}$ , … $c_{k}$ are all $0$ so this reduces to the equation $0 = c_{k + 1} r_{k + 1, ℓ_{k + 1}} + \dots + c_{m} r_{m, ℓ_{k + 1}}$ . The matrix is in echelon form so the entries $r_{k + 2, ℓ_{k + 1}}$ , …, $r_{m, ℓ_{k + 1}}$ are all $0$ . Thus $c_{k + 1} = 0$ , because $r_{k + 1, ℓ_{k + 1}} \neq 0$ as it is the leading entry.

QED

With that, we are ready to show that the end product of Gauss-Jordan reduction is unique.

Theorem 2.6 Each matrix is row equivalent to a unique reduced echelon form matrix.

Proof [Yuster] Fix a number of rows $m$ . We will proceed by induction on the number of columns $n$ .

The base case is that the matrix has $n = 1$ column. If this is the zero matrix then its echelon form is the zero matrix. If instead it has any nonzero entries then when the matrix is brought to reduced echelon form it must have at least one nonzero entry, which must be a $1$ in the first row. Either way, its reduced echelon form is unique.

For the inductive step we assume that $n > 1$ and that all $m$ row matrices having fewer than $n$ columns have a unique reduced echelon form. Consider an $m \times n$ matrix $A$ and suppose that $B$ and $C$ are two reduced echelon form matrices derived from $A$ . We will show that these two must be equal.

Let $\hat{A}$ be the matrix consisting of the first $n - 1$ columns of $A$ . Observe that any sequence of row operations that bring $A$ to reduced echelon form will also bring $\hat{A}$ to reduced echelon form. By the inductive hypothesis this reduced echelon form of $\hat{A}$ is unique, so if $B$ and $C$ differ then the difference must occur in column $n$ .

We finish the inductive step and the argument by showing that the two cannot differ only in that column. Consider a homogeneous system of equations for which $A$ is the matrix of coefficients.

$\begin{matrix} \begin{array}{rcrcrcrcr} a_{1, 1} x_{1} & + & a_{1, 2} x_{2} & + & \dots & + & a_{1, n} x_{n} & = & 0 \\ a_{2, 1} x_{1} & + & a_{2, 2} x_{2} & + & \dots & + & a_{2, n} x_{n} & = & 0 \\ ⋮ \\ a_{m, 1} x_{1} & + & a_{m, 2} x_{2} & + & \dots & + & a_{m, n} x_{n} & = & 0 \end{array} & (*) \end{matrix}$

By Theorem One.I.1.5 the set of solutions to that system is the same as the set of solutions to $B$ ’s system

$\begin{matrix} \begin{array}{rcrcrcrcr} b_{1, 1} x_{1} & + & b_{1, 2} x_{2} & + & \dots & + & b_{1, n} x_{n} & = & 0 \\ b_{2, 1} x_{1} & + & b_{2, 2} x_{2} & + & \dots & + & b_{2, n} x_{n} & = & 0 \\ ⋮ \\ b_{m, 1} x_{1} & + & b_{m, 2} x_{2} & + & \dots & + & b_{m, n} x_{n} & = & 0 \end{array} & (* *) \end{matrix}$

and to $C$ ’s.

$\begin{matrix} \begin{array}{rcrcrcrcr} c_{1, 1} x_{1} & + & c_{1, 2} x_{2} & + & \dots & + & c_{1, n} x_{n} & = & 0 \\ c_{2, 1} x_{1} & + & c_{2, 2} x_{2} & + & \dots & + & c_{2, n} x_{n} & = & 0 \\ ⋮ \\ c_{m, 1} x_{1} & + & c_{m, 2} x_{2} & + & \dots & + & c_{m, n} x_{n} & = & 0 \end{array} & (* * *) \end{matrix}$

With $B$ and $C$ different only in column $n$ , suppose that they differ in row $i$ . Subtract row $i$ of ( $* * *$ ) from row $i$ of ( $* *$ ) to get the equation $(b_{i, n} - c_{i, n}) \cdot x_{n} = 0$ . We’ve assumed that $b_{i, n} \neq c_{i, n}$ and so we get $x_{n} = 0$ . Thus $x_{n}$ is not a free variable and so in ( $* *$ ) and ( $* * *$ ) the $n$ -th column contains the leading entry of some row, since in an echelon form matrix any column that does not contain a leading entry is associated with a free variable.

But now, with $B$ and $C$ equal on the first $n - 1$ columns, by the definition of reduced echeleon form their leading entries in the $n$ -th column are in the same row. And, both leading entries would have to be $1$ , and would have to be the only nonzero entries in that column. Therefore $B = C$ .

QED

We have asked whether any two echelon form versions of a linear system have the same number of free variables, and if so are they exactly the same variables? With the prior result we can answer both questions “yes.” There is no linear system such that, say, we could apply Gauss’s Method one way and get $y$ and $z$ free but apply it another way and get $y$ and $w$ free.

Before the proof, recall the distinction between free variables and parameters. This system

$\begin{array}{rcrcrcr} x & + & y & = & 1 \\ y & + & z & = & 2 \end{array}$

has one free variable, $z$ , because it is the only variable not leading a row. We have the habit of parametrizing using the free variable $y = 2 - z$ , $x = - 1 + z$ , but we could also parametrize using another variable, such as $z = 2 - y$ , $x = 1 - y$ . So the set of parameters is not unique, it is the set of free variables that is unique.

Corollary 2.7 If from a starting linear systems we derive by Gauss’s Method two different echelon form systems, then the two have the same free variables.

Proof The prior result says that the reduced echelon form is unique. We get from any echelon form version to the reduced echelon form by eliminating up, so any echelon form version of a system has the same free variables as the reduced echelon form version.

QED

We close with a recap. In Gauss’s Method we start with a matrix and then derive a sequence of other matrices. We defined two matrices to be related if we can derive one from the other. That relation is an equivalence relation, called row equivalence, and so partitions the set of all matrices into row equivalence classes.

Two matrices, (1,3;2,7) and (1,3;0,1), are marked in the same row-equivalence class within a partition of matrix space.

(There are infinitely many matrices in the pictured class, but we’ve only got room to show two.) We have proved there is one and only one reduced echelon form matrix in each row equivalence class. So the reduced echelon form is a canonical form³ for row equivalence: the reduced echelon form matrices are representatives of the classes.

A star marks a canonical representative in each row-equivalence class. The two-by-two identity matrix is the representative of the indicated class.

The idea here is that one way to understand a mathematical situation is by being able to classify the cases that can happen. This is a theme in this book and we have seen this several times already. We classified solution sets of linear systems into the no-elements, one-element, and infinitely-many elements cases. We also classified linear systems with the same number of equations as unknowns into the nonsingular and singular cases.

Here, where we are investigating row equivalence, we know that the set of all matrices breaks into the row equivalence classes and we now have a way to put our finger on each of those classes—we can think of the matrices in a class as derived by row operations from the unique reduced echelon form matrix in that class.

Put in more operational terms, uniqueness of reduced echelon form lets us answer questions about the classes by translating them into questions about the representatives. For instance, as promised in this section’s opening, we now can decide whether one matrix can be derived from another by row reduction. We apply the Gauss-Jordan procedure to both and see if they yield the same reduced echelon form.

Example 2.8 These matrices are not row equivalent

$(\begin{matrix} 1 & - 3 \\ - 2 & 6 \end{matrix}) (\begin{matrix} 1 & - 3 \\ - 2 & 5 \end{matrix})$

because their reduced echelon forms are not equal.

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

Example 2.9 Any nonsingular $3 \times 3$ matrix Gauss-Jordan reduces to this.

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

Example 2.10 We can describe all the classes by listing all possible reduced echelon form matrices. Any $2 \times 2$ matrix lies in one of these: the class of matrices row equivalent to this,

$(\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$

the infinitely many classes of matrices row equivalent to one of this type

$(\begin{matrix} 1 & a \\ 0 & 0 \end{matrix})$

where $a \in ℝ$ (including $a = 0$ ), the class of matrices row equivalent to this,

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

and the class of matrices row equivalent to this

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

(this is the class of nonsingular $2 \times 2$ matrices).

Exercises

Exercise 2.11 Worked answer

Recommended. Decide if the matrices are row equivalent.
1. $(\begin{matrix} 1 & 2 \\ 4 & 8 \end{matrix}), (\begin{matrix} 0 & 1 \\ 1 & 2 \end{matrix})$
2. $(\begin{matrix} 1 & 0 & 2 \\ 3 & - 1 & 1 \\ 5 & - 1 & 5 \end{matrix}), (\begin{matrix} 1 & 0 & 2 \\ 0 & 2 & 10 \\ 2 & 0 & 4 \end{matrix})$
3. $(\begin{matrix} 2 & 1 & - 1 \\ 1 & 1 & 0 \\ 4 & 3 & - 1 \end{matrix}), (\begin{matrix} 1 & 0 & 2 \\ 0 & 2 & 10 \end{matrix})$
4. $(\begin{matrix} 1 & 1 & 1 \\ - 1 & 2 & 2 \end{matrix}), (\begin{matrix} 0 & 3 & - 1 \\ 2 & 2 & 5 \end{matrix})$
5. $(\begin{matrix} 1 & 1 & 1 \\ 0 & 0 & 3 \end{matrix}), (\begin{matrix} 0 & 1 & 2 \\ 1 & - 1 & 1 \end{matrix})$
Back to Exercise 2.11

Answer. Bring each to reduced echelon form and compare.
1. The first gives
  
  $⟶_{\begin{array}{l} \end{array}}^{- 4 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix})$
  
  while the second gives
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
  
  The two reduced echelon form matrices are not identical, and so the original matrices are not row equivalent.
2. The first is this.
  
  $⟶_{\begin{array}{l} - 5 ρ_{1} + ρ_{3} \end{array}}^{- 3 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 0 & 2 \\ 0 & - 1 & - 5 \\ 0 & - 1 & - 5 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 0 & 2 \\ 0 & - 1 & - 5 \\ 0 & 0 & 0 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2}} (\begin{matrix} 1 & 0 & 2 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \end{matrix})$
  
  The second is this.
  
  $⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{1} + ρ_{3}} (\begin{matrix} 1 & 0 & 2 \\ 0 & 2 & 10 \\ 0 & 0 & 0 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{(1 / 2) ρ_{2}} (\begin{matrix} 1 & 0 & 2 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \end{matrix})$
  
  These two are row equivalent.
3. These two are not row equivalent because they have different sizes.
4. The first,
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 1 & 1 \\ 0 & 3 & 3 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{(1 / 3) ρ_{2}} (\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix})$
  
  and the second.
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{matrix} 2 & 2 & 5 \\ 0 & 3 & - 1 \end{matrix}) ⟶_{\begin{array}{l} (1 / 3) ρ_{2} \end{array}}^{(1 / 2) ρ_{1}} (\begin{matrix} 1 & 1 & 5 / 2 \\ 0 & 1 & - 1 / 3 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 17 / 6 \\ 0 & 1 & - 1 / 3 \end{matrix})$
  
  These are not row equivalent.
5. Here the first is
  
  $⟶_{\begin{array}{l} \end{array}}^{(1 / 3) ρ_{2}} (\begin{matrix} 1 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$
  
  while this is the second.
  
  $⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{matrix} 1 & - 1 & 1 \\ 0 & 1 & 2 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 3 \\ 0 & 1 & 2 \end{matrix})$
  
  These are not row equivalent.
Exercise 2.12 Worked answer

Which of these matrices are row equivalent to each other?
1. $(\begin{matrix} 1 & 3 \\ 2 & 4 \end{matrix})$
2. $(\begin{matrix} 1 & 5 \\ 2 & 10 \end{matrix})$
3. $(\begin{matrix} 1 & - 1 \\ 3 & 0 \end{matrix})$
4. $(\begin{matrix} 2 & 6 \\ 4 & 10 \end{matrix})$
5. $(\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$
6. $(\begin{matrix} 3 & 3 \\ 2 & 2 \end{matrix})$
Back to Exercise 2.12

Answer. Perform Gauss-Jordan reduction on each. Two matrices are row-equivalent if and only if they have the same reduced echelon form. Here is the reduced form for each.
1. $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
2. $(\begin{matrix} 1 & 5 \\ 0 & 0 \end{matrix})$
3. $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
4. $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
5. $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
6. $(\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$
Exercise 2.13 Worked answer

Produce three other matrices row equivalent to the given one.
1. $(\begin{matrix} 1 & 3 \\ 4 & - 1 \end{matrix})$
2. $(\begin{matrix} 0 & 1 & 2 \\ 1 & 1 & 1 \\ 2 & 3 & 4 \end{matrix})$
Back to Exercise 2.13

Answer. For each you can just perform some row operations on the starting matrix.
1. Multiplying the first row by $3$ gives this.
  
  $(\begin{matrix} 3 & 9 \\ 4 & - 1 \end{matrix})$
  
  (There is no sense to this particular choice of row operation; it is just the first thing that came to mind.) Two other row operations are a row swap $ρ_{1} \leftrightarrow ρ_{2}$ and adding $ρ_{1} + ρ_{2}$ .
  
  $(\begin{matrix} 4 & - 1 \\ 1 & 3 \end{matrix}) (\begin{matrix} 1 & 3 \\ 5 & 2 \end{matrix})$
2. Doing the same three arbitrary row operations gives these three.
  
  $(\begin{matrix} 0 & 3 & 6 \\ 1 & 1 & 1 \\ 2 & 3 & 4 \end{matrix}) (\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 2 & 3 & 4 \end{matrix}) (\begin{matrix} 0 & 1 & 2 \\ 1 & 2 & 3 \\ 2 & 3 & 4 \end{matrix})$
Exercise 2.14 Worked answer

Recommended. Perform Gauss’s Method on this matrix. Express each row of the final matrix as a linear combination of the rows of the starting matrix.

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

Back to Exercise 2.14

Answer. The Gaussian reduction is routine.

$(\begin{matrix} 1 & 2 & 1 \\ 3 & - 1 & 0 \\ 0 & 4 & 0 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- 3 ρ_{1} + ρ_{2}} (\begin{matrix} 1 & 2 & 1 \\ 0 & - 7 & - 3 \\ 0 & 4 & 0 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{(4 / 7) ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 2 & 1 \\ 0 & - 7 & - 3 \\ 0 & 0 & - 12 / 7 \end{matrix})$

Denoting those matrices $A$ , $D$ , and $B$ respectively, we have this.

$\begin{aligned} (\begin{array}{c} α_{1} \\ α_{2} \\ α_{3} \end{array}) & ⟶_{\begin{matrix} \end{matrix}}^{- 3 ρ_{1} + ρ_{2}} (\begin{array}{c} δ_{1} = α_{1} \\ δ_{2} = - 3 α_{1} + α_{2} \\ δ_{3} = α_{3} \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{(4 / 7) ρ_{2} + ρ_{3}} (\begin{array}{c} β_{1} = α_{1} \\ β_{2} = - 3 α_{1} + α_{2} \\ β_{3} = - (12 / 7) α_{1} + (4 / 7) α_{2} + α_{3} \end{array}) \end{aligned}$
Exercise 2.15 Worked answer

Describe the matrices in each of the classes represented in Example 2.10.

Back to Exercise 2.15

Answer. First, the only matrix row equivalent to the matrix of all $0$ ’s is itself (since row operations have no effect).

Second, the matrices that reduce to

$(\begin{matrix} 1 & a \\ 0 & 0 \end{matrix})$

have the form

$(\begin{matrix} b & b a \\ c & c a \end{matrix})$

(where $a, b, c \in ℝ$ , and $b$ and $c$ are not both zero).

Next, the matrices that reduce to

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

have the form

$(\begin{matrix} 0 & a \\ 0 & b \end{matrix})$

(where $a, b \in ℝ$ , and not both are zero).

Finally, the matrices that reduce to

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

are the nonsingular matrices. That’s because a linear system for which this is the matrix of coefficients will have a unique solution, and that is the definition of nonsingular. (Another way to say the same thing is to say that they fall into none of the above classes.)
Exercise 2.16 Worked answer

Describe all matrices in the row equivalence class of these.
1. $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$
2. $(\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})$
3. $(\begin{matrix} 1 & 1 \\ 1 & 3 \end{matrix})$
Back to Exercise 2.16

Answer.
1. They have the form
  
  $(\begin{matrix} a & 0 \\ b & 0 \end{matrix})$
  
  where at least one of $a, b \in ℝ$ is nonzero.
2. They have this form
  
  $(\begin{matrix} a & 2 a \\ b & 2 b \end{matrix})$
  
  where at least one of $a, b \in ℝ$ is nonzero.
3. The given matrix is nonsingular. So the row equivalence class consists of all nonsinglar $2 \times 2$ matrices. (To give a formula, they have the form
  
  $(\begin{matrix} a & b \\ c & d \end{matrix})$
  
  for $a, b, c, d \in ℝ$ ) where $a d - b c \neq 0$ . We will see in Chapter Four that this formula determines when a $2 \times 2$ matrix is nonsingular.)
Exercise 2.17 Worked answer

How many row equivalence classes are there?

Back to Exercise 2.17

Answer. Infinitely many. For instance, in

$(\begin{matrix} 1 & k \\ 0 & 0 \end{matrix})$

each $k \in ℝ$ gives a different class.
Exercise 2.18 Worked answer

Can row equivalence classes contain different-sized matrices?

Back to Exercise 2.18

Answer. No. Row operations do not change the size of a matrix.
Exercise 2.19 Worked answer

How big are the row equivalence classes?
1. Show that for any matrix of all zeros, the class is finite.
2. Do any other classes contain only finitely many members?
Back to Exercise 2.19

Answer.
1. A row operation on a matrix of zeros has no effect. Thus each such matrix is alone in its row equivalence class.
2. No. Any nonzero entry can be rescaled.
Exercise 2.20 Worked answer

Recommended. Give two reduced echelon form matrices that have their leading entries in the same columns, but that are not row equivalent.

Back to Exercise 2.20

Answer. Here are two.

$(\begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) and (\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix})$
Exercise 2.21 Worked answer

Recommended. Show that any two $n \times n$ nonsingular matrices are row equivalent. Are any two singular matrices row equivalent?

Back to Exercise 2.21

Answer. Any two $n \times n$ nonsingular matrices have the same reduced echelon form, namely the matrix with all $0$ ’s except for $1$ ’s down the diagonal.

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ ⋱ \\ 0 & 0 & 1 \end{matrix})$

Two same-sized singular matrices need not be row equivalent. For example, these two $2 \times 2$ singular matrices are not row equivalent.

$(\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}) and (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$
Exercise 2.22 Worked answer

Recommended. Describe all of the row equivalence classes containing these.
1. $2 \times 2$ matrices
2. $2 \times 3$ matrices
3. $3 \times 2$ matrices
4. $3 \times 3$ matrices
Back to Exercise 2.22

Answer. Since there is one and only one reduced echelon form matrix in each class, we can just list the possible reduced echelon form matrices.

For that list, see the answer for Exercise 1.14.
Exercise 2.23 Worked answer
1. Show that a vector ${\vec{β}}_{0}$ is a linear combination of members of the set ${{\vec{β}}_{1}, \dots, {\vec{β}}_{n}}$ if and only if there is a linear relationship $\vec{0} = c_{0} {\vec{β}}_{0} + \dots + c_{n} {\vec{β}}_{n}$ where $c_{0}$ is not zero. (Hint. Watch out for the ${\vec{β}}_{0} = \vec{0}$ case.)
2. Use that to simplify the proof of Lemma 2.5.
Back to Exercise 2.23

Answer.
1. If there is a linear relationship where $c_{0}$ is not zero then we can subtract $c_{0} {\vec{β}}_{0}$ from both sides and divide by $- c_{0}$ to get ${\vec{β}}_{0}$ as a linear combination of the others. (Remark: if there are no other vectors in the set—if the relationship is, say, $\vec{0} = 3 \cdot \vec{0}$ —then the statement is still true because the zero vector is by definition the sum of the empty set of vectors.)
  
  Conversely, if ${\vec{β}}_{0}$ is a combination of the others ${\vec{β}}_{0} = c_{1} {\vec{β}}_{1} + \dots + c_{n} {\vec{β}}_{n}$ then subtracting ${\vec{β}}_{0}$ from both sides gives a relationship where at least one of the coefficients is nonzero; namely, the $- 1$ in front of ${\vec{β}}_{0}$ .
2. The first row is not a linear combination of the others for the reason given in the proof: in the equation of components from the column containing the leading entry of the first row, the only nonzero entry is the leading entry from the first row, so its coefficient must be zero. Thus, from the prior part of this exercise, the first row is in no linear relationship with the other rows.
  
  Thus, when considering whether the second row can be in a linear relationship with the other rows, we can leave the first row out. But now the argument just applied to the first row will apply to the second row. (That is, we are arguing here by induction.)
Exercise 2.24 Worked answer

Recommended. [Trono] Three truck drivers went into a roadside cafe. One truck driver purchased four sandwiches, a cup of coffee, and ten doughnuts for $ $8.45$ . Another driver purchased three sandwiches, a cup of coffee, and seven doughnuts for $ $6.30$ . What did the third truck driver pay for a sandwich, a cup of coffee, and a doughnut?

Back to Exercise 2.24

Answer. We know that $4 s + c + 10 d = 8.45$ and that $3 s + c + 7 d = 6.30$ , and we’d like to know what $s + c + d$ is. Fortunately, $s + c + d$ is a linear combination of $4 s + c + 10 d$ and $3 s + c + 7 d$ . Calling the unknown price $p$ , we have this reduction.

$\begin{aligned} (\begin{array}{cccc} 4 & 1 & 10 & 8.45 \\ 3 & 1 & 7 & 6.30 \\ 1 & 1 & 1 & p \end{array}) & ⟶_{\begin{matrix} - (1 / 4) ρ_{1} + ρ_{3} \end{matrix}}^{- (3 / 4) ρ_{1} + ρ_{2}} (\begin{array}{cccc} 4 & 1 & 10 & 8.45 \\ 0 & 1 / 4 & - 1 / 2 & - 0.037 5 \\ 0 & 3 / 4 & - 3 / 2 & p - 2.112 5 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- 3 ρ_{2} + ρ_{3}} (\begin{array}{cccc} 4 & 1 & 10 & 8.45 \\ 0 & 1 / 4 & - 1 / 2 & - 0.037 5 \\ 0 & 0 & 0 & p - 2.00 \end{array}) \end{aligned}$

The price paid is $ $2.00$ .
Exercise 2.25 Worked answer

The Linear Combination Lemma says which equations can be gotten from Gaussian reduction of a given linear system.
1. Produce an equation not implied by this system.
  
  $\begin{array}{rcrcr} 3 x & + & 4 y & = & 8 \\ 2 x & + & y & = & 3 \end{array}$
2. Can any equation be derived from an inconsistent system?
Back to Exercise 2.25

Answer.
1. An easy answer is this.
  
  $0 = 3$
  
  For a less wise-guy-ish answer, solve the system:
  
  $(\begin{array}{ccr} 3 & 4 & 8 \\ 2 & 1 & 3 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- (2 / 3) ρ_{1} + ρ_{2}} (\begin{array}{ccr} 3 & 4 & 8 \\ 0 & - 5 / 3 & - 7 / 3 \end{array})$
  
  gives $y = 7 / 5$ and $x = 4 / 5$ . Now any equation not satisfied by $(7 / 5, 4 / 5)$ will do, e.g., $5 x + 5 y = 10$ .
2. Every equation can be derived from an inconsistent system. For instance, here is how to derive $3 x + 2 y = 4$ from $0 = 5$ . First,
  
  $0 = 5 ⟶_{\begin{array}{l} \end{array}}^{(3 / 5) ρ_{1}} 0 = 3 ⟶_{\begin{array}{l} \end{array}}^{x ρ_{1}} 0 = 3 x$
  
  (validity of the $x = 0$ case is separate but clear). Similarly, $0 = 2 y$ . Ditto for $0 = 4$ . But now, $0 + 0 = 0$ gives $3 x + 2 y = 4$ .
Exercise 2.26 Worked answer

[Hoffman & Kunze] Extend the definition of row equivalence to linear systems. Under your definition, do equivalent systems have the same solution set?

Back to Exercise 2.26

Answer. Define linear systems to be equivalent if their augmented matrices are row equivalent. The proof that equivalent systems have the same solution set is easy.
Exercise 2.27 Worked answer

In this matrix

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

the first and second columns add to the third.
1. Show that remains true under any row operation.
2. Make a conjecture.
3. Prove that it holds.
Back to Exercise 2.27

Answer.
1. The three possible row swaps are easy, as are the three possible rescalings. One of the six possible row combinations is $k ρ_{1} + ρ_{2}$ :
  
  $(\begin{matrix} 1 & 2 & 3 \\ k \cdot 1 + 3 & k \cdot 2 + 0 & k \cdot 3 + 3 \\ 1 & 4 & 5 \end{matrix})$
  
  and again the first and second columns add to the third. The other five combinations are similar.
2. The obvious conjecture is that row operations do not change linear relationships among columns.
3. A case-by-case proof follows the sketch given in the first item.

References cited in this section

Cleary

R. Cleary, private communication, Nov. 2011.

Yuster

Thomas Yuster, The Reduced Row Echelon Form of a Matrix is Unique: a Simple Proof, Mathematics Magazine, vol. 57, no. 2 (Mar. 1984), pp. 93-94.

Trono

Tony Trono, compiler, University of Vermont Mathematics Department High School Prize Examinations 1958-1991, mimeographed printing, 1991.

Hoffman & Kunze

Kenneth Hoffman, Ray Kunze, Linear Algebra, second edition, Prentice-Hall, 1971.

More information on equivalence relations is in the appendix.↩︎
More information on partitions and class representatives is in the appendix.↩︎
More information on canonical representatives is in the appendix.↩︎