§ 18. Systems of Linear Equations - Computational Aspects

Equivalent Systems of Linear Equations

Definition 18.1 : Equivalent Systems of Linear Equations

Two systems of linear equations are called equivalent if they have the same solution set.

Theorem 18.2 : Obtaining equivalent systems via invertible matrices

Let \(A x=b\) be a system of \(m\) linear equations in \(n\) unknowns, and let \(C\) be an invertible \(m \times m\) matrix. Then the system \((C A) x=C b\) is equivalent to \(A x=b\).

Proof

Let \(K\) be the solution set for \(A x=b\) and \(K^{\prime}\) the solution set for \((C A) x=C b\). If \(w \in K\), then \(A w=b\). So \((C A) w=C b\), and hence \(w \in K^{\prime}\). Thus \(K \subseteq K^{\prime}\).

Conversely, if \(w \in K^{\prime}\), then \((C A) w=C b\). Hence

\[ A w=C^{-1}(C A w)=C^{-1}(C b)=b \]

so \(w \in K\). Thus \(K^{\prime} \subseteq K\), and therefore, \(K=K^{\prime}\).

Corollary 18.3 : Obtaining equivalent systems via via elementary row operations

Let \(A x=b\) be a system of \(m\) linear equations in \(n\) unknowns. If \(\left(A^{\prime} \mid b^{\prime}\right)\) is obtained from \((A \mid b)\) by a finite number of elementary row operations, then the system \(A^{\prime} x=b^{\prime}\) is equivalent to the original system.

Proof

Suppose that \(\left(A^{\prime} \mid b^{\prime}\right)\) is obtained from \((A \mid b)\) by elementary row operations. These may be executed by multiplying \((A \mid b)\) by elementary \(m \times m\) matrices \(E_{1}, E_{2}, \ldots, E_{p}\). Let \(C=E_{p} \cdots E_{2} E_{1}\); then

\[ \left(A^{\prime} \mid b^{\prime}\right)=C(A \mid b)=(C A \mid C b) \]

Since each \(E_{i}\) is invertible, so is \(C\). Now \(A^{\prime}=C A\) and \(b^{\prime}=C b\). Thus by Theorem 18.2, the system \(A^{\prime} x=b^{\prime}\) is equivalent to the system \(A x=b\).

Reduced Row Echelon Form and Gaussian Elimination

Definition 18.4 : Reduced Row Echelon Form

A matrix is said to be in reduced row echelon form if the following three conditions are satisfied.

• (a) Any row containing a nonzero entry precedes any row in which all the entries are zero (if any).
• (b) The first nonzero entry in each row is the only nonzero entry in its column.
• (c) The first nonzero entry in each row is 1 and it occurs in a column to the right of the first nonzero entry in the preceding row.

Example 18.5 : Row reduction to reduced row echelon form

Consider the system of linear equations

\[ \begin{aligned} 3 x_{1}+2 x_{2}+3 x_{3}-2 x_{4} & =1 \\ x_{1}+x_{2}+x_{3} & =3 \\ x_{1}+2 x_{2}+x_{3}-x_{4} & =2 . \end{aligned} \]

First, we form the augmented matrix

\[ \left(\begin{array}{rrrr|r} 3 & 2 & 3 & -2 & 1 \\ 1 & 1 & 1 & 0 & 3 \\ 1 & 2 & 1 & -1 & 2 \end{array}\right) . \]

By using elementary row operations, we transform the augmented matrix into an upper triangular matrix in which the first nonzero entry of each row is 1, and it occurs in a column to the right of the first nonzero entry of each preceding row.

1. In the leftmost nonzero column, create a 1 in the first row. In our example, we can accomplish this step by interchanging the first and third rows. The resulting matrix is

   \[ \left(\begin{array}{rrrr|r} 1 & 2 & 1 & -1 & 2 \\ 1 & 1 & 1 & 0 & 3 \\ 3 & 2 & 3 & -2 & 1 \end{array}\right) . \]

2. By means of type 3 row operations, use the first row to obtain zeros in the remaining positions of the leftmost nonzero column. In our example, we must add -1 times the first row to the second row and then add -3 times the first row to the third row to obtain

   \[ \left(\begin{array}{rrrr|r} 1 & 2 & 1 & -1 & 2 \\ 0 & -1 & 0 & 1 & 1 \\ 0 & -4 & 0 & 1 & -5 \end{array}\right) . \]

3. Create a 1 in the next row in the leftmost possible column, without using previous row(s). In our example, the second column is the leftmost possible column, and we can obtain a 1 in the second row, second column by multiplying the second row by -1. This operation produces

   \[ \left(\begin{array}{rrrr|r} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & -4 & 0 & 1 & -5 \end{array}\right) . \]

4. Now use type 3 elementary row operations to obtain zeros below the 1 created in the preceding step. In our example, we must add four times the second row to the third row. The resulting matrix is

   \[ \left(\begin{array}{rrrr|r} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & -3 & -9 \end{array}\right) . \]

5. Repeat steps 3 and 4 on each succeeding row until no nonzero rows remain. (This creates zeros above the first nonzero entry in each row.) In our example, this can be accomplished by multiplying the third row by \(-\frac{1}{3}\). This operation produces

   \[ \left(\begin{array}{rrrr|r} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 1 & 3 \end{array}\right) . \]

   We have now obtained the desired matrix. To complete the simplification of the augmented matrix, we must make the first nonzero entry in each row the only nonzero entry in its column. (This corresponds to eliminating certain unknowns from all but one of the equations.)

6. Work upward, beginning with the last nonzero row, and add multiples of each row to the rows above. (This creates zeros above the first nonzero entry in each row.) In our example, the third row is the last nonzero row, and the first nonzero entry of this row lies in column 4. Hence we add the third row to the first and second rows to obtain zeros in row 1, column 4 and row 2, column 4. The resulting matrix is

   \[ \left(\begin{array}{llll|l} 1 & 2 & 1 & 0 & 5 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}\right) \]

7. Repeat the process described in step 6 for each preceding row until it is performed with the second row, at which time the reduction process is complete. In our example, we must add -2 times the second row to the first row in order to make the first row, second column entry become zero. This operation produces

   \[ \left(\begin{array}{llll|l} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}\right) . \]

---

We have now obtained the desired reduction of the augmented matrix. This matrix corresponds to the system of linear equations

\[ \begin{aligned} x_{1}+x_{3} & =1 \\ x_{2} & =2 \\ x_{4} & =3 \end{aligned} \]

Recall that, by Corollary 18.3, this system is equivalent to the original system. But this system is easily solved. Obviously \(x_{2}=2\) and \(x_{4}=3\). Moreover, \(x_{1}\) and \(x_{3}\) can have any values provided their sum is 1. Letting \(x_{3}=t\), we then have \(x_{1}=1-t\). Thus an arbitrary solution to the original system has the form

\[ \left(\begin{array}{c} 1-t \\ 2 \\ t \\ 3 \end{array}\right)=\left(\begin{array}{l} 1 \\ 2 \\ 0 \\ 3 \end{array}\right)+t\left(\begin{array}{r} -1 \\ 0 \\ 1 \\ 0 \end{array}\right) \]

Observe that

\[ \left\{\left(\begin{array}{r} -1 \\ 0 \\ 1 \\ 0 \end{array}\right)\right\} \]

is a basis for the homogeneous system of equations corresponding to the given system.

Concept 18.6 : Gaussian elimination

The procedure described in Example 18.5 for reducing an augmented matrix to reduced row echelon form is called Gaussian elimination. It consists of two separate parts.

1. In the forward pass (steps 1-5), the augmented matrix is transformed into an upper triangular matrix in which the first nonzero entry of each row is 1, and it occurs in a column to the right of the first nonzero entry of each preceding row.
2. In the backward pass or back-substitution (steps 6-7), the upper triangular matrix is transformed into reduced row echelon form by making the first nonzero entry of each row the only nonzero entry of its column.

Theorem 18.7 : Gaussian elimination produces reduced row echelon form.

Gaussian elimination transforms any matrix into its reduced row echelon form.

Proof

In the forward pass, we satisfy conditions (a) and (c) in the definition of reduced row echelon form (Definition 18.4) and thereby make zero all entries below the first nonzero entry in each row. Then in the backward pass, we make zero all entries above the first nonzero entry in each row, thereby satisfying condition (b) in the definition of reduced row echelon form (Definition 18.4).

Example 18.8 : Solving a system in reduced row echelon form

We now describe a method for solving a system in which the augmented matrix is in reduced row echelon form. To illustrate this procedure, we consider the system

\[ \begin{aligned} 2 x_{1}+3 x_{2}+x_{3}+4 x_{4}-9 x_{5} & =17 \\ x_{1}+x_{2}+x_{3}+x_{4}-3 x_{5} & =6 \\ x_{1}+x_{2}+x_{3}+2 x_{4}-5 x_{5} & =8 \\ 2 x_{1}+2 x_{2}+2 x_{3}+3 x_{4}-8 x_{5} & =14 \end{aligned} \]

for which the augmented matrix is

\[ \left(\begin{array}{rrrrr|r} 2 & 3 & 1 & 4 & -9 & 17 \\ 1 & 1 & 1 & 1 & -3 & 6 \\ 1 & 1 & 1 & 2 & -5 & 8 \\ 2 & 2 & 2 & 3 & -8 & 14 \end{array}\right) . \]

Applying Gaussian elimination to the augmented matrix of the system produces the following sequence of matrices.

\[ \left(\begin{array}{rrrrr|r} 2 & 3 & 1 & 4 & -9 & 17 \\ 1 & 1 & 1 & 1 & -3 & 6 \\ 1 & 1 & 1 & 2 & -5 & 8 \\ 2 & 2 & 2 & 3 & -8 & 14 \end{array}\right) \longrightarrow\left(\begin{array}{lllll|r} 1 & 1 & 1 & 1 & -3 & 6 \\ 2 & 3 & 1 & 4 & -9 & 17 \\ 1 & 1 & 1 & 2 & -5 & 8 \\ 2 & 2 & 2 & 3 & -8 & 14 \end{array}\right) \longrightarrow \]

\[ \begin{aligned} \left(\begin{array}{rrrrr|r} 1 & 1 & 1 & 1 & -3 & 6 \\ 0 & 1 & -1 & 2 & -3 & 5 \\ 0 & 0 & 0 & 1 & -2 & 2 \\ 0 & 0 & 0 & 1 & -2 & 2 \end{array}\right) & \longrightarrow\left(\begin{array}{rrrrr|r} 1 & 1 & 1 & 1 & -3 & 6 \\ 0 & 1 & -1 & 2 & -3 & 5 \\ 0 & 0 & 0 & 1 & -2 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \longrightarrow \\ \left(\begin{array}{rrrrr|r} 1 & 1 & 1 & 0 & -1 & 4 \\ 0 & 1 & -1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & -2 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) & \longrightarrow\left(\begin{array}{rrrrr|r} 1 & 0 & 2 & 0 & -2 & 3 \\ 0 & 1 & -1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & -2 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{aligned} \]

The system of linear equations corresponding to this last matrix is

\[ \begin{aligned} x_{1}+2 x_{3}-2 x_{5} & =3 \\ x_{2}-x_{3}+x_{5} & =1 \\ x_{4}-2 x_{5} & =2 . \end{aligned} \]

Notice that we have ignored the last row since it consists entirely of zeros. To solve a system for which the augmented matrix is in reduced row echelon form, divide the variables into two sets. The first set consists of those variables that appear as leftmost variables in one of the equations of the system (in this case the set is \(\left\{x_{1}, x_{2}, x_{4}\right\}\)). The second set consists of all the remaining variables (in this case, \(\left\{x_{3}, x_{5}\right\}\)). To each variable in the second set, assign a parametric value \(t_{1}, t_{2}, \ldots\left(x_{3}=t_{1}, x_{5}=t_{2}\right)\), and then solve for the variables of the first set in terms of those in the second set:

\[ \begin{aligned} x_{1} & = -2 x_{3}+2 x_{5}+3 & = -2 t_{1}+2 t_{2}+3 \\ x_{2} & = x_{3}-x_{5}+1 & = t_{1}-t_{2}+1 \\ x_{4} & = 2 x_{5}+2 & =2 t_{2}+2 \end{aligned} \]

Thus an arbitrary solution is of the form

\[ \left(\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}\right)=\left(\begin{array}{c} -2 t_{1}+2 t_{2}+3 \\ t_{1}-t_{2}+1 \\ t_{1} \\ 2 t_{2}+2 \\ t_{2} \end{array}\right)=\left(\begin{array}{l} 3 \\ 1 \\ 0 \\ 2 \\ 0 \end{array}\right)+t_{1}\left(\begin{array}{r} -2 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}\right)+t_{2}\left(\begin{array}{r} 2 \\ -1 \\ 0 \\ 2 \\ 1 \end{array}\right), \]

where \(t_{1}, t_{2} \in R\). Notice that

\[ \left\{\left(\begin{array}{r} -2 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}\right),\left(\begin{array}{r} 2 \\ -1 \\ 0 \\ 2 \\ 1 \end{array}\right)\right\} \]

is a basis for the solution set of the corresponding homogeneous system of equations and

\[ \left(\begin{array}{l} 3 \\ 1 \\ 0 \\ 2 \\ 0 \end{array}\right) \]

is a particular solution to the original system.

Concept 18.9 : General solution from reduced row echelon form

As in Example 18.8, in simplifying the augmented matrix of the system to reduced row echelon form, we are in effect simultaneously finding a particular solution to the original system and a basis for the solution set of the associated homogeneous system.

Moreover, this procedure detects when a system is inconsistent, for solutions exist if and only if, in the reduction of the augmented matrix to reduced row echelon form, we do not obtain a row in which the only nonzero entry lies in the last column.

Proof

Reduce the augmented matrix \((A \mid b)\) to reduced row echelon form \((A' \mid b')\) using elementary row operations. These operations do not change the solution set, so \(A x=b\) is consistent if and only if \(A' x=b'\) is consistent.

If \((A' \mid b')\) has a row of the form \((0,\ldots,0 \mid c)\) with \(c \neq 0\), then the corresponding equation is \(0=c\), which is impossible. Hence the system is inconsistent.

Conversely, suppose no such row occurs. Set all free variables to \(0\). In reduced row echelon form, each pivot variable then equals the entry in the last column of its row (since the pivot is \(1\) and all other pivot columns are \(0\)). This produces a solution, so the system is consistent.

Therefore, solutions exist if and only if the reduction does not produce a row whose only nonzero entry lies in the last column.

Thus to use this procedure for solving a system \(A x=b\) of \(m\) linear equations in \(n\) unknowns, we need only begin to transform the augmented matrix \((A \mid b)\) into its reduced row echelon form \((A^{\prime} \mid b^{\prime})\) by means of Gaussian elimination. If a row is obtained in which the only nonzero entry lies in the last column, then the original system is inconsistent. Otherwise, discard any zero rows from \((A^{\prime} \mid b^{\prime})\), and write the corresponding system of equations. Solve this system as described in Example 18.8 to obtain an arbitrary solution of the form

\[ s=s_{0}+t_{1} u_{1}+t_{2} u_{2}+\cdots+t_{n-r} u_{n-r} \]

where \(r\) is the number of nonzero rows in \(A^{\prime}(r \leq m)\). The preceding equation is called a general solution of the system \(A x=b\). It expresses an arbitrary solution \(s\) of \(A x=b\) in terms of \(n-r\) parameters.

Theorem 18.10 : General solution in reduced row echelon form

Let \(A x=b\) be a system of \(r\) nonzero equations in \(n\) unknowns. Suppose that \(\operatorname{rank}(A)=\operatorname{rank}(A \mid b)\) and that \((A \mid b)\) is in reduced row echelon form. Then

• (a) \(\operatorname{rank}(A)=r\).

• (b) If the general solution obtained by the procedure described in Concept 18.9 is of the form

  \[ s=s_{0}+t_{1} u_{1}+t_{2} u_{2}+\cdots+t_{n-r} u_{n-r} \]

  then \(\left\{u_{1}, u_{2}, \ldots, u_{n-r}\right\}\) is a basis for the solution set of the corresponding homogeneous system, and \(s_{0}\) is a solution to the original system.

Proof

Since \((A \mid b)\) is in reduced row echelon form, \((A \mid b)\) must have \(r\) nonzero rows. Clearly these rows are linearly independent by the definition of the reduced row echelon form, and so \(\operatorname{rank}(A \mid b)=r\). Thus \(\operatorname{rank}(A)=r\).

Let \(K\) be the solution set for \(A x=b\), and let \(K_{H}\) be the solution set for \(A x=0\). Setting \(t_{1}=t_{2}=\cdots=t_{n-r}=0\), we see that \(s=s_{0} \in K\). But by Theorem 17.5, \(K=\left\{s_{0}\right\}+K_{H}\). Hence

\[ K_{H}=\left\{-s_{0}\right\}+K=\operatorname{span}\left(\left\{u_{1}, u_{2}, \ldots, u_{n-r}\right\}\right) . \]

Because \(\operatorname{rank}(A)=r\), we have \(\operatorname{dim}\left(K_{H}\right)=n-r\). Thus since \(\operatorname{dim}\left(K_{H}\right)=n-r\) and \(K_{H}\) is generated by a set \(\left\{u_{1}, u_{2}, \ldots, u_{n-r}\right\}\) containing at most \(n-r\) vectors, we conclude that this set is a basis for \(K_{H}\).

Interpretation of the Reduced Row Echelon Form

Theorem 18.11 : Pivot columns describe the column space.

Let \(A\) be an \(m \times n\) matrix of rank \(r\), where \(r>0\), and let \(B\) be the reduced row echelon form of \(A\). Then

• (a) The number of nonzero rows in \(B\) is \(r\).
• (b) For each \(i=1,2, \ldots, r\), there is a column \(b_{j_{i}}\) of \(B\) such that \(b_{j_{i}}=e_{i}\).
• (c) The columns of \(A\) numbered \(j_{1}, j_{2}, \ldots, j_{r}\) are linearly independent.
• (d) For each \(k=1,2, \ldots, n\), if column \(k\) of \(B\) is \(d_{1} e_{1}+d_{2} e_{2}+\cdots+d_{r} e_{r}\), then column \(k\) of \(A\) is \(d_{1} a_{j_{1}}+d_{2} a_{j_{2}}+\cdots+d_{r} a_{j_{r}}\).

Proof

Let \(A\) be an \(m \times n\) matrix with columns \(a_{1}, a_{2}, \ldots, a_{n}\), and let \(B\) be the reduced row echelon form of \(A\). Denote the columns of \(B\) by \(b_{1}, b_{2}, \ldots, b_{n}\). If the rank of \(A\) is \(r\), then the rank of \(B\) is also \(r\) by Corollary 16.5.

• (a)
  Because \(B\) is in reduced row echelon form, no nonzero row of \(B\) can be a linear combination of the other rows of \(B\). Therefore, the number of nonzero rows of \(B\) equals the dimension of the subspace spanned by the rows of \(B\). By Corollary 16.10 (b), this dimension equals \(\operatorname{rank}(B)=r\). Hence \(B\) has exactly \(r\) nonzero rows.

• (b)
  Since \(r>0\), \(B\) has \(r\) nonzero rows by part (a). In reduced row echelon form, each nonzero row has a leading entry equal to \(1\), and each leading \(1\) is the only nonzero entry in its column. Thus, for each \(i=1,2,\ldots,r\), the leading \(1\) in row \(i\) occurs in some column, say column \(j_i\), and that column is exactly the standard basis vector \(e_i\). Therefore, for each \(i=1,2,\ldots,r\), there exists a column \(b_{j_i}\) of \(B\) such that \(b_{j_i}=e_i\).

• (c)
  For \(i=1,2,\ldots,r\), let \(j_i\) denote a column number of \(B\) such that \(b_{j_i}=e_i\). We claim that \(a_{j_{1}}, a_{j_{2}}, \ldots, a_{j_{r}}\), the columns of \(A\) corresponding to these columns of \(B\), are linearly independent.

  Suppose that there are scalars \(c_{1}, c_{2}, \ldots, c_{r}\) such that

  \[ c_{1} a_{j_{1}}+c_{2} a_{j_{2}}+\cdots+c_{r} a_{j_{r}}=0 \]

  Because \(B\) can be obtained from \(A\) by a sequence of elementary row operations, there exists an invertible \(m \times m\) matrix \(M\) such that \(M A=B\). Multiplying the preceding equation by \(M\) yields

  \[ c_{1} M a_{j_{1}}+c_{2} M a_{j_{2}}+\cdots+c_{r} M a_{j_{r}}=0 \]

  Since \(M a_{j_i}=b_{j_i}=e_i\), it follows that

  \[ c_{1} e_{1}+c_{2} e_{2}+\cdots+c_{r} e_{r}=0 \]

  Hence \(c_{1}=c_{2}=\cdots=c_{r}=0\). Therefore \(a_{j_{1}}, a_{j_{2}}, \ldots, a_{j_{r}}\) are linearly independent.

• (d)
  Because \(B\) has only \(r\) nonzero rows by part (a), every column of \(B\) has the form

  \[ \left(\begin{array}{c} d_{1} \\ d_{2} \\ \vdots \\ d_{r} \\ 0 \\ \vdots \\ 0 \end{array}\right) \]

  for scalars \(d_{1}, d_{2}, \ldots, d_{r}\), that is, column \(k\) of \(B\) can be written as \(d_{1} e_{1}+d_{2} e_{2}+\cdots+d_{r} e_{r}\). Since \(M A=B\), we have \(a_k = M^{-1} b_k\) for each \(k\). Thus, if \(b_k=d_{1} e_{1}+d_{2} e_{2}+\cdots+d_{r} e_{r}\), then

  \[ \begin{aligned} a_k & =M^{-1} b_k \\ & =M^{-1}\left(d_{1} e_{1}+d_{2} e_{2}+\cdots+d_{r} e_{r}\right) \\ & =d_{1} M^{-1} e_{1}+d_{2} M^{-1} e_{2}+\cdots+d_{r} M^{-1} e_{r} \\ & =d_{1} M^{-1} b_{j_{1}}+d_{2} M^{-1} b_{j_{2}}+\cdots+d_{r} M^{-1} b_{j_{r}} \\ & =d_{1} a_{j_{1}}+d_{2} a_{j_{2}}+\cdots+d_{r} a_{j_{r}} . \end{aligned} \]

Corollary 18.12 : Reduced row echelon form is unique.

The reduced row echelon form of a matrix is unique.

Proof

Let \(A\) be an \(m \times n\) matrix. Suppose that \(B\) and \(C\) are both reduced row echelon forms of \(A\). We must show that \(B=C\).

Let the rank of \(A\) be \(r\). Then \(\operatorname{rank}(B)=\operatorname{rank}(A)=\operatorname{rank}(C)=r\) by Corollary 16.5. If \(r=0\), then \(A\) is the zero matrix, and hence \(B=C=O\). So assume \(r>0\).

Denote the columns of \(B\) by \(b_{1},\ldots,b_{n}\) and the columns of \(C\) by \(c_{1},\ldots,c_{n}\). By Theorem 18.11 (b) applied to \(B\), there exist column indices \(j_{1},\ldots,j_{r}\) such that

\[ b_{j_i}=e_i \quad \text{for } i=1,2,\ldots,r . \]

We first show that the same column indices \(j_{1},\ldots,j_{r}\) are pivot columns of \(C\), and in fact that

\[ c_{j_i}=e_i \quad \text{for } i=1,2,\ldots,r . \]

Since \(B\) is a reduced row echelon form of \(A\), there exists an invertible \(m \times m\) matrix \(M\) such that \(B=MA\). Similarly, since \(C\) is also a reduced row echelon form of \(A\), there exists an invertible \(m \times m\) matrix \(N\) such that \(C=NA\). Hence

\[ C = N A = N M^{-1} B . \]

Let \(P = N M^{-1}\). Then \(P\) is invertible and

\[ C = P B . \]

Now consider the columns \(j_1,\ldots,j_r\). Since \(b_{j_i}=e_i\) for each \(i\), we have

\[ c_{j_i} = P b_{j_i} = P e_i , \]

so \(c_{j_i}\) is the \(i\)th column of \(P\).

Because \(C\) is in reduced row echelon form and has rank \(r\), by Theorem 18.11 (a) it has exactly \(r\) nonzero rows, and by Theorem 18.11 (b) its pivot columns are exactly standard basis vectors among \(e_1,\ldots,e_r\). In particular, every pivot column of \(C\) is some \(e_i\), and the pivot columns are all distinct. Therefore, for each \(i=1,\ldots,r\), the column \(c_{j_i}\) must equal \(e_i\). (Otherwise, if \(c_{j_i}=e_{k}\) with \(k\neq i\), then the pivot columns of \(C\) would not match the row positions of leading ones in reduced row echelon form.)

Thus \(c_{j_i}=e_i\) for \(i=1,\ldots,r\), so \(B\) and \(C\) have the same pivot columns, in the same positions, and those pivot columns agree entrywise.

Now let \(k\) be any column index, \(1 \le k \le n\). By Theorem 18.11 (d) applied to \(B\), since \(b_{j_i}=e_i\), we can write

\[ b_k = d_1 e_1 + d_2 e_2 + \cdots + d_r e_r \]

for unique scalars \(d_1,\ldots,d_r\) (namely the first \(r\) entries of \(b_k\)). Applying Theorem 18.11 (d) to \(C\) and using that \(c_{j_i}=e_i\), the same reasoning shows that

\[ c_k = d_1 e_1 + d_2 e_2 + \cdots + d_r e_r . \]

Hence \(c_k=b_k\) for every \(k\), and therefore \(C=B\). This proves that the reduced row echelon form of \(A\) is unique.

Applications

Example 18.13 : Reducing a finite generating set to a basis.

The set \(S=\left\{2+x+2 x^{2}+3 x^{3}, 4+2 x+4 x^{2}+6 x^{3}, 6+3 x+8 x^{2}+7 x^{3}, 2+x+5 x^{3}, 4+x+9 x^{3}\right\}\) generates a subspace \(V\) of \(\mathrm{P}_{3}(R)\). To find a subset of \(S\) that is a basis for \(V\), we consider the subset

\[ S^{\prime}=\{(2,1,2,3),(4,2,4,6),(6,3,8,7),(2,1,0,5),(4,1,0,9)\} \]

consisting of the images of the polynomials in \(S\) under the standard representation of \(\mathrm{P}_{3}(R)\) with respect to the standard ordered basis. Form the \(4 \times 5\) matrix \(A\) whose columns are the vectors in \(S^{\prime}\), namely,

\[ A=\left(\begin{array}{rrrrr} 2 & 4 & 6 & 2 & 4 \\ 1 & 2 & 3 & 1 & 1 \\ 2 & 4 & 8 & 0 & 0 \\ 3 & 6 & 7 & 5 & 9 \end{array}\right) . \]

The reduced row echelon form of \(A\) is

\[ B=\left(\begin{array}{rrrrr} 1 & 2 & 0 & 4 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right) . \]

From \(B\), we see that the pivot columns are columns \(1,3,\) and \(5\). Therefore the first, third, and fifth columns of \(A\) are linearly independent, and the second and fourth columns of \(A\) are linear combinations of the first, third, and fifth columns.

Hence

\[ \{(2,1,2,3),(6,3,8,7),(4,1,0,9)\} \]

is a basis for the subspace of \(\mathbb{R}^{4}\) that is generated by \(S^{\prime}\). It follows that

\[ \left\{2+x+2 x^{2}+3 x^{3}, 6+3 x+8 x^{2}+7 x^{3}, 4+x+9 x^{3}\right\} \]

is a basis for the subspace \(V\) of \(\mathrm{P}_{3}(\mathbb{R})\).

Example 18.14 : Extending a linearly independent set to a basis.

We now describe a method for extending a linearly independent subset \(S\) of a finite-dimensional vector space \(V\) to a basis for \(V\). Recall that this is always possible by (c) of Corollary 6.13. Our approach is based on the replacement theorem and assumes that we can find an explicit basis \(\beta\) for \(V\). Let \(S^{\prime}\) be the ordered set consisting of the vectors in \(S\) followed by those in \(\beta\). Since \(\beta \subseteq S^{\prime}\), the set \(S^{\prime}\) generates \(V\). We can then apply the technique described above to reduce this generating set to a basis for \(V\) containing \(S\).

Let

\[ V=\left\{\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right) \in \mathbb{R}^{5}: x_{1}+7 x_{2}+5 x_{3}-4 x_{4}+2 x_{5}=0\right\} \]

It is easily verified that \(V\) is a subspace of \(\mathbb{R}^{5}\) and that

\[ S=\{(-2,0,0,-1,-1),(1,1,-2,-1,-1),(-5,1,0,1,1)\} \]

is a linearly independent subset of \(V\).

To extend \(S\) to a basis for \(V\), we first obtain a basis \(\beta\) for \(V\). To do so, we solve the system of linear equations that defines \(V\). Since in this case \(V\) is defined by a single equation, we need only write the equation as

\[ x_{1}=-7 x_{2}-5 x_{3}+4 x_{4}-2 x_{5} \]

and assign parametric values to \(x_{2}, x_{3}, x_{4}\), and \(x_{5}\). If \(x_{2}=t_{1}, x_{3}=t_{2}\), \(x_{4}=t_{3}\), and \(x_{5}=t_{4}\), then the vectors in \(V\) have the form

\[ \begin{aligned} & \left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right)=\left(-7 t_{1}-5 t_{2}+4 t_{3}-2 t_{4}, t_{1}, t_{2}, t_{3}, t_{4}\right) \\ & \quad=t_{1}(-7,1,0,0,0)+t_{2}(-5,0,1,0,0)+t_{3}(4,0,0,1,0)+t_{4}(-2,0,0,0,1) \end{aligned} \]

Hence

\[ \beta=\{(-7,1,0,0,0),(-5,0,1,0,0),(4,0,0,1,0),(-2,0,0,0,1)\} \]

is a basis for \(V\) by Theorem 18.10. The matrix whose columns consist of the vectors in \(S\) followed by those in \(\beta\) is

\[ \left(\begin{array}{rrrrrrr} -2 & 1 & -5 & -7 & -5 & 4 & -2 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & -2 & 0 & 0 & 1 & 0 & 0 \\ -1 & -1 & 1 & 0 & 0 & 1 & 0 \\ -1 & -1 & 1 & 0 & 0 & 0 & 1 \end{array}\right), \]

and its reduced row echelon form is

\[ \left(\begin{array}{rrrrrrr} 1 & 0 & 0 & 1 & 1 & 0 & -1 \\ 0 & 1 & 0 & 0 & -.5 & 0 & 0 \\ 0 & 0 & 1 & 1 & .5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) . \]

Thus

\[ \{(-2,0,0,-1,-1),(1,1,-2,-1,-1),(-5,1,0,1,1),(4,0,0,1,0)\} \]

is a basis for \(V\) containing \(S\).

Exercise

Exercise 18.3

Suppose that the augmented matrix of a system \(A x=b\) is transformed into a matrix \(\left(A^{\prime} \mid b^{\prime}\right)\) in reduced row echelon form by a finite sequence of elementary row operations.

• (a) Prove that \(\operatorname{rank}\left(A^{\prime}\right) \neq \operatorname{rank}\left(A^{\prime} \mid b^{\prime}\right)\) if and only if \(\left(A^{\prime} \mid b^{\prime}\right)\) contains a row in which the only nonzero entry lies in the last column.
• (b) Deduce that \(A x=b\) is consistent if and only if \(\left(A^{\prime} \mid b^{\prime}\right)\) contains no row in which the only nonzero entry lies in the last column.

Exercise 18.14

If \((A \mid b)\) is in reduced row echelon form, prove that \(A\) is also in reduced row echelon form.