2. Elimination with Matrices.

okay this is it this is then the second lecture in linear algebra and uh 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 you would have thought of it right uh I mean gaus thought of it before we did but only because he was born earlier it's a natural idea uh um 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 H all the key ideas get expressed as Matrix operations not as words and uh one of the operations of course that will 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 3X3 Matrix that that so this is the system uh ax equal B you could say this is this is our system to solve ax equal and the right hand side is that Vector 2122 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 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 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 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' I'd like to stick to that convention I'll do a subtraction so what oh 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'm 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 leave so the multiplier is three 3 * that will leave will make that zero that was our purpose 32 is 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 get carried along actually mat lab finishes up with the left side before and then just goes back to do the right side maybe I I'll be matl for for a moment and do that okay so I just like I'm leaving a room for a column of B the right hand side but I 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 21 position row two column one so I got a zero in the 21 position I I'll use 21 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 31 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 mat lab 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 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 is this guy who who has appeared there and what's the multiplier the appropriate multiplier now and what and what's my purpose is to clean up the is to wipe out the 32 position right this was the this was the two1 step and now I'm going to take the 32 step so this all stays the same 1 2 1 0 2 - 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 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 oh did I just invent a negative one I 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 it correct now okay so the three pivots are there I I know right away a lot about this Matrix th 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 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 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 are uh are here okay now oh let me talk about failure for a moment and then and then uh come back to success 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 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 zero I I will not say zero pill 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 changed that eight a little bit I would have got again uh a a little trouble what should I change that 8 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 nonzero 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 r 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 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 oh if 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 -4 good if it was a ne4 here if it happened to be a NE -4 can I can I

I'll temporarily put it up here if if this had been a Nega 4 Z then I would have gone through the same steps this would have been a minus 4 it still would have been aus4 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 mat lab do and what should we do let's let's let me bring in the rightand side as an extra column so there comes B so it's 2122 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 should 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's 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 32s got taken away from 12 leaving six and that two stayed the same so this is the how it's looking halfway along and let 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 two and subtracted from that so I think I take two sixths 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 be 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 + 2 y + Z = 2 is still there then 2 y - 2 Z = 6 is there and 5 Z is -1 okay that those are the equations that are that these numbers are telling me about those are the equations uux equal 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 2 y+ the 4 is six 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 2 y is 2 - 2 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 and Z's in there then I really uh got to write 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 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 121 381 041 I I want to operate on that I 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 by a right hand side if

I have some Matrix there and I multiply it by 345 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 3 * column 1 plus 4 * column 2 + 5 * column 3 okay I'm going to come back to that multiple times what I wanted to do now was to emphasize

the parallel thing be 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 it 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 two7 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 by3 Matrix a row Vector multiplying a 3X3 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 a sorry a matrix times a column is a column so Matrix times 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 one * 1 time Row one plus 2 * row two 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 * time Row one from row two and leaves the other rows the same Ju 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 one0 Z 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 0 01 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 uh didn't have to do anything what Matrix uh does nothing like just leaves you where you were uh if I put in if I put in 0 one Z 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 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 subtract my I I I want three of Row one to get subtracted off so what's that row what's the right m

matx to finish that Matrix for me -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 two should we just like check some particular entry 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 3 so where does the entry in row two column 3 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 dotproduct minus three I'm multiplying minus 3+ one and zero gives the minus two 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 21 because it's the Matrix that we needed to fix the 21 position it's the it's the Matrix that we needed to get this 21 position to be zero okay good enough so what do I do next I need another Matrix right I I need to 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 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 2 * time Row 2 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 use to tell me what e 32 right because it's fixing this 32 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 leave supposed to leave the first row it's supposed to leave the second row and it's supposed to straighten out the third row to to this and what's the Matrix that does that one Z 0 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 I do let's see them I subtract two times so

what's this row what's this here zero right because the first row is not involved the SEC it's just in the 3-2 position isn't it this n 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 the 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 because they're in like little space a few bits when it's compressed

on the web is everything is this whole lecture okay now there 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 th 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 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 facts come from just moving the parentheses it's a it's like and it's not that easy to I mean the to prove that 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 why 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 this this one like Exchange rows so I exchange rows one and two just to make life easy so if I had my Matrix oh let let me just do 2 by two ab 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 the row I want here is up top so I'll take one of that

so actually I've just the easy this is 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 AB c d then I wouldn't I I'm not even going

to write this down I'm just going to ask you cuz it because in elimination we're we're doing rowes but suppose we wanted to exchange The Columns of a matrix H 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 mult 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 a 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 I I I

mentioned in passing but I better say it very clearly that you can't exchange the orders of matrices and 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 gaus given order here right you you but uh but you can move the parenthesis 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 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

you but how do I get from you back to a so reversing steps is going to come in inverse I'll use the 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 invert 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 1 0 0 -3 1 0 0 0 1 and I want to find the Matrix that undo that step so what was that step the step was subtract 3 * Row one from row two so what Matrix will get me back

what Matrix will bring back you know if I started with a 2122 and it changed it to a 262 because of this guy I want to get back to the 2122 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 it does it if this step subtracted 3 * Row one from row two what's the inverse step I add 3 * 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 3 * Row one to row two so I won't change Row one I won't change Row three and I'll add three * 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 St by subtracting three of Row one so to invert it I go that way and if

you if we do that calculation 3 * this row plus 1 time 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 for