Row reduction algorithm II
2.83K subscribers
SUBSCRIBED
We describe the second half of the row reduction algorithm: to go from a matrix in row echelon form to one in reduced row echelon form. This is a matrix equivalent of the naive high school method of back-substitution: evaluating the variables one at a time, starting with the last one, and successively substituting into the next equation.
00:00
hello everyone i'm norman wahlberger
00:03
today we're going to carry on with the
00:05
row reduction algorithm
00:07
explaining how you perform this gaussian
00:10
elimination
00:10
procedure to solve a general system of
00:14
linear equations and we're doing this
00:16
all in matrix form
00:17
typically starting with an augmented
00:19
matrix
00:20
for some system of equations so for
00:22
example in the uh
00:24
this little matrix that we have right
00:26
here we have a
00:28
augmented matrix and we see that uh
00:31
there's three equations here one for
00:33
every row
00:34
and um and the variables there's four of
00:37
the variables we don't know what their
00:38
names are maybe we'll call them x1 x2 x3
00:41
x4
00:42
and already this has been reduced
00:45
to row echelon form so we probably
00:47
started with some
00:48
prior system and we've reduced it to row
00:50
echelon form and i remind you what that
00:52
means
00:53
okay that means that um all the zero
00:56
rows are at the bottom
00:57
as we see here that the
01:01
leading entries of the leading row so
01:05
the rows which are not zero are called
01:07
leading rows
01:08
and the left most entries are called
01:10
leading entries and they are staggered
01:12
to the right as we move down from row to
01:14
row
01:15
and i've circled those two leading
01:16
entries so there are two leading entries
01:18
in this
01:19
row echelon matrix now
01:22
as a system of equations the form
01:26
of it already tells us that there are
01:28
going to be solutions
01:29
okay there are going to be solutions
01:31
because the last
01:33
column is not a leading column so
01:36
the last column
01:40
is not a leading column
01:47
and that tells us that solutions
01:51
exist at least one solution exists but
01:54
maybe more
01:56
the leading columns in this case are
01:59
these ones here the second column and
02:01
the fourth column those are the leading
02:03
columns
02:05
and we're going to see that
02:08
the other columns maybe these ones here
02:11
the green ones these are the non-leading
02:13
columns
02:14
they are going to correspond to
02:16
parameters ultimately in a solution so
02:19
just the form of this row echelon matrix
02:21
tells us
02:22
what kind of solution we can expect
02:25
that this is going to be a two parameter
02:28
family of solutions because of those two
02:31
green non-leading columns on the left
02:34
hand side of the matrix
02:37
this is also this one here is also a
02:40
non-leading
02:41
column but it's the non-leading columns
02:43
on the left hand side that tell you how
02:45
many
02:46
variables are going to be in the final
02:50
solution
02:51
okay so let's see how that actually
02:53
translates
02:54
to you know a solution to actually a
02:56
system so
02:57
we can do that by translating this
03:00
information in the matrix
03:01
back to a bunch of equations in the
03:04
variables and we'll suppose that the
03:05
variables are
03:07
x1 x2 x3 x4 okay so the first equation
03:10
has 0x1 plus 2x2 plus x3 plus 3x4 equals
03:14
minus 1.
03:15
and the second equation is x4 equals
03:18
five and the third equation is well
03:20
zero equals zero with zero xy plus zero
03:22
x two plus zero x three plus zero x four
03:24
equals zero
03:25
it doesn't tell us anything but we'll
03:27
stick it in there anyway because it's
03:29
part of the system okay so
03:32
if we were just asked to solve this
03:35
system of equations in the variables x1
03:37
x2 x3 x4 how would we do that
03:41
the key is to look at the circled
03:44
elements
03:44
ones in red which correspond to the
03:47
leading entries
03:49
in the original matrix so these two
03:51
leading entries correspond to these
03:53
particular variables the x2 and the x4
03:58
and what we're going to do is we're
03:59
going to solve for those leading
04:01
variables
04:03
so we solve for
04:07
the leading variables
04:12
those are the ones corresponding to the
04:15
leading columns
04:29
in terms of
04:34
parameters
04:40
corresponding
04:44
to the non-leading
04:47
variables
04:54
all right so in this example here the
04:57
leading variables
05:03
will be x2 and x4
05:07
and the non-leading variables
05:13
will be x1 and x3
05:17
so they have a different relation here
05:19
so the process of row reduction
05:22
has singled out some of the variables as
05:24
being maybe
05:25
more primary than the others okay we're
05:28
going to solve for x2 and x4
05:30
in terms of x1 and x3
05:33
so how do we do that well let's set
05:36
x1 equal to a parameter say lambda
05:40
and x3 equal to another parameter
05:44
say mu okay so we've
05:47
agreed that the non-leading variables
05:50
are going to be parameters in
05:52
the solution and then x2 and x4 are
05:55
going to be
05:56
defined in terms of them okay and to do
05:58
that
05:59
this process is what we're going to call
06:02
back substitution is a kind of a high
06:03
school method really
06:05
where we're just taking this system of
06:06
equations now and kind of performing
06:08
high school
06:10
algebra with this idea of
06:13
replacing the non-leading variables with
06:15
suitable parameters
06:18
and the way the back substitution works
06:20
is we start
06:21
at the bottom with the bottom equation
06:24
of the bottom row
06:25
and we work our way up okay so
06:30
with this back substitution
06:36
we start to the bottom and work our way
06:46
up okay
06:48
so the bottom is this equation x4
06:51
equals five okay so we have the first
06:56
thing is x4 equals five actually that's
06:58
finished that's already done we know
06:59
what x4
07:00
is okay and then we
07:03
go to the next highest row
07:07
and i'll just copy that 2x2
07:12
then 2x2 plus
07:15
x 3 plus
07:19
3 x 4 equals minus 1.
07:25
okay and we're solving for x2 okay
07:28
well we know that x3 is going to be our
07:30
parameter mu
07:32
and we know that x4 has just been
07:35
obtained from the previous step
07:36
about circleable we know what x4 is okay
07:40
so now we can write
07:41
the equation as 2x2 plus
07:44
x3 is replaced with the parameter mu
07:48
and x4 is replaced
07:51
with 5. so we get
07:55
that equation and that
07:59
is the equation 2 x 2
08:04
equals minus 16 minus
08:07
mu okay when we solve
08:10
for x x2 we get x2 equals -8
08:14
minus one-half mu and then
08:17
we can put everything together because
08:19
now we know all
08:20
four variables we have
08:25
x1 and x3 from up here we have
08:28
x2 right here and we have x4
08:31
right here so we put that all that
08:33
together we get x1 equals
08:35
lambda x2 equals minus 8 minus one-half
08:38
mu
08:39
x3 equals mu
08:42
and x4 equals five
08:45
so this is a a solution and it's an
08:48
acceptable
08:49
form of solution that means that when
08:51
any
08:53
values of lambda and mu are given then
08:55
we can plug them in there and we're
08:56
going to get a solution
08:58
for the original system whatever it was
09:01
if we want to understand what this is
09:02
geometrically well then we can write it
09:04
in this formula sort of separating the
09:06
things involving lambda
09:08
things involving mu and the things not
09:10
involving lambda mu
09:12
all right so things not involving lambda
09:14
omega is the
09:16
vector 0 minus 805
09:19
the lambda is then multiplied by one
09:22
zero zero
09:23
zero and the mu multiplied by zero
09:26
minus a half one zero and when we have
09:29
it this way
09:30
we recognize that this is a plane in
09:32
four dimensional space
09:34
through the point this point here
09:38
through that point which is say a
09:41
coordinates zero minus eight zero five
09:43
and it has two direction vectors
09:47
given by the
09:50
vectors one zero zero and zero minus a
09:54
half
09:54
one zero
09:59
okay so that describes a kind of high
10:02
school approach
10:03
to this second half of the row reduction
10:07
algorithm
10:08
to go from a row echelon augmented
10:10
matrix
10:11
to a reduced row echelon
10:14
augmented matrix so let me remind you
10:17
about that
10:18
so a reduced
10:22
row echelon matrix
10:29
it has some some properties first of all
10:33
all the leading entries
10:39
are one okay and
10:42
secondly all the entries
10:47
in the leading columns
10:54
are 0 except for the actual leading
10:58
entry
11:05
so there's kind of two steps that we
11:08
need to do
11:09
we need if we're starting with the row
11:11
echelon matrix and we want a reduced row
11:13
echelon matrix
11:14
we have to do two things so we go from a
11:17
row echelon matrix
11:19
to a reduced
11:24
row echelon matrix
11:29
what we do we need to
11:31
[Music]
11:34
first of all re-normalize
11:39
re-normalize the leading entries
11:45
to one and we need to
11:50
add multiples
11:56
the leading rows
12:01
to the rows above them
12:09
to clear the columns
12:13
the leading columns
12:19
of of entries above the
12:25
above the leading entries
12:32
now to do that the algorithm then is
12:38
[Music]
12:41
what we do is we
12:45
start with the
12:50
bottom leading row
12:56
in a row echelon form
13:03
and normalize
13:08
its leading entry
13:13
to be one
13:17
okay so we multiply that row by a
13:20
suitable constant so that the leading
13:21
entry becomes one
13:23
and then what we do is we use
13:27
that row
13:31
to eliminate
13:35
all the entries eliminate means reduce
13:39
to zero
13:40
eliminate all the entries above
13:43
that leading
13:47
tree and we do that by
13:50
add multiples of the row to the ones
13:52
above it
13:53
add multiples of that row that leading
13:56
row
13:58
to the ones above it
14:07
then we repeat
14:11
steps
14:14
one and two with
14:18
the next lowest row
14:30
until we've gotten all the way up to the
14:32
top row and then once we've gotten there
14:34
well we're finished because then
14:36
everything above the leading entries
14:38
will also be zero and then the matrix
14:41
will be in reduced row echelon form
14:46
okay so let's see how it works in an
14:48
example
14:50
so let's start with something in row
14:51
echelon
14:53
form say
14:57
uh one two
15:00
three minus one five
15:05
four zero eight
15:08
twelve zero
15:11
zero three
15:16
minus three okay also zeros here
15:20
okay this is a matrix in
15:24
row echelon form because these leading
15:26
entries here
15:27
okay are staggered to the right and all
15:30
the zero rows which there aren't any are
15:31
at the bottom
15:33
i want to point out that at this point
15:35
here before we actually
15:37
proceed we should check that the last
15:40
column is not a leading column
15:43
because if the last column is a leading
15:45
column if one of these circled leading
15:47
entries is in the last column then the
15:48
whole thing has no solutions and there's
15:50
no point in going further because you're
15:52
not going to find any solutions no
15:54
matter what you do
15:55
okay so let's just check check
15:58
that the last
16:01
column the one on the right hand side
16:05
is not leading
16:09
okay that's good yes it's not leading
16:12
there it is right there that column
16:13
there is not leading because it doesn't
16:14
have a red
16:15
circled entry okay there's no leading
16:18
entry in that column
16:19
it's not leading that means that
16:21
solutions
16:22
do exist so we know solutions
16:25
exist maybe one maybe a one parameter
16:29
family
16:29
maybe a two parameter family etc but
16:32
some solutions definitely exist
16:34
and so now the purpose is to find those
16:36
solutions
16:38
okay so let's perform our algorithm we
16:41
are going to
16:43
start with the bottom row okay that
16:46
bottom pivot
16:47
is three we want to change that three
16:50
into a one
16:52
so we're going to replace row three with
16:55
one third of row three in other words
16:57
we're gonna be dividing
16:59
that last row by three so the first row
17:02
stays where it is
17:05
the second row stays where it is
17:09
the third row becomes
17:13
zero zero zero one minus one
17:18
okay so there's the new leading entry
17:21
there are the leading entries now now
17:24
what we're going to do is we're going to
17:25
eliminate
17:27
the things above that leading entry of
17:29
one that we just found at the bottom
17:31
we're gonna eliminate this eight and
17:33
we're gonna eliminate this
17:34
minus one
17:37
so we're gonna do two steps at once the
17:39
new row two is going to be the old row
17:42
two
17:43
minus eight times row three
17:47
and the new row one is going to be the
17:49
old row one
17:51
plus row three
17:54
okay so we can kind of start at the
17:56
bottom here actually because that bottom
17:58
row is not going to change going in the
18:01
opposite direction than we did with the
18:03
gaussian elimination
18:04
the first half of the procedure sort of
18:07
goes from the top to the bottom
18:09
this second half of the procedure goes
18:11
from the bottom up to the top
18:15
okay so what do we say we're going to do
18:17
we're going to add i would subtract
18:19
eight times
18:20
the third row from the second okay so
18:23
we're gonna have zero
18:24
four zero eight minus eight will be zero
18:28
that's what we're arranging
18:29
and twelve minus eight
18:32
times minus one that's like twelve plus
18:34
eight that's twenty
18:36
it's twenty and the first row we're
18:40
adding the third row to it so we get a
18:42
one
18:43
a two a three one plus minus one is a
18:46
zero
18:46
and five plus minus one is four
18:51
great okay so now we're going to work
18:53
with this
18:54
next row from the bottom so we're now
18:56
with the second bottom row
18:58
and that entry four we have to change
19:01
that into a one
19:03
okay well that's easy we're just going
19:05
to divide so the row two is going to be
19:08
one quarter of the old row two so
19:10
everything stays the same
19:12
except that we just
19:15
divide everything by four in the second
19:18
row
19:22
one zero zero divided by four we get
19:24
five and the last row stays where it is
19:28
great and now we're going to use this
19:30
entry that we're sort of working on
19:32
to eliminate everything above it namely
19:34
that two
19:36
okay what happens uh
19:39
well we're going to take row one the new
19:42
row one is going to be the old row one
19:44
minus two times row two
19:47
so we'll subtract two times row two from
19:50
row one
19:51
which will give us one two minus two is
19:54
zero
19:54
three minus zero three zero now four
19:58
minus two times five so that's
20:00
minus six second row stays where it is
20:05
the third row stays where it is
20:09
and now we're in a happy situation
20:12
because
20:13
the leading entries
20:16
have only zeros otherwise
20:20
in their columns so the leading columns
20:22
here
20:24
the leading columns are all cleared
20:27
of entries except for the leading
20:29
entries
20:32
all the other entries are zero
20:36
now there's one non-leading this one is
20:39
a
20:40
non-leading
20:43
column and that corresponds to a
20:46
parameter
20:52
okay so let's see how unfold so let's
20:54
suppose that the variables are
20:56
we don't know what the variables are so
20:57
let's suppose the variables are
21:02
x1 x2 x3
21:05
and x4 right there's all there's four of
21:07
them because there's
21:09
four columns on the left hand side of
21:13
the matrix one corresponding to each
21:14
variable
21:16
so what have we just decided we're going
21:19
to set
21:20
the non-leading variable which is the
21:23
third one
21:24
equal to a parameter so we're going to
21:25
set x3 equal to
21:27
some parameter lambda so now we
21:30
solve
21:34
for the other variables
21:42
um actually we don't really have to do
21:45
it from the bottom but
21:46
we can do it uh just write write
21:49
them all down because we've already done
21:51
that work of
21:52
eliminating with the the entries above
21:55
the leading entries
21:56
so we're going to solve for the other
21:57
variables let's write down the three
21:58
equations here
22:00
so the first one is x1
22:03
plus 0x2 i won't write that plus 3x3 but
22:06
instead of writing x3
22:07
we know that x3 is lambda so i'm just
22:09
going to write plus 3 lambda
22:11
plus 0x4 i'm not going to write that
22:13
equals minus 6. so that first equation
22:15
becomes that one involving x1 which is
22:18
one of our leading
22:19
variables and involving this parameter
22:22
lambda
22:24
okay the next equation is x2
22:28
equals uh just five and the next one is
22:32
x4 equals minus one
22:37
so all together we can maybe come over
22:38
here so we
22:40
see that the solution is x1 x2 x3
22:44
x4 equals
22:49
equals x1 is what
22:52
it's minus 6 minus 3 lambda
22:55
solving for x1 x2 was just
22:58
- x3 is the parameter
23:01
lambda and x4 is minus 1.
23:07
so we don't have to rewrite this we get
23:10
a
23:12
one parameter family of solutions
23:25
and okay that's ie a line
23:29
a line in this four dimensional space
23:34
and we could if we want to or we could
23:37
write this
23:38
as say x is
23:42
the vector which doesn't involve
23:44
anything having to do with lambda so
23:46
minus 6
23:47
5 0 one plus lambda times
23:51
some vector which will be minus three
23:54
zero one zero okay so if we write it
23:57
that way
23:58
separating the things involving lambda
23:59
and things not involving lambda
24:01
then geometrically we see that this is a
24:04
line
24:05
through the point -6501
24:09
in the direction or with direction
24:11
vector the vector -3
24:14
0 1 0.
24:18
all right so that's that's the
24:22
row reduction algorithm okay so there's
24:24
two steps
24:25
we start with a general system okay we
24:28
start with the general system
24:29
we write down the augmented matrix
24:32
okay so maybe i'll write that down so
24:36
so the review then what we've
24:37
accomplished is we start with a system
24:40
of
24:40
equations
24:44
linear equations and then we write down
24:46
the augmented matrix
24:49
that's what we are working with okay
24:54
and then what we do is we perform row
24:57
reduction
24:59
or gaussian elimination
25:04
to get a row echelon
25:09
matrix
25:13
and at this stage there's two things
25:14
that can happen
25:17
one is that the last column is leading
25:23
last column is a leading column
25:30
in which case there's no solutions
25:36
the system has no
25:39
solutions okay if the last column is
25:42
leaking
25:43
the other possibility is the last column
25:45
is
25:49
is not leading
25:53
okay in that case what we do is we carry
25:56
on we have to do
25:57
more work okay we have to do more work
25:59
we have to
26:00
do this sort of second half
26:05
second half of row reduction that i've
26:08
described
26:09
in this lecture to get to a reduced
26:15
row echelon
26:19
matrix okay
26:22
and then from there what we do is we
26:28
from there what we do is we introduce
26:33
introduce variables or parameters
26:38
parameters for each
26:43
non-leading
26:46
column on the left hand side
26:56
so corresponding to the variables on the
26:58
left hand side
27:00
and then we solve then we solve
27:04
for the leading variables
27:12
in terms of these parameters
27:23
and then well and then we
27:27
you know put everything together and
27:30
exhibit
27:33
exhibit the solution
27:36
the baby only one or maybe the solution
27:39
set
27:44
so that's that's the entire uh story
27:46
that's a row reduction
27:48
okay so very powerful algorithm which is
27:51
a
27:52
key technology for solving all kinds of
27:55
problems in linear algebra
27:57
okay so many things computationally
27:59
ultimately
28:00
boil down to this and
28:04
there's some tricks you know to to make
28:06
things a little bit smoother and then to
28:08
simplify things
28:09
and we'll see some of that as we look to
28:11
uh examples so we're going to be
28:13
doing a lot of examples of this okay get
28:16
better at it
28:17
in a number of different applications so
28:20
we'll see all that
28:23
happening