Subtitles section Play video Print subtitles 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.