Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

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 $A x = b$ $A x = b$ be a system of m linear equations in n unknowns, and let C be an invertible $m \times m$ $m \times m$ matrix. Then the system $(C A) x = C b$ $(C A) x = C b$ is equivalent to $A x = b$ $A x = b$ .

Proof.

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

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

A w = C^{- 1} (C A w) = C^{- 1} (C b) = b;

$A w = C^{- 1} (C A w) = C^{- 1} (C b) = b;$

so $w \in K$ $w \in K$ . Thus $K^{'} \subseteq K$ $K^{'} \subseteq K$ , and therefore, $K = K^{'}$ $K = K^{'}$ .

Corollary.

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

Proof.

Suppose that $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ is obtained from $(A | b)$ $(A | b)$ by elementary row operations. These may be executed by multiplying $(A | b)$ $(A | b)$ by elementary $m \times m$ $m \times m$ matrices $E_{1}, E_{2}, \dots, E_{p}$ $E_{1}, E_{2}, \dots, E_{p}$ . Let $C = E_{p} \dots E_{2} E_{1};$ $C = E_{p} \dots E_{2} E_{1};$ then

(A^{'} | b^{'}) = C (A | b) = (C A | C b) .

$(A^{'} | b^{'}) = C (A | b) = (C A | C b) .$

Since each $E_{i}$ $E_{i}$ is invertible, so is C. Now $A^{'} = C A$ $A^{'} = C A$ and $b^{'} = C b$ $b^{'} = C b$ . Thus by Theorem 3.13, the system $A^{'} x = b^{'}$ $A^{'} x = b^{'}$ is equivalent to the system $A x = b$ $A x = b$ .

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

\begin{array}{rcrcrcrcl} 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{array}

$\begin{array}{rcrcrcrcl} 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{array}$

First, we form the augmented matrix

(\begin{array}{r} 3 & 2 & 3 & - 2 & 1 \\ 1 & 1 & 1 & 0 & 3 \\ 1 & 2 & 1 & - 1 & 2 \end{array}) .

$(\begin{array}{r} 3 & 2 & 3 & - 2 & 1 \\ 1 & 1 & 1 & 0 & 3 \\ 1 & 2 & 1 & - 1 & 2 \end{array}) .$

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 $A_{i j} = 0$ $A_{i j} = 0$ whenever $i > j$ $i > j$ .)

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

$(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 1 & 1 & 1 & 0 & 3 \\ 3 & 2 & 3 & - 2 & 1 \end{array}) .$ $(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 1 & 1 & 1 & 0 & 3 \\ 3 & 2 & 3 & - 2 & 1 \end{array}) .$
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$ $- 1$ times the first row to the second row and then add $- 3$ $- 3$ times the first row to the third row to obtain

$(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & - 1 & 0 & 1 & 1 \\ 0 & - 4 & 0 & 1 & - 5 \end{array}) .$ $(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & - 1 & 0 & 1 & 1 \\ 0 & - 4 & 0 & 1 & - 5 \end{array}) .$
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$ $- 1$ . This operation produces

$(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & 1 & 0 & - 1 & - 1 \\ 0 & - 4 & 0 & 1 & - 5 \end{array}) .$ $(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & 1 & 0 & - 1 & - 1 \\ 0 & - 4 & 0 & 1 & - 5 \end{array}) .$
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

$(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & 1 & 0 & - 1 & - 1 \\ 0 & 0 & 0 & - 3 & - 9 \end{array}) .$ $(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & 1 & 0 & - 1 & - 1 \\ 0 & 0 & 0 & - 3 & - 9 \end{array}) .$
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 $- \frac{1}{3}$ $- \frac{1}{3}$ . This operation produces

$(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & 1 & 0 & - 1 & - 1 \\ 0 & 0 & 0 & 1 & 3 \end{array}) .$ $(\begin{array}{r} 1 & 2 & 1 & - 1 & 2 \\ 0 & 1 & 0 & - 1 & - 1 \\ 0 & 0 & 0 & 1 & 3 \end{array}) .$

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

$(\begin{array}{c} 1 & 2 & 1 & 0 & 5 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}) .$ $(\begin{array}{c} 1 & 2 & 1 & 0 & 5 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}) .$
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$ $- 2$ times the second row to the first row in order to make the first row, second column entry become zero. This operation produces

$(\begin{array}{c} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}) .$ $(\begin{array}{c} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array}) .$

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

$\begin{array}{rrrrrcl} x_{1} & + & x_{3} & = & 1 \\ x_{2} & = & 2 \\ x_{4} & = & 3 . \end{array}$ $\begin{array}{rrrrrcl} x_{1} & + & x_{3} & = & 1 \\ x_{2} & = & 2 \\ x_{4} & = & 3 . \end{array}$

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

(\begin{array}{c} 1 - t \\ 2 \\ t \\ 3 \end{array}) = (\begin{array}{c} 1 \\ 2 \\ 0 \\ 3 \end{array}) + t (\begin{array}{r} - 1 \\ 0 \\ 1 \\ 0 \end{array}) .

$(\begin{array}{c} 1 - t \\ 2 \\ t \\ 3 \end{array}) = (\begin{array}{c} 1 \\ 2 \\ 0 \\ 3 \end{array}) + t (\begin{array}{r} - 1 \\ 0 \\ 1 \\ 0 \end{array}) .$

Observe that

{(\begin{array}{r} - 1 \\ 0 \\ 1 \\ 0 \end{array})}

${(\begin{array}{r} - 1 \\ 0 \\ 1 \\ 0 \end{array})}$

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.

(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 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.
(b) The matrix

$(\begin{array}{c} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array}),$ $(\begin{array}{c} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array}),$

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

$(\begin{array}{c} 0 & 1 & 0 & 2 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array}),$ $(\begin{array}{c} 0 & 1 & 0 & 2 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array}),$

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

$(\begin{array}{c} 2 & 0 & 0 \\ 0 & 1 & 0 \end{array}),$ $(\begin{array}{c} 2 & 0 & 0 \\ 0 & 1 & 0 \end{array}),$

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 $Q^{'}$ $Q^{'}$ in reduced row echelon form, then $Q = Q^{'}$ $Q = Q^{'}$ . 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.

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

\begin{array}{rcrcrcrcrcr} 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{array}

$\begin{array}{rcrcrcrcrcr} 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{array}$

for which the augmented matrix is

(\begin{array}{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}) .

$(\begin{array}{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}) .$

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

\begin{array}{l} (\begin{array}{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}) \to (\begin{array}{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}) \to \\ (\begin{array}{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}) \to (\begin{array}{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}) \to \\ (\begin{array}{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}) \to (\begin{array}{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}) . \end{array}

$\begin{array}{l} (\begin{array}{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}) \to (\begin{array}{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}) \to \\ (\begin{array}{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}) \to (\begin{array}{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}) \to \\ (\begin{array}{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}) \to (\begin{array}{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}) . \end{array}$

The system of linear equations corresponding to this last matrix is

\begin{array}{rrcrrcrcl} x_{1} & + & 2 x_{3} & - & 2 x_{5} & = & 3 \\ x_{2} & - & x_{3} & + & x_{5} & = & 1 \\ x_{4} & - & 2 x_{5} & = & 2 . \end{array}

$\begin{array}{rrcrrcrcl} x_{1} & + & 2 x_{3} & - & 2 x_{5} & = & 3 \\ x_{2} & - & x_{3} & + & x_{5} & = & 1 \\ x_{4} & - & 2 x_{5} & = & 2 . \end{array}$

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 ${x_{1}, x_{2}, x_{4}}$ ${x_{1}, x_{2}, x_{4}}$ ). The second set consists of all the remaining variables (in this case, ${x_{3}, x_{5}}$ ${x_{3}, x_{5}}$ ). To each variable in the second set, assign a parametric value $t_{1}, t_{2}, \dots (x_{3} = t_{1}, x_{5} = t_{2})$ $t_{1}, t_{2}, \dots (x_{3} = t_{1}, x_{5} = t_{2})$ , and then solve for the variables of the first set in terms of those in the second set:

\begin{array}{rcrcrcrcrcrcl} 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{array}

$\begin{array}{rcrcrcrcrcrcl} 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{array}$

Thus an arbitrary solution is of the form

(\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}) = (\begin{array}{rcrcl} - 2 t_{1} & + & 2 t_{2} & + & 3 \\ t_{1} & - & t_{2} & + & 1 \\ t_{1} \\ 2 t_{2} & + & 2 \\ t_{2} \end{array}) = (\begin{array}{c} 3 \\ 1 \\ 0 \\ 2 \\ 0 \end{array}) = t_{1} (\begin{array}{r} - 2 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}) + t_{2} (\begin{array}{r} 2 \\ - 1 \\ 0 \\ 2 \\ 1 \end{array}),

$(\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{array}) = (\begin{array}{rcrcl} - 2 t_{1} & + & 2 t_{2} & + & 3 \\ t_{1} & - & t_{2} & + & 1 \\ t_{1} \\ 2 t_{2} & + & 2 \\ t_{2} \end{array}) = (\begin{array}{c} 3 \\ 1 \\ 0 \\ 2 \\ 0 \end{array}) = t_{1} (\begin{array}{r} - 2 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}) + t_{2} (\begin{array}{r} 2 \\ - 1 \\ 0 \\ 2 \\ 1 \end{array}),$

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

{(\begin{array}{r} - 2 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}), (\begin{array}{r} 2 \\ - 1 \\ 0 \\ 2 \\ 1 \end{array})}

${(\begin{array}{r} - 2 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}), (\begin{array}{r} 2 \\ - 1 \\ 0 \\ 2 \\ 1 \end{array})}$

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

(\begin{array}{c} 3 \\ 1 \\ 0 \\ 2 \\ 0 \end{array})

$(\begin{array}{c} 3 \\ 1 \\ 0 \\ 2 \\ 0 \end{array})$

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 $A x = b$ $A x = b$ of m linear equations in n unknowns, we need only begin to transform the augmented matrix $(A | b)$ $(A | b)$ into its reduced row echelon form $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ 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^{'} | b^{'})$ $(A^{'} | b^{'})$ , and write the corresponding system of equations. Solve this system as described above to obtain an arbitrary solution of the form

s = s_{0} + t_{1} u_{1} + t_{2} u_{2} + \dots + t_{n - r} u_{n - r},

$s = s_{0} + t_{1} u_{1} + t_{2} u_{2} + \dots + t_{n - r} u_{n - r},$

where r is the number of nonzero rows in $A^{'} (r \leq m)$ $A^{'} (r \leq m)$ . The preceding equation is called a general solution of the system $A x = b$ $A x = b$ . It expresses an arbitrary solution s of $A x = b$ $A x = b$ in terms of $n - r$ $n - r$ parameters. The following theorem states that s cannot be expressed in fewer than $n - r$ $n - r$ parameters.

Theorem 3.15.

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

(a) $rank (A) = r .$ $rank (A) = r .$
(b) If the general solution obtained by the procedure above is of the form

$s = s_{0} + t_{1} u_{1} + t_{2} u_{2} + \dots + t_{n - r} u_{n - r},$ $s = s_{0} + t_{1} u_{1} + t_{2} u_{2} + \dots + t_{n - r} u_{n - r},$

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

Proof.

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

K_{H} = {- s_{0}} + K = span ({u_{1}, u_{2}, \dots, u_{n - r}}) .

$K_{H} = {- s_{0}} + K = span ({u_{1}, u_{2}, \dots, u_{n - r}}) .$

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

An Interpretation of the Reduced Row Echelon Form

Let A be an $m \times n$ $m \times n$ matrix with columns $a_{1}, a_{2}, \dots, a_{n}$ $a_{1}, a_{2}, \dots, a_{n}$ , and let B be the reduced row echelon form of A. Denote the columns of B by $b_{1}, b_{2}, \dots, b_{n}$ $b_{1}, b_{2}, \dots, b_{n}$ . 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 $r \geq 1$ $r \geq 1$ , the vectors $e_{1}, e_{2}, \dots, e_{r}$ $e_{1}, e_{2}, \dots, e_{r}$ must occur among the columns of B. For $i = 1, 2, \dots, r$ $i = 1, 2, \dots, r$ , let $j_{i}$ $j_{i}$ denote a column number of B such that $b_{j_{i}} = e_{i}$ $b_{j_{i}} = e_{i}$ . We claim that $a_{j_{1}}, a_{j_{2}}, \dots, a_{j_{r}}$ $a_{j_{1}}, a_{j_{2}}, \dots, a_{j_{r}}$ , the columns of A corresponding to these columns of B, are linearly independent. For suppose that there are scalars $c_{1}, c_{2}, \dots, c_{r}$ $c_{1}, c_{2}, \dots, c_{r}$ such that

c_{1} a_{j_{1}} + c_{2} a_{j_{2}} + \dots + c_{r} a_{j_{r}} = 0 .

$c_{1} a_{j_{1}} + c_{2} a_{j_{2}} + \dots + c_{r} a_{j_{r}} = 0 .$

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 $m \times m$ $m \times m$ matrix M such that $M A = B$ $M A = B$ . Multiplying the preceding equation by M yields

c_{1} M a_{j_{1}} + c_{2} M a_{j_{2}} + \dots + c_{r} M a_{j_{r}} = 0 .

$c_{1} M a_{j_{1}} + c_{2} M a_{j_{2}} + \dots + c_{r} M a_{j_{r}} = 0 .$

Since $M a_{j_{i}} = b_{j_{i}} = e_{i}$ $M a_{j_{i}} = b_{j_{i}} = e_{i}$ , it follows that

c_{1} e_{1} + c_{2} e_{2} + \dots + c_{r} e_{r} = 0 .

$c_{1} e_{1} + c_{2} e_{2} + \dots + c_{r} e_{r} = 0 .$

Hence $c_{1} = c_{2} = \dots = c_{r} = 0$ $c_{1} = c_{2} = \dots = c_{r} = 0$ , proving that the vectors $a_{j_{1}}, a_{j_{2}}, \dots, a_{j_{r}}$ $a_{j_{1}}, a_{j_{2}}, \dots, a_{j_{r}}$ are linearly independent.

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

(\begin{array}{c} d_{1} \\ d_{2} \\ ⋮ \\ d_{r} \\ 0 \\ ⋮ \\ 0 \end{array})

$(\begin{array}{c} d_{1} \\ d_{2} \\ ⋮ \\ d_{r} \\ 0 \\ ⋮ \\ 0 \end{array})$

for scalars $d_{1}, d_{2}, \dots, d_{r}$ $d_{1}, d_{2}, \dots, d_{r}$ . The corresponding column of A must be

\begin{array}{rcl} M^{- 1} (d_{1} e_{1} + d_{2} e_{2} + \dots + d_{r} e_{r}) & = & d_{1} M^{- 1} e_{1} + d_{2} M^{- 1} e_{2} + \dots + d_{r} M^{- 1} e_{r} \\ = & d_{1} M^{- 1} b_{j_{1}} + d_{2} M^{- 1} b_{i_{2}} + \dots + d_{r} M^{- 1} b_{j_{r}} \\ = & d_{1} a_{j_{1}} + d_{2} a_{j_{2}} + \dots + d_{r} a_{j_{r}} . \end{array}

$\begin{array}{rcl} M^{- 1} (d_{1} e_{1} + d_{2} e_{2} + \dots + d_{r} e_{r}) & = & d_{1} M^{- 1} e_{1} + d_{2} M^{- 1} e_{2} + \dots + d_{r} M^{- 1} e_{r} \\ = & d_{1} M^{- 1} b_{j_{1}} + d_{2} M^{- 1} b_{i_{2}} + \dots + d_{r} M^{- 1} b_{j_{r}} \\ = & d_{1} a_{j_{1}} + d_{2} a_{j_{2}} + \dots + d_{r} a_{j_{r}} . \end{array}$

The next theorem summarizes these results.

Theorem 3.16.

Let A be an $m \times n$ $m \times n$ matrix of rank r, where $r > 0$ $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, \dots, r$ $i = 1, 2, \dots, r$ there is a column $b_{j_{i}}$ $b_{j_{i}}$ of B such that $b_{j_{i}} = e_{i}$ $b_{j_{i}} = e_{i}$ .
(c) The columns of A numbered $j_{1}, j_{2}, \dots, j_{r}$ $j_{1}, j_{2}, \dots, j_{r}$ are linearly independent.
(d) For each $k = 1, 2, \dots, n$ $k = 1, 2, \dots, n$ , if column k of B is $d_{1} e_{1} + d_{2} e_{2} + \dots + d_{r} e_{r}$ $d_{1} e_{1} + d_{2} e_{2} + \dots + d_{r} e_{r}$ , then column k of A is $d_{1} a_{j_{1}} + d_{2} a_{j_{2}} + \dots + d_{r} a_{j_{r}} .$ $d_{1} a_{j_{1}} + d_{2} a_{j_{2}} + \dots + d_{r} a_{j_{r}} .$

Corollary.

The reduced row echelon form of a matrix is unique.

Proof.

Exercise. (See Exercise 15.)

Example 2

Let

A = (\begin{array}{c} 2 & 4 & 6 & 2 & 4 \\ 1 & 2 & 3 & 1 & 1 \\ 2 & 4 & 8 & 0 & 0 \\ 3 & 6 & 7 & 5 & 9 \end{array}) .

$A = (\begin{array}{c} 2 & 4 & 6 & 2 & 4 \\ 1 & 2 & 3 & 1 & 1 \\ 2 & 4 & 8 & 0 & 0 \\ 3 & 6 & 7 & 5 & 9 \end{array}) .$

The reduced row echelon form of A is

B = (\begin{array}{r} 1 & 2 & 0 & 4 & 0 \\ 0 & 0 & 1 & - 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}) .

$B = (\begin{array}{r} 1 & 2 & 0 & 4 & 0 \\ 0 & 0 & 1 & - 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}) .$

Since B has three nonzero rows, the rank of A is 3. The first, third, and fifth columns of B are $e_{1}, e_{2}$ $e_{1}, e_{2}$ , and $e_{3}$ $e_{3}$ ; 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 $a_{1}, a_{2}, a_{3}, a_{4}, and a_{5}$ $a_{1}, a_{2}, a_{3}, a_{4}, and a_{5}$ . Because the second column of B is $2 e_{1}$ $2 e_{1}$ , it follows from Theorem 3.16(d) that $a_{2} = 2 a_{1}$ $a_{2} = 2 a_{1}$ , as is easily checked. Moreover, since the fourth column of B is $4 e_{1} + (- 1) e_{2}$ $4 e_{1} + (- 1) e_{2}$ , the same result shows that

a_{4} = 4 a_{1} + (- 1) a_{3} .

$a_{4} = 4 a_{1} + (- 1) a_{3} .$

In Example 6 of Section 1.6, we extracted a basis for $R^{3}$ $R^{3}$ from the generating set

S = {(2, - 3, 5), (8, - 12, 20), (1, 0, - 2), (0, 2, - 1), (7, 2, 0)} .

$S = {(2, - 3, 5), (8, - 12, 20), (1, 0, - 2), (0, 2, - 1), (7, 2, 0)} .$

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 $R^{3}$ $R^{3}$ . In this case, it is clear that S is linearly dependent because S contains more than $\dim (R^{3}) = 3$ $\dim (R^{3}) = 3$ 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 $c_{1}, c_{2}, c_{3}, c_{4}$ $c_{1}, c_{2}, c_{3}, c_{4}$ , and $c_{5}$ $c_{5}$ , not all zero, such that

c_{1} (2, - 3, 5) + c_{2} (8, - 12, 20) + c_{3} (1, 0, - 2) + c_{4} (0, 2, - 1) + c_{5} (7, 2, 0) = (0, 0, 0) .

$c_{1} (2, - 3, 5) + c_{2} (8, - 12, 20) + c_{3} (1, 0, - 2) + c_{4} (0, 2, - 1) + c_{5} (7, 2, 0) = (0, 0, 0) .$

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

\begin{array}{rcrcrcrcrcl} 2 c_{1} & + & 8 c_{2} & + & c_{3} & + & 7 c_{5} & = & 0 \\ - 3 c_{1} & - & 12 c_{2} & + & 2 c_{4} & + & 2 c_{5} & = & 0 \\ 5 c_{1} & + & 20 c_{2} & - & 2 c_{3} & - & c_{4} & = & 0 \end{array}

$\begin{array}{rcrcrcrcrcl} 2 c_{1} & + & 8 c_{2} & + & c_{3} & + & 7 c_{5} & = & 0 \\ - 3 c_{1} & - & 12 c_{2} & + & 2 c_{4} & + & 2 c_{5} & = & 0 \\ 5 c_{1} & + & 20 c_{2} & - & 2 c_{3} & - & c_{4} & = & 0 \end{array}$

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

A = (\begin{array}{r} 2 & 8 & 1 & 0 & 7 & 0 \\ - 3 & - 12 & 0 & 2 & 2 & 0 \\ 5 & 20 & - 2 & - 1 & 0 & 0 \end{array}),

$A = (\begin{array}{r} 2 & 8 & 1 & 0 & 7 & 0 \\ - 3 & - 12 & 0 & 2 & 2 & 0 \\ 5 & 20 & - 2 & - 1 & 0 & 0 \end{array}),$

and its reduced row echelon form is

B = (\begin{array}{c} 1 & 4 & 0 & 0 & 2 & 0 \\ 0 & 0 & 1 & 0 & 3 & 0 \\ 0 & 0 & 0 & 1 & 4 & 0 \end{array}) .

$B = (\begin{array}{c} 1 & 4 & 0 & 0 & 2 & 0 \\ 0 & 0 & 1 & 0 & 3 & 0 \\ 0 & 0 & 0 & 1 & 4 & 0 \end{array}) .$

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 $e_{1}, e_{2}$ $e_{1}, e_{2}$ , and $e_{3}$ $e_{3}$ , 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

β = {(2, - 3, 5), (1, 0, - 2), (0, 2, - 1)}

$β = {(2, - 3, 5), (1, 0, - 2), (0, 2, - 1)}$

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 $R^{3}$ $R^{3}$ .

Because every finite-dimensional vector space over F is isomorphic to $F^{n}$ $F^{n}$ 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

S = {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}}

$S = {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}}$

generates a subspace V of $P_{3} (R)$ $P_{3} (R)$ . To find a subset of S that is a basis for V, we consider the subset

S^{'} = {(2, 1, 2, 3), (4, 2, 4, 6), (6, 3, 8, 7), (2, 1, 0, 5), (4, 1, 0, 9)}

$S^{'} = {(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 $P_{3} (R)$ $P_{3} (R)$ with respect to the standard ordered basis. Note that the $4 \times 5$ $4 \times 5$ matrix in which the columns are the vectors in $S^{'}$ $S^{'}$ 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

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

${(2, 1, 2, 3), (6, 3, 8, 7), (4, 1, 0, 9)}$

is a basis for the subspace of $R^{4}$ $R^{4}$ that is generated by $S^{'}$ $S^{'}$ . It follows that

{2 + x + 2 x^{2} + 3 x^{3}, 6 + 3 x + 8 x^{2} + 7 x^{3}, 4 + x + 9 x^{3}}

${2 + x + 2 x^{2} + 3 x^{3}, 6 + 3 x + 8 x^{2} + 7 x^{3}, 4 + x + 9 x^{3}}$

is a basis for the subspace V of $P_{3} (R)$ $P_{3} (R)$ .

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 $S^{'}$ $S^{'}$ be the ordered set consisting of the vectors in S followed by those in $β$ $β$ . Since $β \subseteq S^{'}$ $β \subseteq S^{'}$ , the set $S^{'}$ $S^{'}$ 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

V = {(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \in R^{5} : x_{1} + 7 x_{2} + 5 x_{3} - 4 x_{4} + 2 x_{5} = 0} .

$V = {(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \in R^{5} : x_{1} + 7 x_{2} + 5 x_{3} - 4 x_{4} + 2 x_{5} = 0} .$

It is easily verified that V is a subspace of $R^{5}$ $R^{5}$ and that

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

$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 $β$ $β$ 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}

$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}$ $x_{2}, x_{3}, x_{4}$ , and $x_{5}$ $x_{5}$ . If $x_{2} = t_{1}, x_{3} = t_{2}, x_{4} = t_{3}$ $x_{2} = t_{1}, x_{3} = t_{2}, x_{4} = t_{3}$ , and $x_{5} = t_{4}$ $x_{5} = t_{4}$ , then the vectors in V have the form

\begin{array}{l} (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (- 7 t_{1} - 5 t_{2} + 4 t_{3} - 2 t_{4}, t_{1}, t_{2}, t_{3}, t_{4}) \\ = 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{array}

$\begin{array}{l} (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (- 7 t_{1} - 5 t_{2} + 4 t_{3} - 2 t_{4}, t_{1}, t_{2}, t_{3}, t_{4}) \\ = 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{array}$

Hence

β = {(- 7, 1, 0, 0, 0), (- 5, 0, 1, 0, 0), (4, 0, 0, 1, 0), (- 2, 0, 0, 0, 1)}

$β = {(- 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 3.15.

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

(\begin{array}{r} - 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}),

$(\begin{array}{r} - 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}),$

and its reduced row echelon form is

(\begin{array}{r} 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}) .

$(\begin{array}{r} 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}) .$

Thus

{(- 2, 0, 0, - 1, - 1), (1, 1, - 2, - 1, - 1), (- 5, 1, 0, 1, 1), (4, 0, 0, 1, 0)}

${(- 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.

Exercises

Label the following statements as true or false.
1. (a) If $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ is obtained from $(A | b)$ $(A | b)$ by a finite sequence of elementary column operations, then the systems $A x = b$ $A x = b$ and $A^{'} x = b^{'}$ $A^{'} x = b^{'}$ are equivalent.
2. (b) If $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ is obtained from $(A | b)$ $(A | b)$ by a finite sequence of elementary row operations, then the systems $A x = b$ $A x = b$ and $A^{'} x = b^{'}$ $A^{'} x = b^{'}$ are equivalent.
3. (c) If A is an $n \times n$ $n \times n$ matrix with rank n, then the reduced row echelon form of A is $I_{n}$ $I_{n}$ .
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 $(A | b)$ $(A | b)$ is in reduced row echelon form, then the system $A x = b$ $A x = b$ is consistent.
6. (f) Let $A x = b$ $A x = b$ 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 $A x = 0$ $A x = 0$ is $n - r$ $n - r$ , 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 $A^{'}$ $A^{'}$ in reduced row echelon form, then the number of nonzero rows in $A^{'}$ $A^{'}$ equals the rank of A.
Use Gaussian elimination to solve the following systems of linear equations.
1. (a) $\begin{array}{rcrcrcr} x_{1} & + & 2 x_{2} & - & x_{3} & = & - 1 \\ 2 x_{1} & + & 2 x_{2} & + & x_{3} & = & 1 \\ 3 x_{1} & + & 5 x_{2} & - & 2 x_{3} & = & - 1 \end{array}$ $\begin{array}{rcrcrcr} x_{1} & + & 2 x_{2} & - & x_{3} & = & - 1 \\ 2 x_{1} & + & 2 x_{2} & + & x_{3} & = & 1 \\ 3 x_{1} & + & 5 x_{2} & - & 2 x_{3} & = & - 1 \end{array}$
2. (b) $\begin{array}{rcrcrcl} x_{1} & - & 2 x_{2} & - & x_{3} & = & 1 \\ 2 x_{1} & - & 3 x_{2} & + & x_{3} & = & 6 \\ 3 x_{1} & - & 5 x_{2} & = & 7 \\ x_{1} & + & 5 x_{3} & = & 9 \end{array}$ $\begin{array}{rcrcrcl} x_{1} & - & 2 x_{2} & - & x_{3} & = & 1 \\ 2 x_{1} & - & 3 x_{2} & + & x_{3} & = & 6 \\ 3 x_{1} & - & 5 x_{2} & = & 7 \\ x_{1} & + & 5 x_{3} & = & 9 \end{array}$
3. (c) $\begin{array}{rcrcrcrcr} x_{1} & + & 2 x_{2} & + & 2 x_{4} & = & 6 \\ 3 x_{1} & + & 5 x_{2} & - & x_{3} & + & 6 x_{4} & = & 17 \\ 2 x_{1} & + & 4 x_{2} & + & x_{3} & + & 2 x_{4} & = & 12 \\ 2 x_{1} & - & 7 x_{3} & + & 11 x_{4} & = & 7 \end{array}$ $\begin{array}{rcrcrcrcr} x_{1} & + & 2 x_{2} & + & 2 x_{4} & = & 6 \\ 3 x_{1} & + & 5 x_{2} & - & x_{3} & + & 6 x_{4} & = & 17 \\ 2 x_{1} & + & 4 x_{2} & + & x_{3} & + & 2 x_{4} & = & 12 \\ 2 x_{1} & - & 7 x_{3} & + & 11 x_{4} & = & 7 \end{array}$
4. (d) $\begin{array}{rcrcrcrcr} x_{1} & - & x_{2} & - & 2 x_{3} & + & 3 x_{4} & = & - 63 \\ 2 x_{1} & - & x_{2} & + & 6 x_{3} & + & 6 x_{4} & = & - 2 \\ - 2 x_{1} & + & x_{2} & - & 4 x_{3} & - & 3 x_{4} & = & 0 \\ 3 x_{1} & - & 2 x_{2} & + & 9 x_{3} & + & 10 x_{4} & = & - 5 \end{array}$ $\begin{array}{rcrcrcrcr} x_{1} & - & x_{2} & - & 2 x_{3} & + & 3 x_{4} & = & - 63 \\ 2 x_{1} & - & x_{2} & + & 6 x_{3} & + & 6 x_{4} & = & - 2 \\ - 2 x_{1} & + & x_{2} & - & 4 x_{3} & - & 3 x_{4} & = & 0 \\ 3 x_{1} & - & 2 x_{2} & + & 9 x_{3} & + & 10 x_{4} & = & - 5 \end{array}$
5. (e) $\begin{array}{rcrcrcrcr} x_{1} & - & 4 x_{2} & - & x_{3} & + & x_{4} & = & 3 \\ 2 x_{1} & - & 8 x_{2} & + & x_{3} & - & 4 x_{4} & = & 9 \\ - x_{1} & + & 4 x_{2} & - & 2 x_{3} & + & 5 x_{4} & = & - 6 \end{array}$ $\begin{array}{rcrcrcrcr} x_{1} & - & 4 x_{2} & - & x_{3} & + & x_{4} & = & 3 \\ 2 x_{1} & - & 8 x_{2} & + & x_{3} & - & 4 x_{4} & = & 9 \\ - x_{1} & + & 4 x_{2} & - & 2 x_{3} & + & 5 x_{4} & = & - 6 \end{array}$
6. (f) $\begin{array}{rcrcrcrcl} x_{1} & + & 2 x_{2} & - & x_{3} & + & 3 x_{4} & = & 2 \\ 2 x_{1} & + & 4 x_{2} & - & x_{3} & + & 6 x_{4} & = & 5 \\ x_{2} & + & 2 x_{4} & = & 3 \end{array}$ $\begin{array}{rcrcrcrcl} x_{1} & + & 2 x_{2} & - & x_{3} & + & 3 x_{4} & = & 2 \\ 2 x_{1} & + & 4 x_{2} & - & x_{3} & + & 6 x_{4} & = & 5 \\ x_{2} & + & 2 x_{4} & = & 3 \end{array}$
7. (g) $\begin{array}{rcrcrcrcrcl} 2 x_{1} & - & 2 x_{2} & - & x_{3} & + & 6 x_{4} & - & 2 x_{5} & = & 1 \\ x_{1} & - & x_{2} & + & x_{3} & + & 2 x_{4} & - & x_{5} & = & 2 \\ 4 x_{1} & - & 4 x_{2} & + & 5 x_{3} & + & 7 x_{4} & - & x_{5} & = & 6 \end{array}$ $\begin{array}{rcrcrcrcrcl} 2 x_{1} & - & 2 x_{2} & - & x_{3} & + & 6 x_{4} & - & 2 x_{5} & = & 1 \\ x_{1} & - & x_{2} & + & x_{3} & + & 2 x_{4} & - & x_{5} & = & 2 \\ 4 x_{1} & - & 4 x_{2} & + & 5 x_{3} & + & 7 x_{4} & - & x_{5} & = & 6 \end{array}$
8. (h) $\begin{array}{rcrcrcrcrcr} 3 x_{1} & - & x_{2} & + & x_{3} & - & x_{4} & + & 2 x_{5} & = & 5 \\ x_{1} & - & x_{2} & - & x_{3} & - & 2 x_{4} & - & x_{5} & = & 2 \\ 5 x_{1} & - & 2 x_{2} & + & x_{3} & - & 3 x_{4} & + & 3 x_{5} & = & 10 \\ 2 x_{1} & - & x_{2} & - & 2 x_{4} & + & x_{5} & = & 5 \end{array}$ $\begin{array}{rcrcrcrcrcr} 3 x_{1} & - & x_{2} & + & x_{3} & - & x_{4} & + & 2 x_{5} & = & 5 \\ x_{1} & - & x_{2} & - & x_{3} & - & 2 x_{4} & - & x_{5} & = & 2 \\ 5 x_{1} & - & 2 x_{2} & + & x_{3} & - & 3 x_{4} & + & 3 x_{5} & = & 10 \\ 2 x_{1} & - & x_{2} & - & 2 x_{4} & + & x_{5} & = & 5 \end{array}$
9. (i) $\begin{array}{rcrcrcrcrcr} 3 x_{1} & - & x_{2} & + & 2 x_{3} & + & 4 x_{4} & + & x_{5} & = & 2 \\ x_{1} & - & x_{2} & + & 2 x_{3} & + & 3 x_{4} & + & x_{5} & = & - 1 \\ 2 x_{1} & - & 3 x_{2} & + & 6 x_{3} & + & 9 x_{4} & + & 4 x_{5} & = & - 5 \\ 7 x_{1} & - & 2 x_{2} & + & 4 x_{3} & + & 8 x_{4} & + & x_{5} & = & 6 \end{array}$ $\begin{array}{rcrcrcrcrcr} 3 x_{1} & - & x_{2} & + & 2 x_{3} & + & 4 x_{4} & + & x_{5} & = & 2 \\ x_{1} & - & x_{2} & + & 2 x_{3} & + & 3 x_{4} & + & x_{5} & = & - 1 \\ 2 x_{1} & - & 3 x_{2} & + & 6 x_{3} & + & 9 x_{4} & + & 4 x_{5} & = & - 5 \\ 7 x_{1} & - & 2 x_{2} & + & 4 x_{3} & + & 8 x_{4} & + & x_{5} & = & 6 \end{array}$
10. (j) $\begin{array}{rcrcrcrcrcr} 2 x_{1} & + & 3 x_{3} & - & 4 x_{5} & = & 5 \\ 3 x_{1} & - & 4 x_{2} & + & 8 x_{3} & + & 3 x_{4} & = & 8 \\ x_{1} & - & x_{2} & + & 2 x_{3} & + & x_{4} & - & x_{5} & = & 2 \\ - 2 x_{1} & + & 5 x_{2} & - & 9 x_{3} & - & 3 x_{4} & - & 5 x_{5} & = & - 8 \end{array}$ $\begin{array}{rcrcrcrcrcr} 2 x_{1} & + & 3 x_{3} & - & 4 x_{5} & = & 5 \\ 3 x_{1} & - & 4 x_{2} & + & 8 x_{3} & + & 3 x_{4} & = & 8 \\ x_{1} & - & x_{2} & + & 2 x_{3} & + & x_{4} & - & x_{5} & = & 2 \\ - 2 x_{1} & + & 5 x_{2} & - & 9 x_{3} & - & 3 x_{4} & - & 5 x_{5} & = & - 8 \end{array}$
Suppose that the augmented matrix of a system $A x = b$ $A x = b$ is transformed into a matrix $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ in reduced row echelon form by a finite sequence of elementary row operations.
1. (a) Prove that $rank (A^{'}) \neq rank (A^{'} | b^{'})$ $rank (A^{'}) \neq rank (A^{'} | b^{'})$ if and only if $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ contains a row in which the only nonzero entry lies in the last column.
2. (b) Deduce that $A x = b$ $A x = b$ is consistent if and only if $(A^{'} | b^{'})$ $(A^{'} | b^{'})$ 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.
1. (a) $\begin{array}{rcrcrcrcl} x_{1} & + & 2 x_{2} & - & x_{3} & + & x_{4} & = & 2 \\ 2 x_{1} & + & x_{2} & + & x_{3} & - & x_{4} & = & 3 \\ x_{1} & + & 2 x_{2} & - & 3 x_{3} & + & 2 x_{4} & = & 2 \end{array}$ $\begin{array}{rcrcrcrcl} x_{1} & + & 2 x_{2} & - & x_{3} & + & x_{4} & = & 2 \\ 2 x_{1} & + & x_{2} & + & x_{3} & - & x_{4} & = & 3 \\ x_{1} & + & 2 x_{2} & - & 3 x_{3} & + & 2 x_{4} & = & 2 \end{array}$
2. (b) $\begin{array}{rcrcrcrcr} x_{1} & + & x_{2} & - & 3 x_{3} & + & x_{4} & = & - 2 \\ x_{1} & + & x_{2} & + & x_{3} & - & x_{4} & = & 2 \\ x_{1} & + & x_{2} & - & x_{3} & = & 0 \end{array}$ $\begin{array}{rcrcrcrcr} x_{1} & + & x_{2} & - & 3 x_{3} & + & x_{4} & = & - 2 \\ x_{1} & + & x_{2} & + & x_{3} & - & x_{4} & = & 2 \\ x_{1} & + & x_{2} & - & x_{3} & = & 0 \end{array}$
3. (c) $\begin{array}{rcrcrcrcl} x_{1} & + & x_{2} & - & 3 x_{3} & + & x_{4} & = & 1 \\ x_{1} & + & x_{2} & + & x_{3} & - & x_{4} & = & 2 \\ x_{1} & + & x_{2} & - & x_{3} & = & 0 \end{array}$ $\begin{array}{rcrcrcrcl} x_{1} & + & x_{2} & - & 3 x_{3} & + & x_{4} & = & 1 \\ x_{1} & + & x_{2} & + & x_{3} & - & x_{4} & = & 2 \\ x_{1} & + & x_{2} & - & x_{3} & = & 0 \end{array}$
Let the reduced row echelon form of A be

$(\begin{array}{r} 1 & 0 & 2 & 0 & - 2 \\ 0 & 1 & - 5 & 0 & - 3 \\ 0 & 0 & 0 & 1 & 6 \end{array}) .$ $(\begin{array}{r} 1 & 0 & 2 & 0 & - 2 \\ 0 & 1 & - 5 & 0 & - 3 \\ 0 & 0 & 0 & 1 & 6 \end{array}) .$

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

$(\begin{array}{r} 1 \\ - 1 \\ 3 \end{array}), (\begin{array}{r} 0 \\ - 1 \\ 1 \end{array}), and (\begin{array}{r} 1 \\ - 2 \\ 0 \end{array}),$ $(\begin{array}{r} 1 \\ - 1 \\ 3 \end{array}), (\begin{array}{r} 0 \\ - 1 \\ 1 \end{array}), and (\begin{array}{r} 1 \\ - 2 \\ 0 \end{array}),$

respectively.
Let the reduced row echelon form of A be

$(\begin{array}{r} 1 & - 3 & 0 & 4 & 0 & 5 \\ 0 & 0 & 1 & 3 & 0 & 2 \\ 0 & 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}) .$ $(\begin{array}{r} 1 & - 3 & 0 & 4 & 0 & 5 \\ 0 & 0 & 1 & 3 & 0 & 2 \\ 0 & 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}) .$

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

$(\begin{array}{r} 1 \\ - 2 \\ - 1 \\ 3 \end{array}), (\begin{array}{r} - 1 \\ 1 \\ 2 \\ - 4 \end{array}), and (\begin{array}{r} 3 \\ - 9 \\ 2 \\ 5 \end{array}),$ $(\begin{array}{r} 1 \\ - 2 \\ - 1 \\ 3 \end{array}), (\begin{array}{r} - 1 \\ 1 \\ 2 \\ - 4 \end{array}), and (\begin{array}{r} 3 \\ - 9 \\ 2 \\ 5 \end{array}),$

respectively.
It can be shown that the vectors $u_{1} = (2, - 3, 1), u_{2} = (1, 4, - 2), u_{3} = (- 8, 12, - 4), u_{4} = (1, 37, - 17)$ $u_{1} = (2, - 3, 1), u_{2} = (1, 4, - 2), u_{3} = (- 8, 12, - 4), u_{4} = (1, 37, - 17)$ and $u_{5} = (- 3, - 5, 8)$ $u_{5} = (- 3, - 5, 8)$ generate $R^{3}$ $R^{3}$ . Find a subset of ${u_{1}, u_{2}, u_{3}, u_{4}, u_{5}}$ ${u_{1}, u_{2}, u_{3}, u_{4}, u_{5}}$ that is a basis for $R^{3}$ $R^{3}$ .
Let W denote the subspace of $R^{5}$ $R^{5}$ consisting of all vectors having coordinates that sum to zero. The vectors

$\begin{array}{rcl} u_{1} = (2, - 3, 4, - 5, 2), & u_{2} = (- 6, 9, - 12, 15, - 6), \\ u_{3} = (3, - 2, 7, - 9, 1), & u_{4} = (2, - 8, 2, - 2, 6), \\ u_{5} = (- 1, 1, 2, 1, - 3), & u_{6} = (0, - 3, - 18, 9, 12), \\ u_{7} = (1, 0, - 2, 3, - 2), & and & u_{8} = (2, - 1, 1, - 9, 7) \end{array}$ $\begin{array}{rcl} u_{1} = (2, - 3, 4, - 5, 2), & u_{2} = (- 6, 9, - 12, 15, - 6), \\ u_{3} = (3, - 2, 7, - 9, 1), & u_{4} = (2, - 8, 2, - 2, 6), \\ u_{5} = (- 1, 1, 2, 1, - 3), & u_{6} = (0, - 3, - 18, 9, 12), \\ u_{7} = (1, 0, - 2, 3, - 2), & and & u_{8} = (2, - 1, 1, - 9, 7) \end{array}$

generate W. Find a subset of ${u_{1}, u_{2}, \dots, u_{8}}$ ${u_{1}, u_{2}, \dots, u_{8}}$ that is a basis for W.
Let W be the subspace of $M_{2 \times 2} (R)$ $M_{2 \times 2} (R)$ consisting of the symmetric $2 \times 2$ $2 \times 2$ matrices. The set

$S = {(\begin{array}{r} 0 & - 1 \\ - 1 & 1 \end{array}), (\begin{array}{r} 1 & 2 \\ 2 & 3 \end{array}), (\begin{array}{r} 2 & 1 \\ 1 & 9 \end{array}), (\begin{array}{r} 1 & - 2 \\ - 2 & 4 \end{array}), (\begin{array}{r} - 1 & 2 \\ 2 & - 1 \end{array})}$ $S = {(\begin{array}{r} 0 & - 1 \\ - 1 & 1 \end{array}), (\begin{array}{r} 1 & 2 \\ 2 & 3 \end{array}), (\begin{array}{r} 2 & 1 \\ 1 & 9 \end{array}), (\begin{array}{r} 1 & - 2 \\ - 2 & 4 \end{array}), (\begin{array}{r} - 1 & 2 \\ 2 & - 1 \end{array})}$

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

$V = {(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \in R^{5} : x_{1} - 2 x_{2} + 3 x_{3} - x_{4} + 2 x_{5} = 0} .$ $V = {(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \in R^{5} : x_{1} - 2 x_{2} + 3 x_{3} - x_{4} + 2 x_{5} = 0} .$
1. (a) Show that $S = {(0, 1, 1, 1, 0)}$ $S = {(0, 1, 1, 1, 0)}$ is a linearly independent subset of V.
2. (b) Extend S to a basis for V.
Let V be as in Exercise 10.
1. (a) Show that $S = {(1, 2, 1, 0, 0)}$ $S = {(1, 2, 1, 0, 0)}$ is a linearly independent subset of V.
2. (b) Extend S to a basis for V.
Let V denote the set of all solutions to the system of linear equations

$\begin{array}{rcrcrcrcrcrcl} x_{1} & - & x_{2} & + & 2 x_{4} & - & 3 x_{5} & + & x_{6} & = & 0 \\ 2 x_{1} & - & x_{2} & - & x_{3} & + & 3 x_{4} & - & 4 x_{5} & + & 4 x_{6} & = & 0. \end{array}$ $\begin{array}{rcrcrcrcrcrcl} x_{1} & - & x_{2} & + & 2 x_{4} & - & 3 x_{5} & + & x_{6} & = & 0 \\ 2 x_{1} & - & x_{2} & - & x_{3} & + & 3 x_{4} & - & 4 x_{5} & + & 4 x_{6} & = & 0. \end{array}$
1. (a) Show that $S = {(0, - 1, 0, 1, 1, 0), (1, 0, 1, 1, 1, 0)}$ $S = {(0, - 1, 0, 1, 1, 0), (1, 0, 1, 1, 1, 0)}$ is a linearly independent subset of V.
2. (b) Extend S to a basis for V.
Let V be as in Exercise 12.
1. (a) Show that $S = {(1, 0, 1, 1, 1, 0), (0, 2, 1, 1, 0, 0)}$ $S = {(1, 0, 1, 1, 1, 0), (0, 2, 1, 1, 0, 0)}$ is a linearly independent subset of V.
2. (b) Extend S to a basis for V.
If $(A | b)$ $(A | b)$ 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/cZVzxM for a solution.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.4 Systems of Linear Equations&#8212;Computational Aspects Systems of Linear Equations—Computational Aspects

Create new playlist

Sign In

Sign Up

Table of Contents for
3.4 Systems of Linear Equations—Computational Aspects Systems of Linear Equations—Computational Aspects