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
are readily seen (as in Problem 31) to be row equivalent. Hence it is possible to begin with an appropriate 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.
The following matrices are reduced echelon matrices.
The echelon matrices
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.
Find the reduced echelon form of the matrix
In Example 3 of Section 3.2 we found the echelon form
which already satisfies Property 3. To clear out columns 2 and 3 (in order to satisfy Property 4), we continue the reduction as follows.
For instance, we see immediately from this reduced echelon form that the linear system
with augmented coefficient matrix A has the unique solution .
To use Gauss-Jordan elimination to solve the linear system
we transform its augmented coefficient matrix into reduced echelon form, as follows:
Thus the reduced echelon form of the system in (2) is
The leading variables are and ; the free variables are and If we set
then (3) immediately yields
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 chief importance of Gauss-Jordan elimination stems from the fact that the reduced echelon form of a general linear system
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 then the reduced echelon form of the system in (4) looks like
where the summations involve only the (non-leading) free variables
Now if any of the constants in (5) is nonzero, then clearly the system has no real solution. On the other hand, suppose that If then there are free variables that we can set equal to arbitrary parameters, and so the system has infinitely many solutions. If instead then the summations in (5) disappear and we have the unique solution These observations establish the following result, to which we have already alluded.
The linear system in (4) is called homogeneous provided that the constants on the right-hand side are all zero. Thus a homogeneous system of m equations in n variables has the form
Every homogeneous system obviously has at least the trivial solution
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 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: 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 it then follows that 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.
The homogeneous linear system
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
shows that such a system may be inconsistent. But if it is consistent—meaning that in the reduced echelon form in (5)—then the fact that 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.
An especially important case in the theory of linear systems is that of a homogeneous system
with the same number n of variables and equations. The coefficient matrix then has the same number of rows and columns and thus is an square matrix.
Here we are most interested in the situation when (8) has only the trivial solution This occurs if and only if the reduced echelon system contains no free variables. That is, all n of the variables must be leading variables. Because the system consists of exactly n equations, we conclude that the reduced echelon system is simply
and, therefore, that the reduced echelon form of the coefficient matrix A is the matrix
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 and identity matrices are
The matrix in (9) is the identity matrix. With this terminology, the preceding argument establishes the following theorem.
The computation in Example 2 (disregarding the fourth column in each matrix there) shows that the matrix
is row equivalent to the identity matrix. Hence Theorem 4 implies that the homogeneous system
with coefficient matrix A has only the trivial solution .
Find the reduced echelon form of each of the matrices given in Problems 1–20.
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 matrix
is row equivalent to the identity matrix provided that .
List all possible reduced row-echelon forms of a matrix, using asterisks to indicate elements that may be either zero or nonzero.
List all possible reduced row-echelon forms of a matrix, using asterisks to indicate elements that may be either zero or nonzero.
Consider the homogeneous system
If and is a solution and k is a real number, then show that and is also a solution.
If and are both solutions, then show that is a solution.
Suppose that 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 .
Use the result of Problem 37 to find all values of c for which the homogeneous system
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 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 .
Most computer algebra systems include commands for the immediate reduction of matrices to reduced echelon form. For instance, if the matrix
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 query
row reduce ((1, 2, 1, 4), (3, 8, 7, 20), (2, 7, 9, 23))
produces the reduced echelon matrix
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):
18.191.176.194