Search for probability and statistics terms on Statlect
StatLect

Reduced row echelon form

by , PhD

A matrix is said to be in reduced row echelon form when it is in row echelon form and its basic columns are vectors of the standard basis (i.e., vectors having one entry equal to 1 and all the other entries equal to 0).

When the coefficient matrix of a linear system is in reduced row echelon form, it is straightforward to derive the solutions of the system from the coefficient matrix and the vector of constants.

Table of Contents

Prerequisites

In order to understand this lecture, you should first read the lecture on the Row echelon form.

In particular, remember that a matrix is in row echelon form if and only if:

When a column of a matrix in row echelon form contains a pivot, it is called a basic column. When it does not contain a pivot, we say that it is a non-basic column.

Example Define[eq1]The matrix A is in row echelon form. Its pivots are the underlined entries $A_{11}$, $A_{22}$, $A_{33}$. All the columns of A are basic. There is not any non-basic column.

Example The matrix[eq2]is in row echelon form. Its pivots are $A_{11}$ and $A_{23}$. The first and third column are basic, the second is non-basic.

Definition of reduced row echelon form

A precise definition of reduced row echelon form follows.

Definition We say that a matrix is in reduced row echelon form if and only if it is in row echelon form, all its pivots are equal to 1 and the pivots are the only non-zero entries of the basic columns.

We show some matrices in reduced row echelon form in the following examples.

Example The matrix[eq3]is in reduced row echelon form. It has one zero row (the third), which is below the non-zero rows. The first and the second row are non-zero, but have a pivot ($A_{11}$ and $A_{23}$, respectively). The two pivots are equal to $1 $ and they are the only non-zero entries in their respective columns.

Example The matrix[eq4]is in row echelon form because both of its rows have a pivot. However, it is not in reduced row echelon form because there is a non-zero entry in the column of the pivot $A_{23}$.

Example The matrix[eq5]is in reduced row echelon form. Its zero rows are below the non-zero rows. The first and the second row are non-zero, but have a pivot ($A_{11}$ and $A_{22}$, respectively). The pivots are equal to 1 and they are the only non-zero entries in their respective columns.

Example The identity matrix[eq6]is in reduced row echelon form.

How to solve a system in reduced echelon form

Consider a linear system [eq7]where A is a $K	imes L$ matrix of coefficients, x is an $L	imes 1$ vector of unknowns, and $b$ is a Kx1 vector of constants.

The system is said to be in reduced row echelon form if the matrix A is in reduced row echelon form.

As explained in the lecture on Matrix multiplication and linear combinations, the product $Ax$ can be written as a linear combination of the columns of A: [eq8]where the coefficients of the combination are the unknowns [eq9].

If an unknown multiplies a basic column, it is called a basic variable. Otherwise, if it corresponds to a non-basic column, it is called a non-basic variable.

Example Define a system whose matrix of coefficients[eq10]is in reduced row echelon form, and[eq11]Then, $x_{1}$ is non-basic and $x_{2}$ and $x_{3}$ are basic.

Since the reduced echelon form is a special case of the echelon form, the conditions for the existence of a solution of a system in the latter form apply, and we can use the back-substitution algorithm to solve the system.

Remember how the back-substitution algorithm works:

  1. if there are $B$ basic columns, we choose $L-B$ values arbitrarily for the non-basic variables (i.e., for the unknowns corresponding to the non-basic columns);

  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, we set[eq12]

If A is in reduced row echelon form, then $A_{kl}=1$, so that equation 1 becomes[eq13]Furthermore, the coefficients $A_{kj}$ in equation 2 are equal to 0 when $j $ is the index of a basic column.

Example Consider a system in reduced row echelon form with augmented matrix[eq14]Since the third column is non basic, $x_{3}$ is a non-basic variable and we can choose it arbitrarily. We choose[eq15]We skip the third row because it is zero. On the second row, we have[eq16]and on the first one we have[eq17]

How to transform a system to reduced row echelon form

The standard algorithm used to transform a system into an equivalent system in reduced row echelon form is called Gauss Jordan elimination.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

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

Solution

Let us first underline the pivots:[eq19]Each non-zero row has a pivot. Furthermore, there is a zero row, but it is below the non-zero rows. Therefore A is in echelon form. It is not in reduced form because the third column is basic but it contains a non-zero element that is not a pivot.

Exercise 2

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

Solution

Let us first underline the pivots:[eq21]Each non-zero row has a pivot. Moreover, the only zero row (the fourth) is preceded by the non-zero rows. Therefore A is in echelon form. It is also in reduced form because all the pivots are equal to 1 and the non-pivotal elements in the basic columns are all equal to 0.

How to cite

Please cite as:

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

The books

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