# 4. Factorization into A = LU

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=MsIvs_6vC38
**Transcript page:** https://www.withtranscript.ai/video/MsIvs_6vC38

## Chapters

- 0:12 — Chapter 1 (0:12)
- 6:02 — Chapter 2 (6:02)
- 18:25 — Chapter 3 (18:25)
- 20:26 — Chapter 4 (20:26)
- 24:05 — Chapter 5 (24:05)
- 26:42 — Chapter 6 (26:42)
- 34:22 — Chapter 7 (34:22)
- 41:34 — Chapter 8 (41:34)

## Transcript

**[0:12]:** okay this is linear algebra lecture four and uh the first thing I have to do is something that was on the list for last time but here it is now what's the inverse of a product If I multiply two matrices together and I know they're inverses how do I get the inverse of a * B so I know what inverses mean for a single Matrix a and for a matrix B what Matrix do I multiply by to get the identity if I have AB okay that that'll be simple but so basic then uh then I'm going to use use that to I will have a product of matrices and the product that we'll meet will be these elimination matrices and the net result of today's lecture is the big formula for elimination so the the net result of today's lecture is this is this great way to look at gaussian elimination we know that we

**[1:28]:** get from a to U by elimination we know the steps but now we get the right way to look at it AAL Lu so that's the high point for today okay can I take the easy part the the first step first uh so suppose a is invertible and of course it's going to be a big question when is a matrix invertible but let's say a is invertible and B is invertible then what Matrix gives me the inverse of ab so so that's the direct question what's the inverse of ab do I multiply those separate inverses yes I I multiply the two matrices a inverse and B inverse but what order do I multiply in reverse order and you see why so the the right thing to put here is B inverse a inverse that the inverse I'm after I we we can just check that AB times that Matrix gives the identity okay so why

**[2:41]:** once again it's this fact that I can move parentheses around I can actually I can just erase them all and do the multiplications any way I want to so what's the right multiplication to do first B * B inverse this this product here is the identity then a * the identity is the identity and then finally a * a inverse gives the idty so forgive the dumb dumb example in the book it's just why do you why do you uh do the inverse things in reverse order it's just like taking you take off your shoes you take off your socks then the good way to invert that process is socks back on first then Sho sorry okay I'm sorry that's on tape but all right um and of course on the other side we should really just check on the other side I'd have B inverse a inverse that does multiply a b and this

**[3:51]:** time it's these guys that give the identity squeeze down they give the identity we're in shape okay so there's the there where's the inverse good while we're at it let me do a transpose cuz the next lecture has got a lot to involves transposes so how do I if I transpose a matrix I'm talking about square and vertial matrices right now if I transpose one what's its inverse well the nice formula is let's see let me start from a a inverse equal the identity and let me transpose both sides that that will bring a transpose into the picture so if I transpose the identity Matrix what do I have the identity right if I if I exchange rows and columns the identity is a symmetric Matrix it doesn't know the difference if I transpose these guys that product then again it turns out that I have to trans I have to reverse the order I

**[5:09]:** can transpose them separately but when I multiply those transposes come in the opposite order so it's a inverse transpose time a transpose giving the identity so that's this equation it just comes directly from that one but this equation tells me what I wanted to know namely what is the inverse of this guy a transpose what's the inverse of that if I transpose a matrix what what's the inverse of the result and this equation telling me that here it is this is this is the inverse this is the inverse of a transer inverse of a trans

**[6:02]:** of a I I just so I'll put a big circle around that because that's the answer we that's the best answer we could hope for that if you want to know the inverse of a transpose and you know the inverse of a then you just transpose that so in in to put it another way transpose and inversing you can do in either order for a single okay so that these are like basic facts that we can now use all right so now I put it to use I put it to use by thinking we're we're really completing uh the subject of elimination actually I the thing about elimination is it's it's the right way to to understand what the Matrix has got this AAL L is the most basic factorization of a matrix um it's it's I always worry that you will think this course is just uh is all elimination it's just throw operations and please don't it's it will will be beyond that uh but it's the right uh it's the right uh algebra to do first okay so I'm

**[7:43]:** coming near the end of it but I want to get it in a decent form so my decent form is Matrix form I have a matrix a let's suppose it's a good Matrix I can do elimination no row exchanges so no row exchanges for now pivots all fine nothing zero in the pivot position I get to the very end which is U so I get from a to U and I want to know what's the connection how is a related to you and this is going to tell me that there's a matrix L that connects okay can I can I do it for a 2X two first okay 2 by two uh elimination okay so I'll do it under here okay so let let my Matrix a be uh let's let's just we'll keep it simple say two and an eight so we know that the first pivot is a two and the multiplier is

**[8:50]:** going to be a four and then let me put a one here and what number do I not want to put there four I don't want a four there because in that case the second pivot would not we wouldn't have a second pivot The Matrix would be singular General screw up okay so let me put some other number here like seven okay okay now I want to operate on that with my elementary Matrix so what's what's the elementary Matrix I'm I'll strictly speaking it's E21 because it's it's the guy that's going to produce a zero in that position and it's going to produce you in one in one shot because it's just a 2X two Matrix uh so 2 one and I'm going to take four of those away from those produce that zero and leave a three there and that's you and what's the Matrix that did it quick review then what's the elimination

**[9:57]:** Elementary Matrix E2 2 1 it's 1 Z thanks and -41 right good okay so that I I you see the difference between this and what I'm shooting for I'm shooting for a on one side and the other matrices on the other side of the equation okay so I can do that right away now I'm now here's going to be my AAL l and you won't have any trouble telling me what uh so a is still 2187 L is what you're going to tell me and U is still 2 1 03 okay so what's l in this case well first so how is L related to this e gu it's the inverse because I want multiply through by the inverse of this which will put the identity here and the inverse will show up there and I'll call it l so what is the inverse of this remember that's uh those those elimination matrices are

**[11:15]:** easy to invert the inverse Matrix for this one is 1 Z 41 it's it has the plus sign because it adds back what this removes okay do you want so if if we did the numbers right we must this this should be correct okay and of course it is that that says the first row is Right four * the first row plus the second row is 87 good okay that's simple 2x two but it already shows the form that we're headed for it shows so what's the L stand for why the letter L If U stood for upper triangular then of course L stands for lower triangle and actually it has ones on the diagonal where this thing has the pivots on the diet oh sometimes uh we may want to separate out the pivot so can I just mention that sometimes we could also write this as we could have this one41 I'll just

**[12:34]:** show you how I would divide out this Matrix of pivots 2 3 there's a diagonal matrix and I've just whatever is left is here now what left if I divide this first row by two to pull out the two then I have a one and a 1/2 and if I divide the second row by three to pull out the three then I have a one so that's the if this is l u this is maybe called l d for pivot U and now it's a little more balanced because we have ones on the diagonal here and here and the diagonal matrix in the middle so both of those mat lab would would uh produce uh either one I I'll basically stay with L okay now I have to think about bigger than 2x two right now this was just like easy exercise and to tell the truth that this one with a minus sign and

**[13:49]:** this one with a plus sign uh I mean that's the only difference but with 3x3 there's a more significant difference let me let me show you how that works let me let me uh move up to a 3X3 let's say some Matrix a okay just imagine it's 3x3 I won't write numbers down for now so what what's the first elimination step that I do the first Matrix I multiply it by what what what letter will I use for that it's the it it be e to one because it's the it's the first step will be to get a to get a zero in that 21 position and then the next step will be to get a zero in the 31 position and the final step will be to get a zero in the 32 position that's what elimination is and it produce you and again no row

**[15:03]:** exchange we will I'm taking the nice case now the typical case too when I don't have to do any row exchange all I do is these elimination steps okay now suppose I want that stuff over on the right hand side as I really do that that's like my point here I I can multiply these together to get a matrix e but I want it over on the right I want its inverse over there so what what's the what's the right expression now how if I write a and u what goes

**[15:45]:** there okay so I've got the inverse of this I've got three matrices in a row now and it's their inverses that are going to show up cuz each one is easy to invert question is what about the whole bunch how how how easy is it to invert the whole bunch so that's what we know how to do we know how to invert we should take the separate inverses but they go in the opposite order so what goes here e32 inverse right cuz I'll multiply from the left by e32 inverse it'll pop it up next to you and then we come E31 inverse and then this will be I'll be this will be the only guy left standing and that's gone when I do an E21 inverse so there is L that's that's l u l is this product of inverses now you still can ask why is this guy preferring inverses and let me explain why let me explain why why is this product nicer than this one this this product turns out to be

**[17:08]:** better than this one let me take a typical case here uh let me let me take a typical case so so let me I have to do 3x3 for you to see the see the Improvement 2 by two there was just one e no no problem but let me go up to this case suppose my matrices E21 suppose E21 has a has a minus two in there suppose that and now suppose oh I'll even suppose E31 is the identity so I'll just I'm just going to I'm going to make the point with just a couple of these okay now this guy will have do something now let let's suppose - 5 what okay there's temp that's a typical case in which we didn't need an E31 maybe we already had a zero in that 31 position okay let me see if that is that going to be enough to uh show my point let's let

**[18:25]:** me do that multiplication

**[18:29]:** okay so if I do that multiplication this is it's like good practice to multiply these matrices tell me what's above the diagonal when I do this multiplication all zeros when I do this multiplication I'm going to get ones on the diagonal and Zer above because what does that say that says that I'm subtracting rows from lower rows so nothing nothing is moving upwards as it did last time in in G Jordan okay now so really the uh what I have to do is check this - 2 1 Z now this is so what am I what's that number that this is the number that I'm really have in mind that number is 10 and this one is what goes here Row three against column two looks like the minus5

**[19:33]:** what it's that 10 how did that 10 get in there I don't like that 10 I mean of course I don't want to erase it because it's right but I don't wanted that uh it's because the 10 got in there because I subtracted two of Row one from row two and then I subtracted five of that new row two from Row three so doing it in that order how did Row one affect Row three well it did cuz two of it got removed from row two and then five of those got removed from Row three so alog together 10 of Row one got got thrown into Row three now my point is in the reverse Direction so now I can do now I'll do below it I'll do the

**[20:26]:** inverses okay and of course opposite order reverse order reverse

**[20:35]:** order okay so now this is going to this is the this is the E that go goes on the left side left of a now I'm going to do the inverses in the opposite order so what's the so so the opposite order means I put this Inverse First and what is its inverse what's the inverse of E21 same thing with a plus sign right for for this for the individual matrices instead of taking away two I add back two of Row one to row two so no problem and now in reverse order I want to invert that just just right I'm doing just this this so now the inverse is again the same thing but add in the five and now I'll do that multiplication and I'll get a happy result I hope did I do it right so far yes okay let me do the multiplication I believe this comes out so Row one of the answer is 1 0 oh I know that all this is going to

**[21:58]:** be that right then I have 2 1 0 so I get 2 1 0 there right and what's the third row what's the third row in this product just read it out to me the third row 0 5 1 because I I mean one way to say is this is saying take one of the last row and there it is and this is my Matrix L and it's the one that goes to the left it goes on the left of you it goes into this is by what do I mean here maybe maybe rather than saying left of a left of U let me write down again what I mean e a is U whereas a is l u okay let let me let me make the point now in words the the order that the matrices come for L is the right order the two and the five don't sort of interfere to produce this tent in the in the right order the multipliers just sit in the Matrix L that's that's the point that the so that that if I want

**[23:31]:** to know l i I have no work to do I just keep a record of what those multipliers were and that gives me l so so I'll I'll draw the draw the

**[23:49]:** um so let let me let me state so this is this is the AAL Lu so if no row exchanges

**[24:05]:** the multipliers those numbers that we multiplied rows by and subtracted when we did an elimination steps the multipliers go

**[24:23]:** directly into L okay so so so L is this is the way uh to look at elimination that uh the you go through the elimination steps and actually if if you do it right you can you can throw away a as you create L andu it if you think about it though steps of elimination as you when you've done when you've finished with row two of a you've created a new row two of U which you have to save and you've created the multipliers that you used which you have to save and then you can forget hey so the because it's all there in L and U so that's uh that's like I this may this moment is maybe the the new uh Insight in elimination that comes from Matrix doing it in Matrix form so it was the product of of ease is we we can't see what that product of ease is that

**[25:52]:** the Matrix e is not particularly attractive what's great is when we put them on the other side they're inverses in the opposite order there the L comes out just F okay now oh gosh so today is a sort of like practical day uh can I can we think together how expensive is elimination how much how many operations do we do so I so this is now kind of new topic which I didn't list as on the program but here it came here it comes how many

**[26:42]:** operations on an N byn Matrix

**[26:54]:** a I mean it's a very practical question can can we can we solve systems of order a thousand uh in a second or a minute or a week can we solve systems of order a million in a second or an hour or a week I mean what's the if it's n byn we we often want to take in bigger I mean we put in more information we make the the whole thing is more accurate for the bigger Matrix but it's more expensive too and the question is how much more expensive if I go if I have uh matrices of order 100 let's say 100 by 100 let me let me take n to be 100 say n equal 100 how many steps are we doing how many operations are we actually doing that we that or or not we the and let's Suppose there aren't any zeros cuz of course if the if the Matrix

**[28:05]:** has got a lot of zeros in good places we don't have to do those operations and uh it'll be much faster but so just think for a moment about the first step so here's our Matrix a 100 by 100 and the first step will be that column is got zeros down here so it's it's down to 99 by 99 right that that that's really like the first uh stage of elimination to get from this 100 by 100 nonzero Matrix to this stage where the first pivot is sitting up here and the first row is okay and the first column is okay so essentially I what did how many steps did that take you see I'm I'm trying to get an idea is the answer proportional to n is the is the total number of steps in elimination the total number is at proportional to n in which case if I double n from 100 to

**[29:20]:** 200 does it take me twice as long does it Square so it would take me four times as long does it Cube so it would take me 8 times as long or is it n factorial so it would take me 100 times as long I I think you know from a practical point of view we have to have some idea of the cost here so so the these are the questions let me ask those questions again is it proportional it does it go like n like N squared like n cubed like some higher power of n like n factorial where where every step up multiplies by 100 and then by 101 and then by 102 which is it okay so that's the only way I know to answer that is to is to Think Through what we actually had to do okay so how much what was the cost here well let's see what do

**[30:23]:** I mean by an operation I guess I mean uh um well an addition or yeah no big deal I guess I mean an addition or a subtraction or a multiplication or a division okay uh and actually what operation am I doing all the time I'm I'm uh when I when I multiply Row one by a multiplier L and I subtract from row six

**[30:58]:** what's happening there individually what what's the what's going on if I multiply I do a multiplication by L and then a subtraction so I I guess operation can I count that for the moment as like one operation or you may want to count them separately the typical operation is multiply plus a subtract so if I count those together uh my answer is going to come out half as many as if if I count them separately I'd have a certain number of multiplies certain number of subtracts that that's really what I want to do okay how many have I got here so uh I think let's see it's about well how many roughly how many operations to to get from here to here well maybe one way to look at it is all these numbers had to get changed all the first row didn't get changed but but

**[32:09]:** all the other rows got changed at this step so this step well I guess maybe shall I say it cost about this cost about about 100 squar I mean if I Chang the first row then then it would have been exactly 100 squar because CU that's how many numbers are here 100 100 squared numbers is the is the total count of the entries and all but this insignificant first row got changed so I would say about 100 squared okay now what about the next step so now the first row is fine the second row is fine and I'm changing and these zeros are all fine so what's what's up at the second step and then you're with me roughly what's the cost if this if this first step cost 100 squar about operations then this one which is really working on this guy to produce this cost about

**[33:26]:** what how many operations to fix about 99 squ or 99 * 98 but less right less cuz our problem is getting smaller about 99 squar and then I go down and down the next one will be 98 Square the next 97 squar and finally I'm down around 1 squar or where it's just like just Little Numbers the big numbers are here so the the number of operation is about N2 plus that was n right n was 100 it n s for the first step then n -1 2ar then N - 2 2ar finally down to 3 2 and 2 2 and even 1

**[34:22]:** SAR no way I should have written that squeeze that in let me try so the count is n^2 + n -1 squ plus all the way down to 1 s that's that's a pretty decent count yeah admittedly we didn't we didn't catch every single tiny operation but we got the right uh the the right leading term here and what do those add up to okay so now we're at we're coming to the punch of this uh question this operation count so this is the operations on the left side on The Matrix a to finally get to you and anybody so which of which of these uh quantities is the right ballpark for that count if I add 100 squar to 99 s to 98 squ 97 squar all the way down 2 squar and 1 squared what what what am I what have I got

**[35:42]:** about it's it's one of these so tell let's identify it first is it n certainly not is it is it n factorial no if it was n factorial we would with determinance it is n factorial I'll put in a bad Mark against determinance because that that uh okay so what is it it's and well this is the answer it's it's it's it's this order NQ it's like I have n terms right I've got n terms in sum uh and the biggest one is n s so the the the worst it could be would be n cubed but it's not as bad as it's n Cub times there's a it's about 1/3 of NQ that's the that's the magic uh operation

**[36:52]:** C somehow that oneir takes account of the fact that the the numbers are getting smaller if they weren't getting smaller we would have n terms times n s would be exactly n Cub but our numbers are getting smaller actually do you remember where where does 1/3 come in this I'll I'll even allow a mention of calculus so calculus can be mentioned integration can be mentioned now in the next minute and and not again for weeks it's not that I don't like 1801 but 1806 is better okay so uh so what's what's the calculus formula that that looks like it looks like an a sum is like if we were in calculus instead of summing stuff we would integrate so I would integrate X2 and I would get 1/3 x cub so so if that was like an integral from 1 to n of x^2 DX it the answer would be 1/3 n cub and it's

**[38:10]:** correct for the sum also because that's like the whole point of calculus the whole point of calculus is oh I don't want to tell you the I mean you know the whole point of calculus calculus is like sums except it's continuous okay and we're and algebra is discreete okay so the answer is 1/3 NQ now I'll just let me let me say one more thing about operations what about the right hand side this was what it cost on the left sub count this is on

**[38:49]:** a this is a that we're working with but what's the cost on the extra column Vector B that we're we're hanging around here so B B costs a lot less obviously cuz it's just one column we carry it through elimination and then actually we do back substitution let me just tell you the answer there it's n s so the cost for every right hand side is n² so let me I'll just fit that in here for the rights for the the cost of B of B turns out to be n² so you see if we have as we often have uh a matrix a and several right hand sides uh then we pay the price on a the higher price on a to get it split up into L and U to do elimin on a but then we can process every right hand side at at low cost okay so the the that's we

**[40:06]:** really have discussed the most fundamental algorithm of uh of for a system of equations okay so uh I'm ready to allow roow exchanges I'm ready to allow now what happens to this whole today's lecture if there are row exchanges when would there be row exchanges there row we need to do row exchanges if a zero shows up in the pivot position so I'm I'm moving then into the final section of this chapter which is about transposes well we've already seen some transposes and uh so what's the the ti the title of this section is um transposes and permutation okay so can I say now where does a permutation come in let me talk a little about permutation so that'll be up here permutation

**[41:34]:** so these are the matrices that I need to do row exchanges and I may have to do two row exchanges is it can you invent a matrix where I would have to do two row exchanges and then it would come out fine yeah let's just for the heck of it uh so I'll put it here let me do 3x3 actually why don't I just plain list all the 3X3 permutation matrices they're a nice little group of them what are all the matrices that exchange no rows at all well I'll include the

**[42:24]:** identity so that's a permutation Matrix that doesn't do anything now what's the permutation Matrix that exchanges what is P1 2 the permutation Matrix that exchanges rows one and two would be 0 1 0 1 0 0 right I just exchanged those rows of the identity and I've got it okay actually I'll yeah let me let me not clut this up okay give me a complete list of all the row exchange matrices so what are they they're all the ways I can take the identity Matrix and rearrange its rows how how many will there be how many 3x3 permutation matrices should we keep going and get the answer so tell me some more

**[43:28]:** zero okay what one are you going to do now I'm switch rows one and three one and three okay one and three leaving two alone okay now what else switch what are we the next easy one is switch two and three good so I'll leave one0 alone and I'll switch I'll move number three up and number two down okay those are the ones that just exchange single single a pair of roads this guy this guy and this guy exchanges a pair of roads but now there are more possibilities what are they what's what's left so tell there is another one here what's that change it's going to move it's going to change all rows right what where should we put them so give me a first row 0 1 0 okay now a second row say 0 0 1 and the third guy 1 0 0 so that that is like a cycle that puts

**[44:46]:** row two moves up to row one row three moves up to row two and Row one moves down to row three and there's one more which which is let's see H what's

**[45:04]:** left is it 0 0 1 okay 1 0 0 okay 0 1 0 okay great six six of 6 p and and they're sort of nice because what happens if I like um multiply two of them together if I multiply two of these matrices together what can you tell me about the answer it's on the list if I if I do some row exchanges and then I do some more row exchanges then altogether I've done row exchanges so if I multiply but I don't know and if I invert then just doing row exchanges to get back again so the inverses are all there it's it's a it's a little family of matrices that like uh they've got their own If I multiply I'm still inside this group if I invert I'm inside this group actually group is the right name for this it's a group of six matrices and what about the inverses what's the inverse of this guy for example what's the inverse if I exchange rows one and two what's the inverse Matrix

**[46:34]:** just tell me fast the inverse of that Matrix is if I is if I exchange rows one and two then what I should do back to get back to where I started is the same thing so this thing is its own inverse this is that's probably its own inverse this is not actually I think these are inverses of each other oh yeah actually the inverse is the transpose there's a curious fact about permutation matrices that the inverses are the transposed and final moment how many are there if I how many 4x4 permutation so let me take 4x4 how many P's

**[47:30]:** well okay make a good guess 24 right 24 P okay so uh we've got these permutation matrixes and in the next uh lecture uh we use them so the next lecture finishes chapter two and move to chapter 3 thank you
