Row reduction towards row echelon form
2.83K subscribers
SUBSCRIBED
We work through a complete example that illustrates all the main features of the row reduction algorithm.
Category
00:04
hello everyone
00:05
abnormal Alberto let's have a look at an
00:08
example of row reduction this is also
00:11
sometimes called Gaussian elimination
00:13
there's two terms for it and it is a
00:16
fundamental algorithm that sort of
00:18
pervades many aspects of linear algebra
00:22
it gives us concrete technology for
00:26
solving systems of linear equations when
00:29
they can be solved finding out if there
00:32
are any solutions and if so how many
00:34
solutions there are and perhaps
00:37
parameterizing the solution so it's a
00:39
very flexible and powerful thing the
00:41
history of row reduction well it
00:44
actually is usually attributed in modern
00:47
times to Gauss Carl Frederick Gauss was
00:49
great German mathematician who lived
00:52
around you know 1800s but actually it
00:56
goes back much earlier goes back to
01:00
ancient Chinese mathematics there is a
01:06
famous Chinese text written or compiled
01:10
somewhere between 200 BC and 280 called
01:13
9 chapters of the mathematical arts nine
01:19
chapters of the mathematical arts and in
01:26
that work
01:28
the technique of row reduction was laid
01:32
out for the first time okay so what I
01:36
want to do is I want to illustrate what
01:39
happened so there's a general theory but
01:40
I want to show you a first concrete
01:42
example so that we learn how to approach
01:46
the problem in a very systematic kind of
01:49
step-by-step procedure okay so let's
01:52
start with this system of linear
01:55
equations we have three equations in
01:57
three unknowns the variables are x1 x2
02:00
and x3 so we know that one
02:05
interpretation of this problem is that
02:07
we have three planes each equation
02:09
represents a plane in 3-dimensional
02:12
space
02:13
and at this point we don't know what the
02:15
various relationships are between these
02:18
planes you don't know whether the common
02:20
intersection is a point or maybe a line
02:22
or maybe even a plane so that's one of
02:25
the things we want to find out another
02:28
interpretation that we've seen is that
02:29
we can also think about this system as
02:32
representing a relation between vectors
02:36
so if you actually sort of look at the
02:38
columns of what's happening here we
02:40
could also write this in alternate form
02:44
as x1 times the vector 2 1 minus 1 plus
02:50
x2 times the vector 7 2 4 plus x3 times
02:55
the vector 4 minus 1 13 equals squeezing
02:59
here 2 1 1 gets sort of an alternate
03:03
form of the same system ok now what
03:06
we're going to do is we're going to work
03:08
uniformly with a matrix approach okay so
03:13
with the matrix approach were interested
03:14
in the matrix of coefficients and an
03:17
Augmented matrix so I'm going to write
03:19
down the matrix equation first so the
03:24
matrix equation is in terms of a 3 by 3
03:30
matrix 2 7 4 1 2 minus 1 minus 1 for 13
03:37
also in terms of a vector of variables
03:40
x1 x2 x3 equals on the right-hand side
03:44
our vector of coefficients 2 1 minus 1
03:49
that's a minus 1 there okay so that's
03:53
now in the form that we often write a x
03:56
equals B kind of form which is quite
03:59
attractive now to actually do the row
04:03
reduction to simplify this what we're
04:06
going to do is we're going to work with
04:07
the Augmented matrix so we think this
04:12
thing has odd mantid matrix what is that
04:20
it's when we put the a matrix together
04:23
with the B column separated by
04:26
line so 2 7 4 1 2 minus 1 minus 1 4 13
04:33
then a line and then on the other side
04:35
of that line 2 1 and minus 1 so it has
04:38
all the information the numerical
04:41
information of the system of equations
04:44
and you know any any one of the original
04:48
equations can be to sort of read off by
04:51
reading across one of these rows of this
04:54
Augmented matrix for example the second
04:56
row would tell us that X 1 plus 2 X 2
04:59
minus X 3 equals 1 which is same one as
05:03
that one there okay so what are we going
05:06
to do we are going to row reduce this
05:11
thing we're going to perform elementary
05:13
row operations so at each stage we're
05:16
performing one of the three elementary
05:18
row operations which replaces the given
05:21
system of three equations with three
05:24
other equations which are equivalent
05:27
equivalent in the sense that the
05:29
solutions are exactly the same okay
05:33
alright so we're going to just create a
05:35
series of steps and the steps will be
05:37
indicated with arrows up and move from
05:39
one Augmented matrix to another to
05:42
another to another hopefully moving
05:44
towards a simpler and simpler form
05:47
eventually the form of the Augmented
05:49
matrix will be so simple that we'll be
05:52
able to read off what the solutions are
05:55
pretty easily that's the aim okay so
06:00
what we're going to do in this case is
06:02
we're going to switch to ropes which Row
06:05
1 and Row 2 that's easy to do so I get 1
06:10
2 minus 1 1 2 7 4 2 and minus 1 4 13
06:19
minus 1 why am i doing that I'm doing
06:22
that so that this one that's there ends
06:25
up at the top of its column we like to
06:29
have ones at the top of the column why
06:32
because we're going to use that entry to
06:36
reduce the other entries in that column
06:40
to zero namely this - that's sitting
06:43
there and this - one that's saying there
06:45
we want to replace those things with
06:48
zero we want to add multiples of the
06:51
first row to both the second row and the
06:54
third row to make those entries zero now
06:58
we could do that individually but since
07:02
you are all very smart we're going to do
07:04
this all at the same time so we're going
07:06
to do two operations sort of at the same
07:08
time the first operation is going to be
07:11
aiming at getting rid of that - so I'm
07:14
going to replace Row 2 with Row 2 - 2
07:19
times Row 1 and then in the same breath
07:24
same step I'm going to replace Row 3
07:27
with Row 3 plus Row 1 so let me do two
07:33
of those things let's see what we get so
07:35
first of all the first row is not
07:37
changing its where it is now the next
07:42
step is we're going to replace Row 2
07:44
with Row 2 - to Rwanda ok so we have to
07:50
make this computation to 7/4 - that row
07:56
minus 2 times the Row 1 2 minus 1 1 okay
08:01
so what are we going to get the 2 minus
08:03
2 times 1 is 0 7 minus 2 times 2 is 3 4
08:12
minus 2 times minus 1 is the same as 4
08:17
plus 2 which is 6 and 2 minus 2 times 1
08:24
is 0 so we have to do a little bit of
08:28
arithmetic in our heads alright please
08:30
do not use a calculator each for your
08:32
calculator you want to do this in your
08:33
head ok but you don't want to do it sort
08:36
of slowly and steadily to make sure that
08:38
you've done it right because if you mess
08:40
up especially near the beginning well
08:42
everything is going to be messed up ok
08:44
so let's just check 2 minus 2 times 1 is
08:46
0 7 minus 2 times 2 is 3s 4 minus 2
08:50
times minus 1 is 6 2 minus 2 times 1 is
08:53
0kay that rose right now what about in
08:56
Row three we were saying that rogue 3 is
08:58
going to be replaced with the some of
09:00
the original row 3 and Row 1 so we're
09:04
doing it that way so that we get a zero
09:06
here that's the aim minus 1 plus 1 is 0
09:11
4 plus 2 is 6 13 plus minus 1 is 12 and
09:18
minus 1 plus 1 is 0 ok great now at this
09:27
stage we're happy with column 1 column 1
09:32
has been arranged just the way we want
09:36
has a 1 up at the top and below that one
09:39
there's only zeros that's excellent now
09:42
we're going to shift our attention to
09:45
the lower part we can draw it in here in
09:49
red so we're now going to switch our
09:51
attention more or less to this smaller
09:55
sub matrix if we just had that we would
10:00
say oh that's a system of two equations
10:02
in two unknowns so in some sense we're
10:04
starting with three equations in three
10:05
and those after having performed this
10:07
first series of steps we now more or
10:10
less in the situation of having two
10:11
equations in two unknowns okay so we're
10:14
gonna sort of apply the same kind of
10:16
thing sort of just looking now at this
10:19
smaller sort of sub matrix okay what are
10:23
we gonna do to this thing well maybe I
10:28
maybe I'll do a little bit of cleaning
10:31
up I'm going to replace Row 2 with one
10:36
third of Row two right there's a common
10:40
factor of three I'm allowed to multiply
10:43
all the elements in a row by a constant
10:46
so I can multiply by 1/3 that'll
10:49
simplify that row and similarly once I
10:52
look at it I see that Row 3 has this
10:54
common factor of 6 and I might as well
10:56
replace Row 3 with one sixth Row 3 what
11:02
happens when I do that I get one two
11:04
minus one one that's not going to
11:06
and then this is going to be 0 1 2 0 and
11:10
this one is also going to be 0 1 2 0 so
11:14
it's a lot simpler now that's quite nice
11:16
and moreover we have the happy situation
11:20
that we have a 1 here in this place just
11:23
like we ended up having a 1 up in that
11:26
previous line ok and we can then use
11:29
this one to eliminate everything below
11:33
it namely that one that's sitting
11:34
underneath it so let's go over here ok
11:42
so I'm now going to take a new Row 3 the
11:46
new Row 3 is going to be wrote the
11:48
current Row 3 minus the current Row 2 so
11:54
the first row does not change the second
11:59
row does not change what the third row
12:03
well I'm taking the third row and I'm
12:05
subtracting the second row 0 minus 0 is
12:09
0 1 minus 1 is 0 2 minus 2 is 0 and 0
12:13
minus 0 is 0 ok now I'm in a pretty
12:21
happy position because the leading
12:25
entries of these rows that is the
12:27
leftmost nonzero entry in in the rows
12:33
are these ones right here this third row
12:37
doesn't have any nonzero entries but the
12:40
first two rows have these nonzero
12:41
entries which I've circled and they
12:43
happen to be one which is very nice and
12:45
they are staggered so one at the top
12:49
corner and then we have to move right
12:51
and down to get the next one so also
12:59
those ones I've circled have the
13:00
property that there's nothing but 0 is
13:02
under underneath them ok so this is a
13:05
this is a pleasant kind of form for a
13:09
matrix we say this is in row echelon
13:11
form it's a kind of not an end
13:20
result but it's a kind of an island of
13:22
safety we believe we've crossed this
13:24
river and we've gotten to this island
13:26
okay where we can pause and take stock
13:28
and this is sort of like the halfway
13:30
point of the algorithm I'm going to show
13:36
you what what happens further on so you
13:39
can see the entire you know algorithm
13:42
expressed in this example then we'll go
13:44
over it again we'll sort of look more
13:47
generally more carefully and what we're
13:49
what the various steps that we're doing
13:51
but I want to you see it all in an
13:54
example here so after we have it in row
13:56
echelon form we are going to further row
13:59
reduce we're going to do some more row
14:02
operations and I'm going to now sort of
14:05
start from the bottom up so I'm going to
14:08
circle this one twice okay I'll think
14:10
about it again and I'm going to use it
14:12
to get rid of everything above it we've
14:15
already got rid of everything below it
14:17
now I'm going to get rid of everything
14:19
above it how am I gonna do that I'm
14:23
going to replace Row 1 with Row 1 minus
14:29
2 times Row 2 ok so what's the new Row 1
14:38
gonna be so we're taking the road 1 and
14:40
we're subtracting twice the second row
14:43
so that one will still be 1 because it's
14:46
1 minus 2 times 0 that's 1 the 2 minus 2
14:51
times 1 and that's going to be 0 the
14:54
next one minus 1 minus 2 times 2 so
14:59
that's like minus 1 minus 4 so that's
15:05
gonna be a total of minus 5 and on the
15:08
right hand side we still put that bar on
15:11
the right hand side we have 1 minus 2
15:14
times 0 that's still 1 and we're not
15:17
doing anything to this second row so
15:19
we'll just copy it and we're not doing
15:21
anything to the third row we'll just
15:24
copy that now we have
15:31
graduated to a final forum really so
15:35
we've got the two leading entries and
15:39
everything else in the columns of those
15:44
leading entries which means things both
15:48
below the entries and above the entries
15:51
are completely free of anything other
15:53
than zeros so those leading entries are
15:56
the only things in those columns these
16:01
two columns that have these specials of
16:04
ones in them just by themselves these
16:06
are called leading columns so that's
16:15
good that's one of the properties of
16:17
this what's sometimes called fully
16:20
reduced row echelon form the leading
16:28
entries are ones the other entries in
16:34
the columns of those leading entries are
16:36
all 0 and we have a row of zeros at the
16:41
bottom there's the row of zeros it's
16:44
just at the bottom it's really not doing
16:47
much for us now this is a very happy
16:51
situation we've reduced the original
16:53
system when we start off with this
16:56
system of equations up here we formed an
17:01
Augmented matrix for it right here that
17:03
was a rather complicated looking thing
17:05
okay and then we've row reduced it and
17:09
now we have this much simpler form which
17:12
is however equivalent to it does I mean
17:14
it means that solutions of this system
17:18
and solutions of the original system are
17:21
winding the same they're exactly the
17:23
same that's the point we're simplifying
17:26
the system so now we can read off the
17:28
solutions very easily hopefully ok so
17:32
let me translate this now back into a
17:34
system of linear equations in the
17:38
original variables which were X 1 X 2
17:43
and X 3
17:44
so the system of equations that
17:48
corresponds to this if we read the top
17:50
row one zero minus five one that
17:53
corresponds to X 1 minus 5x 3 equals 1
17:57
and the second equation is X 2 plus 2 X
18:03
3 equals 0 and the third equation we're
18:07
not even going to write down because
18:09
it's 0 equals 0 so so it's not used to
18:14
us at all now we have two equations in
18:17
three variables how we can solve this
18:22
we're going to look at the non leading
18:25
column on the left hand side so this is
18:29
the non leading column that is going to
18:38
correspond to a parameter it means that
18:45
there's a 1 parameter family of
18:46
solutions to this system and it's the
18:49
existence of this non leading column on
18:51
the left hand side that's going to tell
18:54
us this and let's see why that is
18:55
because if we look at these two
18:56
equations we say a cop if we look at
19:04
these two equations we see that ok X 1
19:07
minus 5 X 3 equals 1 X 2 plus 2 X 3
19:09
equals 0 there's a degree of freedom
19:11
like we could let X 3 be anything we
19:14
wanted to and then X 1 is going to be
19:17
determined in terms of that and X 2 is
19:19
going to be determined in terms of that
19:23
that's what exactly what we're gonna do
19:25
we're thinking about this third variable
19:27
which corresponds to the third column or
19:29
the non leading column as being free
19:33
it's unconstrained it can be anything it
19:36
wants so we're going to let X 3 be a
19:40
parameter okay
19:42
lamb that we often use that's a
19:44
parameter then we can see that X 1 if we
19:55
solve for that
19:57
bring the 5 X 3 on the other side so we
19:59
get 5 lambda 1 plus 5 lambda X 2 we saw
20:04
for that we get minus 2 lambda and X 3
20:07
itself is just lambda we said what we
20:14
had here is a solution to the original
20:18
system we can also write it as vector X
20:23
1 X 2 X 3 is 1 plus 5 lambda minus 2
20:29
lambda lambda and if we separate that
20:33
out we could actually write it as 1 0 0
20:37
that's the stuff not involving lambda
20:39
plus lambda times the vector 5 minus 2 1
20:47
so what is that in terms of a diagram
20:52
gears next one
20:55
and there's X 2 and there's X 3 there's
20:59
one there's one there's one then 1 0 0
21:03
that's that's that point there so it's a
21:05
line that passes through that point and
21:07
a a direction vector for it we have to
21:18
go 5 in this direction minus 2 in this
21:21
direction and one in this direction so
21:23
that's a total of 5 and then over here
21:26
and then up here so maybe something like
21:28
that so this would be the vector that's
21:30
the vector vector 5 minus 2 1 and so the
21:37
line that we're describing is the line
21:39
that goes through this point 1 0 0 which
21:42
is parallel to that direction vector in
21:45
other words it's going the same
21:46
directions we'll draw a parallel like
21:48
that so it's a line in a line in
21:53
three-dimensional space in 3d through
21:57
the point 1 0 0 with Direction vector 5
22:08
minus 2y
22:11
so this illustrates really the entire
22:15
story in some sense of taking an
22:19
original system that we started with
22:22
writing down the Augmented matrix for it
22:27
right here
22:29
it's the Augmented matrix for it and
22:30
then row reducing it first of all to get
22:34
to this row echelon form which is the
22:39
situation where the leading entries of
22:41
the rows are are ones that is the
22:44
leftmost entry in in every row which is
22:48
nonzero is actually one and everything
22:50
below those leading entries is zero and
22:55
then we proceed more and sort of
22:59
eliminate everything above those leading
23:02
entries until we get this fully reduced
23:05
row echelon form where whether zeros
23:07
entirely in the leading columns except
23:10
for the actual leading actors themselves
23:12
which are once and the role zeros if
23:15
there are any are at the bottom and from
23:17
that we only were able to pretty easily
23:21
write down the corresponding new system
23:25
of equations and basically solve it by
23:30
by introducing a parameter for the non
23:35
leading column gives this case there was
23:37
one not lady column so there was only
23:39
one parameter there are more than one
23:42
nominated colors then there will be more
23:43
than one parameter okay so and finally
23:48
we end up with in this case a unbounded
23:51
number of solutions the solution set is
23:54
online geometrically corresponding to
23:56
the situation we were these three planes
23:59
and then you know they two of them meet
24:01
like this and then the third one is like
24:02
that too so they all meet on this common
24:05
line okay that's great
24:10
so please make sure that you understand
24:11
all those steps and next time we'll sort
24:14
of be a little bit more abstract and
24:16
sort of clarify what exactly the so
24:18
official algorithm is but it's all kind
24:21
of contained in this one example
24:23
you understand this example you have you
24:26
have a good basis for understanding row
24:29
reduction and Gaussian elimination