Row echelon form

Systems of linear equations occur everywhere: not only in math itself, but also in physics, chemistry and economics! There are different ways of solving them, but the most general way is based on matrices. In this way of solving, the main stage in the solution process is the reduction of the matrix to an echelon form (also called row echelon form). Let's see how to do this reduction.

Echelon matrix

First, let's define the echelon matrix. It is a matrix that has three properties:

1. If any column contains the leading entry (first non-zero in the row), then below it can be only zero elements.

2. The leading entry of the row above the current one must be to the left of the leading entry of the current row.

3. All rows that contain only zeros must be below all other rows.

Below are matrices reduced to the echelon form:$\begin{pmatrix} 1 & 0 & 2 & 6 & 1\\ 0 & 2 & 5 & 9 & 0\\ 0 & 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 & 1\\ \end{pmatrix}\begin{pmatrix} 9 & 0 & 6 & 1\\ 0 & 1 & -8 & 4\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ \end{pmatrix} \\ \begin{pmatrix} 1 & 0 & 2 & 6 & 1\\ 0 & 0 & 0 & 3 & -1\\ 0 & 0 & 0 & 0 & 0\\ \end{pmatrix}\qquad\begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ \end{pmatrix}$

Elementary row and column operations

Before learning how to reduce a matrix to an echelon form, you have to focus on elementary row and column operations, since they're the core of this process. After applying one of these operations, you'll get a matrix equivalent to the original one. Why is it so? It's connected with solving systems of linear equations using Gaussian elimination. It is better explored in the corresponding topic. Now, let's just focus on the types of these operations.

There are three types of elementary row and column operations:

1. Interchange of any two rows or columns

2. Multiplication of any row or column by a non-zero number

3. Multiplication of any row or column by a non-zero number and adding to another row or column

If these operations are performed on rows, they are called elementary row operations. If they are performed on columns, they are called elementary column operations.

Here's a picture that illustrates all elementary row operations:

Reducing a matrix to echelon form: the algorithm

And now you're ready to learn how to reduce a matrix to the echelon form. Suppose you have a matrix $A = \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \\\end{array} \right)$Here's the algorithm of reduction to echelon form:

1. Find a non-zero element in the first column. This element is called a pivot, and the row containing it is called the pivot row. If the row with the pivot is not the first row, interchange it with the first row. Otherwise, don't change anything. If you were unable to find a non-zero element of the first column, just leave it untouched and move on to the second column

2. For every row $i$ except the first, do the following: multiply the first row by $-(a_{i1}/a_{11})$ and add the result to the $i$-th row. Now all the elements in the first column, but not in the first row, have become zero. You'll get a matrix of the form:$\left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ 0 & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \cdots & \vdots \\ 0 & a_{m2} & \ldots & a_{mn} \\\end{array} \right)$

3. Leave the pivot row and column untouched and move on to the second, third, etc. column and do the same thing as described in $1-2$. Every time, you'll work with a smaller matrix $A'$ from the bottom-right corner. For the second column, it will be$A' = \left( \begin{array}{ccc} a_{22} & \ldots & a_{2n} \\ \vdots & \cdots & \vdots \\ a_{m2} & \ldots & a_{mn} \\\end{array} \right)$

Example

Assume you have a matrix:$\begin{pmatrix} 2 & 0 & -1\\ -1 & 1 & 0\\ 2 & 2 & 1\\ \end{pmatrix}$

The first element of the first row is $2$, so it is a pivot. Now you have to add multipliers of the first row to the second and the third row in order to make all other elements in the first column equal to $0$. How can you do it? As you know, $2\cdot \frac{1}{2}=1$ and $-1+1=0$. So, let's multiply the first row by $\frac{1}{2}$ and add to the second one. You can do it, because $\frac{1}{2}\neq0$. You'll get the following matrix $\begin{pmatrix} 2 & 0 & -1\\ \textcolor{blue} {-1+1} & \textcolor{blue}{1+0} & \textcolor{blue} {0-\frac{1}{2}}\\ 2 & 2 & 1\\ \end{pmatrix}=\begin{pmatrix} 2 & 0 & -1\\ \textcolor{blue} 0 & \textcolor{blue}1 & \textcolor{blue} {-\frac{1}{2}}\\ 2 & 2 & 1\\ \end{pmatrix}$As you know, $2-2=0$, so let's multiply the first row by $-1$ and add it to the third row. You also can do it, because $-1\neq0$. You'll get the following matrix:$\begin{pmatrix} 2 & 0 & -1\\ 0 & 1 & -\frac{1}{2}\\ \textcolor{blue}{2-2} & \textcolor{blue}{2-0} & \textcolor{blue}{1+1}\\ \end{pmatrix}=\begin{pmatrix} 2 & 0 & -1\\ 0 & 1 & -\frac{1}{2}\\ \textcolor{blue}0 & \textcolor{blue}2 & \textcolor{blue}2\\ \end{pmatrix}$

According to our algorithm, you should move on to the second column. Here, add a multiplier of the second row to the third one to make the second element of the third row equal to $0$. You should also apply the fact that $2-2=0$. So, let's multiply the second row by $-2$ and add it to the third row:$\begin{pmatrix} 2 & 0 & -1\\ 0 & 1 & -\frac{1}{2}\\ \textcolor{blue}0 & \textcolor{blue}{2-2} &\textcolor{blue} {2+1}\\ \end{pmatrix}=\begin{pmatrix} 2 & 0 & -1\\ 0 & 1 & -\frac{1}{2}\\ \textcolor{blue}0 & \textcolor{blue}0 &\textcolor{blue} 3\\ \end{pmatrix}$

The matrix is now in echelon form.

Reduced echelon form

A matrix is in reduced echelon form if it satisfies one extra condition: each leading entry of non-zero rows is $1$, and it is the only non-zero element in its column. For instance, these matrices are in reduced echelon form:$\begin{pmatrix} 1 & 0 & 5 & 0\\ 0 & 1 & -2 & 0\\ 0 & 0 & 0 & 1\\ \end{pmatrix}\qquad\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0\\\end{pmatrix}$

As you can see, in each matrix, there's a row with only one element, and this is why such a form of a matrix is the desired result when you solve a system of linear equations. Since only one element is present, it means that the only variable is left, and it's easy to find it. You'll learn more about this process in the next topic on Gaussian elimination.

If you have a matrix reduced to an echelon form, you can easily reduce it to the reduced echelon form.Just multiply all rows by the inverse of their pivots and perform some more elementary operations to make all non-pivot elements of columns equal to $0$. Coming back to the matrix from the previous paragraph, you have $\begin{pmatrix} 2 & 0 & -1\\ 0 & 1 & -\frac{1}{2}\\ 0 & 0 &3\\ \end{pmatrix}$

You have to multiply the first row by $\frac{1}{2}$ and the third one by $\frac{1}{3}$, so you'll get:$\begin{pmatrix} \textcolor{blue}{\frac{1}{2}\cdot2} & \textcolor{blue}{\frac{1}{2}\cdot0} &\textcolor{blue} {\frac{1}{2}\cdot(-1)}\\ 0 & 1 & -\frac{1}{2}\\ \textcolor{red} 0 & \textcolor{red}0 &\textcolor{red}{\frac{1}{3}\cdot1}\\ \end{pmatrix}=\begin{pmatrix} \textcolor{blue}1 & \textcolor{blue}0 &\textcolor{blue} {-\frac{1}{2}}\\ 0 & 1 & -\frac{1}{2}\\ \textcolor{red} 0 & \textcolor{red}0 &\textcolor{red}1\\ \end{pmatrix}$

And now, you have to do something with the last element of the first and the second column. You'll make them equal to $0$, if you just multiply the third row by $\frac{1}{2}$ and add it to them:

$\begin{pmatrix}1 & 0 &\textcolor{blue}{-\frac{1}{2}+\frac{1}{2}}\\ 0 & 1 & \textcolor{blue}{-\frac{1}{2}+\frac{1}{2}}\\ 0 & 0 &1\\ \end{pmatrix}=\begin{pmatrix}1 & 0 &\textcolor{blue}{0}\\ 0 & 1 & \textcolor{blue}{0}\\ 0 & 0 &1\\ \end{pmatrix}$

Conclusion

Let's sum up all the most important facts you've learned so far:

• An echelon matrix has three properties:

  1. If any column contains the leading entry (first non-zero in the row), then below it can be only zero elements.

  2. The leading entry of the row above the current one must be to the left of the leading entry of the current row.

  3. All rows that contain only zeros must be below all other rows.

• There are three elementary row and column operations:

  1. Interchange of any two rows or columns

  2. Multiplication of any row or column by a non-zero number

  3. Multiplication of any row or column by a non-zero number and adding to another row or column

• The algorithm of reduction of a matrix to a row echelon form is based on elementary row and column operations

• There's also a reduced echelon form of a matrix, where each leading entry of non-zero rows is $1$, and it is the only non-zero element in its column