 ## Subtitles section Play video

• Okay. This is it.

• The second lecture in linear algebra, and I've put below my

• main topics for today. I put right there a system of

• equations that's going to be our example to work with.

• But what are we going to do with it?

• We're going to solve it. And the method of solution will

• not be determinants. Determinants are something that

• will come later. The method we'll use is called

• elimination. And it's the way every software

• package solves equations. And elimination,

• well, if it succeeds, it gets the answer.

• And normally it does succeed. If the matrix A that's coming

• into that system is a good matrix, and I think this one is,

• then elimination will work. We'll get the answer in an

• efficient way. But why don't we,

• as long as we're sort of seeing how elimination works -- it's

• always good to ask how could it fail?

• So at the same time, we'll see how elimination

• decides whether the matrix is a good one or has problems.

• Then to complete the answer, there's an obvious step of back

• substitution. In fact, the idea of

• elimination is -- you would have thought of it,

• right? I mean Gauss thought of it

• before we did, but only because he was born

• earlier. It's a natural idea...

• and died earlier, too.

• Okay, and you've seen the idea. But now, the part that I want

• to show you is elimination expressed in matrix language,

• because the whole course -- all the key ideas get expressed

• as matrix operations, not as words.

• And one of the operations, of course, that we'll meet is

• how do we multiply matrices and why?

• Okay, so there's a system of equations.

• Three equations and three unknowns.

• And there's the matrix, the three by three matrix -- so

• this is the system Ax = b. This is our system to solve,

• Ax equal -- and the right-hand side is that vector 2,

• 12, 2. Okay.

• Now, when I describe elimination -- it gets to be a

• pain to keep writing the equal signs and the pluses and so on.

• It's that matrix that totally matters.

• Everything is in that matrix. But behind it is those

• equations. So what does elimination do?

• What's the first step of elimination?

• We accept the first equation, it's okay.

• I'm going to multiply that equation by the right number,

• the right multiplier and I'm going to subtract it from the

• second equation. With what purpose?

• So that will decide what the multiplier should be.

• Our purpose is to knock out the x part of equation two.

• So our purpose is to eliminate x.

• So what do I multiply -- and again, I'll do it with this

• matrix, because I can do it short.

• What's the multiplier here? What do I multiply -- equation

• one and subtract. Notice I'm saying that word

• subtract. I'd like to stick to that

• convention. I'll do a subtraction.

• First of all this is the key number that I'm starting with.

• And that's called the pivot. I'll put a box around it and

• write its name down. That's the first pivot.

• The first pivot. Okay.

• So I'm going to use -- that's sort of like the key number in

• that equation. And now what's the multiplier?

• So I'm going to -- my first row won't change,

• that's the pivot row. But I'm going to use it -- and

• now, finally, let me ask you what the

• multiplier is. Yes?

• 3. 3 times that first equation

• will knock out that 3. Okay.

• So what will it leave? So the multiplier is 3.

• 3 times that will make that 0. That was our purpose.

• 3 2s away from the 8 will leave a 2 and three 1s away from 1

• will leave a minus 2. And this guy didn't change.

• Okay. Now the next step -- this is

• forward elimination and that step's completed.

• Oh, well, you could say wait a minute, what about the right

• hand side? Shall I carry -- the right-hand

• side gets carried along. Actually MatLab finishes up

• with the left side before -- and then just goes back to do the

• right side. Maybe I'll be MatLab for a

• moment and do that. Okay.

• I'm leaving a room for a column of b, the right-hand side.

• But I'll fill it in later. Okay.

• Now the next step of elimination is what?

• Well, strictly speaking... this position that I cleaned up

• was like the 2, 1 position, row 2,

• column 1. So I got a 0 in the 2,

• 1 position. I'll use 2,1 as the index of

• that step. The next step should be to

• finish the column and get a 0 in that position.

• So the next step is really the 3,1 step, row three,

• column one. But of course,

• I already have 0. Okay.

• So the multiplier is 0. I take 0 of this equation away

• from this one and I'm all set. So I won't repeat that,

• but there was a step there which, MatLab would have to look

• -- it would look at this number and, do that step,

• unless you told it in advance that it was 0.

• Okay. Now what?

• Now we can see the second pivot, which is what?

• The second pivot -- see, we've eliminated -- x is now

• gone from this equation, right?

• We're down to two equations in y and z.

• And so now I just do it again. Like, everything's very recursive

• at this -- this is like -- such a basic algorithm and

• you've seen it, but carry me through one last

• step. So this is still the first

• pivot. Now the second pivot is this

• guy, who has appeared there. And what's the multiplier,

• the appropriate multiplier now? And what's my purpose?

• Is it to wipe out the 3, 2 position, right?

• This was the 2, 1 step.

• And now I'm going to take the 3, 2 step.

• So this all stays the same, 1 2 1, 0 2 -1 and the pivots

• are there. Now I'm using this pivot,

• so what's the multiplier? 2.

• 2 times this equation, this row, gets subtracted from

• this row and makes that a 0. So it's 0, 0 and is it a 5?

• Yeah, I guess it's a 5, is that right?

• Because I have a one there and I'm subtracting twice of twice

• this, so I think it's a 5 there. There's the third pivot.

• So let me put a box around all three pivots.

• Is there a -- oh, did I just invent a negative

• one? I'm sorry that the tape can't,

• correct that as easily as I can.

• Okay. Thank you very much.

• You get an A in the course now. Is that correct?

• Is it correct now? Okay.

• So the three pivots are there -- I know right away a lot about

• this matrix. This elimination step from A --

• this matrix I'm going to call U. U for upper triangular.

• So the whole purpose of elimination was to get from A to

• U. And, literally,

• that's the most common calculation in scientific

• computing. And people think of how could I

• do that faster? Because it's a major,

• major thing. But we're doing it the

• straightforward way. We found three pivots,

• and by the way, I didn't say this,

• pivots can't be 0. I don't accept 0 as a pivot.

• And I didn't get 0. So this matrix is great.

• It gave me three pivots, I didn't have to do anything

• special, I just followed the rules and, and the pivots are 1,

• 2 and 5. By the way, just because I

• always anticipate stuff from a later day, if I wanted to know

• the determinant of this matrix --

• which I never do want to know, but I would just multiply the

• pivots. The determinant is 10.

• So even things like the determinant are here.

• Okay. Now -- oh, let me talk about

• failure for a moment, and then --

• and then come back to success. How could this have failed?

• How could -- by fail, I mean to come up with three

• pivots. I mean, there are a couple of

• points. I would have already been in

• trouble if this very first number here was 0.

• If it was a 0 there -- suppose that had been a 0,

• there were no Xs in that equation -- first equation.

• Does that mean I can't solve the problem?

• Does that mean I quit? No.

• What do I do? I switch rows.

• I exchange rows. So in case of a 0,

• I will not say 0 pivot. I will never be heard to utter

• those words, 0 pivot. But if there's a 0 in the pivot

• position, maybe I can say that, I would try to exchange for a

• lower equation and get a proper pivot up there.

• Okay. Now, for example,

• this second pivot came out two. Could it have come out 0?

• What -- actually, if I change that 8 a little

• bit, I would have got a little trouble.

• What should I change that 8 to so that I run into trouble?

• A 6. If that had been a 6,

• then this would have been 0 and I couldn't have used that as the

• pivot. But I could have exchanged

• again. In this case.

• In this case, because when can I get out of

• trouble? I can get out of trouble if

• there's a non-0 below this troublesome 0.

• And there is here. So I would be okay in this

• case. If this was a 6,

• I would survive by a row exchange.

• Now -- of course, it might have happened that I

• couldn't do the row, that -- that there was 0s below

• it, but here there wasn't. Now, I could also have got in

• trouble if this number 1 was a little different.

• See, that 1 became a 5, I guess, by the end.

• So can you see what number there would have got me trouble

• that I really couldn't get out of?

• Trouble that I couldn't get out of would mean if 0 is in the

• pivot position and I've got no place to exchange.

• So there must be some number which if I had had here it would

• have meant failure. Negative 4, good.

• If it was a negative 4 here -- if it happened to be a negative

• 4, I'll temporarily put it up here.

• If this had been a negative 4 z, then I would have gone

• through the same steps. This would have been a minus 4,

• it still would have been a minus 4.

• But at the last minute it would have become 0.

• And there wouldn't have been a third pivot.

• The matrix would have not been invertible.

• Well, of course, the inverse of a matrix is

• coming next week, but, you've heard these words

• before. So, that's how we identify

• failure. There's temporary failure when

• we can do a row exchange -- and get out of it,

• or there's complete failure when we get a 0 and -- and

• there's nothing below that we can use.

• Okay. Let's stay with -- back to

• success now. In fact, I guess the next topic

• is back substitution. So what's back substitution?

• Well, now I'd better bring the right-hand side in.

• So what would MatLab do and what should we do?

• Let me bring in the right-hand side as an extra column.

• So there comes B. So it's 2, 12,

• 2. I would call this the augmented

• matrix. "Augment" means you've tacked

• something on. I've tacked on this extra

• column. Because, when I'm working with

• equations, I do the same thing to both sides.

• So, at this step, I subtracted 2 of the first

• equation away from the second equation so that this augmented

• -- I even brought some colored chalk, but I don't know if it

• shows up. So this is like the augmented

• -- no! Damn, circled the wrong thing.

• Okay. Here is b.

• Okay, that's the extra column. Okay.

• So what happened to that extra column, the right-hand side of

• the equations, when I did the first step?

• So that was 3 of this away from this, so it took -- the 2 stayed

• the same, but three 2s got taken away from 12,

• leaving 6, and that 2 stayed the same.

• So this is how it's looking halfway along.

• And let me just carry to the end.

• The 2 and the 6 stay the same, but -- what do I have here?

• Oh, gosh. Help me out,

• now. What -- so now I'm --

• This is still like forward elimination.

• I got to this point, which I think is right,

• and now what did I do at this step?

• I multiplied that pivot by 2 or that whole equation by 2 and

• subtracted from that, so I think I take two 6s,

• which is 12, away from the 2.

• Do you think minus 10 is my final right-hand side -- the

• right-hand side that goes with U, and let me call that once and

• forever the vector c. So c is what happens to b,

• and U is what happens to A. Okay.

• There you've seen elimination clean.

• Okay. Oh, what's back substitution?

• So what are my final equations, then?

• Can I copy these equations? x+2y+z=2 is still there and

• 2y-2z=6 is there, and 5z=-10.

• Okay. Those are the equations that

• these numbers are telling me about.