Discussion Question
Using echelon form, can you explain why every linear system must have either a unique solution, no solutions, or infinitely many solutions?
Today we'll discuss an extension of Gaussian elimination called Gauss-Jordan elimination, which transforms a matrix to an even simpler state known as reduced (row) echelon form. Then, we'll examine what Gaussian elimination and Gauss-Jordan elimination look like geometrically.
In class on Wednesday, we defined echelon form only for augmented matrices (that is, matrices where the last column is separated from the others by a vertical line). I just wanted to point out that we can (and should!) define echelon form for matrices in general. (In fact, an "augmented" matrix is not actually that distinct from a general matrix; the vertical line is really only there as a notational aid.)
Definition
A matrix is in echelon form if, when reading its rows from top to bottom, the pivots in each row go strictly from left to right. (All rows of all zeros must be at the bottom of the matrix.)
Having this notion of echelon form (and the related notion of reduced echelon form, discussed below) will help us in several situations in this class, besides just solving linear systems.
Let's consider the following linear system:
\[\left\{ \begin{array} \ 2x_1 &-& x_2 &+& x_3 &=& 6 \\ && x_2 &+& 2x_3 &=& 4 \end{array} \right..\]
This system is in echelon form, with leading variables \(x_1\) and \(x_2\) for its two equations, respectively. The corresponding augmented matrix is
\[A = \left( \begin{matrix} 2 & -1 & 1 \\ 0 & 1 & 2 \end{matrix} \; \left| \; \begin{matrix} 6 \\ 4 \end{matrix} \right. \right).\]
This matrix is also in echelon form. As we discussed last time, systems in echelon form are easy to solve (via back-substitution). However, echelon form also has a couple of disadvantages:
This non-uniqueness of echelon form is an example of something that often irks mathematicians: because the echelon form is not unique, there's no way to define a "function" that takes in a matrix and outputs its echelon form. Furthermore, many matrices in echelon form still don't feel quite as "simple" as they could be. Notice that in the matrix \(A\) above, we could add the second row to the first row and make the entry \(A_{1,2}\) become zero. For these reasons, it will be very helpful to have the following notion:
Definition
A matrix is in reduced echelon form if all of the following are true:
(i) It is in echelon form.
(ii) Every pivot entry is equal to \(1\).
(iii) In every column that has a pivot entry, all the other entries are zero.
For example, the following matrix is in reduced echelon form:
\[\begin{pmatrix} 1 & -2 & 0 & 3 \\ 0 & 0 & 1 & 5 \end{pmatrix}.\]
Notice that if we were to multiply either row by a constant, then the resulting matrix would violate (ii), and not be in reduced echelon form. If instead, we added a multiple of one row to the other, then the result would violate either (i) or (iii) (or both!), and again it would not be in reduced echelon form.
In fact, the following result is true:
Theorem
The reduced echelon form of a matrix is always unique.
That is, starting from any matrix, no matter what sequence of row operations you perform, there is only one possible matrix in reduced echelon form you can get to. (In situations like this, we often call such an object "canonical": thus, the reduced echelon form of a matrix is a canonical object associated to that matrix. In fact, some people call the reduced echelon form the row canonical form!)
Definition
Given a matrix \(A\), we will write \(\text{rref}(A)\) to mean the unique matrix in row echelon form which can be obtained from \(A\) by doing row operations.
Note: Why "rref" and not just "ref"? This is because many people refer to echelon form as "row echelon form", and so they refer to reduced echelon form as "reduced row echelon form" (or possibly "row reduced echelon form"). Be careful of this difference if you are ever talking about linear algebra elsewhere!
We can now talk about Gauss-Jordan elimination, which extends Gaussian elimination by going further than echelon form to reduced echelon form. In other words, Gauss-Jordan elimination is a procedure that takes as input any matrix \(A\) and outputs its reduced echelon form, \(\text{rref}(A)\).
To see how Gauss-Jordan elimination works, let's try an example:
Example
Consider the matrix in echelon form from above:
\[A = \begin{pmatrix} 2 & -1 & 1 & 6 \\ 0 & 1 & 2 & 4 \end{pmatrix}.\]
(This was an augmented matrix before, but I just erased the vertical bar.) To transform \(A\) to reduced echelon form, we need to make all the pivot entries equal to \(1\), and zero out all entries that appear above a pivot. (Since \(A\) is already in echelon form, all the entries below a pivot are already zero.) In order to do this, we can proceed in the reverse direction as Gaussian elimination: that is, we can start from the bottom row and work our way up.
In this case, the bottom row is the second row. This row already has its pivot entry equal to \(1\). However, the entry above that pivot is not zero (it's \(-1\)). To fix this, we can add the second row to the first row:
\[\begin{pmatrix} 2 & -1 & 1 & 6 \\ 0 & 1 & 2 & 4 \end{pmatrix} \quad \stackrel{R_1+R_2 \to R_1}{\longrightarrow} \quad \begin{pmatrix} 2 & 0 & 3 & 10 \\ 0 & 1 & 2 & 4 \end{pmatrix}.\]
Now, we move to the first row. For this row, we need to make its pivot entry equal to \(1\), so we should divide the entire row by \(2\) (i.e., multiply the row by \(\frac12\)):
\[\begin{pmatrix} 2 & 0 & 3 & 10 \\ 0 & 1 & 2 & 4 \end{pmatrix} \quad \stackrel{\frac12 R_1 \to R_1}{\longrightarrow} \quad \begin{pmatrix} 1 & 0 & \frac32 & 5 \\ 0 & 1 & 2 & 4 \end{pmatrix}.\]
Now we have a matrix in reduced echelon form, as we wanted. In other words, we have calculated that
\(\text{rref}(A) = \begin{pmatrix} 1 & 0 & \frac32 & 5 \\ 0 & 1 & 2 & 4 \end{pmatrix}.\)
The above example essentially encapsulates how Gauss-Jordan elimination works: first, we perform row operations "from top to bottom" to put the matrix in echelon form, exactly as we would in Gaussian elimination. Then, we perform row operations "from bottom to top" to get from echelon form to reduced echelon form. (These two parts are sometimes called the forward phase and backward phase of Gauss-Jordan elimination, respectively.)
Gauss-Jordan elimination
Given a matrix \(A\), here is how to compute its reduced echelon form, \(\text{rref}(A)\):
Forward phase (Gaussian elimination)
- Find the leftmost column of \(A\) with any nonzero entries. (Usually this is the first column.)
- If necessary, switch rows such that the first row of \(A\) has a nonzero entry in this column. This will be the pivot for the first row.
- By adding a multiple of the first row of \(A\) to other rows below it, ensure that all other rows have zeros in this column.
- Ignore the first row and leftmost (nonzero) column, and repeat steps 2 and 3 on the remainder of the matrix \(A\).
- Continue until \(A\) has reached echelon form.
Backward phase
- Find the bottommost row of \(A\) that has any nonzero entries.
- Scale this row so that its pivot entry is equal to \(1\).
- Then, looking at the column of \(A\) containing the pivot, add multiples of this row to other rows above it, to ensure that all other rows have zeros in this column.
- Now repeat steps 2 and 3 on the row immediately above this one. Continue until \(A\) has reached reduced echelon form.
Note: The "Jordan" in this name refers to Wilhelm Jordan (1842-1899), who was not a mathematician by trade but rather a geodesist, one who surveys and measures the Earth. He used Gaussian elimination in his work, and popularized this variation of it in his Textbook of Geodesy.
To finish our discussion, here is a complete example of Gauss-Jordan elimination:
Example
\[\begin{aligned} \begin{pmatrix} 1 & 1 & 2 & 4 \\ -1 & -2 & 1 & 2 \\ 2 & 0 & -5 & -1 \end{pmatrix} \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 2 & 4 \\ 0 & -1 & 3 & 6 \\ 2 & 0 & -5 & -1 \end{pmatrix} \qquad [ R_1 + R_2 \to R_2 ] \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 2 & 4 \\ 0 & -1 & 3 & 6 \\ 0 & -2 & -9 & -9 \end{pmatrix} \qquad [ -2R_1+R_3 \to R_3 ] \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 2 & 4 \\ 0 & -1 & 3 & 6 \\ 0 & 0 & -15 & -21 \end{pmatrix} \qquad [ -2R_2+R_3 \to R_3 ] \qquad \text{(echelon form)} \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 2 & 4 \\ 0 & -1 & 3 & 6 \\ 0 & 0 & 1 & \frac{7}{5} \\ \end{pmatrix} \qquad [ -\frac{1}{15} R_3 \to R_3 ] \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 2 & 4 \\ 0 & -1 & 0 & \frac{9}{5} \\ 0 & 0 & 1 & \frac{7}{5} \\ \end{pmatrix} \qquad [ -3 R_3 + R_2 \to R_2 ] \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 0 & \frac{6}{5} \\ 0 & -1 & 0 & \frac{9}{5} \\ 0 & 0 & 1 & \frac{7}{5} \\ \end{pmatrix} \qquad [ -2 R_3 + R_1 \to R_1 ] \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 1 & 0 & \frac{6}{5} \\ 0 & 1 & 0 & -\frac{9}{5} \\ 0 & 0 & 1 & \frac{7}{5} \\ \end{pmatrix} \qquad [ -R_2 \to R_2 ] \\ \\ \quad \longrightarrow \quad &\begin{pmatrix} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & -\frac{9}{5} \\ 0 & 0 & 1 & \frac{7}{5} \\ \end{pmatrix} \qquad [ -R_2 + R_1 \to R_1 ] \qquad \text{(reduced echelon form)} \end{aligned}\]
Finally, let's try to get some intuitive sense for what Gaussian elimination and Gauss-Jordan elimination look like geometrically. (That is, let's look at some pretty pictures.) For an augmented matrix, remember that each row represents a linear equation; the graph of that linear equation will be a line (in two dimensions), a plane (in three dimensions), and in general, an \((n-1)\)-dimensional hyperplane (in \(n\) dimensions). Solving a linear system then corresponds to finding all points in the intersection of all these hyperplanes.
When we add a multiple of one equation to another equation, remember that the overall solution set does not change. Therefore, what we will see is that doing this row operation corresponds to "rotating" one of our hyperplanes around their common intersection. To be more specific:
The goal of Gaussian / Gauss-Jordan elimination is essentially to zero out many of the entries in our matrix; this will correspond to our lines / planes / hyperplanes becoming more axially aligned (that is, perpendicular to, or parallel with, the coordinate axes) as they are rotated.
In class, I showed an interactive animation in Desmos to illustrate the example from the end of the last section. (To operate it yourself, click on the "play" buttons for variables \(t_1\) through \(t_6\), in order. I recommend you go to the settings menu — the wrench icon in the top-right of the screen — and select "Translucent surfaces." You can left-click and drag to pan the view, and just refresh the page to reset the animation.)