### 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.

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*reduced echelon form of a matrix.

\(\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.