Subsection Prepare
Performing elementary row operations on an augmented matrix resulted in a new linear system whose solution was the same as the original linear system. This brings to mind two good questions:
What is the goal of using elementary row operations?
How do we achieve that goal the fastest?
We’ll answer the first question first. In
Section 1.3, when we manipulated matrices to find solutions, we were in fact putting the matrix into
reduced row echelon form.
Definition 1.4.1. Reduced Row Echelon Form.
A matrix is in reduced row echelon form if its entries satisfy all four of the following conditions.
The first nonzero entry in each row is a \(1\) (called a leading \(1\)).
Each leading \(1\) comes in a column to the right of the leading \(1\)’s in rows above it.
All rows of all \(0\)’s come at the bottom of the matrix.
If a column contains a leading \(1\text{,}\) then all other entries in that column are \(0\text{.}\)
A matrix that satisfies the first three conditions is said to be in row echelon form.
Activity 1.4.2. RREF or not?
For each of the following matrices, say whether they are in reduced row echelon form or not.
(a)
\begin{equation*}
\left[\begin{array}{cc} 1\amp 0\\0\amp 1
\end{array} \right]
\end{equation*}
Reduced row echelon form
Correct!
Not in reduced row echelon form
The first nonzero entry in each row is a \(1\text{,}\) each leading 1 appears down and to the right from the previous leading 1, and all the entries in the same column as a leading 1 are \(0\text{.}\)
(b)
\begin{equation*}
\left[\begin{array}{ccc} 1\amp 0\amp 1\\0\amp 1\amp 2
\end{array} \right]
\end{equation*}
Reduced row echelon form
Correct!
Not in reduced row echelon form
-
The first nonzero entry in each row is a \(1\text{,}\) each leading 1 appears down and to the right from the previous leading 1, and all the entries in the same column as a leading 1 are \(0\text{.}\)
The third column does not have a leading 1 in it, but that’s okay; the conditions for rref don’t say that every column has to contain a leading 1.
(c)
\begin{equation*}
\left[\begin{array}{cc} 0\amp 0\\0\amp 0
\end{array} \right]
\end{equation*}
Reduced row echelon form
Correct!
Not in reduced row echelon form
The rref conditions don’t say that leading 1’s have to exist; the conditions say that if nonzero entries are present, then leading 1’s have to be in certain relative positions.
(f)
\begin{equation*}
\left[\begin{array}{cccc} 1\amp 2\amp 0\amp 0 \\0\amp 0\amp 3\amp 0\\0\amp 0\amp 0\amp 4
\end{array} \right]
\end{equation*}
Reduced row echelon form
The first nonzero entry of the second row is \(3\text{,}\) and it needs to be \(1\) to be in rref. (The third row fails this condition also).
Not in reduced row echelon form
Correct!
(g)
\begin{equation*}
\left[\begin{array}{cccccc} 0\amp 1\amp 2\amp 3\amp 0\amp 4\\
0\amp 0\amp 0\amp 0\amp 1\amp 5\\0\amp 0\amp 0\amp 0\amp 0\amp 0 \end{array} \right]
\end{equation*}
Reduced row echelon form
Correct!
Not in reduced row echelon form
The first, third, fourth, and sixth columns do not have a leading 1 in them, and that means that the other entries in those columns don’t have to be \(0\text{.}\)
(h)
\begin{equation*}
\left[\begin{array}{ccc} 1\amp 1\amp 0\\ 0\amp 1\amp 0\\0\amp 0\amp 1 \end{array} \right]
\end{equation*}
Reduced row echelon form
The second column has a leading \(1\) in it (from the second row), and that means all the other entries in that column have to be \(0\text{.}\)
Not in reduced row echelon form
Correct!
We began this section with two questions, “Where do we go?” and “How do we get there quickly?” We’ve just answered the first question: most of the time we are going to reduced row echelon form. We now address the second question.
There are many ways to use elementary row operations to transform a matrix into reduced row echelon form, but there is a general technique that is efficient and doesn’t waste time on unnecessary steps. This technique is called Gauss-Jordan elimination, named in honor of the mathematicians Karl Friedrich Gauss and Wilhelm Jordan.
Gauss-Jordan Elimination.
Gauss-Jordan elimination is the technique for finding the reduced row echelon form of a matrix using the procedure summarized below:
Create a leading \(1\text{.}\)
Use this leading \(1\) to put zeros underneath it.
Repeat the above steps until all possible rows have leading \(1\)’s.
Put zeros above these leading \(1\)’s.
This is roughly what we were already doing in previous sections when we used elimination and row operations, but let’s see an example.
Example 1.4.3. Gauss-Jordan Elimination Demonstrated.
Put the augmented matrix of the following system of linear equations into reduced row echelon form.
\begin{equation*}
\begin{array}{ccccccc} -3x_1\amp -\amp 3x_2\amp +\amp 9x_3\amp =\amp 12\\ 2x_1\amp +\amp 2x_2\amp -\amp 4x_3\amp =\amp -2\\ \amp \amp -2x_2\amp -\amp 4x_3\amp =\amp -8 \end{array}
\end{equation*}
We start by converting the linear system into an augmented matrix.
\begin{equation*}
\left[\begin{array}{cccc} \fbox{-3}\amp -3\amp 9\amp 12\\ 2\amp 2\amp -4\amp -2\\0\amp -2\amp -4\amp -8 \end{array} \right]
\end{equation*}
Our first step is to make the first entry in the first row a \(1\text{.}\) We do this by multiplying Row 1 by \(-\frac13\text{.}\) (This row operation is also called “scaling.”)
\(-\frac13R_1\rightarrow R_1\)
\(\left[\begin{array}{cccc} \fbox{1}\amp 1\amp -3\amp -4\\ 2\amp 2\amp -4\amp -2\\0\amp -2\amp -4\amp -8
\end{array} \right]\)
Our next step is to put zeros under this \(1\text{.}\) To create a \(0\) for the first entry in the second row, we’ll use the “multiply and add” elementary row operation.
\(-2R_1+R_2\rightarrow R_2\)
\(\left[\begin{array}{cccc} 1\amp 1\amp -3\amp -4\\ 0\amp \fbox{0}\amp 2\amp 6\\0\amp -2\amp -4\amp -8
\end{array} \right]\)
The first entry in the third row is already \(0\text{,}\) so our first column looks good for reduced row echelon form. We now shift our focus from the leading \(1\) down and to the right, to the position that is boxed.
We want to put a \(1\) in this position, but we need to restrict ourselves to using only the second row and any rows below it, as using the first row would put nonzero entries back into the first column and undo the work we just did. Let’s first swap Row 2 and Row 3, and then scale the new second row (multiply it by a number) so that there is a \(1\) in the desired position.
\(R_2\leftrightarrow R_3\)
\(\left[\begin{array}{cccc} 1\amp 1\amp -3\amp -4\\0\amp \fbox{-2}\amp -4\amp -8 \\0\amp 0\amp 2\amp 6
\end{array} \right]\)
\(-\frac12R_2\rightarrow R_2\)
\(\left[\begin{array}{cccc} 1\amp 1\amp -3\amp -4\\0\amp 1\amp 2\amp 4 \\0\amp 0\amp \fbox{2}\amp 6
\end{array} \right]\)
We have now created another leading \(1\text{,}\) this time in the second row. Our next desire is to put \(0\)’s underneath it, but that’s already done! Therefore we again shift our attention down and to the right to the next position in a box. We want that to be a \(1\text{,}\) and so we multiply the row by \(\frac{1}{2}\text{.}\)
\(\frac12R_3\rightarrow R_3\)
\(\left[\begin{array}{cccc} 1\amp 1\amp -3\amp -4\\0\amp 1\amp 2\amp 4 \\0\amp 0\amp 1\amp 3
\end{array} \right]\)
This ends what we will refer to as the forward steps. Our next task is to use the "multiply and add" row operation to put zeros above the leading \(1\)’s. This is referred to as the backward steps.
\begin{align*}
-2R_3+R_2 \amp \rightarrow R_2\\
3R_3+R_1 \amp \rightarrow R_1
\end{align*}
\(\left[\begin{array}{cccc} 1\amp 1\amp 0\amp 5\\0\amp 1\amp 0\amp -2 \\0\amp 0\amp 1\amp 3
\end{array} \right]\)
\(-R_2+R_1\rightarrow R_1\)
\(\left[\begin{array}{cccc} 1\amp 0\amp 0\amp 7\\0\amp 1\amp 0\amp -2 \\0\amp 0\amp 1\amp 3
\end{array} \right]\)
This matrix is now in reduced row echelon form, and we can read off the solution to the original linear system as \(x_1 = 7\text{,}\) \(x_2 = -2\) and \(x_3 = 3\text{.}\)
We now summarize and try to formalize the steps we performed.
Forward Steps
Start at the top left corner.
If the entry in the row and column that we are considering is \(0\text{,}\) swap rows with a row below the current row so that the entry is nonzero. If this entry is \(0\) and all entries below are \(0\text{,}\) we are done with this column; move to the right and do this step again.
Since the entry we are considering is nonzero, multiply the current row by a number (“scale the row”) to make its first entry a \(1\text{.}\)
Repeatedly use the “multiply and add” row operation to put \(0\)’s underneath the leading \(1\text{.}\)
Move down and to the right. Go back to step 2 and work on the new rows and columns until you run out of either rows or columns.
The above steps accomplish the following things:
The first nonzero entry in each row is a \(1\text{.}\)
Each leading \(1\) is in a column to the right of the leading \(1\)’s above it.
All rows of all \(0\)’s come at the bottom of the matrix.
Note that this means we have just put a matrix into row echelon form. The next steps finish the conversion into reduced row echelon form.
Backward Steps
Starting from the bottom rightmost leading \(1\text{,}\) use the “multiply and add” row operation repeatedly to put zeros above the leading \(1\text{.}\)
Continue this process by moving up and to the left to the next leading \(1\text{,}\) repeatedly use “multiply and add” to put zeros above the leading \(1\text{.}\) Repeat this step until every leading \(1\) has zeros above in all the rows.
By following these “Forward and Backward Steps”, we make use of the presence of zeros to make the computations easier and more efficient.
Many authors call the forward steps Gaussian elimination, which puts a matrix into row echelon form, and the forward-and-backward steps together Gauss-Jordan elimination, which puts a matrix into reduced row echelon form. We will almost always want to obtain reduced row echelon form and will not make a big deal about the distinction between the names Gaussian and Gauss-Jordan.
Activity 1.4.4. Gauss-Jordan Steps.
Answer the following questions about using Gauss-Jordan elimination, which entries to work on next and what row operations to perform.
(a)
Given the matrix
\begin{equation*}
A=\begin{bmatrix} \fbox{2} \amp 4 \amp 6\amp -2 \\ 1 \amp -1 \amp -1 \amp -1 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
the Gauss-Jordan algorithm starts by turning the \(2\) that is entry \(a_{11}\text{,}\) into a \(1\text{.}\) Which row operation do we use?
Scaling (multiplying a row by a nonzero number)
Correct!
Swapping rows
Swapping Row 1 and Row 2 would actually work for this matrix, and we’d end up in the same rref eventually. But part of the beauty of the Gauss-Jordan procedure is that following the prescribed steps of the algorithm always works, and swapping two rows won’t always work to turn a \(2\) into a \(1\text{.}\)
Multiply and add
We use the “multiply and add” row operation when we are trying to get \(0\)’s, not when our goal is to get a \(1\text{.}\)
(b)
Given the matrix
\begin{equation*}
B=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ 1 \amp -1 \amp -1 \amp -1 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
which entry do we focus on turning into a \(1\) or \(0\) next?
\(b_{11}\)
\begin{equation*}
B=\begin{bmatrix} \fbox{1} \amp 2 \amp 3\amp -1 \\ 1 \amp -1 \amp -1 \amp -1 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
This entry is already a \(1\) as required by the Gauss-Jordan method.
\(b_{21}\)
\begin{equation*}
B=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ \fbox{1} \amp -1 \amp -1 \amp -1 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
Correct! We need to turn the entries below the leading \(1\) in Row 1 into \(0\)’s.
\(b_{12}\)
\begin{equation*}
B=\begin{bmatrix} 1 \amp \fbox{2} \amp 3\amp -1 \\ 1 \amp -1 \amp -1 \amp -1 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
No, we finish putting \(0\)’s below the leading \(1\) in the first column before moving to the right.
(c)
To turn the boxed entry below into a \(0\text{,}\) which row operation do we perform?
\begin{equation*}
B=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ \fbox{1} \amp -1 \amp -1 \amp -1 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
Scaling a row
No, scaling a row means multiplying by a nonzero number which won’t result in a \(0\) if we didn’t start with a \(0\text{.}\)
Swapping rows
In this case, swapping Row 2 and Row 3 would put a \(0\) into position \(b_{21}\text{,}\) but that won’t always work, and it just moves the problem down a row.
Multiply and add
Correct! Multiplying Row 1 by \(-1\) and adding to Row 2 will create a \(0\) in position \(b_{21}\text{.}\)
(d)
To continue the Gauss-Jordan algorithm on the matrix below, which entry do we next try to turn into a \(1\) or \(0\text{?}\)
\begin{equation*}
C=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ 0 \amp -3 \amp -4 \amp 0 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix}
\end{equation*}
\(c_{12}\)
No, entry \(c_{12}\) is the entry boxed below. The Gauss-Jordan algorithm says that after finishing a column, we move down and to the right from the leading \(1\text{.}\)
\begin{equation*}
C=\begin{bmatrix} 1 \amp \fbox{2} \amp 3\amp -1 \\ 0 \amp -3 \amp -4 \amp 0 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix}
\end{equation*}
\(c_{31}\)
No, entry \(c_{31}\) is the entry boxed below. It’s already a \(0\) below a leading \(1\text{.}\)
\begin{equation*}
C=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ 0 \amp -3 \amp -4 \amp 0 \\ \fbox{0} \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
\(c_{22}\)
Correct! The next step in the Gauss-Jordan algorithm is to turn entry \(c_{22}\text{,}\) which is boxed below, into a \(1\text{.}\)
\begin{equation*}
C=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ 0 \amp \fbox{-3} \amp -4 \amp 0 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
(e)
Given the matrix
\begin{equation*}
C=\begin{bmatrix} 1 \amp 2 \amp 3\amp -1 \\ 0 \amp \fbox{-3} \amp -4 \amp 0 \\ 0 \amp 2\amp 3\amp 4 \\ \end{bmatrix},
\end{equation*}
which row operation do we use next in the Gauss-Jordan algorithm?
Scaling a row
Correct!
Swapping rows
No, swapping rows is only used when there is a \(0\) with nonzero entries below it.
Multiply and add
We use the “multiply and add” row operation when we are trying to get \(0\)’s, not when our goal is to get a \(1\text{.}\)
Let’s practice the Gauss-Jordan algorithm some more.
Example 1.4.5. Another Gauss-Jordan Elimination.
Use Gauss-Jordan elimination to put the matrix \(A\) into reduced row echelon form, where
\begin{equation*}
A = \left[\begin{array}{ccccc} -2\amp -4\amp -2\amp -10\amp 0\\2\amp 4\amp 1\amp 9\amp -2\\3\amp 6\amp 1\amp 13\amp -4 \end{array} \right]
\end{equation*}
Solution.
We start by wanting to make the entry in the first column and first row a \(1\text{.}\) To do this we’ll scale the first row by a factor of \(-\frac12\text{.}\)
\(-\frac12R_1\rightarrow R_1\)
\(\left[\begin{array}{ccccc} 1\amp 2\amp 1\amp 5\amp 0\\2\amp 4\amp 1\amp 9\amp -2\\3\amp 6\amp 1\amp 13\amp -4
\end{array} \right]\)
Next we need to put zeros in the column below this newly formed leading \(1\text{.}\)
\begin{align*}
-2R_1+R_2 \amp \rightarrow R_2\\
-3R_1+R_3 \amp \rightarrow R_3
\end{align*}
\(\left[\begin{array}{ccccc} 1\amp 2\amp 1\amp 5\amp 0\\0\amp \fbox{0}\amp -1\amp -1\amp -2\\0\amp 0\amp -2\amp -2\amp -4
\end{array} \right]\)
Our attention now shifts to the right one column and down one row to the position indicated by the box. We want to put a \(1\) in that position. Our only options are to either scale the current row or to interchange rows with a row below it. However, neither of those options will change the \(0\) into a \(1\) in this case. Therefore, we shift our attention to the right one more column, to the \(-1\text{.}\)
\begin{equation*}
\left[\begin{array}{ccccc} 1\amp 2\amp 1\amp 5\amp 0\\0\amp 0\amp \fbox{-1}\amp -1\amp -2\\0\amp 0\amp -2\amp -2\amp -4
\end{array} \right]
\end{equation*}
We want to create a leading \(1\) for this row, so we multiply by a nonzero number.
\(\left[\begin{array}{ccccc} 1\amp 2\amp 1\amp 5\amp 0\\0\amp 0\amp 1\amp 1\amp 2\\0\amp 0\amp -2\amp -2\amp -4
\end{array} \right]\)
Next we use “multiply and add” to put a \(0\) underneath this leading \(1\text{.}\)
\(2R_2+R_3\rightarrow R_3\)
\(\left[\begin{array}{ccccc} 1\amp 2\amp 1\amp 5\amp 0\\0\amp 0\amp 1\amp 1\amp 2\\0\amp 0\amp 0\amp 0\amp 0
\end{array} \right]\)
We would continue moving down and to the right, but since the third row is all \(0\)’s, and there aren’t any more rows, we are done with the forward steps.
Our next goal is to put a \(0\) above each of the leading \(1\)’s.
\(-R_2+R_1\rightarrow R_1\)
\(\left[\begin{array}{ccccc} 1\amp 2\amp 0\amp 4\amp -2\\0\amp 0\amp 1\amp 1\amp 2\\0\amp 0\amp 0\amp 0\amp 0
\end{array} \right]\)
This final matrix is in reduced row echelon form.
Example 1.4.6. Gauss-Jordan Elimination Again, this time with fewer words.
Put the matrix
\begin{equation*}
\left[\begin{array}{cccc} 1\amp 2\amp 1\amp 3\\2\amp 1\amp 1\amp 1\\3\amp 3\amp 2\amp 1 \end{array} \right]
\end{equation*}
into reduced row echelon form.
Solution.
Here we will show all steps without explaining each one.
\begin{align*}
-2R_1+R_2 \amp \rightarrow R_2\\
-3R_1+R_3 \amp \rightarrow R_3
\end{align*}
\(\left[\begin{array}{cccc} 1\amp 2\amp 1\amp 3\\0\amp -3\amp -1\amp -5\\0\amp -3\amp -1\amp -8
\end{array} \right]\)
\(-\frac13R_2\rightarrow R_2\)
\(\left[\begin{array}{cccc} 1\amp 2\amp 1\amp 3\\0\amp 1\amp 1/3\amp 5/3\\0\amp -3\amp -1\amp -8
\end{array} \right]\)
\(3R_2+R_3\rightarrow R_3\)
\(\left[\begin{array}{cccc} 1\amp 2\amp 1\amp 3\\0\amp 1\amp 1/3\amp 5/3\\0\amp 0\amp 0\amp -3
\end{array} \right]\)
\(-\frac13R_3\rightarrow R_3\)
\(\left[\begin{array}{cccc} 1\amp 2\amp 1\amp 3\\0\amp 1\amp 1/3\amp 5/3\\0\amp 0\amp 0\amp 1
\end{array} \right]\)
\begin{align*}
-3R_3+R_1 \amp \rightarrow R_1\\
-\frac53R_3+R_2 \amp \rightarrow R_2
\end{align*}
\(\left[\begin{array}{cccc} 1\amp 2\amp 1\amp 0\\0\amp 1\amp 1/3\amp 0\\0\amp 0\amp 0\amp 1
\end{array} \right]\)
\(-2R_2+R_1\rightarrow R_1\)
\(\left[\begin{array}{cccc} 1\amp 0\amp 1/3\amp 0\\0\amp 1\amp 1/3\amp 0\\0\amp 0\amp 0\amp 1
\end{array} \right]\)
We were inspired by solving systems of linear equations to put matrices into reduced row echelon form, in order to make the solution easy to see. Every time we’ve started with a linear system, there was exactly one solution, and the reduced row echelon form always had one particular form. However, we’ve also practiced putting matrices in reduced row echelon form without referring back to their corresponding system of linear equations, and we have seen various different ways that the reduced row echelon form of a matrix can look. Connecting different reduced row echelon forms with solutions to the corresponding linear system is the topic for next section.
Reading Questions Reading Questions
1. Gauss-Jordan Elimination.
Describe how to perform Gauss-Jordan elimination in your own words.
If it helps you to describe the process, you can make up a specific matrix to use, or use an arbitrary one like \(\begin{bmatrix} a_{11} \amp a_{12} \amp a_{13} \\ a_{21} \amp a_{22} \amp a_{23} \\ a_{31} \amp a_{32} \amp a_{33} \\ \end{bmatrix}\text{.}\)
2. Parsons Problem, Reduced Row Echelon Form.
3. Reflection.
Enter a response to both of the following tasks:
Ask a question about the material, either about something you’re not sure you fully understand, or a “what if” question.
Give a percentage from 0 to 100 that reflects how confident you are with the material you just read about, and give one sentence as to why you feel that way. 0 means you didn’t actually do the reading and 100 means that everything makes sense so far and you think you are completely ready to engage with the material more deeply.
