The row reduced echelon form

The row reduced echelon form can be used to solve a system of linear equations

$\displaystyle Ax=b$ (4.8)

Here, the derivation of the row reduced echelon form is given for several specific systems. Afterwards, the interpretation of the row reduced echelon form of a matrix is discussed.

Nonsingular system
Consider the set of equations (4.11) with $ A=\begin{pmatrix}1&2\\ 3&4\end{pmatrix}$ and $ b=\begin{pmatrix}5\\ 6\end{pmatrix}$ . Define a new matrix $ C=[A,b]=\begin{pmatrix}1 & 2 & 5\\ 3&4&6\end{pmatrix}$ . Now, (4.11) is found by solving $ C(:,[1,2])x=C(:,3)$ . We will try to update $ C$ until this matrix clearly has a solution vector $ x$ .

A solution vector $ x=\begin{pmatrix}x_1\\ x_2\end{pmatrix}$ should satisfy the equations:

$\displaystyle 1 x_1+ 2 x_2$ $\displaystyle =$ $\displaystyle 5,$ (4.9)
$\displaystyle 3 x_1+ 4 x_2$ $\displaystyle =$ $\displaystyle 6.$ (4.10)

Subtracting three times the upper equation from the lower yields:
$\displaystyle 1 x_1+ 2 x_2$ $\displaystyle =$ $\displaystyle 5,$ (4.11)
$\displaystyle \phantom{3 x_1+} -2 x_2$ $\displaystyle =$ $\displaystyle -9.$ (4.12)

This set of equations is represented in a new matrix $ C_1=\begin{pmatrix}1 & 2 & 5\\ 0&-2&-9\end{pmatrix}$ . Dividing the lower equation by -2 yields the set of equations
$\displaystyle 1 x_1+ 2 x_2$ $\displaystyle =$ $\displaystyle 5,$ (4.13)
$\displaystyle \phantom{3 x_1+} x_2$ $\displaystyle =$ $\displaystyle 4.5,$ (4.14)

represented in a matrix $ C_2=\begin{pmatrix}1 & 2 & 5\\ 0&1&4.5\end{pmatrix}$ . Now, one can substract twice the lower equation from the upper equation, such that:
$\displaystyle x_1\phantom{+x_1}$ $\displaystyle =$ $\displaystyle -4,$ (4.15)
$\displaystyle \phantom{+x_1}x_2$ $\displaystyle =$ $\displaystyle 4.5,$ (4.16)

is obtained. This is represented in the matrix $ C_3=\begin{pmatrix}1 & 0 & -4\\ 0&1&4.5\end{pmatrix}$ . Clearly, the solution vector $ x=\begin{pmatrix}-4\\ 4.5\end{pmatrix}$ can be obtained from both the last set of equations and the matrix $ C_3$ .

The matrix $ C_3$ is called the row reduced echelon form of $ C$ . When this matrix has an identity matrix at the lefthand side, the righthandside is the unique solution of the system (4.11). In this case, the system is nonsingular.

Overdetermined system
The row reduced echolon form does not always contain the identity matrix. Suppose $ A=\begin{pmatrix}1&2\\ 2&4\end{pmatrix}$ and $ b=\begin{pmatrix}1\\ 3\end{pmatrix}$ . In that case, we find the subsequent matrices

$\displaystyle C=\begin{pmatrix}1 & 2&1 \\ 2& 4 &3 \end{pmatrix},$     (4.17)
$\displaystyle C_1=\begin{pmatrix}1 & 2&1 \\ 0& 0 &1 \end{pmatrix},$     (4.18)
$\displaystyle C_2=\begin{pmatrix}1 & 2&0 \\ 0& 0 &1 \end{pmatrix}.$     (4.19)

Here, $ C_2$ is the row reduced echelon form. Note, that the last line of this matrix represents $ 0 x_1+ 0 x_2=1$ . Of course, this equation cannot be solved, such that there exist no solution satisfying $ A=\begin{pmatrix}1&2\\ 2&4\end{pmatrix}x=\begin{pmatrix}1\\ 3\end{pmatrix}$ . The system is overdetermined.

Underdetermined system
Suppose $ A=\begin{pmatrix}1&2\\ 2&4\end{pmatrix}$ and $ b=\begin{pmatrix}1\\ 2\end{pmatrix}$ . In that case, we find the subsequent matrices
$\displaystyle C=\begin{pmatrix}1 & 2&1 \\ 2& 4 &2 \end{pmatrix},$     (4.20)
$\displaystyle C_1=\begin{pmatrix}1 & 2&1 \\ 0& 0 &0 \end{pmatrix}.$     (4.21)

Here, $ C_1$ is the row reduced echelon form. Note, that the last line of this matrix represents $ 0 x_1+ 0 x_2=0$ , which is satisfied for all $ x$ . The first line represents $ x_1+2x_2=1$ , which is satisfied as soon as $ x_2=0.5-0.5x_1$ . Therefore each $ x$ satisfying this relation is a solution of the system. The system is underdetermined.

The row reduced echelon form of $ C$ , called $ C_{rref}$ , can thus be used to see whether the system is nonsingular, overdetermined or underdetermined. If $ C_{rref}$ has an identity matrix with the size of $ A$ on the lefthand side, the system is nonsingular and has one solution. If the last row of $ C$ consists only of zeros, the matrix is underdetermined and has infinitely many solutions. If the last row of $ C$ consists of only zeros, except the last element, than the system is overdetermined and has no solutions.

In MATLAB, rref(C) obtains the row reduced echelon form of the matrix $ C$ .



Previous      Next      Up      Contents


Esteur 2010-03-22