Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Row echelon form

by , PhD

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.

Table of Contents

Pivot

We start by defining pivots.

Definition Let A be a $K imes L$ matrix. Let $A_{kl}$ be an element of A. We say that $A_{kl}$ is a pivot if and only if [eq1]and[eq2] whenever both $igeq k$ and $jleq l$ (and [eq3]).

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 Define[eq4]The pivots of A are the underlined elements $A_{11}$, $A_{22}$, $A_{33}$.

Example Define[eq5]The pivots of A are $A_{11}$, $A_{23}$, $A_{34}$.

Example Define[eq6]The only pivot of A is $A_{12}$.

Example Define[eq7]The only pivot of A is $A_{21}$. Note that $A_{12}$ is not a pivot because [eq8]

Definition of row echelon form

We are now ready to provide a definition of row echelon form.

Definition Let A be a $K imes L$ matrix. We say that A 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 matrix[eq9]is 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 ($A_{11}$ and $A_{23}$, respectively).

Example The matrix[eq10]is not in row echelon form because its first row is non-zero and has no pivots.

Example The matrix[eq11]is 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 ($A_{11}$ and $A_{22}$, respectively).

Example The matrix[eq12]is not in row echelon form because it has a non-zero row (the third) below a zero row (the second).

Basic and non-basic columns

Given a matrix A in row echelon form, we say that:

Example Define[eq13]Then the first and third column are basic and the second column is non-basic.

How to solve a system in row echelon form

A linear system [eq14]is said to be in row echelon form if the matrix of coefficients A is in row echelon form.

Basic and non-basic variables

The product $Ax$ can be seen as a linear combination of the columns of A with coefficients taken from the vector of unknowns x:[eq15]

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 where[eq16]and[eq17]Then, $x_{2}$ and $x_{3}$ are basic variables, and $x_{1}$ and $x_{4}$ are non-basic variables.

A useful result about basic and non-basic variables follows.

Proposition If $A_{kl}$ is a pivot of a system in row echelon form, then [eq18] can be basic variables only if they correspond to pivots located in rows below the k-th.

Proof

The proof is by contradiction. Suppose that $x_{l+j}$ ($j>0$) is a basic variable corresponding to a pivot $A_{k-i,l+j}$ located in row $k-i$ (with $i>0$). By the definition of pivot, all entries of A located below and to the left of $A_{k-i,l+j}$ must be zero. Therefore, $A_{kl}$ must be zero, which contradicts the hypothesis that $A_{kl}$ is a pivot.

Example Consider the system[eq19]whose coefficient matrix[eq20]The pivot on the second row ($A_{22}=-1$) is associated to the basic variable $x_{2}$. As a consequence $x_{3}$ can be a basic variable only if it corresponds to a pivot located on a lower row. But there are no lower rows, so $x_{3}$ 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.

Existence of solutions

We can easily assess whether a system in row echelon form has a solution.

Proposition If there is a zero row $A_{jullet }$ such that $b_{j} eq 0$, then the system has no solution. If there are no such rows, then the system has at least one solution.

Proof

Clearly, if [eq21]there is no x that can solve the $j$-th equation of the system[eq22]if $b_{j} eq 0$. 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 system[eq14]where[eq24]The system has no solution because the second row is zero, but $b_{2} eq 0$.

The back-substitution algorithm

Suppose there are $Bleq L$ basic variables.

The back-substitution algorithm is as follows:

  1. choose $L-B$ values arbitrarily for the non-basic variables;

  2. for $k=K,ldots ,1$, if the k-th row is non-zero and $x_{l}$ is the basic variable corresponding to the pivot of the k-th row, set[eq25]

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 $x_{l}$ 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.

Proof

We first need to prove that all the numbers on the right-hand side of equation 1 are known. The coefficients $A_{kj}$ and $b_{k}$ 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 [eq26] 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 [eq27] is basic, it corresponds to a pivot located in lower rows and it has already been computed. Therefore [eq27] are known. We now show that x 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 [eq29] for any x. 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 k-th). The corresponding equation is[eq30]If $x_{l}$ is the basic variable corresponding to the pivot of the k-th row, then the pivot is $A_{kl}$. By the definition of pivot, $A_{kj}=0$ if $j<l$. Therefore, the equation becomes[eq31]or[eq32]Since $A_{kl}$ is a pivot, it is non-zero. So, we can divide both sides of the equation by $A_{kl}$ 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 [eq33]The matrix of coefficients and the vector of constants are[eq34]which 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: [eq35]Then, we move to the second row and again we solve for the basic variable corresponding to its pivot:[eq36]And again for the first row:[eq37]Thus, the solution we have found is[eq38]

Example Let us solve the system of two equations in three unknowns [eq39]The matrix of coefficients and the vector of constant are[eq40]The back substitution algorithm can be used because A is in row echelon form. All rows are non-zero. The variables $x_{1}$ and $x_{2}$ are basic because their columns contain a pivot. On the contrary, the third column does not contain a pivot, so $x_{3}$ is non-basic and its value can be chosen arbitrarily. We choose[eq41]We start from the last row and solve for the basic variable corresponding to its pivot: [eq42]Then, we do the same for the first row:[eq43]Thus, the solution we have found is[eq44]

How to transform a system to row echelon form

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.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Determine whether the matrix[eq45]is in row echelon form.

Solution

Let us first underline the pivots:[eq46]The second row is non-zero but it does not contain a pivot. Therefore, A is not in row echelon form.

Exercise 2

Use the back-substitution algorithm to solve the system[eq14]where[eq48]

In case you find non-basic variables, set them equal to 0.

Solution

Let us underline the pivots:[eq49]The third column does not contain a pivot, so $x_{3}$ is non-basic. We choose[eq50]The fourth row is zero, so we skip it and start from the third row. The basic variable corresponding to its pivot is $x_{4}$. Its value is found as follows:[eq51]We then move to the second row:[eq52]and to the first:[eq53]Thus the solution is[eq54]

How to cite

Please cite as:

Taboga, Marco (2021). "Row echelon form", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/row-echelon-form.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.