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 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 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 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 in three unknowns and there's the Matrix the three by three Matrix that that so this is the system uh a x equal B you could say this is this is our system to solve a x equal and the right hand side is that Vector 212 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 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 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 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 because 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 gonna I'm going to 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 you 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 we'll make that zero that was our purpose three twos away from the eight we'll 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 that steps 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 actually Matlab finishes up with the left side before and then just goes back to do the right side maybe uh I'll be Matlab for for a moment and do that okay so I just like I'm leaving a car 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 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 two one position I'll use two one as the index of that step The Next Step should be to finish the column and uh get a zero in that position so the next step is really the three one 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 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 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 has 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 one two one zero two minus one and the the pivots 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 because I have a one there and I'm subtracting twice of the twice this so I think it sits 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'm sorry that the tape can't uh 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 that correct now okay so the three pivots are there I know right away a lot about this Matrix this this elimination step from a this this Matrix I'm going to call you you 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 the pivots are one two and five by the way just because I always anticipate stuff from a later day if I wanted to know the determinant of the determinant of this Matrix which I never do want to know but I would just multiply the pivots that determine it is 10. so even things like the determinant are are 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 um well how could by fail I mean failed to come up with three pivots how 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 in the first equation does that mean I can't solve the problem does that mean I quit no what do I do IX switch rows I exchange rows so in case of a zero 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 nun get a proper pivot up there okay now for example this second pivot came out too could it have come out zero what actually if I change that eight a little bit I would have got again uh a little trouble 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 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 wrong that that there were 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 a pivot is or if if zero is in the pivot position and I can't I've got no place to exchange so 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 4 here if it happened to be a negative 4 can I can I I'll temporarily put it up here if this had been a negative 4z 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 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 the no 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 subtracted two of the first equation away from the second equation so that this augmented I even brought some color 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 that was three of this away from this so it took the two stayed the same but 3-2s got taken away from 12 leaving 6 and that two stayed the same so this is the how it's looking halfway along and 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 at this step I multiplied that pivot by two or that whole equation by 2 and subtracted from that so I think I take two sixes which is 12 away from the two do you think minus ten is my final right hand side the right hand side that goes with you 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 Plus 2y plus Z equals 2 is still there and 2y minus 2z equals 6 is there and 5z is minus ten okay that those are the equations that are that these numbers are telling me about those are the equations u x equals c okay how do I solve them what what one do I solve for first Z I see immediately that the correct value of Z is negative two and what do I do next I go back upwards I now know Z here so uh if Z is negative two that's four there is that right and so 2y plus the 4 is 6 maybe Y is one going this is this is back substitution we're doing it on the Fly because it's so easy and then X is so x two y's is 2 minus two maybe X is two 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 y's and Z's in there then I really uh 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 the the the 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 one two one three eight one oh four one I I want to operate on that I 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 especially important let me let me move the board up for that because we 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 buy a right hand side if I have some Matrix there and I multiply it by three four five 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 one two seven 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 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's a row vector it's a it's I could say that's a one by three Matrix a row Vector multiplying a three by three Matrix what what's the output what's the product of a row times a matrix and okay it's a row a column sorry a matrix times a column is a column so Matrix times a 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 times 1 times Row one plus 2 times Row 2 plus 7 times Row three 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 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 matrix that's going to subtract 3 times Row one from row 2. and leaves the other rows the same 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 because 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 because 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 0 1 0 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's not what we want because 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 subtract my I I want three of Row one to get subtracted off so what's that row what's the right Matrix the finish that Matrix for me but negative 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 minus three of Row one plus the row two and gives the new row 2. should we just like check some particular entry how do I check a particular entry of a matrix in matrix multiplication like suppose I wanted to check the entry here that's in Row 2 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 minus three I'm multiplying minus 3 plus 1 and 0 gives the minus two yeah it works so we got various ways to multiply matrices now 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 two one 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 to I I have 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 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 I use to tell me what e three two right because it's 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 one zero zero 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 them I 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 3-2 position isn't it this num the key number is this minus the multiplier that goes sitting there in that three two position so it's a is it a minus two to subtract two and then this is a one so that I uh 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 you you see why I like Matrix notation because 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 main facts come from just moving the parentheses it's a it's like and it's not that easy that I mean 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 author to do that okay so there we go that's that's uh that's how I so there's a single Matrix I I could call it e now oh one 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 didn't need it in this case but it's the Matrix that exchanges two rows it's 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 this this one will like Exchange rows so I exchange rows one and two just to make life easy so if I had my Matrix oh 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 CD and it's there so I I better take one of it and 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 my Matrix that I'll call P for permutation it's the Matrix actually 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 a b c d then I wouldn't I I'm not even going to write this down I'm just going to ask you because it because in elimination we're we're doing robes but suppose we wanted to exchange The Columns of a matrix 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 a b c d 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 must 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 because now I'm multiplying a column at a time this the 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 mentioned in passing but I better say it very very clearly that you can't exchange the orders of matrices and that's just the point I was making again here A times B is not the same as B times a you have to keep these matrices in their gauss-given order here right 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's a better way to do this 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 you 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 does 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 one zero zero minus three one zero zero zero one and I want to find the Matrix that undoes that step so what was that step the step was subtract 3 times Row 1 from row two so what Matrix will get me back what Matrix will bring back you know if I started with a 212 2 and it changed it to a 262 because of this guy I want to get back to the 212 two 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 3 times Row 1 from row two what's the inverse step I add 3 times Row one to row two right I added back what I subtracted away I add back so the inverse Matrix in this case is I now want to add 3 times Row 1 to row 2. so I won't change Row one I won't change Row three and I'll add 3 times Row 1 to row 2. 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 3 times this row plus 1 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's stop there for today that's the a little jump on what's coming on Monday so see you Monday