As we saw in The Matrix and Solving Systems using Matrices section, the reduced row echelon form method can be used to solve systems.
With this method, we put the coefficients and constants in one matrix (called an augmented matrix, or in coefficient form) and then, with a series of row operations, change it into what we call reduced echelon form, or reduced row echelon form. This is when the leading entry in every nonzero row is $ 1$, and each leading $ 1$ is the only nonzero entry for that column, such as $ \left[ {\begin{array}{*{20}{c}} 1 & 0 & 0 & {\text{”}x\text{”}} \\ 0 & 1 & 0 & {\text{”}y\text{”}} \\ 0 & 0 & 1 & {\text{”}z\text{”}} \end{array}} \right]$. Then the numbers in the last column are the answers!. This is also called Gaussian Elimination, or Row Reduction.
To get the matrix in the correct form, we can 1) swap rows, 2) multiply rows by a non-zero constant, or 3) replace a row with the product of another row times a constant added to the row to be replaced. Here is an example:
Solve the following system of equations: $ \displaystyle \begin{align}5x-6y-7z&=7\\6x-4y+10z&=-34\\2x+4y-3z&=29\end{align}$.
- Find the first non-zero entry in the first column; this is the pivot. Move this to the first row. This is just 5, so the augmented matrix is still $ \displaystyle \left[ {\begin{array}{*{20}{c}} 5 & {-6} & {-7} & 7 \\ 6 & {-4} & {10} & {-34} \\ 2 & 4 & {-3} & {29} \end{array}} \right]\,$.
- Make the pivot (the 5) 1 by multiplying this row by $ \displaystyle \frac{1}{5}$: $ \displaystyle \left[ {\begin{array}{*{20}{c}} 5 & {-6} & {-7} & 7 \\ 6 & {-4} & {10} & {-34} \\ 2 & 4 & {-3} & {29} \end{array}} \right]\,\begin{array}{*{20}{c}}{\frac{1}{5}R1\Rightarrow R1} \\ {} \end{array}$.
Now we have $ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ 6 & {-4} & {10} & {-34} \\ 2 & 4 & {-3} & {29} \end{array}} \right]$.
- Now we want the elements below the $ 1$ (first column) to be $ 0$. To get them to be $ 0$, add multiples of the first (pivot) row to each of the rows below, replacing those rows. Note that we took the opposite (negative) of the first element in that row (like $ -6$) to get the multiplier of the pivot row:
$ \displaystyle \begin{array}{c}\left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ 6 & {-4} & {10} & {-34} \\ 2 & 4 & {-3} & {29} \end{array}} \right]\begin{array}{*{20}{c}} {} \\ {-6R1\text{ }+\text{ }R2\text{ }\Rightarrow \text{ }R2} \\ {-2R1\text{ }+\text{ }R3\text{ }\Rightarrow \text{ }R3} \end{array}\,\,\,\,\\=\left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ {-6\cdot 1+6=0} & {-6\cdot -\frac{6}{5}-4=\frac{{16}}{5}} & {-6\cdot -\frac{7}{5}+10=\frac{{92}}{5}} & {-6\cdot \frac{7}{5}-34=-\frac{{212}}{5}} \\ {-2\cdot 1+2=0} & {-2\cdot -\frac{6}{5}+4=\frac{{32}}{5}} & {-2\cdot -\frac{7}{5}-3=-\frac{1}{5}} & {-2\cdot \frac{7}{5}+29=\frac{{131}}{5}} \end{array}} \right]\end{array}$. Now we have $ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ 0 & {\frac{{16}}{5}} & {\frac{{92}}{5}} & {-\frac{{212}}{5}} \\ 0 & {\frac{{32}}{5}} & {-\frac{1}{5}} & {\frac{{131}}{5}} \end{array}} \right]$.
- Now the second row is the pivot row. To get the second column, second row a $ 1$, divide this row by $ \displaystyle \frac{{16}}{5}$ (multiply by reciprocal): $ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ 0 & {\frac{{16}}{5}} & {\frac{{92}}{5}} & {-\frac{{212}}{5}} \\ 0 & {\frac{{32}}{5}} & {-\frac{1}{5}} & {\frac{{131}}{5}} \end{array}} \right]\begin{array}{*{20}{c}} {} \\ {\frac{5}{{16}}R2} \\ {} \end{array}\Rightarrow R2$.
Now we have $ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ 0 & 1 & {\frac{{23}}{4}} & {-\frac{{53}}{4}} \\ 0 & {\frac{{32}}{5}} & {-\frac{1}{5}} & {\frac{{131}}{5}} \end{array}} \right]\,\,$.
- Repeat the procedure from Step 3 above, using the first and third rows, to make their second column entries $ 0$:
$ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & {-\frac{6}{5}} & {-\frac{7}{5}} & {\frac{7}{5}} \\ 0 & 1 & {\frac{{23}}{4}} & {-\frac{{53}}{4}} \\ 0 & {\frac{{32}}{5}} & {-\frac{1}{5}} & {\frac{{131}}{5}} \end{array}} \right]\begin{array}{*{20}{c}} {\frac{6}{5}R2+R1\Rightarrow R1} \\ {} \\ {-\frac{{32}}{5}R2+R3\Rightarrow R3} \end{array}$.
Now we have $ \left[ {\begin{array}{*{20}{c}} 1 & 0 & {\frac{{11}}{2}} & {-\frac{{29}}{2}} \\ 0 & 1 & {\frac{{23}}{4}} & {-\frac{{53}}{4}} \\ 0 & 0 & {-37} & {111} \end{array}} \right]$.
- Now multiply the third row by $ \displaystyle -\frac{1}{{37}}$ to have the $ 1$ in the third column for another pivot row:
$ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & 0 & {\frac{{11}}{2}} & {-\frac{{29}}{2}} \\ 0 & 1 & {\frac{{23}}{4}} & {-\frac{{53}}{4}} \\ 0 & 0 & {-37} & {111} \end{array}} \right]\begin{array}{*{20}{c}} {} \\ {} \\ {-\frac{1}{{37}}R3\Rightarrow R3} \end{array}$.
Now we have $ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & 0 & {\frac{{11}}{2}} & {-\frac{{29}}{2}} \\ 0 & 1 & {\frac{{23}}{4}} & {-\frac{{53}}{4}} \\ 0 & 0 & 1 & {-3} \end{array}} \right]$, which is in row echelon form.
- Repeat step 3 above again to get $ 0$’s in the third column (first two rows) to get reduced row echelon form:
$ \displaystyle \left[ {\begin{array}{*{20}{c}} 1 & 0 & {\frac{{11}}{2}} & {-\frac{{29}}{2}} \\ 0 & 1 & {\frac{{23}}{4}} & {-\frac{{53}}{4}} \\ 0 & 0 & 1 & {-3} \end{array}} \right]\begin{array}{*{20}{c}} {-\frac{{11}}{2}R3+R1\Rightarrow R1} \\ {-\frac{{23}}{4}R3+R2\Rightarrow R2} \\ {} \end{array}\,$.
We get $ \left[ {\begin{array}{*{20}{c}} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 4 \\ 0 & 0 & 1 & {-3} \end{array}} \right]$.
Yeah! Our answer is $ x=2, y=4$, and $ z=-3$!
Note if at the end we get all $ 0$’s in the last row, we have an infinite number of solutions, and if we get all $ 0$’s except for the last row, fourth column, we have no solution. We saw these examples here in the Matrix and Solving Systems with Matrices section.
On to Introduction to Linear Programming – you are ready!