4. Factorization into A = LU 

The shoes and socks analogy for inverses of matrix products is probably the cutest thing a math genius has ever said.

I remember being a student and rushing out after class, as these students did. But now at the ripe age of 35, I see these students doing the same and I think "HOW DARE THEY NOT STOP AND APPLAUD FOR SUCH A MASTERFUL PERFORMANCE"

Gilbert Strang lecture: "and this is a matrix..." Gilbert Strang textbook: "Find the corners of a square in n dimensions and whether vectors a, s, d,e w,wieidwdjdkdk are contained in the cube...."

Lecture timeline Links Lecture 0:00 What's the Inverse of a Product 0:25 Inverse of a Transposed Matrix 4:02 How's A related to U 7:51 3x3 LU Decomposition (without Row Exchange) 13:53 L is product of inverses 16:45 How expensive is Elimination 26:05 LU Decomposition (with Row exchange) 40:18 Permutations for Row exchanges 41:15

The internet is such a wonder! Thanks to it, I can learn from great educators like Prof. Strang from the comfort of my home. What a nice era to be a human in.

46:15 Holy shit! He gave a teaser to abstract algebra right there! I just finished abstract algebra and was just watching these lectures because... I don't need a reason, and I just noticed that now! Prof Strang is amazing. I am glad I can watch these lectures from anywhere and at anytime I want :)

thank you mit for this...to give such a privilege to the world that they can view and learn from your content,...its commendable,..and i am grateful

how many times has watching a lecture brought a smile to your face ? I was constantly smiling - every time he pointed out something that I hadn't thought of in the way he mentions it. Such an amazing teacher!

i literally waited years for this video. im going to binge watch this bitch

He just gave an intro to computational complexity in CS measured in order notations such as Big O, Omega etc. Pure gold how he also almost put the definition of small O right there. Applauds

for those unaware, this video was originally uploaded in very bad quality (you willl see complaints about this in the next one) and MIT OCW claimed to have lost the original recording and thus were unable to upload in higher quality. Fortunately, the seem to have found the tapes. Thanks MIT OCW!

I feel so sorry for younger version of me who doesn't know about this great course and the nicest instructor. poor guy just hated the math classes. thank MIT, thanks dear Gilbert Strang :)

Professor Strang is really enjoying teaching, I am so appreciate that I could learn from him! I like the way he teaches so much!

"I'm sorry that's on tape" Strang 2005

I won't understand people who disliked this videos. I haven't liked revisiting a topic, unless it is from Deep Learning. But this! This is a gem that I will revisit my entire life, any given day. Bored? Pick a topic from this series. Depressed? Pick a topic from this series. Need inspiration? Pick a topic from this series. Time on your hands? Still need a hint?

26:05 "What did it cost?" ~40:00 "Everything"

I know of no soft power more effective than these lectures. Thank you MIT for the generosity and commitment.

36:49 it's (1/3)n^3 + (1/2)n^2 + (1/6)n for those wanting to know the exact answer.

i guess I am the lucky one since i've just started to watch this video lecture series today!

He just non-chalantly planted the idea of Group Theory in at the very end of the lecture - Genius! If only one can make a math playlist of all the best lecturers in the world... may be I will do this.

n^2 + (n-1)^2 + (n-2)^2 + ... + 2^2 + 1^2 = n * (n+1) * (2n + 1) / 6. As n becomes "big", this sum approaches n^3 / 3. His approach in the lecture is also good. Plot a graph of y = x^2 and identify the points x = n, x = n-1, x = n-2, ..., x = 1, and you'll find that if n is big enough, the discrete plots start to look more and more like the curve y = x^2, which then allows you to approximate the area under the curve. Again, what you get for a reasonably large n is n^3 / 3. One final thing is, if these operations are performed in a loop, you'll need way more time, because his analysis assumes an operation on an entire row. To achieve this, you would need vectorized code that can operate on the entire row at once. Hope this helped someone :)

God bless MIT and Professor Strang. Such a bright light for a wonderful course!

Congratulations for finding this recording! Thank you a lot!!!

Note for myself : Elementary matrices ka inversion simple hai sirf jaha -ve hai usko +ve karna hai Also jab ham row exchanges nahi karte hai then L simply mil jata hai bas identity matrix mein E21 ,E31 and E32 ko zero karne k liye jo operations kiye hai unka sign reverse karke Identity matrix mein respective positions par likhna hai . And jab ham row exchanges karte hai in order to get the U matrix then also its very simple bas as compared to previous case jab row exchanges nahi kar rahe the yaha par permutation matrices will also be present as the elementary matrices and their inverse is also very simple to calculate. Permutation matrix is itself it's inverse.

This man is just a genius in the purest meaning of the word. He is like Neo, he can see matrices everywhere.

The best teacher teaching this material as far as I know. I wonder whether his books are as good as his lectures. May he still have a long and healthy life. :)

Ah that explains it. I don’t understand the math but now I finally understand why my socks are getting wet when it rains

great lectures,, much better than any paid courses on Udemy or other sites

An extra ordinary teacher. Thank you MIT.

So clear the explanation is that for a simple matrix (3X3) I can directly flush out the inverse matrix given the multiplier at each elimination step, without going thru matrix inverse and multiplication. Here is the process: (1) Flip the sign of multiplier at each elimination step. (2) Directly add it in the L matrix in the same position (index) of L. In the example of 18:00, flip (-2) I get 2, then add 2 in position L[2,1]; flip (-5) I get 5, add 5 in position L[2,3]. So I got L. BTW, another way to understand that L is better than E is that: (1) When producing E, there are interfered operations happening and thus a new (implicit) relationship between row1 and row3 is formed. As a result, a new entry (10) is appearing to reflect the newly created (implicit) relationship among row1 and row3, as shown at the position E[3, 1]. (2) When producing L, the operations are in the right order that there are no interfered operations thus no implicit relationships were generated. So we can just plug in the multiplier (the entry) directly to L, without worrying about missing any entries. (3) As a side note, the entry value tells about the multiplication, BUT more importantly, the index of each entry tells about he the relationship between rows. Eg. In matrix E32, the entry E[3, 2] = -5, it means the change coming from row2 to row3, with (-5) as the amount. Getting an explicit explanation on the role of entry indexes helps a lot to build some intuitive in a long run. Thank you Dr. Strang. You are the hero of Linear Algebra!

Good God these lectures are a perfect addendum when trying to learn this topic from the book alone. Thank you thank you thank you

thank god someone uploaded a better audio/video quality version the other one was abysmal

Put on socks > put on shoes, thus to inverse the process take of shoes > take of socks 😂 Great analogy!

Thank you so much. This is the proper education people should receive.

Thank you Dr. W. G. Strang, for all this knowledge you have all us favored of.

This is SO helpful, more than thankful for this upload. I really like this professor too.

when i first run into linear algebra at university i was so stuck to understand even the basic topics of my courses. then after 2-3 years i discovered mr. Strang's lectures and i have to say i am so grateful for this professor because his teaching aproach made me understang the whole concept of linear algebra and i actually found it very interesting for the first time in my life. Plus i finally passed my courses after all these years xD god bless you mr. Strang :)

Thank's MIT to share this type of documents with the worlds. Thank's...

36:05 to sleep in front of 300k people... a fucking legend

36:49 the precise answer would be n(n²-1)/3..

I just repeated watching this video twice and then got the idea of why L is better than E. Thanks Dr. Strang

His closet consists of 7 version of the exact same outfit.

The way he connects the dots. Wow!

(1/3)*n^3, magically! hmm! But hey, it makes sense, that is a sum of all (n-x)^2, and as he assumed for all pivots it is a continues variable then the discrete sum of continues variables turns into integral and there you have it, 1/3n^3.

This python program shows that total sum is n cube divided by 3 import matplotlib.pyplot as plt def r(n): sum = 0 for i in range(1,n+1): sum = sum + i*i return sum def y_axes(n): lst = [] for i in range(1, n+1): lst.append(r(i)) return lst plt.plot([x for x in range(1,1001)], y_axes(1000)) plt.show()

uuuu the quality in this video is better than the another on the previous playlist

thanks, Profesor Gilbert Strang

Since all eliminations must be done by computers for large matrices, intuitive approaches fail quickly. So, precise rigorous algorithms are the only practical way to do elimination. Gilbert Strang style defies the rigorous approach, and does it on purpose to breath life into the dull process of elimination.

I don't understand how some people find it easy to disrespect teachers. In Bangladesh, we respect our teachers.

Thanks, Dr. Strang. I always enjoy your lectures.

100× 100 matrix will take max 49950 steps of ellimination to form an Identity , if and only if -> all the elements are not equal 0 ; explanation -formula as per me 😁 i.e 100 × 100 matrix = 10000 elements , so 100 num of pivots , which are no to be changed and so remaining elements ;10000-100 = 99900 ; we are supposed to make either upper or a lower Tri. , So now we have to change 1/2 of the elements skipping the pivots i.e = 1/2 × 99900 = 49950 elements so 49950 steps 😎

Didn't know there were videos of his classes. I have being learning from his books in my school.

Man the chalk glides so smoothly across the black board, when I give tutorials at my university it's usually a huge pain in the ass to draw stuff on there because it just feels like shit haha

Can anyone explain why the E21 in 11:16 is easy to invert? Did he teach about the skills in the previous lecture? Or the skill is taught in the readings?

I would say that the most efficient way for solving Ax=b would be solving A^t A x = A^t b (minimum square problem) using CG algorithm, due to my personal amazement with CG method. Pretty sure that it's not the case, but this method gives me chills. Hahaha

If you mash right at a steady pace, you can hear my last brain cells spiriting away in agony as I try and fail to comprehend Linear Algebra.

The educational lead up to 40:07 "We really have discussed the most fundamental algorithm for a system of equations."

Wonderful explanation, prof. Gilbert. Thank you!

Can someone please explain how did he get 100^2 and not 100 x 2 (multiply+substract) operations at 33:22?

Correct me if I'm wrong. I was following the lecture series in order but I don't think transpose was taught in any of the previous lectures.

So glad there's a solution to the Sox Shoe Primacy Dilemma.

This lecture on factorization is very helpful ,however I don't fully understand why this concept. is important.

Finally! Where did you end up finding this??? Cached in someone's IE?

I dont understand why the cost is n^2 to make zero first column. A single operationg is multiplication and subtraction ,therefore i need to multiply first row with some constant and substract it from 2nd to get zero. It takes 1 operation to make (21) zero so 99 or 100 operation in total to make first column zero except pivot. Help me out here please

Group. They are a nice little GROUP.

Can someone explain why the computatinal expense is roughly 100^2 for the first step? I thought it would be roughly proportional to n = 100

I did't understand at the first view nor at the 2nd one but at the 3rd or even at the 4th time waw CRAZY approach !

Yes in fact, the shoes-socks rule stands well in this science

I really find it funny how towards the end of the lecture most students can't wait to go..😂

hmm is there a complementary book we must follow? I'm puzzled as I don't think we've introduced the elementary matrices in previous lectures, or Upper/lower matrices. I feel this is not beginner friendly.

4:57 if i transpose these guys, that product, then again, ... : why did he jump suddenly to this theorem without any definition of transpose nor the logical derivation? Did I miss something?

Great video! I love this series. In this lecture, Dr. Strang briefly mentions that the cost of operations for the det(A) will be (n!) He also shows us how the cost of getting A into upper triangular form U will be (1/3)n^3. But from Lecture 2 we know that one way of finding det(A) is to get A into U and then simply find the product of all n pivots. So it seems like the cost for finding det(A) would just be a bit more than (1/3)n^3, perhaps (1/3)n^3 + n. I must be missing something here; any thoughts?

how is the number of operations n^2. 2x2 ----> 1 operations 3x3 ------>1+2=3 operations 4x4 -------> 3+3=6 operations 5x5-------->6+4=10 operations 6x6--------->10+5 = 15 operations 7x7---------> 15+6 = 21 operations So it should be 1+2+3+4+5+6+.....n = n(n+1)/2 Correct me if I am wrong

Thanks for this one ! Was awaiting it for a long time :D

How did transpose suddenly come into the picture?

This professor is awesome!

At 24:20 when he says that the multiplier goes directly into L, he means the negative right? If you keep a track of the operation on the left side, it inverts while bringing it to the right side.

26:10 I have a question about the cost of elimination. Ax=b For an nxn matrix A For the 1st pivot, instead of 100^2, shouldn’t it cost 100*99? 2nd pivot, instead of 99^2, shouldn’t it cost 99*98? 3rd pivot, instead of 98^2, shouldn’t it cost 98*87? So, instead of n^2+(n-1)^2+(n-2)^2+...., shouldn’t it be n(n-1)+(n-1)(n-2)+(n-2)(n-3)+.... instead? Also, how did he get n^2 for the matrix b?

39:35，The cost of columns is about n^2 or 1/2n^2？I think it should be about 1/2n^2.

now doubt sir you are the blessing for mathematicians and also for related to this field,i often enjoy your lectures in my vocations

18:52 It says I'm subtracting rows from lower rows when we are multiplicating the two matrix. Was not able to get this.was able to simply multiply the matrix using combinations of columns and rows.

At 39:00 The cost of b is not EXACTLY n^2 operations like he says in the video. Yes there are n elements, and we assume that all the elements are non-zero from the beginning. But that doesn't mean that EVERY element are being changed. For this to be true(that we are using n^2 operations) we ALSO must assume that there is no 1's in the pivot positions from the beginning. For example if it were 1's in all the pivot positions from the beginning the cost of b would be n^2 - 100(unlikely, but as an example) So the cost of b is not exactly but CLOSE to n^2.

sorry i'm confused at 32:22, it is 100 ^2, but i think it is 100, why it isn't 100? could anyone explain that to me? thx alot

at 32:35 => Should not the first cost be 99*2 instead of 100^2 because there are 99 rows below first one. For pivoting each row below, you need to multiply the first row by some constant then subtract from the row you are pivoting. So, essentially are we not ending up having 2 operations per row for those 99 rows, hence, 99*2 instead of 100^2 ???

Can anyone tell me why can't we obtain the Lower triangular matrix L directly from the combined E which could just be derived from using gaussian elimination? Thanksss

Can anyone explain to me why the answer for cost of B is $n^2$ around 40:00?

What is the insights between E vs L? Is the matrix L can be computed in-place using A's matrix memory?

Tnx to MIT for this kind of stuff.

Why doe she go directly into LU factorization? should we earln first how to solve ax = b or 0?

@32:20 can anyone help me undertand why does it cost 100^2 instead of 99 operations?

June 15/2019-Very good lecture!

Why is space a subspace of itself? A container is not ann object inside of itself, a the components of an object are not the sum of its components.

Look. I’m going say this. I learned much oh this in Pre-Calculus in 1981 👍🏾

Thanks a Lot, Sir & MIT for bringing out these excellent lecture series on Linear Algebra. May I know where one can find the corresponding problems & assignments for these lectures. Thanks.

Thanks Gilbert!

Thanks, Dr. Strang

This actually makes sense now! Thank you!

Gilbert Strang a legend

thank you mit for this

I don't get the point of A = LU. You need to know U to solve for x in Ax=b. You need E to find U, you can't get U from L. Once you have U, you're basically done. What do you need L for? I understand the point that L is less costly than E -- but what use is L if you don't know U yet? What am I missing?