4. Factorization into A = LU

Okay, this is linear algebra, lecture four And, 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 their inverses, how do I get the inverse of A times 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 A B? Okay, that’ll be simple but so basic Then I’m going to 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 lectures is the big formula for elimination, so the net result of today’s lecture is this great way to look at Gaussian elimination We know that we get from A to U by elimination We know the steps — but now we get the right way to look at it, A equals L U So that’s the high point for today Okay Can I take the easy part, the first step first? So, suppose A is invertible — and of course it’s going to be a big question, when is the matrix invertible? But let’s say A is invertible and B is invertible, then what matrix gives me the inverse of A B? So that’s the direct question What’s the inverse of A B? Do I multiply those separate inverses? Yes 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 right thing to put here is B inverse A inverse That’s the inverse I’m after We can just check that A B times that matrix gives the identity Okay So why — once again, it’s this fact that I can move parentheses around 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 times B inverse This product here I is the identity Then A times the identity is the identity and then finally A times A inverse gives the identity So forgive the dumb example in the book Why do you, do the inverse things in reverse order? It’s just like — you take off your shoes, you take off your socks, then the good way to invert that process is socks back on first, then shoes Sorry, okay I’m sorry that’s on the tape And, of course, on the other side we should really just check — on the other side I have B inverse, A inverse That does multiply A B, and this time it’s these guys that give the identity, squeeze down, they give the identity, we’re in shape Okay So there’s the inverse Good While we’re at it, let me do a transpose, because the next lecture has got a lot to — involves transposes So how do I — if I transpose a matrix, I’m talking about square, invertible 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 will bring a transpose into the picture So if I transpose the identity matrix, what do I have? The identity, right? 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 reverse the order I can transpose them separately, but when I multiply, those transposes come in the opposite order So it’s A inverse transpose times A transpose giving the identity So that’s — this equation is — 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’ss the inverse of the result? And this equation tells me that here it is This is the inverse of A transpose Inverse of A transpose Of A transpose So I’ll put a big circle around that, because that’s the answer, 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 a — to put it another way, transposing and inversing you can do in either order for a single matrix Okay So 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 really completing, the subject of elimination Actually, — the thing about elimination is it’s the right way to understand what the matrix has got This A equal L U is the most basic factorization of a matrix I always worry that you will think this course is all elimination It’s just row operations And please don’t We’ll be beyond that, but it’s the right algebra to do first Okay So, now I’m 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 U? And this is going to tell me that there’s a matrix L that connects them Okay Can I do it for a two by two first? Okay Two by two, elimination Okay, so I’ll do it under here Okay So let my matrix A be — We’ll keep it simple, say two and an eight, so we know that the first pivot is a two, and the multiplier’s 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 the elementary matrix? Strictly speaking, it’s E21, because it’s the guy that’s going to produce a zero in that position And it’s going to produce U in one shot, because it’s just a two by two matrix So two one and I’m going to take four of those away from those, produce that zero and leave a three there And that’s U And what’s the matrix that did it? Quick review, then What’s the elimination elementary matrix E21 —

it’s one zero, thanks And — negative four one, right Good Okay So that — 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 here’s going to be my A equals L U And you won’t have any trouble telling me what — so A is still two one eight seven L is what you’re going to tell me and U is still two one zero three Okay So what’s L in this case? Well, first — so how is L related to this E guy? It’s the inverse, because I want to 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 those elimination matrices are easy to invert The inverse matrix for this one is 1 0 4 1, it has the plus sign because it adds back what this removes Okay Do you want — if we did the numbers right, we must — this should be correct Okay And of course it is That says the first row’s right, four times the first row plus the second row is eight seven Good Okay That’s simple, two by 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 triangular And actually, it has ones on the diagonal, where this thing has the pivots on the diagonal Oh, sometimes we may want to separate out the pivots, so can I just mention that sometimes we could also write this as — we could have this one zero four one — I’ll just show you how I would divide out this matrix of pivots — two three There’s a diagonal matrix And I just — whatever is left is here Now what’s left? If I divide this first row by two to pull out the two, then I have a one and a one half And if I divide the second row by three to pull out the three, then I have a one So if this is L U, this is maybe called L D or 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 Matlab would produce either one I’ll basically stay with L U Okay Now I have to think about bigger than two by two But right now, this was just like easy exercise And, to tell the truth, this one was a minus sign and this one was a plus sign I mean, that’s the only difference But, with three by three, there’s a more significant difference Let me show you how that works Let me move up to a three by three, let’s say some matrix A, okay? Let’s imagine it’s three by three I won’t write numbers down for now So what’s the first elimination step that I do, the first matrix I multiply it by, what letter will I use for that? It’ll be E two one, because it’s — the first step will be to get a zero in that two one position right? And then the next step will be to get a zero in the three one position And the final step will be to get a zero in the three two That’s what elimination is, and it produced U. position And again, no row exchanges

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’s, like, my point here 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’s the right expression now? If I write A and U, what goes 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, because each one is easy to invert Question is, what about the whole bunch? 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? E three two inverse, right, because I’ll multiply from the left by E three two inverse, then I’ll pop it up next to U And then will come E three one inverse And then this’ll be the only guy left standing and that’s gone when I do an E two one inverse So there is L That’s L U L is product of inverses Now you still can ask why is this guy preferring inverses? And let me explain why Let me explain why is this product nicer than this one? This product turns out to be better than this one Let me take a typical case here Let me take a typical case So let me — I have to do three by three for you to see the improvement Two by two, it was just one E, no problem But let me go up to this case Suppose my matrices E21 — suppose E21 has a minus two in there Suppose that — and now suppose — oh, I’ll even suppose E31 is the identity I’m going to make the point with just a couple of these Okay Now this guy will have — do something — now let’s suppose minus five one Okay There’s typical That’s a typical case in which we didn’t need an E31 Maybe we already had a zero in that three one position Okay Let me see — is that going to be enough to, show my point? Let me do that multiplication So if I do that multiplication it’s like good practice to multiply these matrices Tell me what’s above the diagonal when I do this multiplication? All zeroes When I do this multiplication, I’m going to get ones on the diagonal and zeroes above Because — what does that say? That says that I’m subtracting rows from lower rows So nothing is moving upwards as it did last time in Gauss Jordan Okay Now — so really, what I have to do is check this minus two one zero, now this is — what’s that number? This is the number that I’m really have in mind That number is ten And this one is — what goes here? Row three against column two, it looks like the minus five What it’s that ten How did that ten get in there? I don’t like that ten I mean — of course, I don’t want to erase it, because it’s right But I don’t want it there It’s because — the ten 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 effect row three?

Well, it did, because two of it got removed from row two and then five of those got removed from row three So altogether ten of row one got thrown into row three Now my point is in the reverse direction — so now I can do it — below it I’ll do the inverses Okay And, of course, opposite order Reverse order Reverse order Okay So now this is going to — this is the E that 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 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 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 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 one zero zero Oh, I know that all this is going to be left, right? Then I have two one zero So I get two one zero 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 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 on the left of U It goes into — what do I mean here? Maybe rather than saying left of A, left of U, let me right down again what I mean E A is U, whereas A is L U Okay Let me make the point now in words 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 ten one In the right order, the multipliers just sit in the matrix L That’s the point — that if I want to know L, I have no work to do I just keep a record of what those multipliers were, and that gives me L So I’ll draw the — let me say it So this is the A=L U So if no row exchanges, the multipliers that those numbers that we multiplied rows by and subtracted, when we did an elimination step — the multipliers go directly into L Okay So L is — this is the way, to look at elimination You go through the elimination steps, and actually if you do it right, you can throw away A as you create L U If you think about it, those steps of elimination,

as 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 A So because it’s all there in L and U So that’s — this moment is maybe the new insight in elimination that comes from matrix — doing it in matrix form So it was — the product of Es is — we can’t see what that product of Es is The matrix E is not a particularly attractive one What’s great is when we put them on the other side — their inverses in the opposite order, there the L comes out just right Okay Now — oh gosh, so today’s a sort of, like, practical day Can we think together how expensive is elimination? How many operations do we do? So this is now a kind of new topic which I didn’t list as — on the program, but here it came Here it comes How many operations on an n by n matrix A I mean, it’s a very practical question Can we solve systems of order a thousand, 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 by n, we often want to take n bigger I mean, we’ve put in more information We make 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 have matrices of order a hundred Let’s say a hundred by a hundred Let me take n to be a hundred Say n equal a hundred How many steps are we doing? How many operations are we actually doing that we — And let’s suppose there aren’t any zeroes, because of course if a matrix has got a lot of zeroes in good places, we don’t have to do those operations, and, it’ll be much faster But — so just think for a moment about the first step So here’s our matrix A, hundred by a hundred And the first step will be — that column, is got zeroes down here So it’s down to 99 by 99, right? That’s really like the first stage of elimination, to get from this hundred by hundred non zero matrix to this stage where the first pivot is sitting up here and the first row’s okay the first column is okay So, eventually — how many steps did that take? You see, I’m trying to get an idea Is the answer proportional to n? Is the total number of steps in elimination, the total number, is it proportional to n — in which case if I double n from a hundred to two hundred — 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 eight times as long? Or is it n factorial, so it would take me a hundred times as long? I think, you know, from a practical point of view, we have to have some idea of the cost, here So these are the questions that I’m — let me ask those questions again Is it proportional — does it go like n, like n squared, like n cubed — or some higher power of n? Like n factorial where every step up multiplies by a hundred

and then by a hundred and one and then by a hundred and two — which is it? Okay, so that’s the only way I know to answer that is to think through what we actually had to do Okay So what was the cost here? Well, let’s see What do I mean by an operation? I guess I mean, well an addition or — yeah No big deal I guess I mean an addition or a subtraction or a multiplication or a division Okay And actually, what operation I doing all the time? When I multiply row one by multiplier L and I subtract from row six What’s happening there individually? What’s going on? If I multiply — I do a multiplication by L and then a subtraction So 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, my answer’s going to come out half as many as if — I mean, if I count them separately, I’d have a certain number of multiplies, certain number of subtracts That’s really want to do Okay How many have I got here? So, I think — let’s see It’s about — well, how many, roughly? How many operations to get from here to here? Well, maybe one way to look at it is all these numbers had to get changed The first row didn’t get changed, but all the other rows got changed at this step So this step — well, I guess maybe — shall I say it cost about a hundred squared I mean, if I had changed the first row, then it would have been exactly hundred squared, because — because that’s how many numbers are here A hundred squared numbers is the total count of the entry, and all but this insignificant first row got changed So I would say about a hundred squared Okay Now, what about the next step? So now the first row is fine The second row is fine And I’m changing these zeroes are all fine, so what’s up with the second step? And then you’re with me Roughly, what’s the cost? If this first step cost a hundred squared, about, operations then this one, which is really working on this guy to produce this, costs about what? How many operations to fix? About ninety nine squared, or ninety nine times ninety eight But less, right? Less, because our problem’s getting smaller About ninety-nine squared And then I go down and down and the next one will be ninety eight squared, the next ninety seven squared and finally I’m down around one squared or — where it’s just like the little numbers The big numbers are here So the number of operations is about n squared plus that was n, right? n was a hundred? n squared for the first step, then n minus one squared, then n minus two squared, finally down to three squared and two squared and even one squared No way I should have written that — squeezed that in Let me try it so the count is n squared plus n minus one squared plus — all the way down to one squared That’s a pretty decent count Admittedly, we didn’t catch every single tiny operation, but we got the right leading term here And what do those add up to?

Okay, so now we’re coming to the punch of this, question, this operation count So the operations on the left side, on the matrix A to finally get to U And anybody — so which of these quantities is the right ballpark for that count? If I add a hundred squared to ninety nine squared to ninety eight squared — ninety seven squared, all the way down to two squared then one squared, what have I got, about? It’s just one of these — let’s identify it first Is it n? Certainly not Is it n factorial? No If it was n factorial, we would — with determinants, it is n factorial I’ll put in a bad mark against determinants, because that — okay, so what is it? It’s n — well, this is the answer It’s this order — n cubed It’s like I have n terms, right? I’ve got n terms in this sum And the biggest one is n squared So the worst it could be would be n cubed, but it’s not as bad as — it’s n cubed times — it’s about one third of n cubed That’s the magic operation count Somehow that one third takes account of the fact that the numbers are getting smaller If they weren’t getting smaller, we would have n terms times n squared, but it would be exactly n cubed But our numbers are getting smaller — actually, row two and row one moves down to row three do you remember where does one third come in this — I’ll even allow a mention of calculus So calculus can be mentioned, integration can be mentioned now in the next minute and not again for weeks It’s not that I don’t like 18.01, but18.06 is better Okay So, — so what’s — what’s the calculus formula that looks like? It looks like — if we were in calculus instead of summing stuff, we would integrate So I would integrate x squared and I would get one third x cubed So if that was like an integral from one to n, of x squared b x, if the answer would be one third n cubed — and it’s 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 whole — I mean, you know the whole point of calculus Calculus is like sums except it’s continuous Okay And algebra is discrete Okay So the answer is one third n cubed Now I’ll just — let me say one more thing about operations What about the right-hand side? This was what it cost on the left side This is on A Because this is A that we’re working with But what’s the cost on the extra column vector b that we’re hanging around here? So b costs a lot less, obviously, because 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 squared So the cost for every right hand side is n squared So let me — I’ll just fit that in here — for the cost of b turns out to be n squared So you see if we have, as we often have, a a matrix A and several right hand sides, then we pay the price on A, the higher price on A to get it split up into L and U to do elimination on A, but then we can process every right hand side at low cost

Okay So the — We really have discussed the most fundamental algorithm for a system of equations Okay So, I’m ready to allow row 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 are row — we need to do row exchanges if a zero shows up in the pivot position So moving then into the final section of this chapter, which is about transposes — well, we’ve already seen some transposes, and — the title of this section is, “Transposes and Permutations.” Okay So can I say, now, where does a permutation come in? Let me talk a little about permutations So that’ll be up here, permutations So these are the matrices that I need to do row exchanges And I may have to do two row exchanges Can you invent a matrix where I would have to do two row exchanges and then would come out fine? Yeah let’s just, for the heck of it — so I’ll put it here Let me do three by threes Actually, why don’t I just plain list all the three by three permutation matrices There’re a nice little group of them What are all the matrices that exchange no rows at all? Well, I’ll include the identity So that’s a permutation matrix that doesn’t do anything Now what’s the permutation matrix that exchanges — what is P12? 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 — yes Let me clutter 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 many will there be? How many three by three permutation matrices? Shall we keep going and get the answer? So tell me some more STUDENT: Zero one STRANG: Zero What one are you going to do now? STUDENT: I’m going to switch the STRANG: Switch rows one and — One and three, okay One and three, leaving two alone Okay Now what else? Switch — what would be the next easy one — is switch two and three, good So I’ll leave one zero zero alone and I’ll switch — I’ll move number three up and number two down Okay Those are the ones that just exchange single — a pair of rows This guy, this guy and this guy exchanges a pair of rows, but now there are more possibilities What’s left? So tell — there is another one here What’s that? It’s going to move — it’s going to change all rows, right? Where shall we put them? So — give me a first row STUDENT: Zero one zero? STRANG: Zero one zero Okay, now a second row — say zero zero one and the third guy One zero zero So that is like a cycle That puts 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 is — let’s see

What’s left? I’m lost STUDENT: Is it zero zero one? STRANG: Is it zero zero one? Okay STUDENT: One zero zero STRANG: One zero zero, okay Zero one zero, okay Great Six Six of them Six P. And they’re sort of nice, because what happens if I write, 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 do some row exchanges and then I do some more row exchanges, then all together I’ve done row exchanges So if I multiply — but, I don’t know And if I invert, then I’m just doing row exchanges to get back again So the inverses are all there It’s a little family of matrices that — 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 subject 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? Just tell me fast The inverse of that matrix is — if I exchange rows one and two, then what I should do to get back to where I started is the same thing So this thing is its own inverse That’s probably its own inverse This is probably not — actually, I think these are inverses of each other Oh, yeah, actually — the inverse is the transpose There’s a curious fact about permutations matrices, that the inverses are the transposes And final moment — how many are there if I — how many four by four permutations? So let me take four by four — how many Ps? Well, okay Make a good guess Twenty four, right Twenty four Ps Okay So, we’ve got these permutation matrices, and in the next lecture, we’ll use them So the next lecture, finishes Chapter 2 and moves to Chapter 3 Thank you