In this explainer, we will learn how to identify the reduced row echelon form of a matrix and use Gauss–Jordan elimination to get it and hence solve a system of linear equations.
When working with a system of linear equations, the most common aim is to find the value(s) of the variable which solves these equations. It may be the case that a system of linear equations has a unique solution and it is also possible that there will be no solutions. The third possibility is that there are infinitely many solutions, where one or more variables are free to take any values.
When working with a system of linear equations, there are ways of simplifying how this is presented but without losing any of the information. For example, take the system of linear equations
Ordinarily, our aim would be to solve the system of equations to find the values of , , and . However, if we assign the coefficients of , , and to particular columns of a matrix, then it is clear how the above system of equations can be entirely encapsulated by the matrix providing we have specified that the first column corresponds to the variable , the second column to the variable , and the third column to the variable , with the fourth column corresponding to the numbers which appear on the right-hand side of the equations.
When solving a system of linear equations, the first step is normally to write out the matrix version of this system, as we have done above, which is called the “augmented coefficient matrix.” Then, row operations are used to maneuver the augmented coefficient matrix into a form which essentially represents the solution of this system. Before learning how to complete this process, it is necessary that we learn several foundational concepts in linear algebra, by which our ability to quickly solve systems of linear equations will be greatly improved.
Definition: Pivots of a Matrix
For a matrix of order , the “pivot” of each row is the first nonzero entry, reading left to right. This is also referred to as the “leading coefficient.”
For a matrix with order , there are rows and hence possible pivots. The identification of each pivot is the first step in being able to solve a system of linear equations using matrix methods. We will demonstrate with the example matrix
The pivot in the first row is the first nonzero entry, which is . The second row has zero entries in the first and second columns, with the first nonzero entry being in the third column and having a value of 1. The pivot of the final row is in the second column and has a value of 4. All of the pivots are highlighted below:
If a row has all zero entries then it has no pivot entry, which is a feature that becomes important in subsequent, related definitions that appear later in this explainer.
Example 1: Recognizing the Pivots of a Matrix
Give the sum of all the pivot entries in the following matrix:
The second row is a zero row and so has no entries which are pivots. All of the remaining pivot entries are highlighted below: The pivot entries are therefore , , , and . The sum of these is 7.
This apparently benign definition is simple to explain but is of a surprising importance. Bearing in mind our overarching aim of solving systems of linear equations, we see how the definition of a pivot feeds into the next definition and examples.
Definition: Echelon Form
A matrix is said to be in “echelon form” or “row echelon form” if the following two criteria are met:
- All zero rows are below all nonzero rows.
- The pivot of a nonzero row appears to the right of the pivot in all rows above it.
This is another seemingly inert and innocuous definition and, in reality, it is little more than a stepping stone towards the much more powerful definition that we will give later in this explainer. For the moment, let us take the following example, where we have already highlighted the pivots:
The third row is a zero row and contains no pivots. However, it is also above a nonzero row, which violates the first requirement for a matrix to be in echelon form. Suppose now that we switched the third and fourth rows of this matrix to give
The zero row is now at the bottom, meaning that the first criterion of echelon form is met. However, the pivot in the second row is not to the right of the pivot in the first row, meaning that this matrix is also not in echelon form. Had we also decided to switch the first and the second rows, we would get
Now the zero row is at the bottom of the matrix and the pivot in the second row is to the right of the pivot in the first row. Similarly, the pivot in the third row is to the right of the pivot in the second row. Therefore, this matrix is in echelon form.
Example 2: Recognizing the Echelon Form of a Matrix
State whether the following matrix is in echelon form:
In order for the matrix to be in echelon form, we first require that all zero rows are below all nonzero rows. However, there are no zero rows in this matrix and so we do not need to consider this condition.
The second criterion that must be met for the matrix to be in echelon form is that all pivots should appear to the right of all pivots in the rows above them. We highlight the pivot entries:
The pivot in the second row is directly below the pivot in the first row. Therefore, the pivot in the second row is not to the right of all pivots in the rows above and hence this matrix is not in echelon form.
One pleasing aspect of working with matrices is that we often have the luxury of switching rows or performing other operations in order to simplify or streamline our calculations. With practice, these types of operations become very natural and can be employed with a degree of instinct and intuition. The next example begins to practice this idea.
Example 3: Converting a Matrix to Echelon Form
Describe the row switches which are necessary to put the following matrix into echelon form:
We observe that the second row is a zero row. In order to appear in echelon form, this zero row must be below all nonzero rows. We therefore switch row 2 with row 4 to obtain the following matrix (with pivots now highlighted):
To meet the second criterion of a matrix being in echelon form, we require all pivots to appear to the right of any pivot entries in the rows above. The matrix above does not meet this condition, as the pivot in row 2 is to the left of the pivot in row 1. We therefore switch these two rows to obtain the matrix
Now the pivots all appear to the right of the pivots in the rows above. Given that the zero row is also at the bottom of the matrix, this is now in echelon form.
We are now ready to meet our final definition in this explainer, which is debatably one of the most well-used definitions in all of linear algebra. As with many concepts in mathematics, the new idea that we are about to introduce is completely dependent on having gained an understanding of several previous ideas.
Definition: Reduced Echelon Form
A matrix is in “reduced echelon form” or “row reduced echelon form” if it meets the following three criteria:
- The matrix is in echelon form.
- All pivots have a value of 1.
- The pivot entry is the only nonzero entry in the column it occupies.
Clearly a large part of this definition is dependent on our understanding of echelon form, as we described above. To help solidify the concept of reduced echelon form, we will give several example matrices, all of which are already in echelon form.
We define the matrix
This matrix is in echelon form, given that the only zero row is below all nonzero rows and that the pivots (highlighted below) are all to the right of any pivots in the row above:
Since the matrix is in echelon form, the first criterion of reduced echelon form is met. However, the second criterion of reduced echelon form is not met given that the pivots are not all equal to 1. If we had instead been given the matrix then the second criterion would have been met. Now working with this new matrix, we will investigate whether it satisfies the third condition of reduced echelon form. We highlight all other entries which appear in columns that contain pivot entries:
Clearly it is not the case that the third criterion is met, as the second column contains a nonzero entry in the first row and also the fifth column contains nonzero entries in the first and second rows. If we had instead been given the matrix then the third criterion would have been met and, consequently, the matrix is in reduced echelon form. As an aside, we observe that the third and fourth columns contain several nonzero entries. This does not contradict any of the criteria of reduced echelon form.
Example 4: Recognizing a Matrix in Reduced Echelon Form
Is the matrix in the reduced echelon form?
It is usually best to highlight the pivot entries in the matrix:
Clearly, the matrix is already in echelon form, which meets the first of the three criteria which are required for the matrix to be in reduced echelon form.
The second criterion is that all pivot entries have a value of 1, which we have shown in the highlighted entries above. The third criterion, however, is that all pivot entries should be the only nonzero entries in the column that they appear in. In the matrix we are considering, we can see that this is not the case, as the pivot in the second row has a nonzero element in the same column, as we have shown in orange:
Since the pivot in the second row is not the only nonzero entry in the column to which it belongs, the given matrix is not in row reduced echelon form.
In order for a matrix to be in reduced echelon form, we know that all pivot entries must be the only nonzero entries in their column. This implies that a matrix in reduced echelon form will have entries that are populated by many zeros. If a matrix does not contain many zeros, then it is unlikely that it will be in reduced echelon form although this is, of course, certainly not a guarantee!
Example 5: Recognizing Reduced Echelon Form
Is the matrix in the reduced echelon form?
The matrix is in echelon form because the only zero row is at the bottom and each pivot appears to the right of the pivots in the rows above it:
This matrix therefore meets the first criterion required to be in reduced echelon form.
All of the pivots have a value of 1, which meets the second criterion of reduced echelon form. Finally, if we highlight the remaining entries in the columns containing pivots, then we have
All of these entries have a value of zero and therefore the matrix meets the third and final condition for being in reduced echelon form.
The third criterion of the definition of reduced echelon form requires that all pivot entries are the only nonzero elements in their columns. Nonetheless, this certainly does not preclude the possibility that nonzero entries appear in other columns of the matrix and without violating the conditions on reduced echelon form. The following question is one such example of this.
Example 6: Reduced Echelon Form
Is the matrix in the reduced echelon form?
The matrix is in echelon form and hence it meets the first condition required for a matrix to be in reduced echelon form.
Next we highlight the pivot entries as shown:
All of the pivots have a value of 1, which meets the second criterion of reduced echelon form. Finally, we highlight all of the entries which appear in the same column as a pivot entry:
Clearly, every pivot is the only nonzero entry in the column that contains it. This implies that the given matrix meets the third and final required condition of being in reduced echelon form.
Note that the entry in the first row and second column is nonzero but it is not required to be zero by the three criteria of reduced echelon form. It is only the columns which contain pivot entries that need to be investigated and any other column can be ignored in this regard.
It will be worthwhile for any new student of linear algebra to become highly acquainted with the definitions of echelon form and row reduced echelon form. In addition to providing an indispensable tool kit for investigating the solutions to systems of linear equations, the understanding of echelon form is assumed when moving onto more abstract and high-level concepts such as the rank and nullity of a matrix. At first, these definitions can seem a little mysterious and slightly tricky to remember. It is not even obvious why the word “echelon” is used, although a quick internet search for “echelon form, cycling” should demystify this to some extent!
- The pivot of a row is the first nonzero entry in that row.
- For a matrix to be in echelon form, all zero rows must be below all nonzero rows and any pivot must appear to the right of any pivots in the rows above.
- For a matrix to be in reduced echelon form, it must already be in echelon form. If each pivot entry is 1 and is the only nonzero entry in its column, then the matrix is in reduced echelon form.
- Changing a matrix into reduced echelon form is essentially equivalent to solving a system of linear equations where the coefficients of each variable are translated into the augmented coefficient matrix. This result is usually achieved with Gauss–Jordan elimination, which is a topic for another explainer.