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).
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.
Let be a system of m linear equations in n unknowns, and let C be an invertible matrix. Then the system is equivalent to .
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, .
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.
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 .)
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
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
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
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
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.)
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
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.
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.
(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.
(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.
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.
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.
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.
Let be a system of r nonzero equations in n unknowns. Suppose that and that is in reduced row echelon form. Then
(a)
(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.
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 .
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.
Let A be an matrix of rank r, where , 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 there is a column of B such that .
(c) The columns of A numbered are linearly independent.
(d) For each , if column k of B is , then column k of A is
The reduced row echelon form of a matrix is unique.
Exercise. (See Exercise 15.)
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.
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.
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.
Label the following statements as true or false.
(a) If is obtained from by a finite sequence of elementary column operations, then the systems and are equivalent.
(b) If is obtained from by a finite sequence of elementary row operations, then the systems and are equivalent.
(c) If A is an matrix with rank n, then the reduced row echelon form of A is .
(d) Any matrix can be put in reduced row echelon form by means of a finite sequence of elementary row operations.
(e) If is in reduced row echelon form, then the system is consistent.
(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.
(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.
Use Gaussian elimination to solve the following systems of linear equations.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
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.
(a) Prove that if and only if contains a row in which the only nonzero entry lies in the last column.
(b) Deduce that is consistent if and only if contains no row in which the only nonzero entry lies in the last column.
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.
(a)
(b)
(c)
Let the reduced row echelon form of A be
Determine A if the first, second, and fourth columns of A are
respectively.
Let the reduced row echelon form of A be
Determine A if the first, third, and sixth columns of A are
respectively.
It can be shown that the vectors and generate . Find a subset of that is a basis for .
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.
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.
Let
(a) Show that is a linearly independent subset of V.
(b) Extend S to a basis for V.
Let V be as in Exercise 10.
(a) Show that is a linearly independent subset of V.
(b) Extend S to a basis for V.
Let V denote the set of all solutions to the system of linear equations
(a) Show that is a linearly independent subset of V.
(b) Extend S to a basis for V.
Let V be as in Exercise 12.
(a) Show that is a linearly independent subset of V.
(b) Extend S to a basis for V.
If is in reduced row echelon form, prove that A is also in reduced row echelon form.
Prove the corollary to Theorem 3.16: The reduced row echelon form of a matrix is unique. Visit goo.gl/