Echelon form and reduced row echelon form

Systems of linear equations: System of linear equations and matrices

Echelon form and reduced row echelon form

In the examples of elimination of variables in augmented matrices which were discussed before, the following concepts play such an important role that we give them with a name.

Echelon form By the leading element of a row in a matrix, we mean the first element of the row (from the left) that is distinct from zero.

A matrix is in echelon form if it has the following two properties:

all elements in the rows below a leading element, in the column in which this leading element resides as well as in the columns to the left of it, are zero;
null rows, also called zero rows (rows all of whose elements are zero), only appear below all other rows.

In other words A matrix in echelon form has a staircase form: the null rows are at the bottom, and the leading element of each row is strictly on the right-hand side of the leading element of the rows above it.

Example

What are the positions in the row of the leading elements of the following #(5\times 2)# matrix?

\[\matrix{3 & 2 \\ 0 & -1 \\ 0 & 0 \\ 0 & 4 \\ -5 & 0 \\ }\]

The leading element of row 1 is at position 1.

The leading element of row 2 is at position 2.

The leading element of row 3 does not exist.

The leading element of row 4 is at position 2.

The leading element of row 5 is at position 1.

New example

The leading elements of a matrix in echelon form correspond to unknowns of the associated system of equations that can be written as a linear combination of unknowns with a higher index. If we can apply row reduction to bring a matrix in echelon form, we will have made a step forward towards the solution of a system of linear equations.

Some examples The following three matrices are in echelon form; check that the conditions are satisfied.\[\left(\begin{array}{ccccc}2&3&0\\0&1&1\\\end{array}\right), \left(\begin{array}{ccccc}6 & -1 & 4\\ 0 & 0 & 1\\0 & 0 & 0\\\end{array}\right)\text{ en }\left(\begin{array}{ccccc} 4 & 4\\ 0 & 1\\\end{array}\right)\] The following matrix is not in echelon form, why not?\[\left(\begin{array}{ccccc}5 & 3 & 3\\ 2 & 3 & 1 \\ 0&0&0\\\end{array}\right)\]

As we will see later on, we can use elementary row operations to transform a matrix into echelon form. But we can go further, until the reduced echelon form defined below.

Reduced echelon form A matrix is in reduced row echelon form, or reduced echelon form, if it has the following three properties:

the matrix is in echelon form;
its leading elements are all equal to #1#;
all elements above a leading element are equal to zero.

A reduced echelon form is recognized by the following properties:

In each row the first element from the left that is not equal to #0# (the leading element), equals #1#; all other elements of the column containing this leading element are zero.
Each row that does not consist of zeros only (a non-null row) starts with more zeros than the previous row. In particular all null rows (rows with only zeros) appear at the bottom.

The matrix \[\left(\begin{array}{ccccc}1 & -1 & -2\\ 0 & 1 & 3\\\end{array}\right)\] is in echelon form, but not in reduced echelon form: the matrix satisfies the first two requirements of the reduced echelon form (the matrix is in echelon form, and all the leading elements are equal to #1#), but not the last condition "all elements above a leading element are equal to zero". After all, in the second column above the leading element #1# of the second row the number #-1#, which is not equal to zero, appears.

Examples The following matrices are in reduced echelon form (check this!). \[\left(\begin{array}{ccccc}1&0&0\\0&1&0\\0&0&1\end{array}\right), \left(\begin{array}{ccccc}1&-2&0\\0&0&1\\0&0&0\end{array}\right)\text{ en }\left(\begin{array}{ccccc}1&4&0&3&0\\0&0&1&2&0\\0&0&0&0&1\end{array}\right)\]

By elementary operations with rows we can always convert a matrix to reduced echelon form. How that will we discuss in the next section work exactly.

Determine the reduced row echelon form of the matrix \[\matrix{1 &5 & 0 &-4 \\
-1 &-21 &-8 &28 \\
-1 &-9 &-18 &26 \\}\] You can enter an intermediate result to check whether you're still on the right track.

Rijgereduceerde stepped form = \(
\matrix{
1 &0 &0 &1\\
0 &1 &0 &-1 \\
0 &0 &1 &-1 \\ }\)

Below is a row reduction of the matrix in smallsteps to this result.
\[\begin{aligned} \matrix{1&5&0&-4\\-1&-21&-8&28\\-1&-9&-18&26\\}&\sim\matrix{1&5&0&-4\\0&-16&-8&24\\-1&-9&-18&26\\}&{\blue{\begin{array}{c}\phantom{x}\\R_2+R_1\\\phantom{x}\end{array}}}\\\\ &\sim\matrix{1&5&0&-4\\0&-16&-8&24\\0&-4&-18&22\\}&{\blue{\begin{array}{c}\phantom{x}\\\phantom{x}\\R_3+R_1\end{array}}}\\\\ &\sim\matrix{1&5&0&-4\\0&1&{{1}\over{2}}&-{{3}\over{2}}\\0&-4&-18&22\\}&{\blue{\begin{array}{c}\phantom{x}\\-{{1}\over{16}}R_2\\\phantom{x}\end{array}}}\\\\ &\sim\matrix{1&0&-{{5}\over{2}}&{{7}\over{2}}\\0&1&{{1}\over{2}}&-{{3}\over{2}}\\0&-4&-18&22\\}&{\blue{\begin{array}{c}R_1-5R_2\\\phantom{x}\\\phantom{x}\end{array}}}\\\\ &\sim\matrix{1&0&-{{5}\over{2}}&{{7}\over{2}}\\0&1&{{1}\over{2}}&-{{3}\over{2}}\\0&0&-16&16\\}&{\blue{\begin{array}{c}\phantom{x}\\\phantom{x}\\R_3+4R_2\end{array}}}\\\\ &\sim\matrix{1&0&-{{5}\over{2}}&{{7}\over{2}}\\0&1&{{1}\over{2}}&-{{3}\over{2}}\\0&0&1&-1\\}&{\blue{\begin{array}{c}\phantom{x}\\\phantom{x}\\-{{1}\over{16}}R_3\end{array}}}\\\\ &\sim\matrix{1&0&0&1\\0&1&{{1}\over{2}}&-{{3}\over{2}}\\0&0&1&-1\\}&{\blue{\begin{array}{c}R_1+{{5}\over{2}}R_3\\\phantom{x}\\\phantom{x}\end{array}}}\\\\ &\sim\matrix{1&0&0&1\\0&1&0&-1\\0&0&1&-1\\}&{\blue{\begin{array}{c}\phantom{x}\\R_2-{{1}\over{2}}R_3\\\phantom{x}\end{array}}} \end{aligned}\]

You can of course also combine steps. The scheme below illustrates this, and the part of the matrix that we have already processed is coloured green.
\[
\begin{array}{rcll}
\left(
\begin{array}{cccc}
1 &5 & 0 &-4 \\
-1 &-21 &-8 &28 \\
-1 &-9 &-18 &26 \\
\end{array}
\right)
&\sim& \left( \begin{array}{cccc} \color{green}{1} & 5 & 0 & -4 \\ \color{green}{0} & -16 & -8 & 24 \\ \color{green}{0} & -4 & -18 & 22 \\ \end{array} \right) &\blue{\begin{array}{l} \phantom{x} \\ R_2 + R_1 \\ R_3 + R_1\end{array}}\\ \\
&\sim& \left( \begin{array}{cccc} \color{green}{1} &5 & 0 &-4 \\ \color{green}{0} &\color{green}{1} &\frac{1}{2} &-\frac{3}{2} \\ \color{green}{0} &-4 &-18 &22 \\ \end{array} \right) &\blue{\begin{array}{l} \phantom{x}\\ -\frac{1}{16} R_2\\ \phantom{z}\end{array}}\\ \\
&\sim& \left( \begin{array}{cccc} \color{green}{1} & \color{green}{0} & -\frac{5}{2} & \frac{7}{2} \\ \color{green}{0} & \color{green}{1} & \frac{1}{2} & -\frac{3}{2} \\ \color{green}{0} &\color{green}{0} & -16 & 16 \\ \end{array} \right) &\blue{\begin{array}{l} R_1 - 5 R_2\\ \phantom{x} \\ R_3 +4 R_2 \end{array}}\\ \\
&\sim& \left( \begin{array}{cccc} \color{green}{1} & \color{green}{0} & -\frac{5}{2} &\frac{7}{2}\\ \color{green}{0} & \color{green}{1} & \frac{1}{2} &-\frac{3}{2} \\ \color{green}{0} & \color{green}{0} & \color{green}{1} &-1 \\ \end{array} \right) &\blue{\begin{array}{l} \phantom{x}\\ \phantom{y}\\ -\frac{1}{16} R_3\end{array}}\\ \\
&\sim& \left( \begin{array}{cccc} \color{green}{1} &\color{green}{0} &\color{green}{0} &1\\ \color{green}{0} &\color{green}{1} &\color{green}{0} &-1 \\ \color{green}{0} &\color{green}{0} &\color{green}{1} &-1 \\ \end{array} \right) &\blue{\begin{array}{l} R_1+\frac{5}{2} R_3 \\ R_2 -\frac{1}{2} R_3 \\ \phantom{z}\end{array}}
\end{array}\]

New example