Transcript

Okay. This is it. This is then the second lecture in linear algebra. And I've put below my main topics for today. That I I put right there a system of equations. That's going to be our example to work with. But let me 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 so and and elimination uh 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 we'll see how elimination decides whether the matrix is a good one or has has problems. Then to complete the answer, there's a obvious step of back substitution. In fact, the idea of elimination is you would have thought of it. Right? Uh I mean, Gauss thought of it before we did, but only because he was born earlier. It's a natural idea. Uh uh and died earlier, too. Okay, so uh uh but then and you've seen the idea.

But now the part that I want to show you is elimination expressed in matrix language cuz 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 in three unknowns. And there's the matrix, the 3 by 3 matrix that that So, this is the system uh Ax = b, you could say. This is This is our system to solve. Ax = and the right-hand side is that vector 2 12 2. Okay. Now, uh when I describe elimination, it gets to be a pain to keep writing the equal signs and the pluses and so on.

It's the It's that matrix that's that 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 we 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, what what what 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 reduce, to eliminate X. So, what do I multiply And again, I'll do it with this matrix cuz I can do it short.

What what's the multiplier here? What do I multiply equation one and subtract? Notice I'm saying that word subtract. I I'd like to stick to that convention. I'll do a subtraction. So, what First of all, this is the key number, right? That I I'm starting with. And that's called the pivot. I'll put a box around it and 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 I'm going to Uh my first row won't change. But I mean that's the pivot row. But I'm going to use it.

And now finally, let me ask what the multiplier is. Yes. Three. Three times that first equation will knock out that three. Okay. So, what will it leave? So, the multiplier is three. Three times that will leave will make that zero. That was our purpose. Three twos away from the eight will leave a two. And three ones away from one will leave a minus two. And this guy didn't change. Okay. Now, the next step. So, that step of 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 is like gets carried along.

I actually MATLAB finishes up with the left side before and then just goes back to do the right side. Maybe I I'll be MATLAB for for a moment and do that. Okay, so I just like I'm leaving a column room for a column of B, the right-hand side, but I will I'll fill it in later. Okay. Now, the next step of elimination is what? Well, strictly speaking, I should I cleaned up this was the This position that I cleaned up was like the 2 1 position, row two, column one. So, I got a zero in the 2 1 position. I'll I'll use 2 1 as the index of that step. The next step should be to finish the column and get a zero in that position.

So, the next step is really the 3 1 step, row three, column one. But, of course, I already have zero. Okay. So, so the multiplier is zero. I take zero of this equation away from this one, and uh I'm all set. So, I won't repeat that, but there was a step there which uh MATLAB would have to look. It would look at this number and uh do that step unless you told it in advance that it was zero. Okay. Now, uh 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 We're down to two equations in Y and Z. And so, now I just do it again.

Like, everything's recursive at this This is a such a basic algorithm, and it's and you've seen it. But, carry me through one last step. What What's the So, this is still the first pivot. Now, the second pivot is this guy who's who's appeared there. And what's the multiplier the appropriate multiplier now? I And what And what's my purpose? Is to clean up the Is to wipe out the 3 2 position, right? This was the This was the two one step. And now I'm going to take the three two step. So, this all stays the same. 1 2 1 0 2 -1 and the the pivot are there. Now I'm using this pivot. So, what's the multiplier?

Two. Two times this equation, this row, gets subtracted from this row and makes that a zero. So, it's zero zero and what's Is it a five? Yeah, I guess it's a five. Is that right? Cuz I have a one there and I'm subtracting twice of the twice this, so I it think it it's a five there. There's the third pivot. So, let me put a box around all three pivots. Is there a I think that's Oh, did I just invent a negative one? I I I'm sorry that the tape can't the correct that as easily as I can. Okay, is that Thank you very much. Uh You get an A in the course now. Is that Is that Is that correct? Is it correct now?

Okay. So, the three pivots are there. Uh I I know right away a lot about this matrix. The this this elimination step from A this 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 any 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 zero. I don't accept zero as a pivot. And I didn't get zero. So this this matrix is great.

It gave me three pivots. I didn't have to do anything special. I just followed the rules and uh and uh the pivots are 1, 2, and 5. By the way, just cuz I always anticipate stuff from a later day, if I wanted to know the determinant of the the determinant of this matrix, which I never do want to know, uh but I would just multiply the pivots. The determinant is 10. So even things like the determinant are are uh are here. Okay. Now Oh, let me talk about failure for a moment and then and then uh come back to success. Uh How could this have failed? How could um Well, how could By fail, I mean fail to come up with three pivots.

What How Tell me I mean there are a couple of points. I would have already been in trouble if this first very first number here was zero. If it was a zero there, suppose that had been a zero. There were no x's in that equation first equation. It Does that mean I can't solve the problem? Does that mean I quit? No. What do I do? I ex- switch rows. I exchange rows. So in case of a zero, I I will not say zero pivot. I will never be heard to utter those words, zero pivot. But, if there's a zero in the pivot position, maybe I can say that, I would try to exchange for a lower equation and get a non get a proper pivot up there.

Okay. Now, for example, this second pivot came out two. Could it have come out zero? What Actually, if I change that eight a little bit, I would have got again a a little trouble. What What should I change that eight to so that I get some so that I run into trouble? A six. If that had been a six, then this would have been zero and I couldn't have used that as the pivot, but I could have exchanged again. In this case, in this case, because what When can I When can I get out of trouble? I can get out of trouble if there's a non-zero below this this troublesome zero. And there is here. So, I would be okay in this case.

If this was a six, 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 zeros below it, but here there wasn't. Now, I could also have got in trouble if this number one was a little different. See, that one became a five, I guess, by the end. So, do you do you 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 the pivot is All right. If the if zero is in the pivot position and I can't I've got no place to exchange. So, there there there must be some number which if I had had here, it would have meant failure.

Negative four, good. If it was a negative four here, if it happened to be a negative four, can I can I I'll temporarily put it up here. If If this had been a negative four Z, then I would have gone through the same steps. This would have been a minus four. It still would have been a minus four. But at the last minute it would have become zero. And there wouldn't have been a third pivot. The matrix would have not been invertible. Of course, the inverse of a matrix is coming next week, but uh you've heard these words before. So, that that's how we we we identify failure. There's temporary failure when we can do a row exchange and and get out of it.

Or there's complete failure when we get a zero and and there's nothing below that we can use. Okay. Let's stay with uh back to success now. In fact, I guess the next topic is back substitution. So, what's back substitution? Well, that Now, I better bring the right hand side in. So, what would MATLAB do? And what should we do? Let's Let's Let me bring in the right hand side as an extra column. So, there comes B. So, it's 2 12 2. This is I 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 I two of the first equation away from the second equation so that this augmented shall I I even brought some colored chalk, but I don't know if it shows up. So, this is like the augmented No, damn. Circle the wrong thing. Okay, here's the 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, with that was three of this away from this, so it took the two stayed the same, but three twos got taken away from 12 leaving six, and that two stayed the same. So, this is the how it's looking halfway along, and then let me just carry to the end.

The two and the six stay the same, but what do I have here? Oh, gosh. Uh help me out now. What So, now I'm I'm This is This is still like forward elimination. I I got to this point, which I think is right. And now, what did I do with this step? I multiplied that pivot by two or that whole equation by two and subtracted from that. So, I think I take two sixes, which is 12 away from the two. 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, So, what are my final equations then? Can I Can I copy these equations? Uh x + 2y + z = 2 is still there. And 2y - 2z = 6 is there. And 5z is -10. Okay. That Those are the equations that are that these numbers are telling me about. That Those are the equations Ux = c. Okay, how do I solve them? What do What one do I solve for first? z I see immediately that the correct value of z is -2. And what do I do next? I go back upwards. I now know z here. So, uh if z is -2, that's four there. Is that right? And so, 2y + the four is six. Maybe y is one. Going This is This is back substitution.

We're doing it on the fly cuz it's so easy. And then x is So, x 2y's is 2 - 2. Maybe x is 2. So, you see what back substitution is. It's the simple step solving the equations in reverse order because the system is triangular. Okay. Good. So, that's elimination and back substitution. And I kept the right-hand side along. Okay, now what do I What So, that That like is first piece of the lecture. What's the second piece? Matrices are going to get in. So, So, I first I wrote stuff with X's, Y's, and Z's in there. Then I really got the right shorthand just writing the matrix entries. And now I want to write the operations that I did in matrices, right?

I've carried the matrices along, but I haven't said the operation that those those elimination steps I I now want to express as matrices. Okay, here they come. So, now this is elimination matrices. Okay. Let me take that Let me take that first step, which which took me from 1 2 1 3 8 1 0 4 1. I I want to operate on that. I'm I'm want to do uh elimination on that. Okay. Okay. Now, actually I'm I'm remembering a point I want to I want to single out as as as uh specially important. Let me Let me move the board up for that. Cuz when we do matrix operations, we got to like be able to see the big picture.

Okay, last time I spoke about the big picture of when I multiply a matrix by a right-hand side. If I have some matrix there, and I multiply it by 3 4 5, let's say. So, here's a matrix. What did I say? Well, I guess I only said it on the videotape, but do you remember how I look at that matrix multiplication, the result of multiplying a matrix by some vector is a combination of the columns of the matrix. It's three times the first column. It's three times column one plus four times column two plus five times column three. Okay. I'm going to come back to that multiple times. What I wanted to do now was to emphasize the parallel thing with rows.

Why? Because all our operations here for this like this two weeks of the course are row operations. So, I have to So, if this isn't what I need for row operations, let me let me let me do a row operation. Suppose I have my matrix again and suppose I multiply on the left by some, let's say 1 2 7. Again, I'm just like saying what the result is. And then we'll say how matrix multiplication works and we'll see that it's true. Okay. But maybe already I'm making uh uh uh I'm sort of bringing up the central idea of linear algebra is how these matrices work by rows as well as by columns. Okay, how does it work by rows?

What what So, this is a that that's a row vector. It's a It's I could say that's a 1 by 3 matrix. A row vector multiplying a 3 by 3 matrix. What What's the output? What's the product of a row times a matrix? And okay, it's a row. A row A column I Sorry, a matrix times a column is a column. So, matrix times a Yeah, matrix times a column is a column. And we know what column it is. Over here, I'm doing a row times a matrix, and what And what is the What's the answer? It's one of that first row. So, it's 1 * 1 * row 1 plus 2 * row 2 plus 7 * row 3. When as we do matrix multiplication, keep your eye on what it's doing with whole vectors.

And what it's doing what what it's doing in this case is it's combining the rows. We have a combination a linear combination of the rows. Okay, I want to use that. Okay. Now, So, my question is, what's the matrix that does this first step? That takes subtracts three of equation one from equation two. That's what I want to do. So, this is going to be a a matrix that's going to subtract 3 * * row 1 from row two. And leaves the other rows the same. Just just I mean the answer is going to be that. So, whatever matrix this is and you're going to like tell me what matrix will do it. It's the matrix that leaves the first row unchanged, leaves the last row unchanged, but takes three of these away from this.

So, it puts a zero there, a two there, and a minus two. Good. What matrix will do it? It's these. It should be a pretty simple matrix cuz we're doing a very simple step. We're just doing this step that changes row two. So, actually row one is not changing. So, tell me how the matrix should begin. One So, the first row of the matrix will be one zero zero. Because that's just the right thing. That takes one of that row and none of the other rows, and that's what we want. What's the last row of the matrix? Zero zero one. Cuz that takes one of the third row and none of the other rows. That's great.

Okay. Now, suppose I didn't want to do anything at all. Suppose my row Well, I guess maybe I had a a case here when I already had a zero and didn't have to do anything. What matrix does nothing? Like just leaves you where you were. If I put in if I put in zero one zero, that would be that would be That's the matrix. What's the name of that matrix? The identity matrix, right. So it does absolutely nothing. It just multiplies everything and leaves it where it is. It's like a one, like the number one for matrices. But that that's not what we want cuz we want to change this row two. Uh so, what's the correct What should I put in here now to come out to do to do it right?

I want to get What do I want What am I I'm after? I want to sub tract my I I I want three of row one to get subtracted off. So what's that row What's the right matrix to finish that matrix for me? But -3 goes here. And what goes here? That one. And what goes here? The zero. That's the good matrix. That's the matrix that takes -3 of row one plus the row two and gives the new row two. Should we just like check uh some particular entry? How How do I check a particular entry of a matrix in in matrix multiplication? Like suppose I wanted to check the entry here that's in row two, column three. So where does the entry in row two, column three come from?

I would look at row two of this guy and column three of this one to get that number. That number comes from the second row and the third column and I just take this dot product. -3 I'm multiplying. -3 + 1 and 0 gives the -2. Yeah, it it works. So we got various ways to multiply matrices now. We're We're sort of like informally we've got by columns, we've got Well, we will have by columns, by rows, by each entry at a time, but it's good to see that matrix multiplication when one of the matrices is so simple. So, this guy is our elementary matrix. Let's Let's call it E for elementary or elimination.

And let me put the indexes 2 1 because it's the matrix that we needed to fix the 2 1 position. It's the It's the matrix that we needed to get this 2 1 position to be zero. Okay. Good enough. So, what do I do next? I need another matrix, right? I I need some I I There's There's another step here. And I want to express the whole elimination process in matrix language. So, tell me what now Now, so next step, step two which was what? Subtract What was What was the actual step that we did? I think I subtracted, do you remember? I had a two in the pivot and a four below it, so I subtracted two times times row two from row three.

From row three. Tell me the matrix that'll do that. And tell me its name. Okay, it's going to be E for elementary or elimination matrix, and what's the index number that that that I used to tell me what E 3 2, right? Because So fixing this 3 2 position. And what's what is the matrix now? Okay, you remember so E32 is supposed to multiply my guy that I have. And it's supposed to produce the right result which was it leaves supposed to leave the first row, it's supposed to leave the second row, and it's supposed to straighten out that third row to to this. And what's the matrix that does that? 100, right?

Because we don't change the first row. And the next row we don't change either. And the last row is the one we do change. And what do I do? Let's see the I've subtract two times So what's this row? What's this here? Zero, right? Because the first row is not involved. The second it's just in the 32 position, isn't it? It's num the key number is this minus the multiplier that goes sitting there in that 32 position. So it's a Is it a minus two? To subtract two and then this is a one so that I I the the overall effect is to take minus two of this row plus one of that. Okay. So I've now given you the pieces.

The elimination matrices, the elementary matrices that take each step. So now what? Now the next point in the lecture is to put those steps together into a matrix that does it all. And and see how it all happens. So now I'm going to express the whole, everything we did today so far on on A. Was to start with A, we multiplied it by E21. That was the first step. And then we multiplied that result by E32. And that led us to this thing, and what was that matrix? U. You see why I like matrix notation cuz there in like little space, a few bits when it's compressed on the web is everything is this whole lecture.

Okay. Now, there are there are important facts about matrix multiplication. And we're close to maybe the most important. And that that is this. Suppose I ask you this question. Suppose I start start with a matrix A, and I want to end with a matrix U, and I want to say, what matrix does the whole job? What matrix takes me from A to U? Using the letters I've got. So, and the answer is simple. I'm not asking this is but it's highly important. How could I how would I create the matrix that does the whole job at once? That does all of elimination in one shot. It would be I would just put these together, right?

In other words, this is the thing I'm struggling to say. I can move those parentheses. If I keep the matrices in order, I can't mess around with the order of the matrices, but I can change the order that I do the multiplications. I can multiply these two first. In other words, you see what those parentheses are doing? It's saying do multiply the E's first. And that gives you the matrix that does everything at once. Okay. What So, this fact that this is automatically the same as this. For every matrix multiplication, which I'm conscious of still not telling you in every detail. But like you're seeing how it works.

And this is highly important and maybe tell me the long word that that describes this law for matrices. That that you can move the parentheses. It's the called the associative law. I I think you can now forget that. Uh it's uh But don't forget the law. I mean like forget the word associative. I don't know. But don't don't forget the law. Because actually we'll see so many uh steps in linear algebra. So many proofs even of of of main fact come from just moving the parentheses. It's a it's like And it's not that easy to I mean the to prove to prove that this is correct, you have to go into the gory details of matrix multiplication, do it both ways, and see that you come out the same.

Maybe I'll leave the uh author to do that. Okay. So, there we go. That's That's uh That's how I So, there's a a single matrix. I I could call it E. Now, oh while while we're talking about these matrices, tell me one other There's another type of elementary matrix. And we already said why we might need it. We We didn't need it in this case, but it's the matrix that exchanges two rows. It's a called a permutation matrix. Can you just like tell me what that would be? So, I'm just like this is a slight digression. And we'll Yeah, so let me get some Let me figure out where I'm going to put a permutation matrix.

You'll see I'm always squeezing stuff in. So, permutation. Or in fact, uh this this one uh like exchange rows. So, I exchange rows one and two just to make life easy. So, if I had my matrix, uh let me just do two by two. A B C D. Suppose I want to find the matrix that exchanges those rows. What is it? So, the matrix that exchanges those rows, the the row I want is C D and it's there. So, I I better take one of it. The row I want here is up top, so I'll take one of that. So, actually, I've just the easy way This is the my matrix that I'll call P for permutation. It's the matrix Actually, the the easy way to find it is just do the thing to the identity matrix.

Exchange rows Exchange the rows of the identity matrix, and then that's the matrix that'll do do row exchanges for you. Could Suppose I wanted to exchange columns instead. Columns have hardly got into today's lecture, but they certainly are going to be around. How could I if I started with this matrix ABCD and then I wouldn't I I'm not even going to write this down. I'm just going to ask you. Cuz it Cuz in elimination, we're we're doing rows. But suppose we wanted to exchange the columns of a matrix. How How would I do that? What What What matrix multiplication would do that job? Actually, why not?

I'll write it down. So this is like just I'll write it under here and then hide it again. Okay. Suppose I had my matrix ABCD and I want to get to AC over here and BD here. What matrix does that job? Can I multiply Can I cook up some matrix that produces that answer? And I You can see from where I put my hand, I was really asking can I put a matrix here on the left that will exchange columns? And the answer is no. If I So I'm just bringing out again this point that when I multiply on the left, I'm doing row operations. So, if I want to do a column operation, where do I put that permutation matrix?

On the on the right. If I put it here, where I just barely left room for it. So, I I'll exchange the two columns of the identity. Then it comes out right. Cuz now I'm multiplying a column at a time. This This is the first column and says take one take none of that column, one of this one, and then you got it. Over here, take one of this one, none of this one, and you've got AC. So, in short, to do column operations, the matrix multiplies on the right. To do row operations, it multiplies on the left. Okay. Okay. And it's row operations that we're really doing. Okay. And of course, do it I I I mentioned in passing, but I better say it very clearly that you can't exchange the orders of matrices.

And that's just the point I was making again here. A * B is not the same as B * A. You have to keep these matrices in their Gauss-given order here, right? You You But uh but you can move the parentheses. So, that In other words, the commutative law, which would allow you to take it in the other order, is false. So, we have to keep it in that order. Okay. So, uh What What next? I could do this multiplication. I could do E32. So, let me come back to see what that was. Here was E21. And here is E32. And if I multiply those matrices together, E32 and then E21, I'll get a single matrix that does elimination.

Uh I don't want to do it that. I don't I don't If I do that multiplication, there there's a better way to do this. And and and so in this last few minutes of today's lecture, can I anticipate that better way? The better way is to think not how do I get from A to U, but how do I get from U back to A? So, reversing steps is going to come in. Inverse I'll use the word inverse here. Okay. So, let me make the first step at what's the inverse matrix. All the matrices you've seen on this board have inverses. I I didn't write any bad matrices down. We we spoke about possible failure and for a moment we put in a matrix that would fail.

But right now, all these matrices are good. They're all invertible. And let's take the inverse Well, let me say first what is the inverse mean and find it. Okay, so we're getting a little leg up on inverses. Okay. So this is the final moments of today. Ah, sorry. He's still there. Okay. Inverses. Okay, and I'm just going to take one example and then we're done. The example I'll take will be that E. I'm So my matrix is 1 0 0 -3 1 0 0 0 1. And I want to find the matrix that undoes that step. So what was that step? The step was subtract three times row one from row two. So what matrix will get me back?

What matrix will bring back you know, if I started with a 2 12 2 and it changed it to a 2 6 2 because of this guy, I want to get back to the 2 12 2. I want to I want to find the matrix which which undoes elimination. The matrix which multiplies this to give the identity. And you can tell me what I should do in words first and then we'll write down the matrix that does it. If this step subtracted three times row one from row two, what's the inverse step? I add three times row one to row two, right? I add it back. What I subtracted away I add back. So, the inverse matrix in this case is I I now want to add three times row one to row two.

So, I won't change row one. I won't change row three. And I'll add three times row one to row two. That's a case where the inverse is clear. It's clear in words what to do. Because what this did was simple to express. It just changed row two by by subtracting three of row one. So, to invert it I go that way. And if you if we do that calculation, three times this row plus one times this row comes out the right row of the identity. Okay. So, inverses are and So, if this matrix was E and this matrix is I for identity, then what's the notation for this guy? E to the minus one. E inverse. Okay. Let Let's stop there for today.

That's the a little jump on what's coming on Monday. So, see you Monday.