Gaussian Elimination and Rank

Row Echelon and Reduced Row Echelon Forms

In Augmented Matrix Notation and Elementary Row Operations, we learned to write linear systems in augmented matrix form and use elementary row operations to transform an augmented matrix to row-echelon form and the reduced row-echelon form in order to solve linear systems.

Recall that a matrix (or augmented matrix) is in row-echelon form if:

  • All entries below each leading entry are \(0\).
  • Each leading entry is in a column to the right of the leading entries in the rows above it.
  • All rows of zeros, if there are any, are located below non-zero rows.

A matrix in row-echelon form is said to be in reduced row-echelon form if it has the following additional properties

  • Each leading entry is a \(1\)
  • All entries above each leading \(1\) are \(0\)

Matrices in row-echelon form and reduced row-echelon form are “convenient" because their corresponding systems of equations are easy to solve.

In this module we turn to the question of existence and uniqueness of the two echelon forms. Can every matrix (augmented matrix) be carried to a row-echelon form? If so, is the row-echelon form unique? Can every matrix be reduced to a reduced row-echelon form? If so, is the reduced row-echelon form unique? The answers we find will have long-lasting implications.

Solve the following system of equations.
\[\begin{array}{ccccccccc} x &+ &2y&-&3z&= &1 \\ -5x& +&2y&-&3z&=&1\\ x&- &2y&+&z&=&1 \end{array}\]

We create an augmented matrix corresponding to the system and apply row operations until the matrix is in row-echelon form.

\[\left [\begin{array}{ccc|c} 1&2&-3&1\\-5&2&-3&1\\1&-2&1&1 \end{array}\right ] \begin{array}{c} \\ \xrightarrow {R_2+5R_1}\\ \xrightarrow {R_3-R_1}\\ \end{array} \left [\begin{array}{ccc|c} 1&2&-3&1\\0&12&-18&6\\0&-4&4&0 \end{array}\right ] \begin{array}{c} \\ \\ \xrightarrow {R_3+\frac {1}{3}R_2}\\ \end{array}\]
\begin{equation}\label {eq:ref1} \left [\begin{array}{ccc|c} 1&2&-3&1\\0&12&-18&6\\0&0&-2&2 \end{array}\right ] \end{equation}

Note that the elementary row operations that lead to (1) were not prescribed. We may employ row-operations in a different manner and obtain a different matrix in row-echelon form. For example, suppose for some reason we had begun by switching the first and third rows.

\[\left [\begin{array}{ccc|c} 1&2&-3&1\\-5&2&-3&1\\1&-2&1&1 \end{array}\right ] \begin{array}{c} \\ \xrightarrow {R_1\leftrightarrow R_3}\\ \\ \end{array} \left [\begin{array}{ccc|c} 1&-2&1&1\\-5&2&-3&1\\1&2&-3&1 \end{array}\right ] \begin{array}{c} \\ \\ \\ \end{array}\]

Next we would reduce this matrix to row-echelon form, perhaps in this way:

\[\left [\begin{array}{ccc|c} 1&-2&1&1\\-5&2&-3&1\\1&2&-3&1 \end{array}\right ] \begin{array}{c} \\ \xrightarrow {R_2+5R_1}\\ \xrightarrow {R_3-R_1}\\ \end{array} \left [\begin{array}{ccc|c} 1&-2&1&1\\0&-8&2&6\\0&4&-4&0 \end{array}\right ] \begin{array}{c} \\ \\ \xrightarrow {R_3+\frac {1}{2}R_2}\\ \end{array} \]
\begin{equation}\label {eq:ref2} \left [\begin{array}{ccc|c} 1&-2&1&1\\0&-8&2&6\\0&0&-3&3 \end{array}\right ] \end{equation}

The augmented matrices in (1) and (2) are clearly not the same, but both are in row-echelon form.

If we write the systems of equations corresponding to (1) and (2), we can employ back substitution to solve them. The matrix in (1) corresponds to

\[\begin{array}{ccccccccc} x &+ &2y&-&3z&= &1 \\ & &12y&-&18z&=&6\\ &&&&-2z&=&2 \end{array}\]

The matrix in (2) corresponds to

\[\begin{array}{ccccccccc} x &- &2y&+&z&= &1 \\ & &-8y&+&2z&=&6\\ &&&&-3z&=&3 \end{array}\]

Because both systems are equivalent to the original system, it is not surprising that back substitution yields the same solution for both systems.

\[x=0,\quad y=-1,\quad z=-1\]

It is clear from Exploration that a row-echelon form corresponding to a matrix is not unique. But what about the reduced row-echelon form?

In this problem we revisit the system
\[\begin{array}{ccccccccc} x &+ &2y&-&3z&= &1 \\ -5x& +&2y&-&3z&=&1\\ x&- &2y&+&z&=&1 \end{array}\]

Following the steps we took to get (1), but taking the process a little further, we get the reduced row-echelon form.

\[\left [\begin{array}{ccc|c} 1&2&-3&1\\-5&2&-3&1\\1&-2&1&1 \end{array}\right ] \begin{array}{c} \\ \xrightarrow {R_2+5R_1}\\ \xrightarrow {R_3-R_1}\\ \end{array} \left [\begin{array}{ccc|c} 1&2&-3&1\\0&12&-18&6\\0&-4&4&0 \end{array}\right ] \begin{array}{c} \\ \\ \xrightarrow {R_3+\frac {1}{3}R_2}\\ \end{array}\]
\[\left [\begin{array}{ccc|c} 1&2&-3&1\\0&12&-18&6\\0&0&-2&2 \end{array}\right ] \color {blue} \begin{array}{c} \\ \xrightarrow {\frac {1}{12}R_2}\\ \xrightarrow {-\frac {1}{2}R_3}\\ \end{array} \left [\begin{array}{ccc|c} 1&2&-3&1\\0&1&-\frac {3}{2}&\frac {1}{2}\\0&0&1&-1 \end{array}\right ] \begin{array}{c} \xrightarrow {R_1+3R_3}\\ \xrightarrow {R_2+\frac {3}{2}R_3}\\ \\ \end{array}\]
\begin{equation}\label {eq:rref3} \color {blue} \left [\begin{array}{ccc|c} 1&2&0&-2\\0&1&0&-1\\0&0&1&-1 \end{array}\right ] \begin{array}{c} \xrightarrow {R_1-2R_2}\\ \\ \\ \end{array} \color {black} \left [\begin{array}{ccc|c} 1&0&0&0\\0&1&0&-1\\0&0&1&-1 \end{array}\right ]\end{equation}
Do you think it is possible to start with (2) and obtain the same reduced row-echelon form? Try to justify your response. If possible, find the elementary row operations that take (2) to the reduced row-echelon form in (3).
\[\left [\begin{array}{ccc|c} 1&2&-3&1\\-5&2&-3&1\\1&-2&1&1 \end{array}\right ] \begin{array}{c} \\ \xrightarrow {R_1\leftrightarrow R_3}\\ \\ \end{array} \left [\begin{array}{ccc|c} 1&-2&1&1\\-5&2&-3&1\\1&2&-3&1 \end{array}\right ]\]
\[\begin{array}{c} \\ \xrightarrow {R_2+5R_1}\\ \xrightarrow {R_3-R_1}\\ \end{array} \left [\begin{array}{ccc|c} 1&-2&1&1\\0&-8&2&6\\0&4&-4&0 \end{array}\right ] \begin{array}{c} \\ \\ \xrightarrow {R_3+\frac {1}{2}R_2}\\ \end{array} \]
\begin{equation*} \left [\begin{array}{ccc|c} 1&-2&1&1\\0&-8&2&6\\0&0&-3&3 \end{array}\right ] \color {red} \begin{array}{c} \rightsquigarrow \text {Elementary}\rightsquigarrow \\ \text {Row Ops.} \end{array} \color {black} \left [\begin{array}{ccc|c} 1&0&0&0\\0&1&0&-1\\0&0&1&-1 \end{array}\right ] \end{equation*}
You will be asked to fill in the elementary row operations in Practice Problem ??.

Our observations in Exploration are summarized in the following diagram.

[Picture]

We observed that a row-echelon form associated with a matrix is not unique. In contrast, we also saw how different sequences of elementary row operations lead to the same solution set and the same reduced row-echelon form. It turns out that the reduced row-echelon form of a matrix is unique.

A proof of this result can be found in [Yuster].

The reduced row-echelon form of a matrix is an instance of a row-echelon form of the matrix. While a given matrix may have multiple row-echelon forms, all row-echelon forms will share one characteristic: the number of nonzero rows in a row-echelon form of the given matrix will be the same. We will prove this result in Theorem ?? .

Gaussian and Gauss-Jordan Elimination

As we saw in the previous section, it is possible to follow different sequences of row operations to arrive at various row-echelon forms. However, it was not clear whether it is always possible to find a row-echelon form. The following algorithm takes any matrix (or augmented matrix) and transforms it into row-echelon form:

Gaussian Algorithm guarantees that every matrix will have a row-echelon form.

Given a matrix in row-echelon form, it is easy to bring it the reduced row-echelon form. For example, continuing with Example 4, we can start where we left off and compute \(\mbox {rref}(A)\). From our earlier computations we have:

\[\begin{bmatrix}2&4\\-1&1\\3&5\\1&2\end{bmatrix}\rightsquigarrow \begin{bmatrix}2&4\\0&3\\0&0\\0&0\end{bmatrix}\]

Now we create leading \(1's\) and use them to to wipe out all non-zero entries above them.

\[\begin{bmatrix}2&4\\0&3\\0&0\\0&0\end{bmatrix} \begin{array}{c} \xrightarrow {(1/2)R_1}\\ \xrightarrow {(1/3)R_2}\\ \\ \\ \end{array} \begin{bmatrix}1&2\\0&1\\0&0\\0&0\end{bmatrix} \begin{array}{c} \xrightarrow {R_1-2R_2}\\ \\ \\ \\ \end{array} \begin{bmatrix}1&0\\0&1\\0&0\\0&0\end{bmatrix}=\mbox {rref}(A)\]

The following modification to the Gaussian Algorithm produces the reduced row-echelon form of a matrix. This algorithm guarantees the existence of the reduced row-echelon form.

The Gauss-Jordan Algorithm guarantees the existence of the reduced row-echelon form for all matrices. When doing computations by hand, however, the algorithm may not always be the optimal method of finding a row-echelon form or the reduced row-echelon form because the procedure often leads to fractions early in the process. The following video shows how to arrive at the same reduced row-echelon form for the matrix in Example 8 without doing any fraction arithmetic. You will see that we still employ row operations, but in a different order.

The video highlights the fact that regardless of what sequence of elementary row operations we take to arrive at the reduced row-echelon form, the end result is the same.

Rank

As stated in Theorem 1, the reduced row-echelon form of a matrix \(A\) is uniquely determined by \(A\). That is, no matter which series of row operations is used to transform \(A\) to its reduced row-echelon matrix, the result will always be the same matrix. In contrast, this is not true for row-echelon matrices: different sequences of row operations can transform the same matrix \(A\) to different row-echelon matrices. However, it is true that the number \(r\) of nonzero rows must be the same in each of these row-echelon matrices, as we will see in Theorem ??. Hence, the number \(r\) depends only on \(A\) and not on the way in which \(A\) is carried to row-echelon form.

The fact that the rank of the coefficient matrix is \(r\) means that there are exactly \(r\) leading variables in the coefficient matrix, and hence exactly \(n - r\) nonleading variables. The nonleading variables are called free variables. All free variables are assigned parameters, so the set of solutions involves exactly \(n - r\) parameters. Hence if \(r < n\), there is at least one parameter, and so infinitely many solutions. If \(r = n\), there are no parameters and the resulting solution is unique.

Theorem 14 shows that, for any system of linear equations, exactly three possibilities exist:

1.
Unique solution. This occurs when every variable is a leading variable.
2.
Infinitely many solutions. This occurs when the system is consistent and there is at least one nonleading variable, so at least one parameter is involved.
3.
No solution. This occurs when a row \(\left [\begin{array}{cccc|c} 0&0&\ldots &0&1 \end{array}\right ]\) appears in the row-echelon form. Such a row corresponds to an equation with no solutions. (See Example ??.)

Practice Problems

Follow the indicated steps of the Gauss-Jordan algorithm to transform the matrix to its reduced row-echelon form. Steps will unfold automatically as you enter correct answers.
\[\left [\begin{array}{ccc|c} 2&1&1&3\\-1&0&1&2\\1&1&-2&0 \end{array}\right ]\]

\(\frac {1}{2}R_1\rightarrow R_1\).

\[ \left [\begin{array}{ccc|c} \answer {1}&\answer {1/2}&\answer {1/2}&\answer {3/2}\\-1&0&1&2\\1&1&-2&0 \end{array}\right ]\]
\(R_1+R_2\rightarrow R_2\).
\[ \left [\begin{array}{ccc|c} 1&1/2&1/2&3/2\\\answer {0}&\answer {1/2}&\answer {3/2}&\answer {7/2}\\1&1&-2&0 \end{array}\right ]\]
\(R_3-R_1\rightarrow R_3\).
\[ \left [\begin{array}{ccc|c} 1&1/2&1/2&3/2\\0&1/2&3/2&7/2\\\answer {0}&\answer {1/2}&\answer {-5/2}&\answer {-3/2} \end{array}\right ]\]
\(2R_2\rightarrow R_2\).
\[ \left [\begin{array}{ccc|c} 1&1/2&1/2&3/2\\\answer {0}&\answer {1}&\answer {3}&\answer {7}\\0&1/2&-5/2&-3/2 \end{array}\right ]\]
\(R_3-\frac {1}{2}R_2\rightarrow R_3\).
\[ \left [\begin{array}{ccc|c} 1&1/2&1/2&3/2\\0&1&3&7\\\answer {0}&\answer {0}&\answer {-4}&\answer {-5} \end{array}\right ]\]
\(-\frac {1}{4}R_3\rightarrow R_3\).
\[\left [\begin{array}{ccc|c} 1&1/2&1/2&3/2\\0&1&3&7\\\answer {0}&\answer {0}&\answer {1}&\answer {5/4} \end{array}\right ]\]
\(R_2-3R_3\rightarrow R_2\).
\[ \left [\begin{array}{ccc|c} 1&1/2&1/2&3/2\\\answer {0}&\answer {1}&\answer {0}&\answer {13/4}\\0&0&1&5/4 \end{array}\right ]\]
\(R_1-\frac {1}{2}R_3\rightarrow R_1\).
\[ \left [\begin{array}{ccc|c} \answer {1}&\answer {1/2}&\answer {0}&\answer {7/8}\\0&1&0&13/4\\0&0&1&5/4 \end{array}\right ]\]
\(R_1-\frac {1}{2}R_2\rightarrow R_1\).
\[ \left [\begin{array}{ccc|c} \answer {1}&\answer {0}&\answer {0}&\answer {-3/4}\\0&1&0&13/4\\0&0&1&5/4 \end{array}\right ]\]
The following reduction steps do not follow the algorithm but are easier for a human to carry out because they use fewer fractions. Follow the indicated steps to transform the matrix to its reduced row-echelon form. Steps will unfold automatically as you enter correct answers.
\[\left [\begin{array}{ccc|c} 2&1&1&3\\-1&0&1&2\\1&1&-2&0 \end{array}\right ]\]

\(R_1+R_2\rightarrow R_1\).

\[\left [\begin{array}{ccc|c} \answer {1}&\answer {1}&\answer {2}&\answer {5}\\-1&0&1&2\\1&1&-2&0 \end{array}\right ]\]
\(R_2+R_3\rightarrow R_3\).
\[\left [\begin{array}{ccc|c} 1&1&2&5\\-1&0&1&2\\\answer {0}&\answer {1}&\answer {-1}&\answer {2} \end{array}\right ]\]
\(R_1+R_2\rightarrow R_1\).
\[\left [\begin{array}{ccc|c} \answer {0}&\answer {1}&\answer {3}&\answer {7}\\-1&0&1&2\\0&1&-1&2 \end{array}\right ]\]
\(R_1-R_3\rightarrow R_1\).
\[\left [\begin{array}{ccc|c} \answer {0}&\answer {0}&\answer {4}&\answer {5}\\-1&0&1&2\\0&1&-1&2 \end{array}\right ]\]
\(\frac {1}{4}R_1\rightarrow R_1\) and \(-R_2\rightarrow R_2\).
\[\left [\begin{array}{ccc|c} \answer {0}&\answer {0}&\answer {1}&\answer {5/4}\\\answer {1}&\answer {0}&\answer {-1}&\answer {-2}\\0&1&-1&2 \end{array}\right ]\]
\(R_1+R_2\rightarrow R_2\).
\[\left [\begin{array}{ccc|c} 0&0&1&5/4\\\answer {1}&\answer {0}&\answer {0}&\answer {-3/4}\\0&1&-1&2 \end{array}\right ]\]
\(R_1+R_3\rightarrow R_3\).
\[\left [\begin{array}{ccc|c} 0&0&1&5/4\\1&0&0&-3/4\\\answer {0}&\answer {1}&\answer {0}&\answer {13/4} \end{array}\right ]\]
Exchange rows. \(\left [\begin{array}{ccc|c} 1&0&0&\answer {-3/4}\\0&1&0&\answer {13/4}\\0&0&1&\answer {5/4} \end{array}\right ]\)
Find the rank \(A\).
\[A=\begin{bmatrix}4&3&-1\\-8&-6&2\end{bmatrix}\]
Answer:
\[\mbox {rank}(A)=\answer {1}\]
Find the rank \(B\).
\[B=\begin{bmatrix}1&1\\2&-2\\3&-1\end{bmatrix}\]
Answer:
\[\mbox {rank}(B)=\answer {2}\]
Find the rank \(C\).
\[C=\begin{bmatrix}1&0&1\\2&1&3\\0&1&-2\end{bmatrix}\]
Answer:
\[\mbox {rank}(C)=\answer {3}\]
Find the rank \(D\).
\[D=\begin{bmatrix}1&1&2\\-1&-2&1\\1&0&5\end{bmatrix}\]
Answer:
\[\mbox {rank}(D)=\answer {2}\]
Suppose \(A\) is a matrix with 5 rows and 7 columns. Which of the following is/are possible? Select ALL that apply.
\(\mbox {rank}(A)=7\) \(\mbox {rank}(A)=6\) \(\mbox {rank}(A)=5\) \(\mbox {rank}(A)=4\)
Suppose a linear system has \(4\) equations and \(5\) unknowns. Which of the following is NOT a possibility?
The system has a unique solution The system has no solutions The system has infinitely many solutions
Suppose \(A\) is a matrix such that \(\mbox {rref}(A)\) has \(5\) leading \(1's\). What do we know to be true about \(A\)? Select ALL that apply.
\(\mbox {rank}(A)=5\) \(A\) has at least \(25\) entries Any row-echelon form of \(A\) will have exactly \(5\) nonzero rows Some row-echelon forms of \(A\) may have more than \(5\) nonzero rows Some row-echelon forms of \(A\) may have fewer than \(5\) nonzero rows
In this problem we will consider how the rank of the coefficient matrix associated with a linear system compares to the rank of the augmented matrix associated with the system.
1.
Explain why the rank of the augmented matrix has to be greater than or equal to the rank of the coefficient matrix.
2.
Prove that for a consistent system the rank of the coefficient matrix will be the same as the rank of the augmented matrix.
3.
Give an example of an inconsistent system for which the rank of the augmented matrix is greater than the rank of the coefficient matrix.
4.
Can the rank of an augmented matrix be greater than the number of variables?
5.
Is the following statement true?

“If the rank of the augmented matrix associated with a linear system is greater than the rank of the coefficient matrix, then the system is inconsistent."

Text Source

The section on Rank is an adaptation of Section 1.2 of Keith Nicholson’s Linear Algebra with Applications.

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p 15-17.

Bibliography

[Yuster] Thomas Yuster, The Reduced Row Echelon Form of a Matrix is Unique: a Simple Proof, Mathematics Magazine, vol. 57, no. 2 (Mar. 1984), pp. 93-94.