Class Notes
(811,170)

Canada
(494,539)

Western University
(47,832)

Mathematics
(261)

Mathematics 1229A/B
(198)

Prof
(7)

Lecture

# unit06.pdf

Unlock Document

Western University

Mathematics

Mathematics 1229A/B

Prof

Fall

Description

Math 1229A/B
Unit 6:
Row Reduction
(text reference: Section 2.3)
▯V. Olds 2010 Unit 6 69
6 Row Reduction
Next, we learn a method known as row-reduction for solving SLE’s. This method works in ba-
sically the same way as the method we used in the previous unit, but we will use a structure called
a matrix to eliminate the repetitive writing down of symbols which never change from one step to
the next. This helps us to organize what we’re doing and develop a systematic procedure for getting
from the system which needs to be solved to an equivalent system in which the solution(s), or the
fact that there is no solution, is obvious. First, we must deﬁne what this mathematical structure
called a matrix is.
Deﬁnition: A matrix is a rectangular array of numbers:
a 11 a 12 a13 ▯▯▯ a1n
a 21 a 22 a23 ▯▯▯ a2n
. . . .
. . . .
am1 a m2 am3 ▯▯▯ amn
The horizontal lines of numbers are called rows and the vertical lines of numbers are
called columns. The number, a ijin row i and column j is called the (i,j)-entry of the
matrix. A matrix with m rows and n columns is called an m × n matrix (pronounced
“m by n”).
Note: The plural of matrix is matrices.
Also Note: Matrices are sometimes written using parentheses (i.e. round brackets) instead of the
square brackets shown here. But in this course, we’ll use square brackets.
Here are some examples of matrices:
1
1 2 −1 0 5 ▯ ▯
3 4 1 2 4 2 1 3 −5 0
3
5 6 −3 6 0 4
We will learn more about these things called matrices later in the course. For now, we want to
learn about one particular use of a matrix, to use it as shorthand to represent a system of linear
equations.
Deﬁnition: Consider any system of m linear equations in n variables, written in stan-
dard form. The coeﬃcient matrix of the SLE is the m × nthatrix in which the
(i,j)-entry is the coeﬃcient, in the iequation, of the j variable. And the aug-
mented matrix for a SLE is obtained by appending the m right hand side values of
the equations to the coeﬃcient matrix, as an extra column in the matrix. We always
delineate this extra column in an augmented matrix by placing a vertical line before it.
That is, row i of the coeﬃcient matrix contains, in order, the coeﬃcients from equation i. Likewise,
column j of the coeﬃent matrix contains the coeﬃcients of the jvariable in the order in which
they appear in the equations. When we form the augmented matrix, by also including the column of
RHS values, the matrix looks just like the SLE, with all of the variables omitted, and with a vertical
line instead of all the equal signs. 70 Unit 6
Example 6.1. Write the coeﬃcient matrix and the augmented matrix for the following SLE:
x − 4y + 3z = 5
−x + 3y − z = −3
2x − 4z = 6
Solution:
Since the system is already in standard form, we can obtain the coeﬃcient matrix by simply writing
the coeﬃcients from the system in the same order in which they appear in the SLE. For instance,
we get the ﬁrst row of the coeﬃcient matrix by extracting the coeﬃcients of x, y and z, i.e. 1, −4
and 3, from the ﬁrst equation. Note: The (3,2)-entry is 0, recognizing that in the third equation,
there is a 0 coeﬃcient making the y-term invisible. We get the Coeﬃcient Matrix:
1 −4 3
−1 3 −1
2 0 −4
For the augmented matrix, we write the columns from the coeﬃcient matrix, then write a vertical
line, and add a new column containing the right hand side values of the equations. In this case, the
Augmented Matrix is:
1 −4 3 5
−1 3 −1 −3
2 0 −4 6
Notice: The augmented matrix for the SLE contains all of the numbers which appear in the system;
we’re simply omitting all the non-numeric objects (i.e. variables and equal signs).
x = 1 + x − 3x
1 2 3
Example 6.2. Write the augmented matrix for the system of linear e2uations: 1 + x4 .
x3 = x2+ x4− x 1
Solution:
Remember: Our deﬁnition of the coeﬃcient matrix and the augmented matrix require that the
system be in standard form. So the ﬁrst thing we have to do is rearrange each equation to get the
standard form SLE. We get:
x1 − x2 + 3x3 = 1
x + x − x = 2
1 2 4
x1 − x2 + x3 − x4 = 0
Now, we just have to leave out all the x’s, +’s, −’s and =’s, while ﬁlling in the invisible 0’s and
±1’s. That is, we write the coeﬃcients as we see (and don’t see) them, and write the RHS’s, with
a vertical line separating the column of RHS values from the coeﬃcients. We get the augmented
matrix:
1 −1 3 0 1
1 1 0 −1 2
1 −1 1 −1 0
▯ ▯
Example 6.3. If the augmented matrix for a particular system of linear equations is,
4 5 6
write the SLE.
Solution:
The augmented matrix tells us everything we need to know about the SLE except what the variables
are called. Then again, it doesn’t matter much what names we use for the variables. We can tell
from the number of columns in the coeﬃcient matrix part of the augmented matrix that there are Unit 6 71
2 variables in the SLE, so let’s use x and y. And since there are 2 rows in the augmented matrix,
the SLE must have 2 equations. We just have to attach the coeﬃcients to the variables for each
equation, replace the vertical line with equal signs, and use the RHS values from the extra column.
We get: ▯ ▯
1 2 3 x + 2y = 3
4 5 6 corresponds to the SLE 4x + 5y = 6
Looking at these examples we see that it is easy to translate a standard form system of linear equa-
tions to its augmented matrix, and to translate from the augmented matrix back to the system.
We are going to use these augmented matrices to transform from one SLE to an equivalent SLE,
using operations corresponding to the elementary operations we have already learnt, until we get to
an augmented matrix which corresponds to a SLE in which it is easy to ﬁnd the solution(s) or to
recognize that the system is inconsistent. We will learn new operations to perform on the augmented
matrices, as well as a procedure for deciding which operations to apply, in what order. But before we
do that, there is another very important consideration ... How do we know when to stop performing
these operations? That is, how do we recognize that we have obtained “an augmented matrix which
corresponds to a SLE in which it is easy to ﬁnd the solution(s) or to recognize that the system is
inconsistent”? We look for something called row-reduced echelon form.
Deﬁnition: A matrix A is said to be in row-reduced echelon form, abbreviated as
RREF, if each of the following four conditions is met:
(i) Every row of A which contains at least one non-zero entry has a 1 as its ﬁrst (from
left to right) non-zero entry. By convention, we refer to this 1 as the leading 1 of
the row in which it occurs.
(ii) Each column of A which contains a leading 1 for some row contains no other non-
zero entries (i.e. all other entries are 0’s).
(iii) In any two rows of A which each contain some non-zero entries, the leading 1 from
the lower row must occur farther to the right than the leading 1 from the upper
row. That is, the leading ones in the matrix move from left to right as we read
down the matrix.
(iv) All rows of A which consist entirely of zeros are placed at the “bottom” of the
matrix, i.e. are lower in the matrix than all rows which contain some non-zero
entries.
For instance, the matrix:
1 0 0 1
0 1 0 2
0 0 1 0
satisﬁes each condition above. That is, looking at row 1, we see that the ﬁrst entry is a 1 — the
leading 1 for row 1. And looking at the rest of column 1 (the column which contains row 1’s lead-
ing 1), we see that the other entries in this column are all 0’s. That is, this column contains no
other non-zero entries. Now, looking at row 2, the ﬁrst non-zero entry is in the second column,
and it is a 1, so this is row 2’s leading 1. Again, looking at the rest of this column, there are no
other non-zero entries. Similarly, in row 3 we see that the ﬁrst two entries are 0’s, so the “leading”
entry is the third, and as before it is a 1. And the rest of the column which contains this 1 is all
0’s. That is, the column which contains the leading 1 for row 3 contains no other non-zero entries.
So conditions (i) and (ii) of the requirements of RREF are satisﬁed. Now, looking at the bigger
picture, we do see the leading 1’s moving from left to right as we read down the matrix. That is,
row 1 has the left-most leading 1, and in the rows below that, each leading 1 is further to the right 72 Unit 6
than the leading 1 in the preceding row. Therefore condition (iii) is satisﬁed. Finally, looking at
the matrix we see that there are no rows which consist entirely of zeros, which means that where
such rows should come in the matrix is irrelevant. We only need to be concerned with condition
(iv) when there are some rows like that. If there aren’t any, then the condition is not violated, so
it is satisﬁed. Therefore all of the conditions required for row-reduced echelon form are satisﬁed
by this matrix, so the matrix is in RREF. Notice that column 4 does not contain any row’s lead-
ing 1, so the requirements of RREF say nothing about what the column 4 entries may or may not be.
Example 6.4. Which of the following matrices are in RREF?
1 0 2 2 3 1 1 0 0 1 0 0 1 0 0
(a) 0 1 3 1 2 (b) 0 1 0 0 (c) 0 0 1 (d) 0 2 0
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
Solution:
(a) We have the matrix
1 0 2 2 3
0 1 3 1 2
0 0 0 0 0
Looking at this matrix, we see that in each row that has any non-zero entries, the ﬁrst non-zero
entry is a 1. That is, row 1 has a leading 1 (in column 1) and row 2 also has a leading 1 (in column
2). Row 3 doesn’t have any non-zero entries, so it doesn’t need (and cannot have) a leading 1.
Therefore condition (i) of the requirements for RREF is satisﬁed. Also, looking at columns 1 and 2,
which are the only columns which contain any row’s leading 1, we see that all of the other entries are
0. That is, the column which contains the leading 1 for row 1 does not contain any other non-zero
entries, and the same is true for the column which contains the leading 1 for row 2. Since these
are the only columns which contain leading 1’s for some row, these are the only columns to which
condition (ii) of the requirements for RREF pertain. Therefore this condition is satisﬁed. And we
see that row 2’s leading 1 is further to the right than row 1’s, above it, so condition (iii) of the
requirements for RREF is satisﬁed, too. Finally, row 3 contains only 0’s and is at the bottom of the
matrix, further down than all the rows which contain some non-zero entries. Thus condition (iv)
of the requirements for RREF is also satisﬁed. Since all of the conditions are satisﬁed, this matrix
does fulﬁll the requirements and therefore is in row-reduced echelon form.
(b) Now we look at the matrix
1 1 0 0
0 1 0 0
0 0 1 0
Here we see that each row does contain a leading 1, so condition (i) is satisﬁed. But this matrix
fails condition (ii), because column 2 contains the leading 1 for row 2, but also contains a non-zero
entry in row 1. In order to satisfy condition (ii) there would have to be a 0 in the (1,2)-entry of
the matrix, since the leading 1 for some row is in that column. Therefore this matrix is not in RREF.
(c) Next we look at the matrix
1 0 0
0 0 1
0 1 0
In this case, each row does contain a leading 1, and each column that contains the leading 1 for some
row has no other non-zero entries, so both condition (i) and condition (ii) are satisﬁed. However,
this matrix does not satisfy condition (iii) because the leading 1 for row 3 is not strictly to the right
of the leading 1 for row 2. That is, the leading 1’s do not move from left to right as we read down Unit 6 73
the matrix. The row whose leading 1 is in column 3 would have to be lower down in the matrix than
the row whose leading 1 is in column 2 in order for codition (iii) to be satisﬁed. (Unless, of course,
there wasn’t any row whose leading 1 was in column 2. But that’s not the case here.) Therefore
this matrix also is not in RREF.
(d) Finally, we look at the matrix
1 0 0
0 2 0
0 0 1
This one fails condition (i). The ﬁrst non-zero entry in row 2 is not a 1. That is, row 2 does have
some non-zero entries, but it does not have a leading 1. Therefore condition (i) is violated, so the
matrix is not in RREF.
Suppose that we have a system of linear equations, and that we also have a RREF augmented
matrix that we know corresponds to a system which is equivalent to that SLE. How do we use it to
ﬁnd the solution(s) to the SLE? We simply use the RREF matrix to write the corresponding SLE so
that we can see the solution(s) to that SLE, and since this SLE is equivalent to the original SLE, we
have also found the solution(s) to the original SLE. For instance, suppose that we have the system
x + y = 3
x − y = 1
for which the augmented matrix is ▯ ▯
1 1 3
1 −1 1
And suppose that (by some means we haven’t yet learnt) it has been determined that the RREF
matrix ▯ ▯
1 0 2
0 1 1
corresponds to a SLE which is equivalent to the original system. Then we write the SLE correspond-
ing to this RREF augmented matrix:
▯ ▯
1 0 2 1x + 0y = 2 x = 2
0 1 1 corresponds to 0x + 1y = 1 i.e. to y = 1
so, because we know that this system is equivalent to, and thus has the same solutions as, the
x + y = 3
original system, we see that (x,y) = (2,1) is the only soxut−on yo = 1 .
Example 6.5. For each of the following, ﬁnd all solutions to a system of linear equations which is
equivalent to the SLE corresponding to the given RREF augmented matrix, where the variables are
as stated.
1 0 0 1
(a) 0 1 0 2 with variables x, y and z.
0 0 1 0
1 0 2 2 3
(b) 0 1 3 1 2 with variables1x 2 x 3 x an4 x .
0 0 0 0 0 74 Unit 6
1 0 0 2 5
0 1 0 0 3
(c) 0 0 1 −3 2 with variables w, x, y and z.
0 0 0 0 1
Solution:
For each of the given RREF matrices, we write the corresponding SLE, using the variables given,
and state all solutions to that SLE.
(a) We can easily conﬁrm that this matrix is in RREF. We see that
1 0 0 1 x = 1
0 1 0 2 corresponds to y = 2
0 0 1 0 z = 0
so the only solution to any SLE which is equivalent to this SLE is (x,y,z) = (1,2,0).
(b) Notice that this is the augmented matrix which we have already conﬁrmed, in Example 6.4(a)
is n RREF. This tie we have
1 0 2 2 3 x + 2x + 2x = 3
1 3 4
0 1 3 1 2 which corresponds to x2 + 3x3 + x4 = 2
0 0 0 0 0 0x1 + 0x2 + 0x3 +0x4 = 0
We see that the ﬁrst equation is telling us about the value of x (relative to x and x ) and the
1 3 4
second equation is telling us about the 2alue of x (3elativ4 to x and x ). The third equation simply
states that 0 = 0, which tells us nothing (except that there isn’t a problem). That is, the original
system must have had 3 equations, but only the ﬁrst 2 ended up giving us useful information, and
the third was consistent with those 2, but contained no new information. There is no equation
telling us about the valu3 of x , so it must be free to have any real value. Likewise, with no equation
telling us about the valu4 of x , this variable is also free to have any real value. Since each of these
variables could have any value, we use a diﬀerent parameter for each. That is, 3e can have x = s
for any s ∈ ℜ and also x = t for any t ∈ ℜ. Using these values in the ﬁrst and second equations,
4
and rearranging to state the corresponding val1es of2x and x we get
x 1 + 2s + 2t = 3 ⇒ x1 = 3 − 2s − 2t
x2 + 3s + t = 2 ⇒ x2 = 2 − 3s − t
Therefore any SLE which is equivalent to this SLE has the two-parameter family of solutions
(x1,x2,3 ,4 ) = (3 − 2s − 2t,2 − 3s − t,s,t).
(c) Checking for leading 1’s, and that their columns are otherwise empty, and seeing that the leading
1’s move from left to right as we read down the matrix (and observing that there is no row which
contains only 0’s), we see that this matrix is, as stated, in RREF. We write the corresponding SLE:
1 0 0 2 5 w + 2z = 5
0 1 0 0 3 corresponds to x = 3
0 0 1 −3 2 y − 3z = 2
0 0 0 0 1 0w + 0x + 0y + 0z = 1
In this system, it doesn’t matter what the ﬁrst 3 equations say, because the fourth equation says
that 0 = 1. The existence of 4 equations tells us that the original SLE, whatever it was, had 4
equations. But the fourth equation has been transformed into an equation which is nonsense, i.e.
cannot be true, no matter what the values of w, x, y and z are. So the SLE corresponding to the
RREF augmented matrix has no solution, and therefore any SLE equivalent to this SLE must be
inconsistent. Unit 6 75
At this point, we have learnt how to write the augmented matrix for any SLE in standard form,
and how to recognize a matrix that is in RREF, as well as how to ﬁnd the solution(s), if any, to
the SLE corresponding to an augmented matrix which is in RREF. But we don’t know yet how to
transform the augmented matrix for a SLE into a matrix in RREF for an equivalent system. That’s
what we learn next.
Manipulating the augmented matrix for a system of linear equations corresponds to, i.e. is
equivalent to, manipulating the equations in the system. In the previous unit, we learnt how to
manipulate equations using the three elementary operations, in order to solve a SLE. What we need
to learn now is how to perform operations on an augmented matrix which correspond to those ele-
mentary operations we perform on equations. But what we are going to learn applies more broadly
than just to augmented matrices corresponding to SLE’s. The operations we are going to learn can
be applied to any kind of matrix.
In an augmented matrix representing a SLE, each row of the matrix corresponds to a diﬀerent
equation in the system. Therefore the kind of operations we perform on equations in a system are
performed on rows of a matrix. There are 3 elementary operations which we are allowed to perform
on equations, and so there are three corresponding elementary row operations which we can perform
on a matrix.
Deﬁnition: The following operations are the elementary row operations (abbrevi-
ated ero’s) which can be performed to transform a matrix into RREF:
I Multiply any row of the matrix by any non-zero scalar.
II Interchange the positions of any two rows in the matrix.
III Replace any row in the matrix by the sum of that row and a scalar multiple of any
other row of the matrix.
No other operations are allowed.
Also, we say that two matrices are row equivalent if one matrix can be transformed
into the other by applying a sequence of elementary row operations.
Notice: When we ‘multiply a row by a scalar’, or ‘sum one row and a scalar multiple of another
row’, we perform these arithmetic operations by treating a row of a matrix like a vector, using the
vector operations we have learnt previously. That is, we multiply a row of a matrix by a scalar
by multiplying each entry in the row by that scalar. Likewise, adding 2 rows of a matrix means
summing corresponding entries (components) in the rows.
Also Notice: Compare the deﬁnitions of the elementary row operations, stated here, to the deﬁnition
of the elementary operations on equations used to transform an SLE into an equivalent SLE, stated
on page 64. You will see that they correspond exactly, and so when we perform these elementary
row operations on an augmented matrix, it is just like performing the corresponding elementary
operations on the equations in the SLE represented by that augmented matrix. And therefore we
have a theorem for augmented matrices similar to Theorem 5.1(see page 64) which told us that when
we perform elementary operations to transform a SLE, the new SLE is always equivalent to the one
we started with.
Deﬁnition: The process of applying elementary row operations to transform a matrix
into RREF is called row-reduction, or simply reduction. We can refer to this as
row-reducing or reducing the matrix. 76 Unit 6
Theorem 6.1. Applying any sequence of elementary row operations to the augmented matrix for a
SLE produces a new augmented matrix whose corresponding SLE has exactly the same solution(s)
as (i.e. is equivalent to) the original SLE.
Using the deﬁnition of row equivalent, another way to state this theorem is:
If 2 augmented matrices are row equivalent, then their corresponding SLE’s have the
same solution(s).
Before we think about applying elementary row operations to an augmented matrix, to ﬁnd the
solution(s) to a SLE, let’s look at some examples of row equivalent matrices, and practice using
these ero’s more generally to row-reduce any matrix (to RREF). For instance, the matrices
1 −4 3 −2 8 −6
−1 3 −1 and −1 3 −1
2 0 −4 2 0 −4
are row equivalent since multiplying row 1 of the ﬁrst matrix by −2 (a type I ero) transforms the
ﬁrst matrix into the second matrix.
Similarly, the matrices
1 −4 3 −1 3 −1
−1 3 −1 and 1 −4 3
2 0 −4 2 0 −4
are row equivalent because the second matrix can be obtained from the ﬁrst by interchanging rows
1 and 2 (a type II ero).
Also, the matrices
1 −4 3 −1 2 1
−1 3 −1 and −1 3 −1
2 0 −4 2 0 −4
are row equivalent since performing the type III ero add twice the second row to the ﬁrst row in the
ﬁrst matrix transforms it to the second matrix.
There is shorthand which we can use to indicate what ero we are performing. If we transform
a matrix by multiplying a row of the matrix by a scalar, i.e. if we replace Row i of the matrix
by c times that row, for some non-zero scalar c, we indicate thii by wiiting R ← cR . (This says
calculate c times Row i and put it where Row i was before. That is, Row i is replaced by c times
Row i.) Likewise, when we interchange two rows of a matrix, i.e. put Row i where Row j was, and
vice versa, we wriie R j R . And for a type III ero, in which we add a scalar multiple of another
row to a row, i.e. Row i is replaced by Row i plus c times Row i, weiwritj R ← R + cR . So for
the three transformations we observed above, we can write
1 −4 3 R1←(−2)R1 −2 8 −6 1 −4 3 R ↔R −1 3 −1
−1 3 −1 −−−−−−−→ −1 3 −1 and −1 3 −1 −−−−→2 1 −4 3
2 0 −4 2 0 −4 2 0 −4 2 0 −4
1 −4 3 R1←R1+2R2 −1 2 1
and −1 3 −1 −−−−−−−−→ −1 3 −1
2 0 −4 2 0 −4
The long arrow says “transform the matrix to a row equivalent matrix by performing the ero indi-
cated”. Unit 6 77
Example 6.6. For each of the matrices in Example 6.4 which is not already in RREF, perform ele-
mentary row operations to transform the matrix into a row equivalent matrix which is in RREF.
Solution:
1 0 2 2 3
(a) As we observed in Example 6.4(a), the matrix 1 3 1 2 is already in RREF.
0 0 0 0 0
1 1 0 0
(b) In Example 6.4(b), we observed that the augmented matrix 1 0 0 is not in RREF
0 0 1 0
because column 2, which contains the leading 1 for row 2, has a non-zero entry in row 1. That is,
the problem here is that the (1,2)-entry of the matrix must be 0 in order to have RREF. Notice
that row 2’s leading 1 in column 2 means that we can eliminate the non-zero entry in this column,
in row 1, by adding the negative of the existing non-zero (1,2)-entry times row 2 to row 1. That
is, we can use a type III ero in which we add a scalar multiple of row 2 to row 1, to get rid of the
non-zero (1,2)-entry. And the scalar we need is just the negative of the entry which we are trying
to transform into 0. Also notice that row 2 has a 0 in column 1, so adding a multiple of row 2 to
row 1 will not have any eﬀect on the (1,1)-entry, which means that after we do this, row 1 will still
have a leading 1. (It’s important that when we perform ero’s we don’t “mess up” the things we
already have which do comply with RREF, so that we don’t create more work for ourselves.) When
we perform the ero 1 ← R 1 (−1)R ,2i.e. R1← R −1R , 2e get the new version of Row 1 by
performing this arithmetic on the vectors which look like those rows of the matrix. (Note: It doesn’t
matter that the matrix happens to be an augmented matrix. We just ignore the | when we do the
arithmetic.) So the new row 1 corresponds to
Row 1 − Row 2 = (1,1,0,0) − (0,1,0,0) = (1,0,0,0)
Therefore transform the matrix by
1 1 0 0 R ←R +(−1)R 1 0 0 0
0 1 0 0 −−−−−−−−−−− → 0 1 0 0
0 0 1 0 0 0 1 0
We see that the new matrix, which is row equivalent to the old one, is in RREF, so we’re done.
1 0 0
(c) In Example 6.4(c), we found that the matrix 0 1 is not in RREF because although
0 1 0
each row does have a leading 1, and the columns containing these leading 1’s each have no other
non-zero entries, the leading 1’s do not follow the required pattern of moving from left to right as
we read down the matrix. The leading 1 in row 3 is not farther to the right than the leading 1 in
row 2. We can easily ﬁx this by simply switching the positions of those two rows. That is, we need
to perform a type II ero to interchange the positions of Rows 2 and 3. We get:
1 0 0 1 0 0
0 0 1 −−−−→3 0 1 0
0 1 0 0 0 1
We see that the transformed matrix is in RREF, so we’re done.
(d) Finally, in part (d) of Example 6.4, we observed that the matrix
1 0 0
0 2 0
0 0 1 78 Unit 6
is not in RREF because row 2 does not have a leading 1. The ﬁrst non-zero entry in row 2 is a 2, not
a 1. We can always transform a “leading c”, for some value c which is neither 0 nor 1, into a leading
1
1 by multiplying it (i.e. by multiplying the row) bc. So all we need to do here is to perform the
type I ero multiply Row 2 by the non-zero scalar. We get
2
1 0 0 R2← (1)R2 1 0 0
0 2 0 −−−−−−−→ 0 1 0
0 0 1 0 0 1
We see that the transformed matrix is now in RREF.
In this example, for each of the matrices which was not already in row-reduced echelon form, we
were able to, quite easily, transform the matrix into RREF using elementary row operations. But
those matrices were very close to RREF to start with. In each case, we needed only a single ero to
get to RREF. Usually, several or perhaps even many ero’s will be required to obtain RREF. One
natural question which may occur to you is Is this always possible?, that is Is it always possible to
transform a matrix into RREF using ero’s?. And when more than one ero is needed, assuming that
it is possible to obtain RREF, you might also wonder Does it matter which ero’s we do, and does
the order we do them in matter?. Well, clearly it does matter which ero’s we do, because some will
take us to RREF and others won’t. But still, there will often be choices about which problem to
tackle next, or which type of ero to use to accomplish a particular goal in moving towards RREF. So
the question is, Does it matter what choices we make?. The next theorem addresses these questions.
Theorem 6.2. Facts about Row-Reduced Echelon Form
(a) Every matrix can be transformed into RREF by applying a ﬁnite sequence of elementary row
operations.
(b) The row-reduced echelon form of a matrix is unique. That is, if the same matrix is reduced by
two diﬀerent sequences of ero’s, the RREF obtained in both cases will be identical.
Although part (a) of Theorem 6.2 tells us that it is always possible to transform a matrix into
RREF by a ﬁnite sequence of ERO’s, and part (b) tells us that any sequence of ERO’s that results
in RREF will produce the same RREF, it is still possible to perform many ERO’s on a matrix with-
out ever getting any closer to having the matrix in RREF. So it is very important to approach
the reduction of a matrix in a systematic way. We want to follow a procedure which ensures that
each ero performed is moving the matrix closer to being in RREF, so that we arrive at RREF quickly.
In order for a matrix to be in row-reduced echelon form, we need each row, if it has any non-zero
entries in it, to have a leading 1. Also, we need the column which has a row’s leading 1 in it to
contain 0’s in all the other rows. When we want to transform a matrix to RREF, we tackle the rows
of the matrix from the top down, and deal with those 2 requirements, in order, for the row we’re
currently dealing with. That is, starting with the top row, we make sure that we have a leading 1
in that row, and then make the rest of the entries in the column that contains that leading 1 be
0’s. Once we’ve accomplished that, we move on to the next row. As we go along, we move any rows
which contain only 0’s down to the bottom of the matrix, and also move rows around if necessary
to ensure that the leading 1 we’re currently getting, or working with, is the left-most of the entries
which don’t yet conform.
And we want to be sure that we never “undo” any of the work done in previous steps, which
can happen if we’re not careful. For instance, if we’ve obtained a leading 1 in a particular row, we
don’t want that 1 to be transformed into some other number later on. A leading 1 should always Unit 6 79
stay a leading 1 as we continue to reduce the matrix. Likewise, if we’ve “zeroed out” a column, so
that the leading 1 it contains is the only non-zero entry in that column, we want to be sure that we
don’t re-introduce any non-zero entries into that column later on in the reduction process.
With these considerations in mind, we use the procedure shown below whenever we need to row-
reduce a matrix. It is strongly recommended that you become familiar with, and comfortable
with using, this procedure/algorithm, in order to save time and work in reaching RREF. While it
may, on rare occasions, be true that the reduction could have been completed slightly more quickly
by some other sequence of operations, far more often this procedure gives a highly eﬃcient route to
obtaining the row-reduced echelon form of the matrix.
Procedure for Transforming a Matrix into RREF:
1. Always work from the top down.
2. Always work from left to right.
So if there is a non-zero entry lower down in the matrix that is farther to the left
than the left-most non-zero entry in the highest row (among rows that do not yet
have a leading 1), interchange rows so that you can simultan▯ously be workin▯ with
0 0 3 4
the highest, and the left-most, such entry. For instance, for we
−1 1 2 1
would start with R1↔ R . 2
3. In the highest up row which has not yet been “dealt with”, obtain a leading 1.
That is, if the ﬁrst non-zero entry in the row is not a 1, perform one or more ero’s
to transform that non-zero entry into a 1. (See Note 1.)
4. As soon as a leading 1 has been obtained, use it to obtain 0’s everywhere else in
the column which contains that leading 1. (See Note 2.)
5. As soon as a row containing only 0’s is obtained, move it to the bottom of the
matrix.
6. Continue in this manner until the matrix is in RREF.
Notes:
1. It is always possible to obtain a leading 1 in a particular row (which has at least
one non-zero entry) using a type I ero, by multiplying that row by, where c is the
c
number which is to be transformed into a 1. However, if there is another row further
down in the matrix which already has a 1 in the column in which the leading 1 is
to be obtained, use a type II ero and interchange those rows. If no other row has a
1 in this column, but there is a row further down whose entry in this column will
lead to less complicated fractions, interchange the rows, to simplify the arithmetic.
For instance, if the top-most row which does not have a leading 1 in it has a 12
as its left-most non-zero entry, and further down in the matrix some row has a 2
in that column, the arithmetic is usually easier if you interchange the rows and
1
multiply by 2 to get a leading ▯ than if you int▯oduce a leading 1 by multiplying
12 10 3 7
the current row by 12. So for , it’s easier to use 1 ↔ R t2
▯ ▯ 2 −1 5 2
2 −1 5 2 1 1
get and then use R 1 2R 1han to apply R ← 1 12R 1o the
12 10 3 7
original matrix, since halves are arithmetically easier to work with than twelfths.
2. Once a leading 1 has been obtained in a particular row, it is always possible to
“zero out” the rest of the column which contains that leading 1 using type III ero’s,
adding scalar multiples of the row with the (newly obtained) leading 1 to the other
rows (those which have non-zero entries in that column). And the particular scalar 80 Unit 6
needed is −c, where c is the entry which is to become 0. For instance, if we have
just obtained a leading one in row i, and some row farther down in the matrix, row
j, has a 2 in the column containing row i’s leading one, perform the type III ero:
replace row j by row j plus (-2) times row i. Or for the matrix obtained at

More
Less
Related notes for Mathematics 1229A/B