MIT has done great service to mankind, by recording his lectures and sharing them online. This are so beautiful, future generations will remember him as the Mozart of this subject
This was probably the most beautiful lecture I have ever watched. The way the knowledge is passed, step after is step is pure poetry. Thank you Prof. Strang.
00:00 Complex numbers and the Fast Fourier Transform 06:33 Complex matrices have a different definition of symmetry and perpendicularity 13:07 Introduction to complex n-dimensional space and unitary matrices 19:17 Understanding the complex numbers in Fourier transform 25:08 The four by four matrix for Fourier transform is remarkable. 30:46 The columns of F4 are orthonormal, making its inverse easy to calculate. 36:15 The 64 by 64 Fourier matrix can be separated into even and odd components and then a 32 size Fourier transform can be done on them separately. 42:02 The fast Fourier transform multiplies by an n by n matrix in half n log n steps. Crafted by Merlin AI.
@@cafe-tomate make a good notes from watching a lecture very slowly and go through them many times. That is how you learn math. "If you don't review your notes, you learn nothing" (a famous math guy, forget the name). Then, no need to watch lectures more than ones.
@@АлександрСницаренко-р4д that's cool. I do that and always watch them a second time (twice, no more) to see if I got the righr interpretation the lecturer wanted to share and I put the same idea in my notes.
The lecture on Complex Matrices and Fast Fourier Transform are excellent. DR. Strang also explained these two subjects in Computational Science and Engineering I and II at MIT.
So true. A professor can be a genius and a lousy teacher at the same time. Unless you’re genius yourself, you’re not gonna learn anything from such a professor. Professor Strang is a great teacher and a genius at the same time. What a beautiful combination.
The only reason you think he's so good is because you're watching a youtube video. If you were sitting in his class you'd think he sucks. Not because he sucks but because EVERYONE thinks anyone on youtube is better than classroom professors. That's how dumb everyone is, you think youtube teachers are better than classroom teachers
@@christopherjoseph651 You are making gross assumptions on what others are thinking solely based on your own thinking about others. And you hinted that you think everyone but you is dumb.
Don't complain whiners. There are TWO whole courses after this one that teach JUST applied linear algebra. 1. Computational Science and Engineering I 2. Mathematical Methods for Engineers II You can also read the book - Introduction to Linear Algebra, AND another entire book just for advanced applications - Computational Science and Engineering, both by Prof. Strang.
Thanks Prof. Strang!!! This lecture is a work of art. I was doing some work on a DFT course and needed a comprehensive approach to DFT/IDFT, Best 50 minutes I have spent. Thanks for the tip on Hermitian and unitary matrices!!!
okay this was extremely useful! revising for exam for discrete mathematics first year at the University of Bath, and from 16:25 best way of thinking of fast fourier transforms and matrices that i have heard!! very simple, well explained, he's a great lecturer.
After a couple of years away from these topics I felt in love again with them. You gave me the light to find them again. Thanks! (there are not enough words to explain you all my gratitude about this) :-), best wishes.
I am a computer science undergrad watching these lectures because I felt I needed to understand Linear Algebra better for two fields: Machine Learning and Quantum Information. It's incredible that both of these get some overlap with this linear algebra course (ML was touched on when we did projection matrices as that is exactly the closed form solution to linear regression), and now QI which uses Complex vectors spaces is being covered. :)
I watched the second video of 6.046J (Design and Analysis of Algorithms), and Erik Demaine explained FFT. That video confused me so fast so much, that I decided to watch18.01, 18.02, and 18.06. Looks like I was right in guessing that this course should be a prereq for 6.046J (even though it isn't). Happy to see FFT in a pure Linear Algebra context :D
Thing that he said eventually is so nice for the computer engineers to understand how computational circuits uses FFT in order to increase efficiency 🥰🥰🥰 legend Gilbert
I can't continue the course anymore, the last 30 minutes of this lecture seems to be way too much for me. *after trying to understand the first 15 minutes of his last 30 minutes for an hour and I'm still confused. Appreciate your work Professor Strang. It's a great experience learning from you. Got this lecture bookmarked, I'll return to it one day
Not sure how's your relation with LA, but - coming from this no hard-science-back-grounded-guy here - you might check 3Blue 1Brown Euler's coeficient videos. I have been following both courses simultaneously and that gave me a good clue to get along with this lecture. Best of luck!
@@jefthervieira1 Where professor introduced F64 can be broken down into two F32 and other premutation stuff I wasn't able to grasp. Can you suggest a good resource to understand that stuff.
Be sure to use the regular transpose (not the Hermetian transpose) when calculating the inverse of a complex matrix from the cofactor matrix. I found out the hard way Matlab and Octave's transpose operator ( ' ) will do the Hermetian transpose. If you want the regular old transpose, you have to use the transpose() function explicitly.
As you can see it is D and -D that will both multiply F_32. Do Basically, the result will be DF_32 and -(DF_32). Reversing the sign can be done for "free" (compared to a multiplication) so there is only DF_32 to compute, hence cost 32. Anyway this is just an illustration and complexity analysis shouldn't account for constant factors: in the end, the number of operation is linear in n, that's all that count.
@@rosadovelascojosuedavid1894 I dropped out of college. I never graduated. Turns out I’m a pretty lousy student lol. If I knew then what I knew now, I would have double majored in computational math and applied physics with a minor in computer science.
at 31.20 when making the columns orthonormal by dividing by 1/2 , F4 should also be divided and the new matrix 1/2(F4) is orthornormal. Then the new matrix and its hermitian are equal to the Identity, which means F4^H x F4 = 4I. Right?
Here's the playlist for 18.06SC: th-cam.com/play/PL221E2BBF13BECF6C.html. You can find the course materials on MIT OpenCourseWare at: ocw.mit.edu/18-06SCF11. Best wishes on your studies!
Correct, but here we are talking about multiplying an nxn matrix with a vector. Each function is a vector with infinite number of coordinates, but when we discretise it (sample it), we get a n-dimensional vector. A matrix linearly transforms a vector by multiplying it on the left, and the Fourier matrix transforms a function in the same way.
Maybe a year too late, but if someone else reads this, I get an additive n rather than n/2 term, too. I think the fact that there are 2 diagonal W matrices of order n/2 was a mistake but he did an excellent job presenting this material. I think it's a mistake based on what I understand, but an inconsequential mistake when considering computational complexity.
@@joem8251 Impossible to comment without seeing the work, but focus on D's; we only need to compute them once (-D need NOT be computed as it is a sign change). Each factorization doubles the number of D's but reduces the elements in D's by half as well, thereby keeping the number of multiplications constant on each step which is (1/2)*n
In that Wikipedia article they say "a clockwise DFT matrix". What he showed would be the counterclockwise (the same direction in which angles are measured in math). Anyway , the two matrices are the same except the signs of i are the opposite, due to this reflection around the real axis, and so one is the Hermitian of the other. When one is a transform of a function, the other one is a reverse transform. A reverse transform is nothing but the Fourier transform of another function, the one that itself is a Fourier transform of the original function... or the direct transform if you start in that other domain.
i will tell you why u understand everthing here..This professor is great and the other thing is..This lecture wont be explained in 10 minutes like here in Germany. Of course u understand fucking nothing if you explain such important things in 10 minutes and then begin with new stuff.
Lecture 26 is Professor Strang’s best performance so far. In lecture 25, in front of students, he screwed up his proof showing real symmetric matrices have real eigenvalues. Got confused and had to refer to his notes. In this lecture, in front of no students, he gives a tour de force performance. Hope there no students in his remaining lectures, because his cyberspace audience is orders of magnitude larger than his MIT audience.
I loved the way how he smoothly recovered the proof consulting his notes, I would be lost just staring at the notes not even seeing anything. He found why he didn't finish the proof the first time around and explained the reason to students (and us) and what was the main reasoning behind the proof, so not did I only learn the matter but also learned how to make proofs myself and what to do when I reach the dead-end like 0 =0 or 1 = 1.
There are two other courses focusing on applications that he teaches (both were made open source). This is a basic course which should only show initial connection between the fundamentals and applications.
There are two other courses focusing on applications that he teaches. This is a basic course which should only show initial connection between the fundamentals and applications.
this is the least satisfying of the Strang lectures I've seen. everything is so dumbed down until he gets into factoring the Fourier matrix and then all of the sudden doesn't really show that the factorization is correct. Not even a rudimentary hand-waving.
Perhaps the students could check that it is correct themselves? Given that there is so much structure here, it is quite easy to check. He suggests as much at 39:59. Furthermore, his book has the algebra on pages 512-513. We must remember that these lectures are not meant to instruct outsiders from scratch. They are merely a window into the MIT experience, which includes, as all good programs of study do, an expectation that students read the book, attend recitations, and do some work on their own. The reading of books (or the internet) and doing work on their own is the most critical part, as this is the only way they will learn once they are out of school. Anyone watching these videos should be expected to do the same.
what the hell bro.. study complex nums and cube roots or nth roots of unity then you'll get it. At least don't blame the prof. for your past ignorance.
MIT has done great service to mankind, by recording his lectures and sharing them online. This are so beautiful, future generations will remember him as the Mozart of this subject
not really, they are just lectures of peopole who actally understood subject and are able to communicate.
This was probably the most beautiful lecture I have ever watched. The way the knowledge is passed, step after is step is pure poetry. Thank you Prof. Strang.
00:00 Complex numbers and the Fast Fourier Transform
06:33 Complex matrices have a different definition of symmetry and perpendicularity
13:07 Introduction to complex n-dimensional space and unitary matrices
19:17 Understanding the complex numbers in Fourier transform
25:08 The four by four matrix for Fourier transform is remarkable.
30:46 The columns of F4 are orthonormal, making its inverse easy to calculate.
36:15 The 64 by 64 Fourier matrix can be separated into even and odd components and then a 32 size Fourier transform can be done on them separately.
42:02 The fast Fourier transform multiplies by an n by n matrix in half n log n steps.
Crafted by Merlin AI.
Prof Strang is the best “old school” teacher you can imagine. Black board and chalk, straightforward and to the point. And no fancy techtronics
Old is gold
1.5 x Gilbert Strang = Gilbert Strong
2 x Gilbert Strang = Gilbert Stark
Binge watch = Gilbert Stretch.
3 x Gilbert Strang = Gilbert Strange--Dr. Gilbert Strange.
244u + Gilbert Strang = Gilbert Strangelove
(Gilbert Strang)^T = Gilbert Strang because he's so positive and excellent ;)
If you start your day with one of the lecture of Gilbert Strang, your day will be perfect! :-)
Yassss 😁 I feel the same 😁
Problem comes when you have to watch it twice thrice or more to fully understand it
@@cafe-tomate make a good notes from watching a lecture very slowly and go through them many times. That is how you learn math. "If you don't review your notes, you learn nothing" (a famous math guy, forget the name). Then, no need to watch lectures more than ones.
Hah! I thought it was Gilbert Strang from the Thumbnail photo 😃
@@АлександрСницаренко-р4д that's cool. I do that and always watch them a second time (twice, no more) to see if I got the righr interpretation the lecturer wanted to share and I put the same idea in my notes.
The lecture on Complex Matrices and Fast Fourier Transform are excellent. DR. Strang also explained these two subjects in Computational Science and Engineering I and II at MIT.
What a great lecture this Professor gives... That's probably why MIT is so good, they actually hire teachers that can teach! Congratulations
So true. A professor can be a genius and a lousy teacher at the same time. Unless you’re genius yourself, you’re not gonna learn anything from such a professor.
Professor Strang is a great teacher and a genius at the same time. What a beautiful combination.
The only reason you think he's so good is because you're watching a youtube video. If you were sitting in his class you'd think he sucks. Not because he sucks but because EVERYONE thinks anyone on youtube is better than classroom professors. That's how dumb everyone is, you think youtube teachers are better than classroom teachers
@@christopherjoseph651 You are making gross assumptions on what others are thinking solely based on your own thinking about others. And you hinted that you think everyone but you is dumb.
@@christopherjoseph651 eh..OCW isn't going to pick the crappy classroom professor to distribute their content to the world!
This was a real eye opener, can't thank MIT OCW enough!!
Don't complain whiners. There are TWO whole courses after this one that teach JUST applied linear algebra.
1. Computational Science and Engineering I
2. Mathematical Methods for Engineers II
You can also read the book - Introduction to Linear Algebra, AND another entire book just for advanced applications - Computational Science and Engineering, both by Prof. Strang.
Ooh yes!
k
So the only background needed is this course, for the two courses you mention?
@@konstantinosarsen581 Don't forget your calculus (± DiffEq) in the meantime
Merci beaucoup
Quality at its extreme !!! Respect professor strang !!! Hats off to you !!!
Thanks Prof. Strang!!! This lecture is a work of art. I was doing some work on a DFT course and needed a comprehensive approach to DFT/IDFT, Best 50 minutes I have spent. Thanks for the tip on Hermitian and unitary matrices!!!
He is a genius...
Really glad I watched this to the end. I've implemented an FFT, but didn't know about the matrix factorization view of the problem.
okay this was extremely useful!
revising for exam for discrete mathematics first year at the University of Bath, and from 16:25 best way of thinking of fast fourier transforms and matrices that i have heard!! very simple, well explained, he's a great lecturer.
17:46 "Math starts counting with one and electrical engineers start counting at zero. Actually, they're probably right."
really a fantastic professor, explain all this idea so clearly and naturally. I was confused about fourier series before, now I am pretty clear!
The conjugate transpose is written with H for Hermitian. In quantum mechanics, we use the "dagger" symbol which looks like a cross.
I took a math class in harmonic analysis and we used star for it. 😊😊
After a couple of years away from these topics I felt in love again with them. You gave me the light to find them again. Thanks! (there are not enough words to explain you all my gratitude about this) :-), best wishes.
simple yet elegant; erudite yet conveyable
Absolutely beautiful.. this is amazing. Thank you so much to MIT and Gilbert Strang
00:00 Hermitian Matrices
16:34 Fourier
Small point: *Two* |D| size multiplies are needed so in a few places where he says 32 it should be 2*32.
Would be golden if the explaination to that factorization came in.
This is truly a fun series of lectures.
Amusingly, every problem seems to boil down to a problem in Linear Algebra!
I am a computer science undergrad watching these lectures because I felt I needed to understand Linear Algebra better for two fields: Machine Learning and Quantum Information. It's incredible that both of these get some overlap with this linear algebra course (ML was touched on when we did projection matrices as that is exactly the closed form solution to linear regression), and now QI which uses Complex vectors spaces is being covered.
:)
And the Fourier Matrix is the QFT !
I watched the second video of 6.046J (Design and Analysis of Algorithms), and Erik Demaine explained FFT. That video confused me so fast so much, that I decided to watch18.01, 18.02, and 18.06. Looks like I was right in guessing that this course should be a prereq for 6.046J (even though it isn't).
Happy to see FFT in a pure Linear Algebra context :D
Thing that he said eventually is so nice for the computer engineers to understand how computational circuits uses FFT in order to increase efficiency 🥰🥰🥰 legend Gilbert
This is my favorite lecture
This lecture made so much sense. My current professor doesn't do a good job in keeping it interesting. Great lecture!
I envy those MIT guys who could learn from Prof.Strang in person.
Hope they could appreciate what an absolute gem of a teacher he is
girlbert is my homie
I can't continue the course anymore, the last 30 minutes of this lecture seems to be way too much for me. *after trying to understand the first 15 minutes of his last 30 minutes for an hour and I'm still confused.
Appreciate your work Professor Strang. It's a great experience learning from you.
Got this lecture bookmarked, I'll return to it one day
Not sure how's your relation with LA, but - coming from this no hard-science-back-grounded-guy here - you might check 3Blue 1Brown Euler's coeficient videos. I have been following both courses simultaneously and that gave me a good clue to get along with this lecture. Best of luck!
also 3b1b lockdown math course.
@@jefthervieira1 I see you are a man of culture.
@@jefthervieira1 Where professor introduced F64 can be broken down into two F32 and other premutation stuff I wasn't able to grasp. Can you suggest a good resource to understand that stuff.
Be sure to use the regular transpose (not the Hermetian transpose) when calculating the inverse of a complex matrix from the cofactor matrix. I found out the hard way Matlab and Octave's transpose operator ( ' ) will do the Hermetian transpose. If you want the regular old transpose, you have to use the transpose() function explicitly.
I just messed up in the odd odd, odd even part, whatever the rest is wonderful. Thanks to Prof. Strang from India.
He's talking about multiplying a matrix by a vector, which is O(n^2).
This lecture was made just fine for dft.
I think prof. Strang gave a much better explanation of the FFT algorithm in his other course - Mathematical methods for engineeers I
At the end I remembered I never read about fourier transform only fourier series. Thought I was going insane for a second.
Gotta respect Gilbert Strang.
Thanks, merci beaucoup prof Strang, absolute brillant
No students today :{
Thanks Gilbert...love your work. JS
25:46 Strang: "I squared I cubed... I squared I cubed... "
Me: "You sure did :DDD"
The difference between EE and Math dept is EE starts counting at 0 and Math at 1....paraphrased at 18:10. That made me laugh.
being confused for more than 20mins with FFT, still watched the whole lecture oops haha, omgg, good jobbbbbbbbbb!
Cutest teacher! EE starts counting from 0, we start counting from 1. Actually they probably right.
40:03 why the fixed count part is 32? I thought 64 since we have 2 D in the left matrix.
As you can see it is D and -D that will both multiply F_32. Do Basically, the result will be DF_32 and -(DF_32). Reversing the sign can be done for "free" (compared to a multiplication) so there is only DF_32 to compute, hence cost 32. Anyway this is just an illustration and complexity analysis shouldn't account for constant factors: in the end, the number of operation is linear in n, that's all that count.
For the FFT, there's another truth to be noticed. $$w_{64}^k = -1.0 * w_{64}^{k+32}$$ Also for this reason, -D appears here.
I dropped out of electrical engineering degree, and here it is, following me around with no chill. Maybe this is a sign lol
So what did you major in?
So you switched from 0-based to 1-based world.
@@rosadovelascojosuedavid1894 I dropped out of college. I never graduated. Turns out I’m a pretty lousy student lol. If I knew then what I knew now, I would have double majored in computational math and applied physics with a minor in computer science.
@@nenadilic9486 lol for a time. But the 0-based world pulled me right back haha 😅
@@ozzyfromspace Now you're a J-man instead of I-man ;)
I'm surprised by the empty seats at 41:41
at 31.20 when making the columns orthonormal by dividing by 1/2 , F4 should also be divided and the new matrix 1/2(F4) is orthornormal. Then the new matrix and its hermitian are equal to the Identity, which means F4^H x F4 = 4I. Right?
What an amazing lecture, thank you!
32:41 - that's where the FFT part starts.
I am shocked at 40:48, why isn't there any students at the lecture hall?
Great video to watch after watching many quantum computing videos and realized you missed a class back to your university times 🤣🤣
i lost my mind when he taught about FFT. Anyway, Prof Gil. Strang is brilliant.
The mathematics of Quantum Mechanics!
Why do we do permutations of 32-matrix?
Is there a playlist where all of these lectures on Linear Algebra of 18.06 can be accessed?
For every course taught by Professor Strang?
Here's the playlist for 18.06SC: th-cam.com/play/PL221E2BBF13BECF6C.html. You can find the course materials on MIT OpenCourseWare at: ocw.mit.edu/18-06SCF11. Best wishes on your studies!
(1)Does it matter which matrix is taken the conjugate of when computing the standard norm?
Isn't the order of complexity for multiplication b/w 2 n x n matrices O(n^3) and not O(n^2)?
Correct, but here we are talking about multiplying an nxn matrix with a vector. Each function is a vector with infinite number of coordinates, but when we discretise it (sample it), we get a n-dimensional vector. A matrix linearly transforms a vector by multiplying it on the left, and the Fourier matrix transforms a function in the same way.
@44:25 2 (2 (2 (2 (2 (2 + 1) + 2) + 4) + 8) + 16) + 32 = 256 ， not 6×32 = 192
2 (2 (2 (2 (2+2) +4) +8) +16) + 32=192=6*32
@@lsun9593 i didn't get you, could you clarify?
i think it should be n + n/2 log n
Maybe a year too late, but if someone else reads this, I get an additive n rather than n/2 term, too. I think the fact that there are 2 diagonal W matrices of order n/2 was a mistake but he did an excellent job presenting this material. I think it's a mistake based on what I understand, but an inconsequential mistake when considering computational complexity.
@@joem8251 Impossible to comment without seeing the work, but focus on D's; we only need to compute them once (-D need NOT be computed as it is a sign change). Each factorization doubles the number of D's but reduces the elements in D's by half as well, thereby keeping the number of multiplications constant on each step which is (1/2)*n
@38:45 why did we count the fix-up cost from just one of the D's. Shouldn't it be twice since we have D and -D in the matrix?
Think what's -D compared to D? :D
I lost it at the end... That is soooo confusing!
Am I only one realize that there is nobody in class?
wish i could be the audience
No sometimes Gilbert strang records his lectures alone for Courseware
Duh corona time remember?
@l955382 it's like an identity matrix except the 1s don't go across the diagonal. The 1s are moved here and there to denote row operations
He made a pretty good circle with one quick move xD
In other places, the DFT matrix has a minus in the exponential (en.wikipedia.org/wiki/DFT_matrix). What am I missing here?
In that Wikipedia article they say "a clockwise DFT matrix". What he showed would be the counterclockwise (the same direction in which angles are measured in math). Anyway , the two matrices are the same except the signs of i are the opposite, due to this reflection around the real axis, and so one is the Hermitian of the other. When one is a transform of a function, the other one is a reverse transform. A reverse transform is nothing but the Fourier transform of another function, the one that itself is a Fourier transform of the original function... or the direct transform if you start in that other domain.
I am controlled by the combination of FFT and linear algebra....
Ty for uploader
i will tell you why u understand everthing here..This professor is great and the other thing is..This lecture wont be explained in 10 minutes like here in Germany. Of course u understand fucking nothing if you explain such important things in 10 minutes and then begin with new stuff.
Good time!
Hi, does the i in this video stand for imaginary number or i hat ?
at 26:42
sqrt (-1)
37minute i dont understand please supplementary data ㅜ
Genius!
what even is a fourier transform?
Look at MIT 18.03 lectures 15-17.
Fast fourier transform part was too tough for me
Lecture 26 is Professor Strang’s best performance so far.
In lecture 25, in front of students, he screwed up his proof showing real symmetric matrices have real eigenvalues. Got confused and had to refer to his notes. In this lecture, in front of no students, he gives a tour de force performance.
Hope there no students in his remaining lectures, because his cyberspace audience is orders of magnitude larger than his MIT audience.
I loved the way how he smoothly recovered the proof consulting his notes, I would be lost just staring at the notes not even seeing anything. He found why he didn't finish the proof the first time around and explained the reason to students (and us) and what was the main reasoning behind the proof, so not did I only learn the matter but also learned how to make proofs myself and what to do when I reach the dead-end like 0 =0 or 1 = 1.
I have lost myself for the last 10 minutes lol
32:56
All his application lectures seem kind of sloppy
There are two other courses focusing on applications that he teaches (both were made open source). This is a basic course which should only show initial connection between the fundamentals and applications.
Near 23 min in, how did he ignore the i, but remember it in his next example with n = 4?
Not sure what you're talking about. He said "i" everywhere it needed to be said, and wrote "i" everywhere it needed to be written.
conjugate
LOL numbers are just ideas.So technically I can't be wrong l.O l
Of course to be a real Electrical Engineer you should use j for imaginary numbers.
He's just showing applications of linear algebra, not teaching them. That's why it seems "sloppy". You just can't teach Fourier Transform in 30 mins.
He doesn't have to teach Fourier in 30 mins. These students have already had 18.03. Look at Prof. Mattuck's lectures 15-17.
There are two other courses focusing on applications that he teaches. This is a basic course which should only show initial connection between the fundamentals and applications.
this is the least satisfying of the Strang lectures I've seen. everything is so dumbed down until he gets into factoring the Fourier matrix and then all of the sudden doesn't really show that the factorization is correct. Not even a rudimentary hand-waving.
Perhaps the students could check that it is correct themselves? Given
that there is so much structure here, it is quite easy to check. He suggests as much at 39:59.
Furthermore, his book has the algebra on pages 512-513. We must
remember that these lectures are not meant to instruct outsiders from
scratch. They are merely a window into the MIT experience, which
includes, as all good programs of study do, an expectation that students
read the book, attend recitations, and do some work on their own. The
reading of books (or the internet) and doing work on their own is the
most critical part, as this is the only way they will learn once they
are out of school. Anyone watching these videos should be expected to
do the same.
what the hell bro.. study complex nums and cube roots or nth roots of unity then you'll get it. At least don't blame the prof. for your past ignorance.
Use a hat or a bag