The preceding example amply illustrates the definitions and theorems we have seen so far. But it still leaves two questions unanswered. Exactly what is this “simpler” form for a matrix, and just how do we get it? Here is the answer to the first question, a definition of reduced row-echelon form.
A matrix is in reduced row-echelon form if it meets all of the following conditions:
The set of column indices for the pivot columns will be denoted by $D=\set{d_1,\,d_2,\,d_3,\,\ldots,\,d_r}$ where $d_1<d_2<d_3<\cdots<d_r$, while the columns that are not pivot columns will be denoted as $F=\set{f_1,\,f_2,\,f_3,\,\ldots,\,f_{n-r}}$ where $f_1<f_2<f_3<\cdots<f_{n-r}$.
The principal feature of reduced row-echelon form is the pattern of leading 1's guaranteed by conditions (2) and (4), reminiscent of a flight of geese, or steps in a staircase, or water cascading down a mountain stream.
There are a number of new terms and notation introduced in this definition, which should make you suspect that this is an important definition. Given all there is to digest here, we will mostly save the use of $D$ and $F$ until Section TSS. However, one important point to make here is that all of these terms and notation apply to a matrix. Sometimes we will employ these terms and sets for an augmented matrix, and other times it might be a coefficient matrix. So always give some thought to exactly which type of matrix you are analyzing.
Our next theorem has a “constructive” proof. Learn about the meaning of this term in Proof Technique C.
Suppose $A$ is a matrix. Then there is a matrix $B$ so that
The procedure given in the proof of Theorem REMEF can be more precisely described using a pseudo-code version of a computer program. Single-letter variables, like m, n, i, j, r have the same meanings as above. := is assignment of the value on the right to the variable on the left, A[i,j] is the equivalent of the matrix entry $\matrixentry{A}{ij}$, while == is an equality test and <> is a “not equals” test.
input m, n and A
r := 0
for j := 1 to n
i := r+1
while i <= m and A[i,j] == 0
i := i+1
if i < m+1
r := r+1
swap rows i and r of A (row op 1)
scale A[r,j] to a leading 1 (row op 2)
for k := 1 to m, k <> r
make A[k,j] zero (row op 3, employing row r)
output r and A
Notice that as a practical matter the “and” used in the conditional statement of the while statement should be of the “short-circuit” variety so that the array access that follows is not out-of-bounds.
So now we can put it all together. Begin with a system of linear equations (Definition SLE), and represent the system by its augmented matrix (Definition AM). Use row operations (Definition RO) to convert this matrix into reduced row-echelon form (Definition RREF), using the procedure outlined in the proof of Theorem REMEF. Theorem REMEF also tells us we can always accomplish this, and that the result is row-equivalent (Definition REM) to the original augmented matrix. Since the matrix in reduced-row echelon form has the same solution set, we can analyze the row-reduced version instead of the original matrix, viewing it as the augmented matrix of a different system of equations. The beauty of augmented matrices in reduced row-echelon form is that the solution sets to the systems they represent can be easily determined, as we will see in the next few examples and in the next section.
We will see through the course that almost every interesting property of a matrix can be discerned by looking at a row-equivalent matrix in reduced row-echelon form. For this reason it is important to know that the matrix $B$ is guaranteed to exist by Theorem REMEF is also unique.
Two proof techniques are applicable to the proof. First, head out and read two proof techniques: Proof Technique CD and Proof Technique U.
Suppose that $A$ is an $m\times n$ matrix and that $B$ and $C$ are $m\times n$ matrices that are row-equivalent to $A$ and in reduced row-echelon form. Then $B=C$.
We will now run through some examples of using these definitions and theorems to solve some systems of equations. From now on, when we have a matrix in reduced row-echelon form, we will mark the leading 1's with a small box. This will help you count, and identify, the pivot columns. In your work, you can box 'em, circle 'em or write 'em in a different color — just identify 'em somehow. This device will prove very useful later and is a very good habit to start developing right now.
Archetypes A and B are meant to contrast each other in many respects. So let us solve Archetype A now.
These three examples (Example SAB, Example SAA, Example SAE) illustrate the full range of possibilities for a system of linear equations — no solutions, one solution, or infinitely many solutions. In the next section we will examine these three scenarios more closely.
We (and everybody else) will often speak of “row-reducing” a matrix. This is an informal way of saying we begin with a matrix $A$ and then analyze the matrix $B$ that is row-equivalent to $A$ and in reduced row-echelon form. So the term row-reduce is used as a verb, but describes something a bit more complicated, since we do not really change $A$. Theorem REMEF tells us that this process will always be successful and Theorem RREFU tells us that $B$ will be unambiguous. Typically, an investigation of $A$ will proceed by analyzing $B$ and applying theorems whose hypotheses include the row-equivalence of $A$ and $B$, and usually the hypothesis that $B$ is in reduced row-echelon form.