A matrix is said to be in row echelon form when all its non-zero rows have a pivot, that is, a non-zero entry such that all the entries to its left and below it are equal to zero.
When the coefficient matrix of a linear system is in row echelon form, it is very easy to compute the solution of the system by using an algorithm called back-substitution.
We start by defining pivots.
Definition Let be a matrix. Let be an element of . We say that is a pivot if and only if and whenever both and (and ).
In other words, an element of a matrix is a pivot if it is non-zero and all the entries to its left and below it are equal to zero.
Example DefineThe pivots of are the underlined elements , , .
Example DefineThe pivots of are , , .
Example DefineThe only pivot of is .
Example DefineThe only pivot of is . Note that is not a pivot because
We are now ready to provide a definition of row echelon form.
Definition Let be a matrix. We say that is in row echelon form if and only if all its non-zero rows contain a pivot and all its zero rows are located below the non-zero rows.
In the definition above, a zero row is a row whose entries are all equal to zero, and a non-zero row is a row that has at least one element different from zero.
Example The matrixis in row echelon form. It has one zero row (the third), which is below the non-zero rows. Both the first and the second row have a pivot ( and , respectively).
Example The matrixis not in row echelon form because its first row is non-zero and has no pivots.
Example The matrixis in row echelon form. It has two zero rows (the third and fourth), which are below the non-zero rows. Both the first and the second row have a pivot ( and , respectively).
Example The matrixis not in row echelon form because it has a non-zero row (the third) below a zero row (the second).
Given a matrix in row echelon form, we say that:
a column of is basic if it contains a pivot;
a column of is non-basic if it does not contain a pivot.
Example DefineThen the first and third column are basic and the second column is non-basic.
A linear system is said to be in row echelon form if the matrix of coefficients is in row echelon form.
The product can be seen as a linear combination of the columns of with coefficients taken from the vector of unknowns :
The unknowns that correspond to (i.e., are the coefficients of) basic columns are called basic variables. Those that correspond to non-basic columns are called non-basic variables.
Example Consider a linear system in row echelon form whereandThen, and are basic variables, and and are non-basic variables.
A useful result about basic and non-basic variables follows.
Proposition If is a pivot of a system in row echelon form, then can be basic variables only if they correspond to pivots located in rows below the -th.
The proof is by contradiction. Suppose that () is a basic variable corresponding to a pivot located in row (with ). By the definition of pivot, all entries of located below and to the left of must be zero. Therefore, must be zero, which contradicts the hypothesis that is a pivot.
Example Consider the systemwhose coefficient matrixThe pivot on the second row () is associated to the basic variable . As a consequence can be a basic variable only if it corresponds to a pivot located on a lower row. But there are no lower rows, so cannot be a basic variable. You might be thinking: "that was obvious, there are no pivots on the third column, so that column is non-basic". This is true, nonetheless it can be helpful in some situations to determine whether a variable is basic or not without looking at all the values in its column.
We can easily assess whether a system in row echelon form has a solution.
Proposition If there is a zero row such that , then the system has no solution. If there are no such rows, then the system has at least one solution.
Clearly, if there is no that can solve the -th equation of the systemif . If such a situation does not arise, then we can use the back-substitution algorithm (explained below) to constructively find a solution.
Example Define a systemwhereThe system has no solution because the second row is zero, but .
Suppose there are basic variables.
The back-substitution algorithm is as follows:
choose values arbitrarily for the non-basic variables;
for , if the -th row is non-zero and is the basic variable corresponding to the pivot of the -th row, set
In other words, we go backwards from the last to the first row. Each time we encounter a row containing a pivot, we solve for the unknown variable corresponding to that pivot. The solution (i.e., the value for computed on the right-hand side of equation 1 depends only on non-basic variables (fixed arbitrarily in advance) and on variables whose values have already been found by solving previous rows.
A proof of the fact that the back-substitution algorithm yields a solution follows.
We first need to prove that all the numbers on the right-hand side of equation 1 are known. The coefficients and are given. Back-substitution starts from the lowermost non-zero row. There are no pivots below that row. Therefore, by the results shown above about basic and non-basic variables, none of can be basic. Since they are non-basic, their values have already been chosen arbitrarily. Therefore, when we are on the lowermost non-zero row, all the quantities on the right-hand side of equation 1 are known. When we move upwards to the other rows, if one of the values is basic, it corresponds to a pivot located in lower rows and it has already been computed. Therefore are known. We now show that is a solution. We need to prove that the vector satisfies all the equations in the system. The equations corresponding to zero rows are always satisfied because for any . So, we need to check only the equations corresponding to non-zero rows. Since the system is in row echelon form, each non-zero row has a pivot. Take any one of these rows (the -th). The corresponding equation isIf is the basic variable corresponding to the pivot of the -th row, then the pivot is . By the definition of pivot, if . Therefore, the equation becomesorSince is a pivot, it is non-zero. So, we can divide both sides of the equation by and we obtain equation 1.
We now provide some examples to show how the back-substitution algorithm works in practice.
Example Let us solve the system of three equations in three unknowns The matrix of coefficients and the vector of constant arewhich is in row echelon form. So, we can use the back substitution algorithm. All columns contain a pivot, so that there are only basic variables (there is not any non-basic variable). We start from the last row and solve for the basic variable corresponding to its pivot: Then, we move to the second row and again we solve for the basic variable corresponding to its pivot:And again for the first row:Thus, the solution we have found is
Example Let us solve the system of two equations in three unknowns The matrix of coefficients and the vector of constant areThe back substitution algorithm can be used because is in row echelon form. All rows are non-zero. The variable and are basic because their columns contain a pivot. On the contrary, the third column does not contain a pivot, so is non-basic and its value can be chosen arbitrarily. We chooseWe start from the last row and solve for the basic variable corresponding to its pivot: Then, we do the same for the first row:Thus, the solution we have found is
Since systems in row echelon form are easily solved by back-substitution, we often try to transform a system we need to solve into an equivalent one in row echelon form.
The most important algorithm used to do so is called Gaussian elimination: it consists in a sequence of elementary row operations that transform the system into an equivalent system whose coefficient matrix is in row echelon form.
Below you can find some exercises with explained solutions.
Determine whether the matrixis in row echelon form.
Let us first underline the pivots:The second row is non-zero but it does not contain a pivot. Therefore, is not in row echelon form.
Use the back-substitution algorithm to solve the systemwhere
In case you find non-basic variables, set them equal to .
Let us underline the pivots:The third column does not contain a pivot, so is non-basic. We chooseThe fourth row is zero, so we skip it and start from the third row. The basic variable corresponding to its pivot is . Its value is found as follows:We then move to the second row:and to the first:Thus the solution is
Most of the learning materials found on this website are now available in a traditional textbook format.