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