Skip to main content

Section 1.2 Gauss-Jordan elimination

Subsection 1.2.1 The method of elimination

In the previous section we saw examples of solving systems of linear equations using substitution. Our goal is now to study a more efficient method of solving systems of linear equations, the method of elimination.

The central observation is that there are some things we can do to the equations in a system of linear equations that can make the equations easier to work with, while not changing the solutions.

Definition 1.2.1.

Two systems of linear equations in the same variables are called equivalent if they have exactly the same solutions; that is, if a point is a solution to one system then it is a solution to the other, and if a point is not a solution to one of the systems then it is not a solution to the other.

It turns out that to change a system into an equivalent system there are only three things that we will need to do:

  • Switch the order in which we write two equations.

  • Multiply an equation by a non-zero constant.

  • Add a multiple of one equation to another equation, replacing the equation that we are adding into.

The idea of elimination is to repeatedly use the three operations above until we reach a new system of equations that is easier to solve. The name elimination comes from the fact that our strategy is to eliminate variables from the equations so that (for example) the first variable ends up appearing only in the first equation. The best way to understand the process is through an example.

Consider this system of equations:

\begin{gather*} x+2y-z=3\\ x-y+z=1\\ -2x-z=0 \end{gather*}

If we add \((-1)\) times the first equation to the second equation, and replace the second equation by the result, we obtain the following system:

\begin{gather*} x+2y-z=3\\ -3y+2z=-2\\ -2x-z=0 \end{gather*}

Notice that only the second equation has changed. Now let's add \(2\) times the first equation to the third equation. We get:

\begin{gather*} x+2y-z=3\\ -3y+2z=-2\\ 4y-3z=6 \end{gather*}

We've made progress - the variable \(x\) now appears only in the first equation! To continue, let's multiply the second equation by \(-1/3\text{:}\)

\begin{gather*} x+2y-z=3\\ y-\frac{2}{3}z=\frac{2}{3}\\ 4y-3z=6 \end{gather*}

Now we'll add \(-4\) times the second equation to the third equation.

\begin{gather*} x+2y-z=3\\ y-\frac{2}{3}z=\frac{2}{3}\\ -\frac{1}{3}z = \frac{10}{3} \end{gather*}

Next, we eliminate \(y\) from the first equation by subtracting \(2\) times the second equation.

\begin{gather*} x+\frac{1}{3}z=\frac{5}{3}\\ y-\frac{2}{3}z=\frac{2}{3}\\ -\frac{1}{3}z = \frac{10}{3} \end{gather*}

To clean things up a bit, we'll multiply the third equation by \(-3\text{.}\)

\begin{gather*} x+\frac{1}{3}z=\frac{5}{3}\\ y-\frac{2}{3}z=\frac{2}{3}\\ z = -10 \end{gather*}

Now we've accomplished something really useful! Since the system we've arrived at has the same solutions as the original solution, we can see from here that any solution to the original system has \(z=-10\text{.}\) We could now subsitute \(z=-10\) into the first two equations, or we can continue with elimination. For the purposes of this example, let's continue with elimination. For our next move, we'll add \(2/3\) times the third equation to the second equation.

\begin{gather*} x+\frac{1}{3}z=\frac{5}{3}\\ y=-6\\ z=-10 \end{gather*}

Finally, we'll subtract \(\frac{1}{3}\) times the third equation from the first.

\begin{gather*} x=5\\ y=-6\\ z=-10 \end{gather*}

After all of these steps we now have a system of equations that is very easy to solve - in fact, it just tells us that the solution is \(x=5, y=-6, z=-10\text{.}\) From Fact 1.2.2 we know that our new system has the same solutions as the original solution, so we conclude that the only solution to our original system

\begin{gather*} x+2y-z=3\\ x-y+z=1\\ -2x-z=0 \end{gather*}

is \(x=5, y=-6, z=-10\text{.}\)

Subsection 1.2.2 Elimination using matrices

The method of elimination is very powerful, but it gets quite tedious to write out all of the steps in the process. In Subsection 1.1.2 we saw that we can keep track of a system of equations as an augmented matrix, with the rows of the augmented matrix representing the equations. Augmented matrices give us a convenient way to keep track of our work when we use elimination to solve systems. Corresponding to the three operations on equations discussed above, we have:

Definition 1.2.4.

The elementary row operations on a matrix are:

  • Swapping the order of two rows. When swapping row \(i\) with row \(j\) we often write \(R_i \leftrightarrow R_j\text{.}\)

  • Multiply a row by a non-zero constant. When we multiply row \(i\) by the constant \(c\) we often write \(cR_i\text{.}\)

  • Add a multiple of one row into another, replacing the row we are adding into. When we add \(c\) times row \(i\) into row \(j\) we often write \(R_j + cR_i\text{.}\) Instead of something like \(R_3+(-2)R_1\) we usually write \(R_3-2R_1\text{.}\)

Definition 1.2.5.

Suppose that \(A\) and \(B\) are two matrices with the same number of rows and the same number of columns. We say that \(A\) and \(B\) are row equivalent if there is a finite sequence of elementary row operations that transforms \(A\) into \(B\text{.}\) The process of using elementary row operations to turn one matrix into another matrix is called row reduction.

With these definitions in place, we now re-do Example 1.2.3 using the notation of augmented matrices.

Consider again this system of equations:

\begin{gather*} x+2y-z=3\\ x-y+z=1\\ -2x-z=0 \end{gather*}

Here is how we write the process of solving this system using elementary row operations. The sequence of operations is exactly the same one that we used in Example 1.2.3, so the only thing that is different this time is how we record what we're doing.

\begin{align*} \matr{ccc|c}{1 \amp 2 \amp -1 \amp 3 \\ 1 \amp -1 \amp 1 \amp 1 \\ -2 \amp 0 \amp -1 \amp 0} \amp\to_{R_2-R_1} \matr{ccc|c}{1 \amp 2 \amp -1 \amp 3 \\ 0 \amp -3 \amp 2 \amp -2 \\ -2 \amp 0 \amp -1 \amp 0}\\ \amp \to_{R_3+2R_1}\matr{ccc|c}{1 \amp 2 \amp -1 \amp 3 \\ 0 \amp -3 \amp 2 \amp -2 \\ 0 \amp 4 \amp -3 \amp 6}\\ \amp \to_{(-1/3)R_2}\matr{ccc|c}{1 \amp 2 \amp -1 \amp 3 \\ 0 \amp 1 \amp -2/3 \amp 2/3 \\ 0 \amp 4 \amp -3 \amp 6}\\ \amp \to_{R_3-4R_2}\matr{ccc|c}{1 \amp 2 \amp -1 \amp 3 \\ 0 \amp 1 \amp -2/3 \amp 2/3 \\ 0 \amp 0 \amp -1/3 \amp 10/3}\\ \amp \to_{R_1-2R_2}\matr{ccc|c}{1 \amp 0 \amp 1/3 \amp 5/3 \\ 0 \amp 1 \amp -2/3 \amp 2/3 \\ 0 \amp 0 \amp -1/3 \amp 10/3}\\ \amp \to_{-3R_3}\matr{ccc|c}{1 \amp 0 \amp 1/3 \amp 5/3 \\ 0 \amp 1 \amp -2/3 \amp 2/3 \\ 0 \amp 0 \amp 1 \amp -10}\\ \amp \to_{R_2+(2/3)R_3}\matr{ccc|c}{1 \amp 0 \amp 1/3 \amp 5/3 \\ 0 \amp 1 \amp 0 \amp -6 \\ 0 \amp 0 \amp 1 \amp -10}\\ \amp \to_{R_1 - (1/3)R_3}\matr{ccc|c}{1 \amp 0 \amp 0 \amp 5 \\ 0 \amp 1 \amp 0 \amp -6 \\ 0 \amp 0 \amp 1 \amp -10} \end{align*}

The matrices in this calculation are all row-equivalent, so Fact 1.2.6 tells us that all of these augmented matrices represent systems with exactly the same set of solutions.

In particular, our original system (which corresponds to the first augmented matrix) has the same solutions as the system corresponding to the final augmented matrix. That final system is \(x=5, y=-6, z=-10\text{,}\) so once again we have found the unique solution to our original system.

Subsection 1.2.3 Gauss-Jordan elimination and reduced row echelon form

In Example 1.2.7 we used a sequence of row operations to transform the augmented matrix of a linear system into the augmented matrix of a much simpler linear system. We could have used the three elementary row operations in any order, and stopped at any time, and we still would have had a system equivalent to our original one. In this section we answer two questions: How can we recognize when we have reached the simplest possible form of a system, and what sequence of row operations will get us there? We start with the question of how to tell when we should stop doing row operations.

Definition 1.2.8.

In any row of any matrix, the first non-zero entry of the row is called the leading entry of the row.

A matrix is in row echelon form if it has all of the following properties:

  • If there are any rows where every entry is \(0\) then those rows occur below any rows with a non-zero entry.

  • In any row where not every entry is \(0\text{,}\) if we look at the leading entry then every number below it in the same column or any column to the left of it is \(0\text{.}\)

Notice that the definition of row echelon form does not require our matrix to be augmented - the definition is the same regardless of whether or not there is a vertical line separating parts of the matrix. We will often (but not always!) be interested in row echelon form for augmented matrices; when determining if an augmented matrix is in row echelon form or not you can simply ignore the vertical line.

Here are some matrices that are in row echelon form.

  • \(\displaystyle \matr{cc|c}{3 \amp 2 \amp 1 \\ 0 \amp -1 \amp 3 \\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0}\)

  • \(\displaystyle \matr{ccc|c}{1 \amp 2 \amp 3 \amp 0 \\ 0 \amp 0 \amp 1 \amp 1 \\ 0 \amp 0 \amp 0 \amp 1}\)

  • \(\displaystyle \matr{cc}{0 \amp 1 \\ 0 \amp 0}\)

Here are some matrices that are not in row echelon form.

  • \(\displaystyle \matr{cc|c}{5 \amp 2 \amp 1 \\ 2 \amp -1 \amp 3}\)

  • \(\displaystyle \matr{ccc|c}{1 \amp 2 \amp 3 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 }\)

  • \(\displaystyle \matr{cc}{1 \amp 1 \\ 1 \amp 2 \\ 0 \amp 0}\)

We will see some uses for row echelon form later on. For our current purposes it isn't quite strict enough, so we introduce the following concept.

Definition 1.2.11.

A matrix is in reduced row echelon form if it is in row echelon form and it also satisfies the following additional properties:

  • If a row has any non-zero entries then the leading entry of that row is \(1\text{.}\)

  • In any row where not every entry is \(0\text{,}\) if we look at the leading entry then every number both above and below it in the same column is \(0\text{.}\)

As with row echelon form, the definition of reduced row echelon form is the same regardless of whether or not the matrix is augmented.

Here are some matrices that are in reduced row echelon form.

  • \(\displaystyle \matr{cc|c}{1 \amp 0 \amp -3\\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0}\)

  • \(\displaystyle \matr{ccc|c}{1 \amp 0 \amp 3 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1}\)

  • \(\displaystyle \matr{cc}{0 \amp 1 \\ 0 \amp 0}\)

  • \(\displaystyle \matr{ccc}{1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1}\)

Here are some matrices that are not in reduced row echelon form.

  • \(\displaystyle \matr{cc|c}{5 \amp 2 \amp 1 \\ 2 \amp -1 \amp 3}\)

  • \(\displaystyle \matr{ccc|c}{2 \amp 0 \amp 1 \amp 3 \\ 0 \amp 1 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0 \amp 0}\)

  • \(\displaystyle \matr{ccc}{1 \amp 0 \amp 1 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1}\)

Note 1.2.15.

The reduced row echelon form of a matrix \(A\) is not the same matrix as \(A\text{,}\) unless the original matrix \(A\) was already in reduced row echelon form. That is, \(\RREF(A) = A\) only when \(A\) itself is already in reduced row echelon form. Performing row operations produces a matrix that is row-equivalent to the original matrix, but not equal to the original one!

If we start with an augmented matrix \(A\) then \(\RREF(A)\) is the simplest form we can reach using row operations; that is, \(\RREF(A)\) represents the simplest system of linear equations that has the same solutions as the system represented by \(A\text{.}\) So when we are faced with a system of linear equations our goal should be to row reduce its augmented matrix until we reach reduced row echelon form. If we choose our row operations at random it is very unlikely that we will get to reduced row echelon form. Fortunately, there is an algorithm (the Gauss-Jordan algorithm) to help us decide which operations to use.

Since we are not planning to prove Fact 1.2.14 we will also not give an entirely precise statement of the Gauss-Jordan algorithm. Instead, we give an informal description that will be adequate for working with examples. Here is the algorithm:

  1. Find the first column (from the left) of the matrix that has a non-zero entry in it. Make that non-zero entry into a \(1\text{,}\) and move it to the top row.

  2. Use the \(1\) you obtained in the previous step to make the rest of that column be \(0\text{.}\)

  3. Find the next column (further to the right from the previous one used) that has a non-zero entry in a position other than the first row. Make that entry into a \(1\text{,}\) and move it to the second row.

  4. Use the \(1\) you obtained in the previous step to make the rest of that column be \(0\text{.}\)

  5. Find the next column (further to the right from the previous one used) that has a non-zero entry in a position other than the first two rows. Make that entry into a \(1\text{,}\) and move it to the third row.

  6. Use the \(1\) you obtained in the previous step to make the rest of that column be \(0\text{.}\)

  7. Repeat this process until you cannot continue.

There are always many different sequences of row operations that take \(A\) to \(\RREF(A)\text{,}\) and sometimes you may find a sequence that is shorter than the one given by the Gauss-Jordan algorithm. The benefit of the Gauss-Jordan algorithm is simply that it provides a sequence that is guaranteed to take you from \(A\) to \(\RREF(A)\text{.}\)

Take a moment to verify that in Example 1.2.7 the steps we followed were exactly the steps of the Gauss-Jordan algorithm.

Let \(A = \matr{ccc|c}{0 \amp 1 \amp 1 \amp 0 \\ 2 \amp 0 \amp 4 \amp 2}\text{.}\) To find \(\RREF(A)\) we can follow the Gauss-Jordan algorithm.

\begin{align*} A \amp \to_{R_1 \leftrightarrow R_2} \matr{ccc|c}{2 \amp 0 \amp 4 \amp 2 \\ 0 \amp 1 \amp 1 \amp 0}\\ \amp \to_{(1/2)R_1}\matr{ccc|c}{1 \amp 0 \amp 2 \amp 1 \\ 0 \amp 1 \amp 1 \amp 0} \end{align*}

We've arrived at a matrix in reduced row echelon form, so we stop.

Let \(B = \matr{ccc}{1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 3 \\ 0 \amp 0 \amp 2}\text{.}\) To find \(\RREF(B)\) we follow Gauss-Jordan.

\begin{align*} B \amp \to_{R_2 - R_1}\matr{ccc}{1 \amp 1 \amp 1 \\ 0 \amp 0 \amp 2 \\ 0 \amp 0 \amp 2}\\ \amp \to_{(1/2)R_2}\matr{ccc}{1 \amp 1 \amp 1 \\ 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 2}\\ \amp \to_{R_1-R_2}\matr{ccc}{1 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 2}\\ \amp \to_{R_3-2R_2}\matr{ccc}{1 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0} \end{align*}

Therefore \(\RREF(B) = \matr{ccc}{1 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0}\text{.}\)

Exercises 1.2.4 Exercises

1.

Find the solution of each of the following systems of linear equations using the Gauss-Jordan algorithm and augmented matrices.

  1. \begin{align*} x - 3y \amp = 1\\ 2x - 7y \amp = 3 \end{align*}

  2. \begin{align*} x - 2y \amp = 1\\ 3x + 4y \amp = -1 \end{align*}

  3. \begin{align*} 2x - 3y \amp = -1\\ 3x + 4y \amp = 2 \end{align*}

  4. \begin{align*} 3x + 4y \amp = 1\\ 4x + 5y \amp = -3 \end{align*}

Answer.

  1. \(\displaystyle x =- 2, y = -1 \)

  2. \(\displaystyle x = \frac{1}{5}, y = -\frac{2}{5} \)

  3. \(\displaystyle x = \frac{2}{17}, y = \frac{7}{17}\)

  4. \(\displaystyle x = -17, y = 13 \)

Solution.

  1. First, we write the augmented matrix for the system of linear equations.

    \begin{align*} \matr{cc|c}{1\amp -3\amp 1\\ 2 \amp -7 \amp 3} \end{align*}
    There is already a 1 in the top left entry, so we use that 1 to make the rest of the first column become 0 by subtracting 2 times row 1 from row 2. We obtain
    \begin{align*} \matr{cc|c}{1\amp -3\amp 1\\ 0\amp -1 \amp 1} \amp \hspace{.25in} \end{align*}
    Now we move to the second column. We want a 1 in the second row of the second column, so we multiply row 2 by (-1) and obtain
    \begin{align*} \matr{cc|c}{1\amp -3\amp 1\\ 0\amp 1 \amp -1} \amp \hspace{.25in} \end{align*}
    Now we use the 1 in row 2 column 2 to make the rest of column 2 be all 0. To do this, we add 3 times row 2 to row 1, and get
    \begin{align*} \matr{cc|c}{1\amp 0\amp -2\\ 0\amp 1 \amp -1} \amp \hspace{.25in} \end{align*}
    At this point we see that the solution to the system is \(x = -2, y = -1 \text{.}\)

  2. For the remaining parts of this question we will show the row operations in the same manner as we did in Example 1.2.20.

    \begin{align*} \matr{cc|c}{1\amp -2\amp 1\\ 3 \amp 4 \amp -1} \amp \to_{R_2 - 3R_1}\matr{cc|c}{1 \amp -2 \amp 1 \\ 0 \amp 10 \amp -4}\\ \amp \to_{(1/10)R_2}\matr{cc|c}{1 \amp -2 \amp 1 \\ 0 \amp 1 \amp -4/10}\\ \amp \to_{R_1+2R_2}\matr{cc|c}{1 \amp 0 \amp 2/10 \\ 0 \amp 1 \amp -4/10} \end{align*}
    Translating back to equations, we find that the solution to the system is \(x = \frac{1}{5}, y = -\frac{2}{5} \text{.}\)

  3. The augmented matrix to the system is given by,

    \begin{align*} \matr{cc|c}{2\amp -3\amp -1\\ 3 \amp 4 \amp 2}. \end{align*}
    Now we follow the Gauss-Jordan algorithm.
    \begin{align*} \matr{cc|c}{2\amp -3\amp -1\\ 3 \amp 4 \amp 2} \amp \to_{(1/2)R_1}\matr{ccc}{1 \amp -3/2 \amp -1/2 \\ 3 \amp 4 \amp 2}\\ \amp \to_{R_2-3R_1}\matr{cc|c}{1 \amp -3/2 \amp -1/2 \\ 0 \amp 17/2 \amp 7/2}\\ \amp \to_{(2/17)R_2}\matr{cc|c}{1 \amp -3/2 \amp -1/2 \\ 0 \amp 1 \amp 7/17}\\ \amp \to_{R_1+(3/2)R_2}\matr{cc|c}{1 \amp 0 \amp 2/17 \\ 0 \amp 1 \amp 7/17} \end{align*}
    Therefore, the solution to the system is \(x = \frac{2}{17} , y = \frac{7}{17} \text{.}\)

  4. The augmented matrix to the system is given by,

    \begin{align*} \matr{cc|c}{3\amp 4\amp 1\\ 4 \amp 5 \amp -3}. \end{align*}
    Now we follow Gauss-Jordan:
    \begin{align*} \matr{cc|c}{3\amp 4\amp 1\\ 4 \amp 5 \amp -3} \amp \to_{(1/3)R_1} \matr{cc|c}{1 \amp 4/3 \amp 1/3 \\ 4 \amp 5 \amp -3}\\ \amp \to_{R_2-4R_1}\matr{cc|c}{1 \amp 4/3 \amp 1/3 \\ 0 \amp -1/3 \amp -13/3}\\ \amp \to_{-3R_2}\matr{cc|c}{1 \amp 4/3 \amp 1/3 \\ 0 \amp 1 \amp 13}\\ \amp \to_{R_1-(4/3)R_2}\matr{cc|c}{1 \amp 0 \amp -17 \\ 0 \amp 1 \amp 13} \end{align*}
    Therefore, the solution to the system is \(x = -17 , y = 13 \text{.}\)

2.

We will see in Chapter 2 that a single linear equation in three variables represents a plane in three-dimensional space. Do the three planes, \(x+y-3z=2\text{,}\) \(2x+y+z=1\text{,}\) and \(3x + 2y-2z =0\) have a common point of intersection? If so, find one and if not, tell why there is no such point. Note that a point of intersection is a point that satisfies all three equations.
Hint 1.
The three planes give a system of three equations. A solution to the system will be the common point of intersection.
Hint 2.
To solve the system of three equations, transform the system into one that exhibits the triangular structure of Exercise 1.1.3.5.
Answer.
The three planes do not have a common point of intersection because the system of equations is inconsistent, it has no solution.
Solution.
We start with the system of three equations.
\begin{align*} x + y -3z \amp = \amp 2\\ 2x + y +z \amp = \amp 1\\ 3x + 2y -2z \amp = \amp 0 \end{align*}
To transform this system into one that exhibits a triangular structure we must first eliminate the variable \(x \) from the third equation. We may do to this by subtracting (3) times the first row from the third row.
\begin{align*} x + y -3z \amp = 2 \amp \hspace{.2in}\\ 2x + y +z \amp = 1 \amp\\ -y +7z \amp = -6 \amp R_3-3R1 \end{align*}
Next, we can eliminate the variable \(x \) from the second equation. We may do this by subtracting (2) times the first row from the second row.
\begin{align*} x + y -3z \amp = 2 \amp \hspace{.2in}\\ -y +7z \amp = -3 \amp R_2-2R_1\\ -y +7z \amp = -6 \amp \end{align*}
Lastly, notice that subtracting the last two equations gives a contradiction, 0 is certainly not equal to -3.
\begin{align*} x + y -3z \amp = 2 \amp \hspace{.2in}\\ -y +7z \amp = -3 \amp \\ 0\amp = -3 \amp R_3 - R_2 \end{align*}
Therefore, the system does not have a solution and so the three planes do not have a common point of intersection.

3.

Find a quadratic \(a +bx +cx^2\) such that the graph of \(y = a + bx + cx^2\) contains the points \((-1,6)\text{,}\) \((2,0)\text{,}\) and \((3,2)\text{.}\)
Hint.
For some fixed value of \(a,b \) and \(c, \) each of the points,\((-1,6)\text{,}\) \((2,0)\text{,}\) and \((3,2)\text{,}\) is a solution to the quadratic equation \(y = a + bx + cx^2\text{.}\)
Answer.
\begin{equation*} 2-3x+x^2 \end{equation*}
Solution.
Each of the points,\((-1,6)\text{,}\) \((2,0)\text{,}\) and \((3,2)\text{,}\) is a solution to the quadratic equation \(y = a + bx + cx^2\text{,}\) which means that each of those values of \(x \) and \(y \) satisfies the equation. This creates a system of three equations with three variables \(a,b \) and \(c \text{.}\)
\begin{align*} a -b +c \amp = 6\\ a + 2b + 4c \amp = 0\\ a + 3b + 9c \amp = 2 \end{align*}
Rewriting this system as an augmented matrix,
\begin{equation*} \matr{ccc|c}{1\amp -1\amp 1\amp 6\\ 1 \amp 2 \amp 4 \amp 0 \\ 1 \amp 3 \amp 9 \amp 2} \end{equation*}
At this point, we may perform row operations to transform this augmented matrix into a triangular form. Our first task is to eliminate the lower left term. We may do this by subtracting row 2 from row 1.
\begin{align*} \matr{ccc|c}{1\amp -1\amp 1\amp 6\\ 1 \amp 2 \amp 4 \amp 0 \\ 0 \amp 1 \amp 5 \amp 2} \amp \hspace{.25in} R_3 - R_2 \to R_3 \end{align*}
Next, we may eleminate the left most entry of the middle row by subtracting row 1 from row 2.
\begin{align*} \matr{ccc|c}{1\amp -1\amp 1\amp 6\\ 0 \amp 3 \amp 3 \amp -6 \\ 0 \amp 1 \amp 5 \amp 2} \amp \hspace{.25in} R_2 - R_1 \to R_2 \end{align*}
Next, we simplify the second row by multiplying by \(\frac{1}{3} .\) This step is not necessary for getting the matrix to triangular form, it just makes things simpler.
\begin{align*} \matr{ccc|c}{1\amp -1\amp 1\amp 6\\ 0 \amp 1 \amp 1 \amp -2 \\ 0 \amp 1 \amp 5 \amp 2} \amp \hspace{.25in} \frac{1}{3}R_2 \to R_2 \end{align*}
Our last step to write this augmented matrix in triangular form is to eliminate the middle term of the last row. We may do this by subtracting row 2 from row 3.
\begin{align*} \matr{ccc|c}{1\amp -1\amp 1\amp 6\\ 0 \amp 1 \amp 1 \amp -2 \\ 0 \amp 0 \amp 4 \amp 4} \amp \hspace{.25in} R_3-R_3 \to R_3 \end{align*}
Now, we can solve the system by back substitution.
\begin{align*} a -b +c \amp = 6\\ b + c \amp = -2\\ 4c \amp = 4 \end{align*}
Substitution \(c =1 \) into the second equation gives \(b = -3. \) Finally, substituting both \(b \) and \(c \) into the first equation and solving for \(a, \) yields the final solution \(a = 2, b = -3, c = 1 \text{.}\) Just for fun, we may graph the parabola \(y = 2 -3 x + x^2 \) to verify that it indeed does contain the points given.

4.

Which of the following matrices are in reduced row-echelon form? Which are in row-echelon form?

  1. \(\displaystyle \begin{bmatrix} 1\amp -1 \amp 2\\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 1 \end{bmatrix}\)

  2. \(\displaystyle \begin{bmatrix} 1 \amp 0 \amp 2 \amp 0 \\ 0 \amp 0 \amp 1 \amp 3 \\ 0 \amp 1 \amp 4 \amp -2 \end{bmatrix}\)

  3. \(\displaystyle \begin{bmatrix}1\amp -2 \amp 3 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \end{bmatrix}\)

  4. \(\displaystyle \begin{bmatrix} 1\amp 0 \amp 0 \amp 3 \amp 1 \\ 0 \amp 0 \amp 0 \amp 1 \amp 1\\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \end{bmatrix}\)

  5. \(\displaystyle \begin{bmatrix} 1 \amp 1 \\ 0 \amp 1\end{bmatrix}\)

  6. \(\displaystyle \begin{bmatrix} 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 1 \end{bmatrix}\)

Hint.
See Definition 1.2.8 for the definition of REF and Definition 1.2.11 for the definition of RREF.
Answer.

  1. Neither in REF nor in RREF.

  2. Neither in REF not in RREF.

  3. In RREF.

  4. In REF, but not in RREF.

  5. In REF, but not in RREF.

  6. Neither in REF nor in RREF.

Solution.

  1. The matrix is not in REF: The zero row is not at the bottom.

  2. The matrix is not in REF: The leading entry of the second row has a non-zero entry below and left of it.

  3. The matrix is in RREF as it satisfies all of the requirements of Definition 1.2.11.

  4. The matrix is in REF, but not in RREF: The fourth column, which contains a leading \(1\) in the second row, has a non-zero entry (\(3\)).

  5. The matrix is in REF, but not in RREF: The second column, which contains a leading \(1\) in the second row, has a non-zero entry (\(1\)).

  6. The matrix is not in REF: The leading entry of the second row (\(1\) in the \((2, 3)\)-entry) is not strictly to the right of the leading entry of the first row (\(1\) in the \((1, 3)\)-entry). In particular, the matrix is not in RREF.

5.

Give two distinct echelon form versions of this matrix.
\begin{equation*} \begin{bmatrix} 2 \amp 1 \amp 1 \amp 3 \\ 6 \amp 4 \amp 1 \amp 2 \\ 1 \amp 5 \amp 1 \amp 5 \end{bmatrix} \end{equation*}
Hint.
See Definition 1.2.8 for the definition of REF.
Answer.
\begin{equation*} \begin{bmatrix} 1 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 1 \amp -2 \amp -7 \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix} \quad\text{ and }\quad \begin{bmatrix} 1 \amp 0 \amp 0 \amp \frac{-10}{19} \\ 0 \amp 1 \amp 0 \amp \frac{7}{19} \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix} \end{equation*}
(There are many other solutions, since the REF is not unique.)
Solution.
We start by row reducing from top to bottom:
\begin{align*} \begin{bmatrix} 2 \amp 1 \amp 1 \amp 3 \\ 6 \amp 4 \amp 1 \amp 2 \\ 1 \amp 5 \amp 1 \amp 5 \end{bmatrix} \overset{-3R_{1}+R_{2}}{\underset{-R_{1}+2R_{3}}{\longrightarrow}} \amp\begin{bmatrix} 2 \amp 1 \amp 1 \amp 3 \\ 0 \amp 1 \amp -2 \amp -7 \\ 0 \amp 9 \amp 1 \amp 7 \end{bmatrix}\\ \overset{-9R_{2} + R_{3}}{\underset{\frac{1}{2}R_{1}}{\longrightarrow}} \amp\begin{bmatrix} 1 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 1 \amp -2 \amp -7 \\ 0 \amp 0 \amp 19 \amp 70 \end{bmatrix}\\ \overset{\frac{1}{19}R_{3}}{\longrightarrow} \amp\begin{bmatrix} 1 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 1 \amp -2 \amp -7 \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix}. \end{align*}
We have arrived at a matrix in REF. (Actually, the second-to-last matrix above is already in REF). Since we are supposed to give two answers, we continue:
\begin{align*} \begin{bmatrix} 1 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 1 \amp -2 \amp -7 \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix} \overset{2R_{3}+R_{2}}{\longrightarrow} \begin{bmatrix} 1 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 1 \amp 0 \amp \frac{7}{19} \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix}. \end{align*}
Since we were not asked for a matrix in RREF, we could stop here and have our second answer. But instead, we might as well continue to manipulate our matrix to arrive at RREF:
\begin{align*} \begin{bmatrix} 1 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 1 \amp 0 \amp \frac{7}{19} \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix} \overset{-\frac{1}{2}R_{2}+R_{1}}{\longrightarrow} \amp\begin{bmatrix} 1 \amp 0 \amp \frac{1}{2} \amp \frac{25}{19} \\ 0 \amp 1 \amp 0 \amp \frac{7}{19} \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix}\\ \overset{-\frac{1}{2}R_{3} + R_{1}}{\longrightarrow} \amp\begin{bmatrix} 1 \amp 0 \amp 0 \amp \frac{-10}{19} \\ 0 \amp 1 \amp 0 \amp \frac{7}{19} \\ 0 \amp 0 \amp 1 \amp \frac{70}{19} \end{bmatrix}. \end{align*}

6.

Row reduce the following matrix to obtain a row-echelon form. Then continue to obtain the reduced row-echelon form.
\begin{equation*} \begin{bmatrix} 2 \amp -1 \amp 3 \amp -1 \\ 1 \amp 0 \amp 2 \amp 1 \\ 1 \amp -1 \amp 1 \amp -2 \end{bmatrix}. \end{equation*}
Hint.
See Definition 1.2.8 for the definition of REF and Definition 1.2.11 for the definition of RREF.
Answer.
There are many answers for the REF, for example
\begin{equation*} \begin{bmatrix} 1 \amp -\frac{1}{2} \amp \frac{3}{2} \amp -\frac{1}{2} \\ 0 \amp 1 \amp 1 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}. \end{equation*}
As always, the RREF is unique, and in this case, it is given by
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 2 \amp 1 \\ 0 \amp 1 \amp 1 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}. \end{equation*}
Solution.
\begin{align*} \begin{bmatrix} 2 \amp -1 \amp 3 \amp -1 \\ 1 \amp 0 \amp 2 \amp 1 \\ 1 \amp -1 \amp 1 \amp -2 \end{bmatrix} \overset{-\frac{1}{2}R_{1} + R_{2}}{\underset{-\frac{1}{2}R_{1} + R_{3}}{\longrightarrow}} \amp \begin{bmatrix} 2 \amp -1 \amp 3 \amp -1 \\ 0 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp -\frac{1}{2} \amp -\frac{1}{2} \amp -\frac{3}{2} \end{bmatrix}\\ \overset{\frac{1}{2}R_{1}}{\underset{R_{2}+R_{3}}{\longrightarrow}} \amp \begin{bmatrix} 1 \amp -\frac{1}{2} \amp \frac{3}{2} \amp -\frac{1}{2} \\ 0 \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{3}{2} \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}\\ \overset{2R_{2}}{\longrightarrow} \amp \begin{bmatrix} 1 \amp -\frac{1}{2} \amp \frac{3}{2} \amp -\frac{1}{2} \\ 0 \amp 1 \amp 1 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}. \end{align*}
We have arrived at a matrix in REF. To get it into RREF, we need to make sure that any column with a leading \(1\) has no other non-zero entries, so:
\begin{equation*} \begin{bmatrix} 1 \amp -\frac{1}{2} \amp \frac{3}{2} \amp -\frac{1}{2} \\ 0 \amp 1 \amp 1 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}. \overset{\frac{1}{2}R_{2} + R_{1}}{\longrightarrow} \begin{bmatrix} 1 \amp 0 \amp 2 \amp 1 \\ 0 \amp 1 \amp 1 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}. \end{equation*}

7.

List the reduced row-echelon forms possible for each size.

  1. \(\displaystyle 2 \times 2\)

  2. \(\displaystyle 2 \times 3\)

  3. \(\displaystyle 3 \times 2\)

  4. \(\displaystyle 3 \times 3\)

Answer.
In the following, \(\ast\) can be any number.

  1. \begin{equation*} \begin{bmatrix} 0 \amp 0 \\ 0 \amp 0 \end{bmatrix} , \begin{bmatrix} 1 \amp \ast \\ 0 \amp 0 \end{bmatrix} \begin{bmatrix} 0 \amp 1 \\ 0 \amp 0 \end{bmatrix} , \begin{bmatrix} 1 \amp 0 \\ 0 \amp 1 \end{bmatrix}. \end{equation*}

  2. \begin{align*} \begin{bmatrix} 0 \amp 0 \amp 0 \\ 0 \amp 0\amp 0 \end{bmatrix}, \begin{bmatrix} 1 \amp \ast \amp \ast \\ 0 \amp 0\amp 0 \end{bmatrix} , \begin{bmatrix} 0 \amp 1 \amp \ast \\ 0 \amp 0\amp 0 \end{bmatrix} , \begin{bmatrix} 0 \amp 0 \amp 1 \\ 0 \amp 0\amp 0 \end{bmatrix},\\ \begin{bmatrix} 1 \amp 0 \amp \ast \\ 0 \amp 1 \amp \ast \end{bmatrix} , \begin{bmatrix} 1 \amp \ast \amp 0 \\ 0 \amp 0 \amp 1 \end{bmatrix}. \begin{bmatrix} 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \end{bmatrix}. \end{align*}

  3. \begin{equation*} \begin{bmatrix} 0 \amp 0 \\ 0 \amp 0 \\ 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 1 \amp \ast \\ 0 \amp 0 \\ 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 0 \amp 1 \\ 0 \amp 0 \\ 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 1 \amp 0 \\ 0 \amp 1 \\ 0 \amp 0 \end{bmatrix}. \end{equation*}

  4. \begin{align*} \begin{bmatrix} 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 1 \amp \ast \amp \ast \\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 0 \amp 1 \amp \ast \\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \end{bmatrix},\\ \begin{bmatrix} 1 \amp 0 \amp \ast \\ 0 \amp 1 \amp \ast \\ 0 \amp 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 1 \amp \ast \amp 0 \\ 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0 \end{bmatrix}, \begin{bmatrix} 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \end{bmatrix}. \end{align*}

8.

Prove that each of the three row operations is reversible. More precisely, if the matrix \(B\) is obtained from \(A\) by application of a single row operation, show that there is a single row operation that will transform B back into \(A\text{.}\)
Hint.
The three row operations are given by:

  1. Swap the locations of row \(i\) with row \(j\text{:}\) \(R_{i} \leftrightarrow R_{j}\text{.}\)

  2. Multiply each entry of a single row \(i\) by a nonzero quantity \(\alpha\text{:}\) \(\alpha R_{i}\text{.}\)

  3. Multiply each entry of one row \(R_{i}\) by some quantity \(\alpha\text{,}\) and add these values to the entries in the same columns of a second row \(R_{j}\) (where \(i\neq j\)). Leave the first row the same after this operation (i.e. \(R_{i}\) remains unchanged), but replace the second row by the new values (i.e. row \(j\) is new): \(R_{j} + \alpha R_{i}\text{.}\)

Solution.
First, assume that \(B \overset{R_{i}\leftrightarrow R_{j}}{\longrightarrow} A\text{.}\) Then \(A \overset{R_{j}\leftrightarrow R_{i}}{\longrightarrow} B\text{,}\) so the first row operation is invertible. To be more precise, the first row operation is its own inverse. Next, assume that \(B \overset{\alpha R_{i}}{\longrightarrow} A\text{.}\) For this to be a legitimate row operation, we must have \(\alpha\neq 0\text{.}\) In particular, \(\frac{1}{\alpha}\) exists and \(A \overset{\frac{1}{\alpha} R_{i}}{\longrightarrow} B\) is also a legitimate row operation. Thus, the row operation of multiplication by \(\alpha\) is invertible with inverse the row operation of multiplication by \(\frac{1}{\alpha}\text{.}\) Lastly, assume that \(B \overset{R_{j} + \alpha R_{i}}{\longrightarrow} A\text{.}\) If \(\alpha = 0 \) or row \(i\) in \(B\) is a zero-row, then the operation does nothing and \(B=A\text{.}\) If \(\alpha\neq 0\) and row \(i\) in \(B\) is not a zero-row, then \(A\) differs from \(B\) exactly in row \(j\text{;}\) in particular, row \(i\) is the same in \(A\) and \(B\text{.}\) We see from this that \(A \overset{R_{j} -\alpha R_{i}}{\longrightarrow} B\) inverts the row operation.

9.

Prove Fact Fact 1.2.16. That is, show that \(A\) is row equivalent to \(B\) if and only if \(\RREF(A) = \RREF(B)\text{.}\)
Hint.
For the forward direction, notice that by Fact 1.2.14 there is only one matrix in reduced row echelon form that is row equivalent to \(A\text{,}\) so to show \(\RREF(A)=\RREF(B)\) it is sufficient to show that \(A\) is row equivalent to \(\RREF(B)\text{.}\) For the backward direction, the result from Exercise 1.2.4.8 can help you get from \(\RREF(B)\) back to \(B\text{.}\)
Solution.

Suppose that \(A\) is row equivalent to \(B\text{.}\) This means that there is a sequence of row operations that will take us from \(A\) to \(B\text{.}\) Another sequence of row operations (such as the ones from the Gauss-Jordan algorithm) will take us from \(B\) to \(\RREF(B)\text{.}\) Put together, this gives us a sequence starting at \(A\) and ending at \(\RREF(B)\text{,}\) so \(A\) is row equivalent to \(\RREF(B)\text{.}\) Now \(\RREF(B)\) is in reduced row echelon form, and Fact 1.2.14 says that the only matrix row equivalent to \(A\) that is in reduced row echelon form is \(\RREF(A)\text{,}\) so we must have \(\RREF(A) = \RREF(B)\text{.}\)

For the other direction, suppose that \(\RREF(A) = \RREF(B)\text{.}\) We have a sequence of row operations taking \(A\) to \(\RREF(A) = \RREF(B)\text{.}\) We have another sequence taking us from \(B\) to \(\RREF(B)\text{,}\) and Exercise 1.2.4.8 tells us that we can reverse each of these operations, which means that we can get a sequence taking us from \(\RREF(B)\) back to \(B\text{.}\) Put together this gives us a sequence from \(A\) to \(B\text{,}\) so \(A\) is row equivalent to \(B\text{.}\)