Row reduction of a matrix to a reduced echelon form

Systems of linear equations: System of linear equations and matrices

Row reduction of a matrix to a reduced echelon form

In row reduction we apply elementary row operations; thereby, one or more of the following operations are applied:

multiplying a row with a number distinct from zero
adding a scalar multiple of a row to another row
changing the order of the rows

These are the authorized operations. This does not yet fully determine the row reduction process. The aim of row reduction is to bring the matrix in reduced echelon form. We first look at a few examples.

Determine the reduced echelon form of the following matrix:

$A=\left(\,\begin{array}{rrrr} {1} & 2 & -4 & 8\\ -1 & -2 & 6 & -4\\ 1 & 4 & -2 & 0\end{array}\,\right)$

$\left (\, \begin{array}{rrrr} {1} & {0} &{0} & 28\\ {0} & {1} & {0} & -6\\ {0} & {0} &{1} & 2 \end {array} \, \right)$

We start with the matrix:

$A=\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ -1 & -2 & 6 & -4\\ 1 & 4 & -2 & 0\end{array}\,\right)$ Green elements are elements we want to leave unchanged. We first use the first row to get as many zeros as possible in the first column. We do that by adding the first row to the second and subtracting it from the third. This gives

$\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -\,4 & 8\\ \color{green}{0} & 0 & 2 & 4\\ \color{green}{0} & 2 & 2 & -8 \end{array}\,\right)$ Now we try to wipe the second column clean by use of the second row. This not possible because the second element equals $0$ . Therefore we swap the second and third row (not the second and first row, because that way we would distort the first column!)

$\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ \color{green}{0} & 2 & 2 & -8\\ \color{green}{0} & \color{green}{0} & 2 & 4 \end{array}\,\right)$
and divide the second row by $2$ :

$\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} &\color{green}{0} & 2 & 4 \end{array}\,\right)$ Now we can wipe the second column clean by use of the second row. We subtract it twice from the first. Note that the first column remains unchanged:

$\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & -6 & 16\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} & \color{green}{0} & 2 & 4 \end{array}\,\right)$ Now we wipe the third column clean by use of the third row. To this end, we first divide it by $2$ :

$\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & -6 & 16\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} & \color{green}{0} & \color{green}{1} & 2\end{array}\,\right)$ Then we add the new third row $6$ times to the first row and subtract it from the second row; note again that the first two columns remain unchanged:

$\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & \color{green}{0} & 28\\ \color{green}{0} & \color{green}{1} & \color{green}{0} & -6\\ \color{green}{0} & \color{green}{0} & \color{green}{1} & 2 \end{array}\,\right)$
Now we cannot continue; each wiping of the fourth column by use of a row would disrupt the results in the first three columns. But there is no need to continue: the obtained result is the reduced echelon form of $A$ .

The process does not make it immediately clear, but row reduction of a matrix produces a unique result; we can indeed speak of the reduced echelon form of a matrix.

New example

$\phantom{x}$

We now describe the general process of row reduction in the form of an algorithm. The reader is advised to compare the examples just given with the following description.

Gaussian elimination

The Gauss elimination method, abbreviated as Gaussian elimination, is a method of reducing a matrix to a matrix in reduced row echelon form by means of elementary row operations.

Any matrix can be reduced to a unique reduced row echelon form. The method below performs Gaussian elimination.

The first step consists of the following operations on a given matrix with $m$ rows and $n$ columns:

Let $n_1$ be the number of the first column that does not consist exclusively of zeros.
If needed, swap two rows in such a way that the first element of column $n_1$ is not zero.
Divide the first row by the first element of the column $n_1$ , so $a_{1n_1}=1$ .
The matrix now has the following form: $\left(\,\begin{array}{cccccccc} 0 & \ldots & 0 & 1 & \ast & \ast & \ldots & \ast \\ 0 & \ldots & 0 & \alpha_2 & \ast & \ast & \ldots & \ast \\ 0 & \ldots & 0 & \alpha_3 & \ast & \ast & \ldots & \ast \\ \vdots & & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 0 & \ldots & 0 & \alpha_m & \ast & \ast & \ldots & \ast \end{array}\,\right)$ By $\ast$ we denote the matrix elements whose values are insignificant to our reasoning; they may be zero or non-zero.
Use the first row to create in column $n_1$ zeros below the leading element. We get a matrix of the form (with a framed submatrix):
$\left(\,\begin{array}{cc} \begin{array}{cccc} 0 & \ldots & 0 & 1\end{array} & \begin{array}{cccc} \ast & \ast & \ldots & \ast \end{array} \\ \begin{array}{cccc} 0 & \ldots & 0 & 0 \\ 0 & \ldots & 0 & 0 \\ \vdots & & \vdots & \vdots \\ 0 & \ldots & 0 & 0\end{array} & \boxed{\begin{array}{cccc}\ast & \ast & \ldots & \ast\\ \ast & \ast & \ldots & \ast\\ \vdots & \vdots & & \vdots\\ \ast & \ast & \ldots & \ast\end{array}} \end{array}\,\right)$

The first step is now complete. In the next steps we apply the same procedure to the framed submatrix (but wiping clean all the columns in the last step) and repeat this process until we are no longer left with a framed submatrix or with a framed submatrix with only zeros; then the whole process of row reduction is completed.

Said further steps can be written formally as follows: Suppose that we have performed $k$ steps. Then the first $k$ rows of the resulting matrix will have been use for wiping columns clean, and the last wiped column is $n_k$ . We now proceed as follows:

Let $n_{k+1}$ e the number of the first column that doed not have zeros only from the $(k+1)$ -th element on.
If needed, interchange row $k+1$ with a next row in such a way that the $(k+1)$ -st element of column $n_{k+1}$ is distinct from zero.
Divide row $k+1$ by that element, so $a_{k+1,n_{k+1}}=1$ .
Use row $k+1$ to wipe column $n_{k+1}$ clean.

The result of this reduction process may look like this after, for example, three steps:

$\left[\,\begin{array}{ccccccccccccccc} 0 & \ldots & 0 & 1 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast\\ 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast\\ 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & \ast & \ldots & \ast\\ \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & 0 & \vdots & & \vdots\\ \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots\\ 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 0 & \ast & \ldots & \ast \end{array}\,\right]$ At places denoted by $\ast$ the elements need no necessarily be $0$ or $1$ .

The process stops automatically when all rows are used for creating columns with only one nonzero element or when the last rows contain only zeros.

Terminology Via elementary row operations, we can turn a arbitrary nonzero element of a matrix into 1 and also to ensure that this is the only nonzero element is in its column. This process is called the pivoting of a matrix, and the selected non-zero matrix element is called pivot element (or simply pivot). Row reduction of a matrix to its reduced row echelon form is actually nothing more than executing the pivoting process as far as possible.