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.3 Reduced Row-Echelon Matrices

The result of the process of Gaussian elimination described in Section 3.2 is not uniquely determined. That is, two different sequences of elementary row operations, both starting with the same matrix A, may yield two different echelon matrices, each of course still row equivalent to A. For instance, the two echelon matrices

[\begin{array}{l} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{array}] and [\begin{array}{l} 1 & 1 & 1 \\ 0 & 2 & 2 \\ 0 & 0 & 3 \end{array}]

$[\begin{array}{l} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{array}] and [\begin{array}{l} 1 & 1 & 1 \\ 0 & 2 & 2 \\ 0 & 0 & 3 \end{array}]$ (1)

are readily seen (as in Problem 31) to be row equivalent. Hence it is possible to begin with an appropriate $3 \times 3$ $3 \times 3$ matrix and derive by Gaussian elimination either of the two different echelon matrices in (1).

A full understanding of the structure of systems of linear equations depends on the definition of a special class of echelon matrices, a class having the property that every matrix in it is row equivalent to one and only one of these special echelon matrices. Recall that an echelon matrix E is one that has the following two properties:

Every all-zero row of E lies beneath every row that contains a nonzero element.
The leading nonzero entry in each row lies to the right of the leading nonzero entry in the preceding row.

A reduced echelon matrix (sometimes called a reduced row-echelon matrix) has two additional properties.

A matrix is said to be in reduced echelon form if it is a reduced echelon matrix. Similarly, a linear system is in reduced echelon form if its augmented coefficient matrix is a reduced echelon matrix.

Example 1

The following matrices are reduced echelon matrices.

\begin{array}{c} [\begin{array}{l} 1 & 0 \\ 0 & 1 \end{array}] [\begin{array}{r} 1 & 0 & - 3 & 0 \\ 0 & 1 & 4 & 0 \\ 0 & 0 & 0 & 1 \end{array}] \\ [\begin{array}{r} 1 & - 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array}] [\begin{array}{r} 1 & 0 & - 7 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \end{array}] \end{array}

$\begin{array}{c} [\begin{array}{l} 1 & 0 \\ 0 & 1 \end{array}] [\begin{array}{r} 1 & 0 & - 3 & 0 \\ 0 & 1 & 4 & 0 \\ 0 & 0 & 0 & 1 \end{array}] \\ [\begin{array}{r} 1 & - 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array}] [\begin{array}{r} 1 & 0 & - 7 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \end{array}] \end{array}$

The echelon matrices

A = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{array}] and B = [\begin{array}{c} 1 & 0 & 2 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}]

$A = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{array}] and B = [\begin{array}{c} 1 & 0 & 2 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}]$

are not in reduced echelon form, because A does not have Property 3 and B does not have Property 4.

The process of transforming a matrix A into reduced echelon form is called Gauss-Jordan elimination.

The reduced echelon form of a matrix is unique. The special class of matrices that we mentioned at the beginning of this discussion is simply the class of all reduced echelon matrices. A proof of the following theorem may be found in Section 4.2 of B. Noble and J. W. Daniel, Applied Linear Algebra, 3rd ed., Hoboken, NJ: Pearson, 1988.

Example 2

Find the reduced echelon form of the matrix

A = [\begin{array}{r} 1 & 2 & 1 & 4 \\ 3 & 8 & 7 & 20 \\ 2 & 7 & 9 & 23 \end{array}] .

$A = [\begin{array}{r} 1 & 2 & 1 & 4 \\ 3 & 8 & 7 & 20 \\ 2 & 7 & 9 & 23 \end{array}] .$

Solution

In Example 3 of Section 3.2 we found the echelon form

[\begin{array}{l} 1 & 2 & 1 & 4 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 \end{array}],

$[\begin{array}{l} 1 & 2 & 1 & 4 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 \end{array}],$

which already satisfies Property 3. To clear out columns 2 and 3 (in order to satisfy Property 4), we continue the reduction as follows.

\begin{array}{l} [\begin{array}{r} 1 & 2 & 1 & 4 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 \end{array}] & \overset{(- 2) R_{2} + R_{1}}{\to} & [\begin{array}{r} 1 & 0 & - 3 & - 4 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 \end{array}] \\ \overset{(- 2) R_{3} + R_{2}}{\to} & [\begin{array}{r} 1 & 0 & - 3 & - 4 \\ 0 & 1 & 0 & - 2 \\ 0 & 0 & 1 & 3 \end{array}] \\ \overset{(3) R_{3} + R_{1}}{\to} & [\begin{array}{r} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & - 2 \\ 0 & 0 & 1 & 3 \end{array}] \end{array}

$\begin{array}{l} [\begin{array}{r} 1 & 2 & 1 & 4 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 \end{array}] & \overset{(- 2) R_{2} + R_{1}}{\to} & [\begin{array}{r} 1 & 0 & - 3 & - 4 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 \end{array}] \\ \overset{(- 2) R_{3} + R_{2}}{\to} & [\begin{array}{r} 1 & 0 & - 3 & - 4 \\ 0 & 1 & 0 & - 2 \\ 0 & 0 & 1 & 3 \end{array}] \\ \overset{(3) R_{3} + R_{1}}{\to} & [\begin{array}{r} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & - 2 \\ 0 & 0 & 1 & 3 \end{array}] \end{array}$

For instance, we see immediately from this reduced echelon form that the linear system

\begin{array}{rcrcrcr} x & + & 2 y & + & z & = & 4 \\ 3 x & + & 8 y & + & 7 z & = & 20 \\ 2 x & + & 7 y & + & 9 z & = & 23 \end{array}

$\begin{array}{rcrcrcr} x & + & 2 y & + & z & = & 4 \\ 3 x & + & 8 y & + & 7 z & = & 20 \\ 2 x & + & 7 y & + & 9 z & = & 23 \end{array}$

with augmented coefficient matrix A has the unique solution $x = 5, y = - 2, z = 3$ $x = 5, y = - 2, z = 3$ .

Example 3

To use Gauss-Jordan elimination to solve the linear system

\begin{array}{rcrcrcrcl} x_{1} & + & x_{2} & + & x_{3} & + & x_{4} & = & 12 \\ x_{1} & + & 2 x_{2} & + & 5 x_{4} & = & 17 \\ 3 x_{1} & + & 2 x_{2} & + & 4 x_{3} & - & x_{4} & = & 31, \end{array}

$\begin{array}{rcrcrcrcl} x_{1} & + & x_{2} & + & x_{3} & + & x_{4} & = & 12 \\ x_{1} & + & 2 x_{2} & + & 5 x_{4} & = & 17 \\ 3 x_{1} & + & 2 x_{2} & + & 4 x_{3} & - & x_{4} & = & 31, \end{array}$ (2)

we transform its augmented coefficient matrix into reduced echelon form, as follows:

\begin{array}{l} [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 1 & 2 & 0 & 5 & 17 \\ 3 & 2 & 4 & - 1 & 31 \end{array}] & \overset{(- 1) R_{1} + R_{2}}{\to} & [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 0 & 1 & - 1 & 4 & 5 \\ 3 & 2 & 4 & - 1 & 31 \end{array}] \\ \overset{(- 3) R_{1} + R_{3}}{\to} & [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 0 & 1 & - 1 & 4 & 5 \\ 0 & - 1 & 1 & - 4 & - 5 \end{array}] \\ \overset{(1) R_{2} + R_{3}}{\to} & [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 0 & 1 & - 1 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 \end{array}] \\ \overset{(- 1) R_{2} + R_{1}}{\to} & [\begin{array}{r} 1 & 0 & 2 & - 3 & 7 \\ 0 & 1 & - 1 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 \end{array}] . \end{array}

$\begin{array}{l} [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 1 & 2 & 0 & 5 & 17 \\ 3 & 2 & 4 & - 1 & 31 \end{array}] & \overset{(- 1) R_{1} + R_{2}}{\to} & [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 0 & 1 & - 1 & 4 & 5 \\ 3 & 2 & 4 & - 1 & 31 \end{array}] \\ \overset{(- 3) R_{1} + R_{3}}{\to} & [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 0 & 1 & - 1 & 4 & 5 \\ 0 & - 1 & 1 & - 4 & - 5 \end{array}] \\ \overset{(1) R_{2} + R_{3}}{\to} & [\begin{array}{r} 1 & 1 & 1 & 1 & 12 \\ 0 & 1 & - 1 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 \end{array}] \\ \overset{(- 1) R_{2} + R_{1}}{\to} & [\begin{array}{r} 1 & 0 & 2 & - 3 & 7 \\ 0 & 1 & - 1 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 \end{array}] . \end{array}$

Thus the reduced echelon form of the system in (2) is

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

$\begin{array}{rccrcrl} x_{1} & + & 2 x_{3} & - & 3 x_{4} & = & 7 \\ x_{2} & - & x_{3} & + & 4 x_{4} & = & 5 \\ 0 & = & 0. \end{array}$ (3)

The leading variables are $x_{1}$ $x_{1}$ and $x_{2}$ $x_{2}$ ; the free variables are $x_{3}$ $x_{3}$ and $x_{4} .$ $x_{4} .$ If we set

x_{3} = s and x_{4} = t,

$x_{3} = s and x_{4} = t,$

then (3) immediately yields

\begin{array}{rcl} x_{1} & = & 7 - 2 s + 3 t, \\ x_{2} & = & 5 + s - 4 t . \end{array}

$\begin{array}{rcl} x_{1} & = & 7 - 2 s + 3 t, \\ x_{2} & = & 5 + s - 4 t . \end{array}$

As a practical matter, Gauss-Jordan elimination generally offers no significant computational advantage over Gaussian elimination (transformation to nonreduced echelon form) followed by back substitution. Therefore, Gaussian elimination is commonly employed in practical procedures and in computer programs used to solve linear systems numerically.

The Three Possibilities

The chief importance of Gauss-Jordan elimination stems from the fact that the reduced echelon form of a general linear system

\begin{array}{rcrcrcrcrcl} a_{11} x_{1} & + & a_{12} x_{2} & + & a_{13} x_{3} & + & \dots & + & a_{1 n} x_{n} & = & b_{1} \\ a_{21} x_{1} & + & a_{22} x_{2} & + & a_{23} x_{3} & + & \dots & + & a_{2 b} x_{n} & = & b_{2} \\ ⋮ \\ a_{m 1} x_{1} & + & a_{m 2} x_{2} & + & a_{m 3} x_{3} & + & \dots & + & a_{m n} x_{n} & = & b_{m} \end{array}

$\begin{array}{rcrcrcrcrcl} a_{11} x_{1} & + & a_{12} x_{2} & + & a_{13} x_{3} & + & \dots & + & a_{1 n} x_{n} & = & b_{1} \\ a_{21} x_{1} & + & a_{22} x_{2} & + & a_{23} x_{3} & + & \dots & + & a_{2 b} x_{n} & = & b_{2} \\ ⋮ \\ a_{m 1} x_{1} & + & a_{m 2} x_{2} & + & a_{m 3} x_{3} & + & \dots & + & a_{m n} x_{n} & = & b_{m} \end{array}$ (4)

most clearly exhibits its underlying structure and enables us most readily to answer questions about the number and type of its solutions. If the leading variables are $x_{j_{1}}, x_{j_{2}}, \dots, x_{j_{r}},$ $x_{j_{1}}, x_{j_{2}}, \dots, x_{j_{r}},$ then the reduced echelon form of the system in (4) looks like

\begin{array}{rcrcrcrcrcl} x_{j_{1}} & + & \sum_{k = r + 1}^{n} c_{1 k} x_{j_{k}} & = & d_{1} \\ x_{j_{2}} & + & \sum_{k = r + 1}^{n} c_{2 k} x_{j_{k}} & = & d_{2} \\ ⋱ & ⋮ \\ x_{j_{r}} & + & \sum_{k = r + 1}^{n} c_{r k} x_{j_{k}} & = & d_{r} \\ 0 & = & d_{r + 1} \\ ⋮ \\ 0 & = & d_{m}, \end{array}

$\begin{array}{rcrcrcrcrcl} x_{j_{1}} & + & \sum_{k = r + 1}^{n} c_{1 k} x_{j_{k}} & = & d_{1} \\ x_{j_{2}} & + & \sum_{k = r + 1}^{n} c_{2 k} x_{j_{k}} & = & d_{2} \\ ⋱ & ⋮ \\ x_{j_{r}} & + & \sum_{k = r + 1}^{n} c_{r k} x_{j_{k}} & = & d_{r} \\ 0 & = & d_{r + 1} \\ ⋮ \\ 0 & = & d_{m}, \end{array}$ (5)

where the summations involve only the (non-leading) free variables $x_{j_{r + 1}}, \dots, x_{j_{n}} .$ $x_{j_{r + 1}}, \dots, x_{j_{n}} .$

Now if any of the constants $d_{r + 1}, d_{r + 2}, \dots, d_{m}$ $d_{r + 1}, d_{r + 2}, \dots, d_{m}$ in (5) is nonzero, then clearly the system has no real solution. On the other hand, suppose that $d_{r + 1} = d_{r + 2} = \dots = d_{m} = 0 .$ $d_{r + 1} = d_{r + 2} = \dots = d_{m} = 0 .$ If $r < n,$ $r < n,$ then there are free variables that we can set equal to arbitrary parameters, and so the system has infinitely many solutions. If instead $r = n,$ $r = n,$ then the summations in (5) disappear and we have the unique solution $x_{1} = d_{1}, x_{2} = d_{2}, \dots, x_{n} = d_{n} .$ $x_{1} = d_{1}, x_{2} = d_{2}, \dots, x_{n} = d_{n} .$ These observations establish the following result, to which we have already alluded.

Homogeneous Systems

The linear system in (4) is called homogeneous provided that the constants $b_{1}, b_{2}, \dots, b_{m}$ $b_{1}, b_{2}, \dots, b_{m}$ on the right-hand side are all zero. Thus a homogeneous system of m equations in n variables has the form

\begin{array}{rcrcrcrcrcl} a_{11} x_{1} & + & a_{12} x_{2} & + & a_{13} x_{3} & + & \dots & + & a_{1 n} x_{n} & = & 0 \\ a_{21} x_{1} & + & a_{22} x_{2} & + & a_{23} x_{3} & + & \dots & + & a_{2 n} x_{n} & = & 0 \\ ⋮ \\ a_{m 1} x_{1} & + & a_{m 2} x_{2} & + & a_{m 3} x_{3} & + & \dots & + & a_{m n} x_{n} & = & 0. \end{array}

$\begin{array}{rcrcrcrcrcl} a_{11} x_{1} & + & a_{12} x_{2} & + & a_{13} x_{3} & + & \dots & + & a_{1 n} x_{n} & = & 0 \\ a_{21} x_{1} & + & a_{22} x_{2} & + & a_{23} x_{3} & + & \dots & + & a_{2 n} x_{n} & = & 0 \\ ⋮ \\ a_{m 1} x_{1} & + & a_{m 2} x_{2} & + & a_{m 3} x_{3} & + & \dots & + & a_{m n} x_{n} & = & 0. \end{array}$ (6)

Every homogeneous system obviously has at least the trivial solution

x_{1} = 0, x_{2} = 0, \dots, x_{n} = 0.

$x_{1} = 0, x_{2} = 0, \dots, x_{n} = 0.$ (7)

Thus (by Theorem 2) we know from the outset that every homogeneous linear system either has only the trivial solution or has infinitely many solutions. If it has a nontrivial solution—one with not every $x_{i}$ $x_{i}$ equal to zero—then it must have infinitely many solutions.

An important special case, in which a nontrivial solution is guaranteed, is that of a homogeneous system with more variables than equations: $m < n .$ $m < n .$ To see why there must be a solution, consider the reduced echelon system in (5) with the constants on the right-hand side all zero (because the original system is homogeneous). The number r of leading variables is at most the number m of equations (because there is at most one leading variable per equation). If $m < n,$ $m < n,$ it then follows that $r < n,$ $r < n,$ so there is at least one free variable that can be set equal to an arbitrary parameter, thereby yielding infinitely many solutions. This argument establishes the following key result.

Example 4

The homogeneous linear system

\begin{array}{rcl} 47 x_{1} - 73 x_{2} + 56 x_{3} + 21 x_{4} & = & 0 \\ 19 x_{1} + 81 x_{2} - 17 x_{3} - 99 x_{4} & = & 0 \\ 53 x_{1} + 62 x_{2} + 39 x_{3} + 25 x_{4} & = & 0 \end{array}

$\begin{array}{rcl} 47 x_{1} - 73 x_{2} + 56 x_{3} + 21 x_{4} & = & 0 \\ 19 x_{1} + 81 x_{2} - 17 x_{3} - 99 x_{4} & = & 0 \\ 53 x_{1} + 62 x_{2} + 39 x_{3} + 25 x_{4} & = & 0 \end{array}$

of three equations in four unknowns necessarily has infinitely many solutions. The only question (which we could answer by reducing the system to echelon form) is whether the system has one, two, or three free variables.

The situation is different for a nonhomogeneous system with more variables than equations. The simple example

\begin{array}{rcl} x_{1} + x_{2} + x_{3} & = & 0 \\ x_{1} + x_{2} + x_{3} & = & 1 \end{array}

$\begin{array}{rcl} x_{1} + x_{2} + x_{3} & = & 0 \\ x_{1} + x_{2} + x_{3} & = & 1 \end{array}$

shows that such a system may be inconsistent. But if it is consistent—meaning that $d_{r + 1} = \dots = d_{m} = 0$ $d_{r + 1} = \dots = d_{m} = 0$ in the reduced echelon form in (5)—then the fact that $m < n$ $m < n$ implies (just as in the proof of Theorem 3) that there is at least one free variable, and that the system therefore has infinitely many solutions. Hence every nonhomogeneous system with more variables than equations either has no solution or has infinitely many solutions.

Equal Numbers of Equations and Variables

An especially important case in the theory of linear systems is that of a homogeneous system

\begin{array}{rcrcrcrcrcl} a_{11} x_{1} & + & a_{12} x_{2} & + & a_{13} x_{3} & + & \dots & + & a_{1 n} x_{n} & = & 0 \\ a_{21} x_{1} & + & a_{22} x_{2} & + & a_{23} x_{3} & + & \dots & + & a_{2 n} x_{n} & = & 0 \\ ⋮ \\ a_{n 1} x_{1} & + & a_{n 2} x_{2} & + & a_{n 3} x_{3} & + & \dots & + & a_{n n} x_{n} & = & 0 \end{array}

$\begin{array}{rcrcrcrcrcl} a_{11} x_{1} & + & a_{12} x_{2} & + & a_{13} x_{3} & + & \dots & + & a_{1 n} x_{n} & = & 0 \\ a_{21} x_{1} & + & a_{22} x_{2} & + & a_{23} x_{3} & + & \dots & + & a_{2 n} x_{n} & = & 0 \\ ⋮ \\ a_{n 1} x_{1} & + & a_{n 2} x_{2} & + & a_{n 3} x_{3} & + & \dots & + & a_{n n} x_{n} & = & 0 \end{array}$ (8)

with the same number n of variables and equations. The coefficient matrix $A = [a_{i j}]$ $A = [a_{i j}]$ then has the same number of rows and columns and thus is an $n \times n$ $n \times n$ square matrix.

Here we are most interested in the situation when (8) has only the trivial solution $x_{1} = x_{2} = \dots = x_{n} = 0 .$ $x_{1} = x_{2} = \dots = x_{n} = 0 .$ This occurs if and only if the reduced echelon system contains no free variables. That is, all n of the variables $x_{1}, x_{2}, \dots, x_{n}$ $x_{1}, x_{2}, \dots, x_{n}$ must be leading variables. Because the system consists of exactly n equations, we conclude that the reduced echelon system is simply

\begin{array}{ccccrcl} x_{1} & = & 0 \\ x_{2} & = & 0 \\ x_{3} & = & 0 \\ ⋱ & ⋮ \\ x_{n} & = & 0, \end{array}

$\begin{array}{ccccrcl} x_{1} & = & 0 \\ x_{2} & = & 0 \\ x_{3} & = & 0 \\ ⋱ & ⋮ \\ x_{n} & = & 0, \end{array}$

and, therefore, that the reduced echelon form of the coefficient matrix A is the matrix

[\begin{array}{c} 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \end{array}] .

$[\begin{array}{c} 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \end{array}] .$ (9)

Such a (square) matrix, with ones on its principal diagonal (the one from upper left to lower right) and zeros elsewhere, is called an identity matrix (for reasons given in Section 3.4). For instance, the $2 \times 2$ $2 \times 2$ and $3 \times 3$ $3 \times 3$ identity matrices are

[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}] and [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] .

$[\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}] and [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] .$

The matrix in (9) is the $n \times n$ $n \times n$ identity matrix. With this terminology, the preceding argument establishes the following theorem.

Example 5

The computation in Example 2 (disregarding the fourth column in each matrix there) shows that the matrix

A = [\begin{array}{c} 1 & 2 & 1 \\ 3 & 8 & 7 \\ 2 & 7 & 9 \end{array}]

$A = [\begin{array}{c} 1 & 2 & 1 \\ 3 & 8 & 7 \\ 2 & 7 & 9 \end{array}]$

is row equivalent to the $3 \times 3$ $3 \times 3$ identity matrix. Hence Theorem 4 implies that the homogeneous system

\begin{array}{rcrcrcl} x_{1} & + & 2 x_{2} & + & x_{3} & = & 0 \\ 3 x_{1} & + & 8 x_{2} & + & 7 x_{3} & = & 0 \\ 2 x_{1} & + & 7 x_{2} & + & 9 x_{3} & = & 0 \end{array}

$\begin{array}{rcrcrcl} x_{1} & + & 2 x_{2} & + & x_{3} & = & 0 \\ 3 x_{1} & + & 8 x_{2} & + & 7 x_{3} & = & 0 \\ 2 x_{1} & + & 7 x_{2} & + & 9 x_{3} & = & 0 \end{array}$

with coefficient matrix A has only the trivial solution $x_{1} = x_{2} = x_{3} = 0$ $x_{1} = x_{2} = x_{3} = 0$ .

3.3 Problems

Find the reduced echelon form of each of the matrices given in Problems 1–20.

$[\begin{array}{c} 1 & 2 \\ 3 & 7 \end{array}]$ $[\begin{array}{c} 1 & 2 \\ 3 & 7 \end{array}]$
$[\begin{array}{c} 3 & 7 \\ 2 & 5 \end{array}]$ $[\begin{array}{c} 3 & 7 \\ 2 & 5 \end{array}]$
$[\begin{array}{c} 3 & 7 & 15 \\ 2 & 5 & 11 \end{array}]$ $[\begin{array}{c} 3 & 7 & 15 \\ 2 & 5 & 11 \end{array}]$
$[\begin{array}{r} 3 & 7 & - 1 \\ 5 & 2 & 8 \end{array}]$ $[\begin{array}{r} 3 & 7 & - 1 \\ 5 & 2 & 8 \end{array}]$
$[\begin{array}{r} 1 & 2 & - 11 \\ 2 & 3 & - 19 \end{array}]$ $[\begin{array}{r} 1 & 2 & - 11 \\ 2 & 3 & - 19 \end{array}]$
$[\begin{array}{r} 1 & - 2 & 19 \\ 4 & - 7 & 70 \end{array}]$ $[\begin{array}{r} 1 & - 2 & 19 \\ 4 & - 7 & 70 \end{array}]$
$[\begin{array}{r} 1 & 2 & 3 \\ 1 & 4 & 1 \\ 2 & 1 & 9 \end{array}]$ $[\begin{array}{r} 1 & 2 & 3 \\ 1 & 4 & 1 \\ 2 & 1 & 9 \end{array}]$
$[\begin{array}{r} 1 & - 4 & - 5 \\ 3 & - 9 & 3 \\ 1 & - 2 & 3 \end{array}]$ $[\begin{array}{r} 1 & - 4 & - 5 \\ 3 & - 9 & 3 \\ 1 & - 2 & 3 \end{array}]$
$[\begin{array}{r} 5 & 2 & 18 \\ 0 & 1 & 4 \\ 4 & 1 & 12 \end{array}]$ $[\begin{array}{r} 5 & 2 & 18 \\ 0 & 1 & 4 \\ 4 & 1 & 12 \end{array}]$
$[\begin{array}{r} 5 & 2 & - 5 \\ 9 & 4 & - 7 \\ 4 & 1 & - 7 \end{array}]$ $[\begin{array}{r} 5 & 2 & - 5 \\ 9 & 4 & - 7 \\ 4 & 1 & - 7 \end{array}]$
$[\begin{array}{r} 3 & 9 & 1 \\ 2 & 6 & 7 \\ 1 & 3 & - 6 \end{array}]$ $[\begin{array}{r} 3 & 9 & 1 \\ 2 & 6 & 7 \\ 1 & 3 & - 6 \end{array}]$
$[\begin{array}{r} 1 & - 4 & - 2 \\ 3 & - 12 & 1 \\ 2 & - 8 & 5 \end{array}]$ $[\begin{array}{r} 1 & - 4 & - 2 \\ 3 & - 12 & 1 \\ 2 & - 8 & 5 \end{array}]$
$[\begin{array}{r} 2 & 7 & 4 & 0 \\ 1 & 3 & 2 & 1 \\ 2 & 6 & 5 & 4 \end{array}]$ $[\begin{array}{r} 2 & 7 & 4 & 0 \\ 1 & 3 & 2 & 1 \\ 2 & 6 & 5 & 4 \end{array}]$
$[\begin{array}{r} 1 & 3 & 2 & 5 \\ 2 & 5 & 2 & 3 \\ 2 & 7 & 7 & 22 \end{array}]$ $[\begin{array}{r} 1 & 3 & 2 & 5 \\ 2 & 5 & 2 & 3 \\ 2 & 7 & 7 & 22 \end{array}]$
$[\begin{array}{r} 2 & 2 & 4 & 2 \\ 1 & - 1 & - 4 & 3 \\ 2 & 7 & 19 & - 3 \end{array}]$ $[\begin{array}{r} 2 & 2 & 4 & 2 \\ 1 & - 1 & - 4 & 3 \\ 2 & 7 & 19 & - 3 \end{array}]$
$[\begin{array}{r} 1 & 3 & 15 & 7 \\ 2 & 4 & 22 & 8 \\ 2 & 7 & 34 & 17 \end{array}]$ $[\begin{array}{r} 1 & 3 & 15 & 7 \\ 2 & 4 & 22 & 8 \\ 2 & 7 & 34 & 17 \end{array}]$
$[\begin{array}{r} 1 & 1 & 1 & - 1 & - 4 \\ 1 & - 2 & - 2 & 8 & - 1 \\ 2 & 3 & - 1 & 3 & 11 \end{array}]$ $[\begin{array}{r} 1 & 1 & 1 & - 1 & - 4 \\ 1 & - 2 & - 2 & 8 & - 1 \\ 2 & 3 & - 1 & 3 & 11 \end{array}]$
$[\begin{array}{r} 1 & - 2 & - 5 & - 12 & 1 \\ 2 & 3 & 18 & 11 & 9 \\ 2 & 5 & 26 & 21 & 11 \end{array}]$ $[\begin{array}{r} 1 & - 2 & - 5 & - 12 & 1 \\ 2 & 3 & 18 & 11 & 9 \\ 2 & 5 & 26 & 21 & 11 \end{array}]$
$[\begin{array}{r} 2 & 7 & - 10 & - 19 & 13 \\ 1 & 3 & - 4 & - 8 & 6 \\ 1 & 0 & 2 & 1 & 3 \end{array}]$ $[\begin{array}{r} 2 & 7 & - 10 & - 19 & 13 \\ 1 & 3 & - 4 & - 8 & 6 \\ 1 & 0 & 2 & 1 & 3 \end{array}]$
$[\begin{array}{r} 3 & 6 & 1 & 7 & 13 \\ 5 & 10 & 8 & 18 & 47 \\ 2 & 4 & 5 & 9 & 26 \end{array}]$ $[\begin{array}{r} 3 & 6 & 1 & 7 & 13 \\ 5 & 10 & 8 & 18 & 47 \\ 2 & 4 & 5 & 9 & 26 \end{array}]$

21–30. Use the method of Gauss-Jordan elimination (transforming the augmented matrix into reduced echelon form) to solve Problems 11–20 in Section 3.2 .

Show that the two matrices in (1) are both row equivalent to the $3 \times 3$ $3 \times 3$ identity matrix (and hence, by Theorem 1, to each other).
Show that the $2 \times 2$ $2 \times 2$ matrix

$A = [\begin{array}{c} a & b \\ c & d \end{array}]$ $A = [\begin{array}{c} a & b \\ c & d \end{array}]$

is row equivalent to the $2 \times 2$ $2 \times 2$ identity matrix provided that $a d - b c \neq 0$ $a d - b c \neq 0$ .
List all possible reduced row-echelon forms of a $2 \times 2$ $2 \times 2$ matrix, using asterisks to indicate elements that may be either zero or nonzero.
List all possible reduced row-echelon forms of a $3 \times 3$ $3 \times 3$ matrix, using asterisks to indicate elements that may be either zero or nonzero.
Consider the homogeneous system

$\begin{array}{rcl} a x + b y & = & 0 \\ c x + d y & = & 0. \end{array}$ $\begin{array}{rcl} a x + b y & = & 0 \\ c x + d y & = & 0. \end{array}$
1. If $x = x_{0}$ $x = x_{0}$ and $y = y_{0}$ $y = y_{0}$ is a solution and k is a real number, then show that $x = k x_{0}$ $x = k x_{0}$ and $y = k y_{0}$ $y = k y_{0}$ is also a solution.
2. If $x = x_{1}, y = y_{1}$ $x = x_{1}, y = y_{1}$ and $x = x_{2}, y = y_{2}$ $x = x_{2}, y = y_{2}$ are both solutions, then show that $x = x_{1} + x_{2}, y = y_{1} + y_{2}$ $x = x_{1} + x_{2}, y = y_{1} + y_{2}$ is a solution.
Suppose that $a d - b c \neq 0$ $a d - b c \neq 0$ in the homogeneous system of Problem 35. Use Problem 32 to show that its only solution is the trivial solution.
Show that the homogeneous system in Problem 35 has a nontrivial solution if and only if $a d - b c = 0$ $a d - b c = 0$ .
Use the result of Problem 37 to find all values of c for which the homogeneous system

$\begin{array}{rcrcl} (c + 2) x & + & 3 y & = & 0 \\ 2 x & + & (c - 3) y & = & 0 \end{array}$ $\begin{array}{rcrcl} (c + 2) x & + & 3 y & = & 0 \\ 2 x & + & (c - 3) y & = & 0 \end{array}$

has a nontrivial solution.
Consider a homogeneous system of three equations in three unknowns. Suppose that the third equation is the sum of some multiple of the first equation and some multiple of the second equation. Show that the system has a nontrivial solution.
Let E be an echelon matrix that is row equivalent to the matrix A. Show that E has the same number of nonzero rows as does the reduced echelon form $E^{*}$ $E^{*}$ of A. Thus the number of nonzero rows in an echelon form of A is an “invariant” of the matrix A. Suggestion: Consider reducing E to $E^{*}$ $E^{*}$ .

3.3 Application Automated Row Reduction

Most computer algebra systems include commands for the immediate reduction of matrices to reduced echelon form. For instance, if the matrix

A = [\begin{array}{r} 1 & 2 & 1 & 4 \\ 3 & 8 & 7 & 20 \\ 2 & 7 & 9 & 23 \end{array}]

$A = [\begin{array}{r} 1 & 2 & 1 & 4 \\ 3 & 8 & 7 & 20 \\ 2 & 7 & 9 & 23 \end{array}]$

of Example 2 has been entered—as illustrated in the 3.2 Application—then the Maple command


with(linalg):  R := rref(A);

or the Mathematica command


R = RowReduce[A] // MatrixForm

or the Matlab command


R = rref(A)

or the $Wolfram | Alpha$ $Wolfram | Alpha$ query


row reduce ((1, 2, 1, 4), (3, 8, 7, 20), (2, 7, 9, 23))

produces the reduced echelon matrix

R = [\begin{array}{r} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & - 2 \\ 0 & 0 & 1 & 3 \end{array}]

$R = [\begin{array}{r} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & - 2 \\ 0 & 0 & 1 & 3 \end{array}]$

that exhibits the solution of the linear system having augmented coefficient matrix A. The same calculation is illustrated in the calculator screen of Fig. 3.3.1. Solve similarly the systems in the following problems (which apparently would be somewhat tedious to solve by manual row reduction):

FIGURE 3.3.1.

Finding a reduced row-echelon matrix with a TI-89 calculator.

$\begin{array}{rcl} 17 x + 42 y - 36 z & = & 213 \\ 13 x + 45 y - 34 z & = & 226 \\ 12 x + 47 y - 35 z & = & 197 \end{array}$ $\begin{array}{rcl} 17 x + 42 y - 36 z & = & 213 \\ 13 x + 45 y - 34 z & = & 226 \\ 12 x + 47 y - 35 z & = & 197 \end{array}$
$\begin{array}{rcl} 32 x + 57 y - 41 z & = & 713 \\ 23 x + 43 y - 37 z & = & 130 \\ 42 x - 61 y + 39 z & = & 221 \end{array}$ $\begin{array}{rcl} 32 x + 57 y - 41 z & = & 713 \\ 23 x + 43 y - 37 z & = & 130 \\ 42 x - 61 y + 39 z & = & 221 \end{array}$
$\begin{array}{rcl} 231 x + 157 y - 241 z & = & 420 \\ 323 x + 181 y - 375 z & = & 412 \\ 542 x + 161 y - 759 z & = & 419 \end{array}$ $\begin{array}{rcl} 231 x + 157 y - 241 z & = & 420 \\ 323 x + 181 y - 375 z & = & 412 \\ 542 x + 161 y - 759 z & = & 419 \end{array}$
$\begin{array}{rcl} 837 x + 667 y - 729 z & = & 1659 \\ 152 x - 179 y - 975 z & = & 1630 \\ 542 x + 328 y - 759 z & = & 1645 \end{array}$ $\begin{array}{rcl} 837 x + 667 y - 729 z & = & 1659 \\ 152 x - 179 y - 975 z & = & 1630 \\ 542 x + 328 y - 759 z & = & 1645 \end{array}$
$\begin{array}{rcl} 49 w - 57 x + 37 y - 59 z & = & 97 \\ 73 w - 15 x - 19 y - 22 z & = & 99 \\ 52 w - 51 x + 14 y - 29 z & = & 89 \\ 13 w - 27 x + 27 y - 25 z & = & 73 \end{array}$ $\begin{array}{rcl} 49 w - 57 x + 37 y - 59 z & = & 97 \\ 73 w - 15 x - 19 y - 22 z & = & 99 \\ 52 w - 51 x + 14 y - 29 z & = & 89 \\ 13 w - 27 x + 27 y - 25 z & = & 73 \end{array}$
$\begin{array}{rcl} 64 w - 57 x + 97 y - 67 z & = & 485 \\ 92 w + 77 x - 34 y - 37 z & = & 486 \\ 44 w - 34 x + 53 y - 34 z & = & 465 \\ 27 w + 57 x - 69 y + 29 z & = & 464 \end{array}$ $\begin{array}{rcl} 64 w - 57 x + 97 y - 67 z & = & 485 \\ 92 w + 77 x - 34 y - 37 z & = & 486 \\ 44 w - 34 x + 53 y - 34 z & = & 465 \\ 27 w + 57 x - 69 y + 29 z & = & 464 \end{array}$

..................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.3 Reduced Row-Echelon Matrices

Create new playlist

Sign In

Sign Up

Table of Contents for
3.3 Reduced Row-Echelon Matrices