Linear Algebra Solutions of Linear Systems, Part 1

Welcome back to educator.com, today we are going to be continuing our study of linear algebra, and we are going to be discussing solutions of linear systems part 1.0000

This lesson is going to consist of a couple of very, careful, systematic, slow examples of something called elimination in order to put a matrix into something called reduced row echelon form, so let's get started.0012

When we talked about linear systems earlier, we talked about the three things that we can do to a system of linear equations or a matrix, which is of ‘course just a representation of that linear system.0033

We can switch two rows, we can multiply one row by a constant and we can ad multiples of one row to another row, all of these three create an equivalent system, which just is our way of manipulating the linear system to make it easier for us to handle.0046

Let's begin today's lesson by defining what we mean by reduced row echelon form, which is going to be the final form that we want to put a augmented matrix into.0065

Again an augmented matrix is just the system of linear equations, the coefficients of the linear systems, plus that extra column which is the solutions to that linear system.0075

We are going to manipulate that, we are going to put it into reduced row echelon form, so an M by N matrix is in reduced row echelon form.0085

We will often refer to it as just RRE, if the following holds, if all rows that are entirely 0, if there are any or at the bottom of the matrix.0094

If we, as we read from left to right, the first non-zero entry in a row is a 1, we call that the leading entry, has to be a 1.0108

If rows I and I + 1, so for example rows 3 and 4, if they both have leading entries, then the leading entry of the I + 1 row is to the right of the leading entry of row I.0120

In other words if I have two leading entries in row three and row four, the one on row four is going to be to the right, it's not going to be right below it or to the left of it.0135

All of these will make sense in just a moment when we give some examples of reduced row echelon form.0143

Now, if a column actually contains a leading entry of some row, then all of the other entries in the column R is 0, note a matrix in reduced row echelon form may not have any rows consisting of al 0's.0149

Reduced row echelon form doesn't mean that we have to have a row that's all 0's, it means that if it does, they need to be at the bottom of the matrix, okay let's look at some examples....0166

... So we have the matrix (1, 0, 0, 4, 0, 1, 0, 5, 0, 0, 1, 2), this is in reduced row echelon form.0192

Notice, this has a leading entry, it is a 1, everything else is a 0, this column has or this row has a leading entry, but notice it's to the right, that's what we meant by to the right.0203

It's to the right of that one, and every other entry in that column is 0, here this row also has a leading entry, it is a 1, it is to the left of these other two, and every other entry in there is a 0, and it doesn't matter what this is.0217

(4, 5, 2) this is not a leading entry, this is the leading entry of that row, these numbers are, they are not irrelevant, but as far as the definition of reduced row echelon, they are not important.0234

Let's take a look at another matrix (2, 1, 2, 0, 0, 2, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0) same thing.0247

We have a leading entry 0's along he column, this one, notice this is a 2 here and there's a (0, 0) here.0264

This is the leading entry we haven't run across yet, so it’s okay that the 2 is here, it has nothing to do with the definition, but now we run, yes leading entry is a (1, 0, 0).0276

It qualifies, it's to the right of this one, the next row, we have a (1, 0, 0,) and it's to the right of these other two, so this one is in reduced row echelon form.0286

C will take (1, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1) and we have a couple of rows of all 0's.0301

We have this nice big, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, , 5 by 5 matrix, let's see we have this 0 entries there at the bottom of the matrix that takes care of part A of the definition.0319

We have a leading entry in this row, it is a 1, that's nice, all of the other entries are 0, there's nothing in this column irrelevant.0332

There is a leading entry in this row and it is to the right of that one and all of the other entries are 0.0340

No leading entry, no leading entry, no leading entry, yes it satisfies the definition for reduced row echelon, so these three matrices are examples of matrices that are in reduced row echelon form.0349

Now let's take a look at a prime...0366

(1, 2, 0, 4, 0, 0, 0, 0, 0, 0, 1, -3) this matrix, it has a leading entry and other two entries are 0.0373

But you notice here, this row is the second row and yet it's on top of the row that's not all 0's, so this one is not in reduced row echelon form because this 0 row needs to be at the bottom.0389

let's take B prime, (1, 0, 3, 4, 0, 2, -2, 5, 0, 0, 1, 2) okay, in this particular case we take a look at the 1, it's a 0 entry.0408

The 0's are, the rest of the entries in the column are 0, here the leading entry, the first number that's non-zero is a 2, kit's not a 1, it has to be a 1for it to be in reduced row echelon form.0424

You can certainly take this entire row and divide it by 2, to get 1, -1, and five halves, and then you will almost be in reduced row echelon form, but as it stands, this is not reduced row echelon form.0440

Let's take (1, 0, 3, 4, 0, 1, -2, 5), let's take (0, 1, 2, 2) and let's take all 0's.0457

Okay, so we have a leading entry, which is nice, all of the other entries are 0's, very good, we have a leading entry which is a 1, it is to the left of, I'm sorry to the right of this one, it's the other, the one above it is to the left of it, so far so good.0472

But this other entry here in this column is a 1, it's not a 0, it needs to be a 0, so as it stands this one is not reduced row echelon form.0491

Okay...0504

... Very important theorem, every M by N matrix, every M by N matrix is row equivalent to a unique matrix in reduced row echelon form, which means that no matter what M by N matrix I give you, with the three operations of exchanging rows...0512

Multiplying a row by a constant, non-zero constant, and multiplying a multiple of, or adding a multiple of one row to another row, with those three operations handled over and over and over again, you can convert it to a reduced row echelon matrix.0535

That is unique, that's what's really interesting, later on we will talk about something called Gaussian elimination and it's the slightly, less detailed version of what it is that we are going to be doing today.0551

And it usually suffices for most purposes in linear algebra, but the matrices that you end up with are not unique.0564

What makes reduced row echelon fantastic is that, even if you and your friend and another friend do a whole bunch of different operations, in the end you'll end up with the same matrix, there is only one matrix that's in reduced row echelon form for any given matrix.0571

That's actually kind of extraordinary when you think about it, so now we are going to go through a very systematic and careful example.0585

We are not going to prove the uniqueness, but this example will actually show how you come across the, how you transform the particular matrix into reduced row echelon form.0592

Okay, so let's start off with our matrix, and again I am not going to be putting the brackets on there, simply because there is a whole bunch iof extra writing that we want to avoid.0603

(0, 2, 3, -4 and 1) (0, 0, 2, 3, 4), (0, 0, 2, 3, 4), (2, 2, -5, 2, 4) (2, , 2, -5, 2and 4).0613

Excuse me, my 4 sometimes look like 9, and (2, 0, -6, 9 and 7), okay, so this is the matrix we started off with, this is the one that we want to convert to reduced row echelon form, that's what we want, that's our goal.0633

And we will check to see that all the properties of RRE are satisfied, okay so step 1...0651

... You want to identify...0662

... The first column...0671

... Which is not all o's, so in this case we go here leading from left to right, this column, right (0, 0, 2, 2,), it's the first column that are not all 0's, okay.0679

Again, very systematic step 2, find...0697

... The first...0705

... Non-zero entry in that column...0710

... By the way, this column is called a pivotal column, and the first entry that you find, which is right there...0719

... First column is the first entry going down, that's non-zero, that's actually called the pivot, so in our first series of steps, 2 is our pivot.0734

Okay...0748

... What we are going to do here is we are going to take this row, this row and we are goign to interchange it with the first row, so we want the row that has the pivot in it to be on top.0754

Okay, so I'll write out step 3, before I write the, step 3...0770

... Interchange if necessary, you don't necessarily have to do this, in this case we do have to, if necessary...0785

... The first row...0799

... With the row containing the pivot...0804

... When we do that, we end up with the following matrix (2, 2, -5, 2, 4, 0, 0, 2, 3, 4, 0, 2, 3, -4, 1, 2, 0, -6, 9 and 7.0810

All we have done is we have exchanged the first and the third rows, that was the one with the pivot, we put it on top, okay.0832

Now we are going to divide this first row, so let's make step 4...0840

... Divide the first row, what is now the first row, not the original first row, so these steps refer to the matrix that I just completed, so divide the first row, by its first entry.0849

In other words I am just trying to make this first entry a 1, so I am going to divide everything in this row by 2, so I end up with (1, 1, -5halves, 1, 2) and then I copy the other, (0, 0, 2, 3, 4, 0, 2, 3, -4, 1).0865

And (2, 0, -6, 9 and 7), so this is what I end up with, okay.0890

Next, I am going to, actually let me rewrite what I had before (1, 1, -5halves, 1, 2, 0, 0, 2, 3, 4, 0, 2, 3, -4, 1, 2, 0, -6, 9 and 7).0903

Okay....0933

.. We are going to take our fifth step, and that is we are going to do is we are going to, remember what we wanted to do, we just draw echelon form we wanted to get all of these 0, so we are going to add a multiple of this to this, to make it, to make this thing 0.0936

In other words we are going to multiply the first line by -2 added to the fourth row and see what we get, so step 5...0950

... Add -2 times first row...0963

... The fourth row, and then when we do that, so -2 times 1 is -2 + 2, so I'll leave everything else the same, nothing changes in the other rows.0972

(2, 3, 4, 0, 2, 3, -4, 1), this becomes 0, -2 times 1 is -2 + 0, we end up with -2...0987

... -2 times -5 halves is 5, 5 - 6, 5 - 6 is -1, -2 times 1 is -2, -2 + 9 is 7.1005

_2 times 2 is -4, -4 + 7 is 3.1022

Look what we have done, we have created a row with a leading entry of 1, everything else is 0, now I am going to put a little bracket here...1029

... My first row is done, now I am going to think about this matrix, I completely ignore this one, I never have to worry about the first row again.1041

Now step 6, well, this is the nice thing about it , we just repeat everything we just did, repeat steps 1 to 5 for this particular matrix here.1049

Okay, so what is it that we did, we found the first column that had the, that was not all 0's, this is all 0's so we go to this column, and in this column, we find the first entry that is non-zero, which is 2.1064

That's going to be our new pivot, okay, we take that pivot and we move it up to the top, and again we don't touch this one, we leave it alone so we exchange this row right here with this row.1080

Now we are talking about 1, 2, 3, so we are going to exchange rows 1 and 2, so now let's go ahead and write down that matrix.1095

Let me actually do a little arrow here, and I am going to say...1104

... Switch 2 and 3, I am sorry, so we are still talking about the entire matrix, so we are going to call this row 2, we are going to call this row 3, so we are going to switch 2 and 3.1112

And when we do that, the matrix we end up with is the following, we get of ‘course the original (1, 1, -5 halves, 1, 2), we get (0, 2, 3 and -4, 1).1124

We get (0, 0, 2, 3, 4) we get (0, -2, -1, 7 and 3), okay.1140

Now, we want to take, remember what we did before, the next step, once we have this pivotal, the row with the pivot, I'll go ahead and circle the pivot, so we know what we did to it.1151

Now we want to go ahead and divide that by that number, everything in that row by that number to turn this into a 1.1162

We will divide...1170

... Row 2 by 2, which is the pivot, matrix we get is (1, 1, -5 halves, 1, 2) nothing changes, (0, 1, 3halves, -2 and 1 half)...1176

...Alright ...1198

... And we get the (0, 0, 2, 3, 4, 0, -2, -1, 7 and 3).1202

Now we have a leading entry of 1, and now we need to do is we need to get rid of...1216

... Did we make a mistake here?..1230

... See here, let us multiply...1234

... Two times the second row, added to this row to get rid of this and make it a 0...1242

... Let me see if I can squeeze this in here, (1, 1, -5 halves, 1 and 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 2, 3, 4).1254

Half...1275

... Okay...1278

1...1283

... Let me see here...1288

... And let me go, so we will do negative, yes we will do +2 times this row + this row, so we will end up with 0 here.1294

+2 times 1 is 2 - 2 is 0, +2 tim3s 3 halves is 3, 3 - 1 will end up giving me a 2, + 2 times -2 is 4.1303

-4, -4 + should be +3 and +2 times 1 half is 1, 1 + 3 is 4.1320

Okay, so I am going to go ahead and copy this onto the next page here...1331

(2, 3, 4, 2, 3, 4), so we have something to continue with, alright, so we have got (1, 1, -5 halves, 1, 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 2, 3, 4).1337

We have (0, 0, 2, 3, 4), okay, let's see what is the best way to handle this one next.1362

Let's go ahead and continue with our process, so now we are dealing with, well...1375

... The couple of things that we can do here, you notice, so we have a leading entry, we have all 0's in this column, we have a leading entry here, 0's down here, not a 0 up here.1388

We have a choice, we can go ahead and take care of this 0, and 0 this out now and then deal with what's left over, the ones that don't have leading entries or we can go ahead and continue the process and get leading entries all the way down and then go back and take care of all the other 0's.1398

I think I am going to go ahead and do that, it's more little bit more consistent with the process that we had done, so now this stays, this stays.1417

We will leave those two alone, now we are just dealing with this one, so again we repeat those steps that we did before, (0, 0) this is the first column non-zero entries.1425

And the first entry is here, so now our pivot is here, and notice we don't have to do anything, we don't have to switch anything, it's already at the top, so since the pivot is there, we can go ahead and divide by 2...1436

... We will divide row 3 by 2 to make it a 1, which turns everything into (1, 1, -5 halves, 1 and 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 1, 3, halves)1462

And...1485

... 4 divided by 2 is 2, and then we have (0, 0, 2, 3, 4), okay so now I am going to go...1490

... I am going to go this way just to create a little bit more room, what I am going to do here is I am going to take -2 times this row added to this row, in order to turn this into a 0, so we wil do...1509

... -2 times the third row + the fourth row.1527

And what I end up with is (1, 1, -5 halves, 1, 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 1, 3 halves, 2, 0).1537

When you multiply this out so, -2 times that + that is 0, -2 times that + that, you end up with -3 + 3 is 0, -2 times that is -4 + 4, you end up with this matrix right here.1558

Again we are getting down to where we want it, we have the all 0's down to the bottom, we have leading entries, now we just have to take care of these other 0's to make sure everything else is 0 in the entries that have, in the columns that have leading entries as 1.1575

Okay, so let's see, let's do...1588

... Let's get rid of...1598

... Let's get rid of this 3 halves first, which means I am going to take 3 halves, -3 halves times this row to this row, so let me write own what it is that I am doing.1602

We have -3 half times the third row + the second and when I do that, I end up with...1611

... (1, 1, -5 halves, 1, 2, 0, 1, 0, -17 fourths, -5 halves, 0, 0, 1, 3 halves 2) and of ‘course the bottom one is all 0's.1626

Now I am going to get rid of...1648

... This 5 halves, so I am going to multiply 5 halves times the third row...1652

... + the first row, that will give me (1, 1, 0, 19 fourth, 7, 0, 1, 0, -17 fourths, -5 halves 0, 0)1662

(3 halves, 2) and of ‘course the final 0's...1687

... Now, let's see what we have got, I am going to create a little bit more space here, this time, I'm going to, so I have taken care of this and this are fine, now I just have this one to take care of, so I am going to multiply...1695

-1, oops, -1 times the second row...1713

... + the first row and when I do that I get (1, 0,), let me do this one actually specifically -1 times 1 is -1 + 1 is 0.1720

-1 times 0, 0 + 0, 0, -1 times -17 fourths + 19 fourths, you end up with 19 fourths + 17 fourths, 36 fourths, which is 9.1739

And then the same thing here, -1 times 5 halves is 5 halves + 7, you end up with 19 halves, 0, 1, 0, -17 fourth, -5 halves.1754

Here you get (0, 0, 1, 3 halves and 2, 0, 0, 0, 0, 0).1772

This, my friends is our final...1783

... Reduced row echelon, my apologies for these little marks with the pen here, so the matrix that we started off with through series of operations was converted to this unique reduced row echelon matrix, okay this is unique.1788

It's the only matrix that you'll end up with, notice we have adding entry 1, all 0's leading entry 1 is to the right of this one, all 0's, leading entry 1, it's to the right, all 0's.1804

No leading entry, so it doesn’t matter what these are...1818

... Okay...1825

... Let's go ahead and do one more example, we will move a little but more quickly this time, again we are just doing the same operations that you are accustomed to....1828

... Let's take as our matrix (1, 2, 3, 9, 2, -1, 1, 8, 3, 0, -1, 3) okay.1841

Look for the first column, not all 0's, that's this one, the first non-zero entry here, our pivot is 1, we don't have to do anything to it, it's already at the top.1860

And we don't have to divide by it, it's already a 1, so all we have to do is turn this into a 0, and this into a 0, so I am going to do this in two steps, okay.1868

I'll go ahead and let you do the, what we are going to be dealing is multiplying -2 times the first row + the second, -2 times that, plus that to turn this and do with 0.1879

And the second step we are going to do is -3 times the second row...1892

...-3 times the first row, of ‘course the first row...1900

... Times the first row + the third, so -3 times that + that, so I am going to do it in two steps, I'm going to combine it and just give the final matrix that we get.1908

We should end up with (1, 2, 3, 9, 0, -5, -5, -10, 0, -6, -10, -24), so we have taken care of this one.1918

This is done, now we want to deal with that, so our pivot here, we look for the first column that's non-zero entry, that's here.1936

We will look for the first entry from top to bottom, so our new pivot is -5, so what we want to do is we want to divide everything in here by that number to turn this into a 1.1949

We will go ahead and...1961

We have (1, 2, 3, 9), we have 0, 1, -5 divided by -5, 1, -5 divided by 2, and we have 0, -6, -10, -24.1969

Okay, so now let me move up...1989

... Here, I want to get rid of this, make it a 0, I want to make 0's, everything underneath, so I am going to multiply 6 times...1995

... The second row + the third, so I end up with the matrix 1, oops...2013

... We don't want these, too many of these stray marks to confuse is, my apologies.2023

(1, 2, 3, 9) and the we are going to have (0, 1, 1, 2) and we are going to have (0, 0, -4, -12) okay.2030

We find a new pivot, so in this particular case, we have taken care of that, our new pivot is now -4, because this were always done, this were always done.2051

We have leading entries of 1 and 1, we can take care of the other's layer, who want to work our way down from the top-left to the bottom right.2061

We go ahead and divide this by -4, the whole thing by -4, so let me move on to the next page...2069

... And rewrite this...2079

... We started off with (1, 2, 3, 9, 0, 1, 1, 2, 0, 0, -4, -12) okay.2083

We divide the third by -4, to get (1, 2, 3, 9, 0, 1, 1, 2, 0, 0, 1 and 3).2099

Now we have that and now we just, now we have our 1, we have our 1, we have our 1, we need to convert this to (0, 0) and we need to convert this to 0.2118

Lets go ahead and take...2129

Lets do this in a couple of steps, let's go...2135

… -1 times the third row + the second...2139

... And we will do -3 times the third row, -3 times the third row + the first...2149

... And when we do that we end up with (1, 2, 0, 0, 0, 1, 0, -1, 0, 0, 1, 3).2161

And now what we want to do is we want to get rid of this 2, so we are going to take -2, times the second.2182

We are going to add it to the first, and what we are going to end up with is (1, 0, 0, 2, 0, 1, 0, -1, 0, 0, 1, 3).2195

Now we check the leading entry, leading entry, right goes to the right, these are all 0's, these are 0's, these are 0's no leaving entry problems here, this is irrelevant.2212

Our final...2225

... Reduced row echelon matrix is this matrix (1, 0, 0, 2, 0, 1, 0, -1, 0, 0, 1, -3), let's start it from our initial ones with series of those operations.2229

Find your pivotal column, find your pivot, move it to the top, divide by the pivot to make it a 1, eliminate all the 0's underneath that one.2243

Leave that row alone; move down to the next into the same thing.2254

Find the column that's not all 0's, find the first entry that's not a 0, that's your pivot, move it to the top, divide by it to turn it into alone.2257

Remove all the zeros, do that all the way down in a stereo step fashion, echelon is a Greek word for stereo step, which is why it's like that.2267

It moves in a stereo step from top-left to bottom right, and then once you get down to where you can't really go further, then you go back and you eliminate all the zero's above the ones, to get a unique matrix and reduced row echelon form.2274

Thank you for joining us today at educator.com, look forward to seeing you next time.2290