# 3.4 Systems of Linear Equations—Computational Aspects

In Section 3.3, we obtained a necessary and sufficient condition for a system of linear equations to have solutions (Theorem 3.11 p. 174) and learned how to express the solutions to a nonhomogeneous system in terms of solutions to the corresponding homogeneous system (Theorem 3.9 p. 172). The latter result enables us to determine all the solutions to a given system if we can find one solution to the given system and a basis for the solution set of the corresponding homogeneous system. In this section, we use elementary row operations to accomplish these two objectives simultaneously. The essence of this technique is to transform a given system of linear equations into a system having the same solutions, but which is easier to solve (as in Section 1.4).

# Definition.

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

The following theorem and corollary give a useful method for obtaining equivalent systems.

# Theorem 3.13.

Let  be a system of m linear equations in n unknowns, and let C be an invertible  matrix. Then the system  is equivalent to .

# Proof.

Let K be the solution set for  and  the solution set for . If , then . So , and hence . Thus .

Conversely, if , then . Hence



so . Thus , and therefore, .

# Corollary.

Let  be a system of m linear equations in n unknowns. If  is obtained from  by a finite number of elementary row operations, then the system  is equivalent to the original system.

# Proof.

Suppose that  is obtained from  by elementary row operations. These may be executed by multiplying  by elementary  matrices . Let  then



Since each  is invertible, so is C. Now  and . Thus by Theorem 3.13, the system  is equivalent to the system .

We now describe a method for solving any system of linear equations. Consider, for example, the system of linear equations



First, we form the augmented matrix



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. (Recall that matrix A is upper triangular if  whenever .)

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


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  times the first row to the second row and then add  times the first row to the third row to obtain


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 . This operation produces


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


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



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


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  times the second row to the first row in order to make the first row, second column entry become zero. This operation produces



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



Recall that, by the corollary to Theorem 3.13, this system is equivalent to the original system. But this system is easily solved. Obviously  and . Moreover,  and  can have any values provided their sum is 1. Letting , we then have . Thus an arbitrary solution to the original system has the form



Observe that



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

In the preceding example we performed elementary row operations on the augmented matrix of the system until we obtained the augmented matrix of a system having properties 1, 2, and 3 on page 28. Such a matrix has a special name.

# Definition.

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

1. (a) Any row containing a nonzero entry precedes any row in which all the entries are zero (if any).

2. (b) The first nonzero entry in each row is the only nonzero entry in its column.

3. (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 1

1. (a) The matrix on page 184 is in reduced row echelon form. Note that the first nonzero entry of each row is 1 and that the column containing each such entry has all zeros otherwise. Also note that each time we move downward to a new row, we must move to the right one or more columns to find the first nonzero entry of the new row.

2. (b) The matrix



is not in reduced row echelon form, because the first column, which contains the first nonzero entry in row 1, contains another nonzero entry. Similarly, the matrix



is not in reduced row echelon form, because the first nonzero entry of the second row is not to the right of the first nonzero entry of the first row. Finally, the matrix



is not in reduced row echelon form, because the first nonzero entry of the first row is not 1.

It can be shown (see the corollary to Theorem 3.16) that the reduced row echelon form of a matrix is unique; that is, if different sequences of elementary row operations are used to transform a matrix into matrices Q and  in reduced row echelon form, then . Thus, although there are many different sequences of elementary row operations that can be used to transform a given matrix into reduced row echelon form, they all produce the same result.

The procedure described on pages 182-184 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.

Of all the methods for transforming a matrix into its reduced row echelon form, Gaussian elimination requires the fewest arithmetic operations. (For large matrices, it requires approximately 50% fewer operations than the Gauss-Jordan method, in which the matrix is transformed into reduced row echelon form by using the first nonzero entry in each row to make zero all other entries in its column.) Because of this efficiency, Gaussian elimination is the preferred method when solving systems of linear equations on a computer. In this context, the Gaussian elimination procedure is usually modified in order to minimize roundoff errors. Since discussion of these techniques is inappropriate here, readers who are interested in such matters are referred to books on numerical analysis.

When a matrix is in reduced row echelon form, the corresponding system of linear equations is easy to solve. We present below a procedure for solving any system of linear equations for which the augmented matrix is in reduced row echelon form. First, however, we note that every matrix can be transformed into reduced row echelon form by Gaussian elimination. In the forward pass, we satisfy conditions (a) and (c) in the definition of reduced row echelon form 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.

# Theorem 3.14.

Gaussian elimination transforms any matrix into its 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



for which the augmented matrix is



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



The system of linear equations corresponding to this last matrix is



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 ). The second set consists of all the remaining variables (in this case, ). To each variable in the second set, assign a parametric value , and then solve for the variables of the first set in terms of those in the second set:



Thus an arbitrary solution is of the form



where . Notice that



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



is a particular solution to the original system.

Therefore, 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 by Exercise 3, 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.

Thus to use this procedure for solving a system  of m linear equations in n unknowns, we need only begin to transform the augmented matrix  into its reduced row echelon form  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 , and write the corresponding system of equations. Solve this system as described above to obtain an arbitrary solution of the form



where r is the number of nonzero rows in . The preceding equation is called a general solution of the system . It expresses an arbitrary solution s of  in terms of  parameters. The following theorem states that s cannot be expressed in fewer than  parameters.

# Theorem 3.15.

Let  be a system of r nonzero equations in n unknowns. Suppose that  and that  is in reduced row echelon form. Then

1. (a) 

2. (b) If the general solution obtained by the procedure above is of the form



then  is a basis for the solution set of the corresponding homogeneous system, and  is a solution to the original system.

# Proof.

Since  is in reduced row echelon form,  must have r nonzero rows. Clearly these rows are linearly independent by the definition of the reduced row echelon form, and so . Thus .

Let K be the solution set for , and let  be the solution set for . Setting , we see that . But by Theorem 3.9 (p. 172), . Hence



Because , we have . Thus since  and  is generated by a set  containing at most  vectors, we conclude that this set is a basis for .

# An Interpretation of the Reduced Row Echelon Form

Let A be an  matrix with columns , and let B be the reduced row echelon form of A. Denote the columns of B by . If the rank of A is r, then the rank of B is also r by the corollary to Theorem 3.4 (p. 152). Because B is in reduced row echelon form, no nonzero row of B can be a linear combination of the other rows of B. Hence B must have exactly r nonzero rows, and if , the vectors  must occur among the columns of B. For , let  denote a column number of B such that . We claim that , the columns of A corresponding to these columns of B, are linearly independent. For suppose that there are scalars  such that



Because B can be obtained from A by a sequence of elementary row operations, there exists (as in the proof of the corollary to Theorem 3.13) an invertible  matrix M such that . Multiplying the preceding equation by M yields



Since , it follows that



Hence , proving that the vectors  are linearly independent.

Because B has only r nonzero rows, every column of B has the form



for scalars . The corresponding column of A must be



The next theorem summarizes these results.

# Theorem 3.16.

Let A be an  matrix of rank r, where , and let B be the reduced row echelon form of A. Then

1. (a) The number of nonzero rows in B is r.

2. (b) For each  there is a column  of B such that .

3. (c) The columns of A numbered  are linearly independent.

4. (d) For each , if column k of B is , then column k of A is 

# Corollary.

The reduced row echelon form of a matrix is unique.

# Proof.

Exercise. (See Exercise 15.)

# Example 2

Let



The reduced row echelon form of A is



Since B has three nonzero rows, the rank of A is 3. The first, third, and fifth columns of B are , and ; so Theorem 3.16(c) asserts that the first, third, and fifth columns of A are linearly independent.

Let the columns of A be denoted . Because the second column of B is , it follows from Theorem 3.16(d) that , as is easily checked. Moreover, since the fourth column of B is , the same result shows that



In Example 6 of Section 1.6, we extracted a basis for  from the generating set



The procedure described there can be streamlined by using Theorem 3.16. We begin by noting that if S were linearly independent, then S would be a basis for . In this case, it is clear that S is linearly dependent because S contains more than  vectors. Nevertheless, it is instructive to consider the calculation that is needed to determine whether S is linearly dependent or linearly independent. Recall that S is linearly dependent if there are scalars , and , not all zero, such that



Thus S is linearly dependent if and only if the system of linear equations



has a nonzero solution. The augmented matrix of this system of equations is



and its reduced row echelon form is



Using the technique described earlier in this section, we can find nonzero solutions of the preceding system, confirming that S is linearly dependent. However, Theorem 3.16(c) gives us additional information. Since the first, third, and fourth columns of B are , and , we conclude that the first, third, and fourth columns of A are linearly independent. But the columns of A other than the last column (which is the zero vector) are vectors in S. Hence



is a linearly independent subset of S. If follows from (b) of Corollary 2 to the replacement theorem (p. 48) that  is a basis for .

Because every finite-dimensional vector space over F is isomorphic to  for some n, a similar approach can be used to reduce any finite generating set to a basis. This technique is illustrated in the next example.

# Example 3

The set



generates a subspace V of . To find a subset of S that is a basis for V, we consider the subset



consisting of the images of the polynomials in S under the standard representation of  with respect to the standard ordered basis. Note that the  matrix in which the columns are the vectors in  is the matrix A in Example 2. From the reduced row echelon form of A, which is the matrix B in Example 2, we see that 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



is a basis for the subspace of  that is generated by . It follows that



is a basis for the subspace V of .

We conclude this section by describing 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 2 to the replacement theorem (p. 48). Our approach is based on the replacement theorem and assumes that we can find an explicit basis  for V. Let  be the ordered set consisting of the vectors in S followed by those in . Since , the set  generates V. We can then apply the technique described above to reduce this generating set to a basis for V containing S.

# Example 4

Let



It is easily verified that V is a subspace of  and that



is a linearly independent subset of V.

To extend S to a basis for V, we first obtain a basis  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



and assign parametric values to , and . If , and , then the vectors in V have the form



Hence



is a basis for V by Theorem 3.15.

The matrix whose columns consist of the vectors in S followed by those in  is



and its reduced row echelon form is



Thus



is a basis for V containing S.

# Exercises

1. Label the following statements as true or false.

1. (a) If  is obtained from  by a finite sequence of elementary column operations, then the systems  and  are equivalent.

2. (b) If  is obtained from  by a finite sequence of elementary row operations, then the systems  and  are equivalent.

3. (c) If A is an  matrix with rank n, then the reduced row echelon form of A is .

4. (d) Any matrix can be put in reduced row echelon form by means of a finite sequence of elementary row operations.

5. (e) If  is in reduced row echelon form, then the system  is consistent.

6. (f) Let  be a system of m linear equations in n unknowns for which the augmented matrix is in reduced row echelon form. If this system is consistent, then the dimension of the solution set of  is , where r equals the number of nonzero rows in A.

7. (g) If a matrix A is transformed by elementary row operations into a matrix  in reduced row echelon form, then the number of nonzero rows in  equals the rank of A.

2. Use Gaussian elimination to solve the following systems of linear equations.

1. (a) 

2. (b) 

3. (c) 

4. (d) 

5. (e) 

6. (f) 

7. (g) 

8. (h)

9. (i) 

10. (j) 

3. Suppose that the augmented matrix of a system  is transformed into a matrix  in reduced row echelon form by a finite sequence of elementary row operations.

1. (a) Prove that  if and only if  contains a row in which the only nonzero entry lies in the last column.

2. (b) Deduce that  is consistent if and only if  contains no row in which the only nonzero entry lies in the last column.

4. For each of the systems that follow, apply Exercise 3 to determine whether the system is consistent. If the system is consistent, find all solutions. Finally, find a basis for the solution set of the corresponding homogeneous system.

1. (a) 

2. (b) 

3. (c) 

5. Let the reduced row echelon form of A be



Determine A if the first, second, and fourth columns of A are



respectively.

6. Let the reduced row echelon form of A be



Determine A if the first, third, and sixth columns of A are



respectively.

7. It can be shown that the vectors  and  generate . Find a subset of  that is a basis for .

8. Let W denote the subspace of  consisting of all vectors having coordinates that sum to zero. The vectors



generate W. Find a subset of  that is a basis for W.

9. Let W be the subspace of  consisting of the symmetric  matrices. The set



generates W. Find a subset of S that is a basis for W.

10. Let


1. (a) Show that  is a linearly independent subset of V.

2. (b) Extend S to a basis for V.

11. Let V be as in Exercise 10.

1. (a) Show that  is a linearly independent subset of V.

2. (b) Extend S to a basis for V.

12. Let V denote the set of all solutions to the system of linear equations


1. (a) Show that  is a linearly independent subset of V.

2. (b) Extend S to a basis for V.

13. Let V be as in Exercise 12.

1. (a) Show that  is a linearly independent subset of V.

2. (b) Extend S to a basis for V.

14. If  is in reduced row echelon form, prove that A is also in reduced row echelon form.

15. Prove the corollary to Theorem 3.16: The reduced row echelon form of a matrix is unique. Visit goo.gl/cZVzxM for a solution.