LU Decomposition

MIT 18.06SC Linear Algebra, Fall 2011
View the complete course: ocw.mit.edu/18...
Instructor: Ben Harris
A teaching assistant works through a problem on LU decomposition.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@moon-ia2068]

Ben really did an amazing job I have been watching videos of the LU decomposition for 2 hours and your explanation is the best so far

[@user-dl8sc6hy2s]

Thank you I can easily understand LU decomposition by following your process in a timely manner

[@lugia8888]

No you dont

[@user-dl8sc6hy2s]

Nah @@lugia8888

[@instinx9154]

@@lugia8888 dawg why you so salty lol

[@stevesgle4025]

absolutely enjoying it. understood the concept the moment i finished the video!

[@harshavardhanlakhinana5280]

Dude you really nailed it!! First I didnot understand the actual procedure from lecture not I get it and I was wondering why L and U decomposition would take less amount of steps to compute and now I have my answer thanks to your clear explaination

[@Hobbit183]

these videos are gold :)

[@mind-blowing_tumbleweed]

Good review. I remember I was puzzled why L doesn't have minuses when it eliminated numbers.

[@wuchinen]

I appreciate your help. Now I have a better understanding of matrices multiplication through your precise description.

[@geekaffairs6475]

Ben, you explained nicely..

[@zakariyemohamudabdi962]

Am watching now thanks to Instructor Harris

[@user-tf3tm2ew8w]

Some one maybe explain to me why " you can't find LU decomposition if you have to do a row exchange in elimination"(4:08) it seems to me that it is because in this problem we happen to have 0 in the right of a in row 2, if a is zero, then row two is dependent row. Without full pivot we can't do LU decomposition. But in other situation, even if we have row exchange in elimination step, we could still find LU decomposition but not in a straight forward way. Someone please help!

[@allenyang5829]

Thank you, you explain very well.

[@samsworking7604]

Wait, is it just me who's finding his LU doesn't end up the original A? I was following all of the steps correctly until the last part where the LU is not equal to A.... Anyone else?

[@rajavignesh7216]

Yeah bro same in matrix U (u33 = 0 ) not a-b ,I used a different method got u33 as zero and A = LU

[@riteshprasadsingh6029]

why a-b can be zero? Suppose a = 1 and b = 1, then the pivot will be zero

[@logancastaway2064]

a was assumed to be zero because it is required to be used as a pivot in order to obtain u. i see what you mean by your question because a-b is the next natural pivot location, but it isn’t necessary for a-b to actually be a pivot since we aren’t eliminating anything underneath of its location. we can still construct an upper triangular matrix even if none of the elements on the diagonal are valid pivots. all that matters is that there are zeros below the diagonal. i know this is 8 months late but this is for anyone who read your comment and is still curious.

[@then-go]

@@logancastaway2064 I really curious about that and I have searched comments to know that. Thank you so much!!

[@mobyokelly52]

Thank you very much, definitely useful for me!

[@mohithjagalmohan]

He's pretty good. Thank you so much, Ben :) :)

[@anuj7876]

U done it beautifully in L 21. There will be -a not just a 😅 8:40

[@bhushandatre1508]

i noticed it too it should be -a and not 0😁

[@ashutoshtiwari4398]

Can anyone explain me what the last part meant? That a-b can be zero and singular matrices can have LU decomposition.

[@yuchenzhao6411]

Singular matrices can have U, they just can’t be eliminated to I.

[@laytion4585]

Thank you! I think he explained it very well

[@davidcruz3400]

Very Helpful! Quick and Clear!

[@StephanyMaraca]

Thank you man, it was a really clear explanation

[@rajajaladurgam]

please explain the last comment you have made regarding permutation.. why if permutation does not allow LU decomposition

[@carlphilip4393]

because if we would do permutations the resulting matricies wouldnt be triangular anymore. ->triangular matricies are our goal (i know the comment is old, its just for anyone having the same question)

[@jeffreylin1245]

Singular matrices are matrices that doesn't have inverse.

[@anandjain717]

Why we not take into account the row exchanges in LU decomposition. As we know that the elementary matrix corresponding to it is invertible(equal to its transpose). So why row exchanges are not considered?

[@Abhi-qi6wm]

But why would you want to exchange rows in this problem? All pivot positions are already non-zero.

[@gaboqv]

thats a plu decomposition

[@alexcosta15178]

But the U matrix contains pivots and pivots can't be zero, so (a - b) can't be zero. Right?

[@zionjohnson8114]

idk

[@pepehimovic3135]

1) Check that your solution is valid. Check that LU gives you A. Just like with checking solutions of differential equations. 2) the a-b pivot in matrix U can be 0, because we don’t have to do a row exchange to get U. That’s the only time when we can’t do LU decomposition. In particular, singular matrices can have LU decompositions. The 2nd point makes no sense to me.

[@JoseSilva-rb1ym]

The second point is true enough, up to a certain point. You can't perform an LU decomposition for some matrix A which needs a row exchange; instead, you have to reorder the matrix A into some other matrix PA (by means of a permutation matrix) such that PA can be factored into LU. Singular matrices can have LU decompositions; in fact, singular matrices can have multiple LU decompositions.

[@MrSazid1]

If we need to change the pivot can we not just do a permutation and added to the elimination

[@Upgradezz]

Then you won't get a LU decomposition.

[@picklerick8844]

Challenge: Take a shot everytime he says "Good".

[@mohdmohtashim9841]

11 shots...

[@yiyu9519]

love this course

[@dylendye7410]

Thanks this will be huge help

[@흠냐링-i4y]

Is there any reason why the sequence is always E32->E31->E21? I guess unless it will be hard to compute L=E21 -I × E31 -I × E32 -I , right?

[@thomassun3046]

because it is elimination, it is about row operations,so the matrix must be on the left of the A matrix, coz it is step by step, so it must be this order

[@Kenjiru]

There is a good reason why it's that exact order. Having E32 x E31 x E21 x A = U, in order to end up only with A on the left side, we need to multiple on the left with a matrix that would result in I x A = L x U. The definition of I is: I = A x A-1 or I = A-1 x A To get I from E32 x E31 x E21 we need to multiply it on the left with the inverse of each matrix (in reverse order). E21-1 x E31-1 x E32-1 x E32 x E31 x E21 = I, because E32-1 x E32 = I, and then E31-1 x I x E31 = I, and then E21-1 x I x E21 = I

[@ixine-fx3wd]

Even E31->E32->E21 gives the same L in this case, just need to follow order of inverses to be multiplied(E21-1->E32-1->E31-1). Not sure if it's limited to this question only.

[@luislopez-tx4tl]

i love his voice

[@biscuitsofdeath]

I still don't get it. I think the e matrices are tripping me up.

[@pinazo07]

Wouldn't it be necessary to highlight that "a - b" must be non-zero?

[@FriggnH8ters]

He mentions it at the very end of the video. I believe it is alright for a-b to be 0 since the location of the entry does not require a row exchange which would prevent us from creating an LU decomposition

[@user-cn6xx5pe4u]

Wait... as the second row is divided by b/a which means b/a is not zero, that leads to a≠0 and b≠0...

[@xiaominsong]

second row times b/a, not divided by b/a

[@hayin2041]

What about the case when we need row interchange?

[@lancelofjohn6995]

Thanks for your video

[@user-vw7su1cu9e]

You're BEN

[@TheRojo387]

It seems that he left-multiplied each successive matrix by the eliminators, rather than right-multiplying!

[@fernandoacuna4650]

I liked this one.

[@skushagra]

this is great

[@andrewgreazel7007]

How do you get -b/a for Esub32 in the third elimination matrix?

[@ElectricTeaCup]

We want to turn the b in row 3 to 0 using the pivot in row 2. In order to do this, the pivot, namely a needs to be first divided by a and then multiplied by b followed by a subtraction from row 3. Translating this into matrix form is E_32.

[@skyatoro]

I miss blackboards. They’re the OG boards

[@thomassun3046]

From professor Strang, when the pivot is ZERO, it can be multiplied by a permutation matrix, to change the the row, so PA=LU, it should be ok, why a =0 is not discussed?

[@Pdvil]

Check the next lesson. ;)

[@thangbui6383]

Thanks. liked.

[@12121921]

nicely

[@None0fY0urConcern]

omnitrix waiting for you mate

[@dylendye7410]

Hey can I get into MIT?

[@mitocw]

See mitadmissions.org/ for info.

[@esmondadjei]

Hello Ben

[@user-se6cc1hr5i]

I think a=0 b=0 can be the solution because A = IA is also LU decomposition

[@krishnkantswarnkar4735]

No it can't be. You essentially said L=I & U=A, which can not be true, as you need to perform some set of elementary operations to reach A (as shown in the video). Hope it was helpful!

[@endogeneticgenetics]

Ah, good point. Technically, if a & b = 0 -> A=U & L=I, so A=IA is a solution.

[@ath216]

What you said is called the "trivial" solution, matrix A should always be equal to IA which is also equal to AI. and you can call this what ever you want, not only LU. I guess by now you have passed the course ! congrats =)

[@pepehimovic3135]

@@endogeneticgenetics a = b = 0 has nothing to do with whether A = IA holds or not. A = IA is always true.

[@vinyltherapy9410]

Güd