Row reduction of a matrix

Systems of linear equations and matrices: Systems and matrices

Row reduction of a matrix

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 an example or two.

Bring the following matrix in reduced echelon form:

$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

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

Gaussian elimination method, or simply Gaussian elimination, is a method of reducing a matrix to a matrix in reduced echelon form by means of elementary row operations.

Any matrix can be reduced to a unique row reduced 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.
Wipe with the first row of column $n_1$ clean. 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 frame 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}$ be the number of the first column that doen not have zeroes 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 wiping columns clean or when the last rows contain only zeros.

In the algorithm we select a non-zero element of the matrix, lift its row higher up (if needed), turn it into $1$ , and ensure that it is the only non-zero element in its column. The elements that are used this way in the above algorithm for finding the reduced echelon form are called the pivots of the matrix. Since rows can be interchanged, the notion of pivot column is used for a column in which a pivot element appears.

The Gauss elimination of the statement shows that, for each matrix, a row reduced echelon form exists. We will focus on showing that it is unique. Let $A$ be an $(m\times n)$ -matrix and suppose both $B$ and $C$ are matrices in row reduced echelon form that are obtained by reduction from $A$ . We need to show $B = C$ .

If $n=1$ , then the uniqueness is obvious: the matrices $B$ and $C$ have a single column with a single nonzero entry, which is equal to $1$ , and $B$ can only be reduced to $C$ if the nonzero element of $B$ is at the same place as the nonzero element of $C$ .

We proceed by induction on $n$ and assume $n\gt 1$ . Let $A_n$ be the submatrix of $A$ obtained by omitting the last column, column $n$ , and similarly for $B$ and $C$ . The elementary operations used in reducing $A$ to $B$ are also elementary operations that reduce $A_n$ to $B_n$ , and similarly for $C_n$ . By the induction hypothesis on $n$ , we conclude $B_n=C_n$ , so $B$ and $C$ can only differ in the last column. Suppose now $B\ne C$ . Then there is an index $j$ with $1\le j \le m$ such that $b_{jn} \ne c_{jn}$ . If $Bx = 0$ , then, as $C$ can be row reduced to $B$ , we also have $Cx=0$ , and the component $j$ of the column vector $(B-C)x$ is equal to $(b_{jn} -c_{jn})\cdot x_j$ , so $x_j = 0$ . Again, since the solutions of $Bx=0$ and $Cx=0$ coincide, the entries $b_{jn}$ and $c_{jn}$ must be the leading elements of row $j$ in $B$ and $C$ , respectively (for otherwise there would be solutions of the equation with $x_j\ne0$ ). But then column $n$ of $B$ as well as $C$ has a $1$ at component $j$ and zeros elsewhere, so they are equal, contradicting $B\ne C$ . This establishes $B=C$ .

The elementary row operations on the matrix $A$ can be regarded as multiplications of $A$ from the left by a square matrix:

$R_i\rightarrow c\cdot R_i\;(c\neq 0)$ : Multiplication of row $i$ of $A$ by a number $c$ is equal to multiplication from the left by the diagonal matrix $B$ having $c$ on position $i$ of the diagonal and ones on the remaining diagonal positions.
$R_i\rightarrow R_i+c\cdot R_j$ : Addition of the multiple $c$ of row $j$ to another row $i$ is equal to multiplication of $A$ from the left by the matrix $I+c\cdot E_{ij}$ , where $E_{ij}$ is the matrix whose $(i,j)$ -entry is equal to $c$ and all of whose other entries are zero.
$R_i\leftrightarrow R_j$ : Interchanging rows $i$ and $j$ of $A$ is equal to multiplying $A$ from the left by the permutation matrix $B$ corresponding to the permutation $(i,j)$ .

The above matrices are called elementary matrices. If we multiply a matrix from the left by an elementary matrix, then we perform an elementary (row) operation on the matrix. In Elementary operations on systems of linear equations we saw that two systems of linear equations that are obtained from each other by elementary reductions, have the same solution. Therefore, elementary operations do not change the (in)dependence of the rows of a matrix. Later we will see that elementary operations neither change the (in)dependence of the columns.