# 26. Complex Matrices; Fast Fourier Transform

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

## Chapters

- 0:08 — Chapter 1 (0:08)
- 4:34 — Chapter 2 (4:34)
- 10:15 — Chapter 3 (10:15)
- 14:26 — Chapter 4 (14:26)
- 20:21 — Chapter 5 (20:21)
- 24:37 — Chapter 6 (24:37)
- 29:14 — Chapter 7 (29:14)
- 31:33 — Chapter 8 (31:33)
- 38:59 — Chapter 9 (38:59)
- 43:00 — Chapter 10 (43:00)
- 46:20 — Chapter 11 (46:20)

## Transcript

**[0:08]:** okay this is a lecture where complex numbers come in it's uh complex numbers have slipped into this course because even a real Matrix can have complex igen values so we met complex numbers there as the igen values and complex igen vectors and we are this is probably the last we have a lot of other things to do about igen values and igen vectors and that will be mostly real but at one point somewhere we have to see what do you do when the numbers become complex numbers what happens when the vectors are complex when the matrices are complex when the what's the inner product of two the product of two complex vectors we just have to make the change just see what is the change when numbers become complex then can I tell you about the most important example of complex matrices it comes in The forier Matrix so the forier Matrix which I'll describe

**[1:23]:** is a complex matrix it's certainly the most important complex matrix it's the Matrix that we need in the 48 transform and the Really the special thing that I want to tell you about is What's called the fast 4A transform and everybody refers to it as the fft and it's in all computers and it's used it's being used as we speak in a thousand places because it has like transformed whole Industries to be a able to do the forier transform fast which means multiplying how do I multiply fast by that matrix by that by that n byn Matrix normally multiplications by an N byn Matrix would normally be n sared multiplications because I've got n squ entries and none of them is zero this is a full Matrix and it's a matrix with orthogonal columns I mean it's just like the best Matrix and this fast 48 transform idea reduces this n SAR which was slowing

**[2:42]:** up the calculation of 48 transforms down to n log n n log n log to the base 2 actually and it's this when that hit when that possibility hit it made a big difference everybody realized gradually what uh that this simple idea you'll see it's just a simple Matrix factorization but it changed everything okay so I want to talk about complex vectors and matrices in general recap a little bit from last time and the forier Matrix in particular okay so what's the deal all right the main point is what about length I I'm given a vector I I have a vector X or let me call it Z as a reminder that it's complex for the moment but I can later I'll call the components X they'll be complex numbers but it's a vector Z1 Z2 down to ZN so the only novelty is it's not in RN any anymore it's in complex n dimensional

**[4:03]:** space each of those numbers is a complex number so this Z Z1 is in CN n dimensional complex space instead of RN it's just a different letter there but now the point about its length is what the point about its length is that Z transpose Z is no good

**[4:34]:** Z transpose Z if I just put down Z transpose here it would be Z1 Z2 to ZN doing that multiplication doesn't give me the right thing what why not because the length squared should be positive and If I multiply suppose this is is like one and I what's the length of the vector with components one and I what if I do this so n is just two I'm inan C2 two-dimensional space complex space with the vector whose components are one and I all right so if I took 1 Time 1 and I * I and added z z transpose Z would be zero but I don't that Vector is not doesn't have length zero the vector with components one and I this multiplication what I really want is Z1 conjugate Z1 you remember that Z1 conjugate Z1 is so you see that first step will be Z1 conjugate Z1 which is the magnitude of Z1

**[5:52]:** squared which is what I want that's like 3 squar or 5 squar now if it's if if Z1 is I then I multiplied by minus I gives 1+ one so the component of length the component I its modulus squared is + one that's great so what I want to do then is do that I want Z1 bar Z1 Z2 bar Z2 Z n bar is the n and remember that you remember this complex conjugate so so there's the point now I can erase the no good and put is good because that now gives the answer zero for the zero Vector of course but it gives a positive length squared for any other Vector so it's a it's the right definition of length and essentially the message is that we're always going to be taking when we transpose we also take complex conjugate so let's let's find the length of one so the vector 1 I that's Z that's that Vector z now I take the conjugate of one is one the conjugate of I is

**[7:23]:** minus I I take this Vector I get one + one I get two so that's a vector and that's a vector of length square root of two square root of two is the length and not the zero that we would have got from 1 minus i^ 2 okay so the message really is whenever we transpose we also take conjugates so here's a symbol one symbol to do both so that symbol h it stands for a guy named herit who didn't actually pronounce the h but let's pronounce it so I would call that z heran z now let me write that word her so his name was air meat and then we make it into an adjective Hermes so Z Z zhz okay so uh that's the that's the uh length squared now what's the inner product well it should match the inner product of two vectors so inner product is no longer used to be

**[8:56]:** y transpose X that's for real vectors for complex vectors whenever we transpose we also take the conjugate so it's y Permian X of course it's not real anymore usually that the inner product will usually be complex number but if Y and X are the same if they're the same Z then we have Z zhz we have the length squared and that's that's what we want the inner product of a vector with itself should be its length squared so this is like forced on us because this is forced on us so so this Z this everybody's picking up what this equals this is Z1 SAR plus ZN 2 that's the length squared and that's the inner product that we have to go with so it could be a complex number now one more change well two more changes we've got to change the idea of a symmetric matric so I I'll just recap on symmetric matrices

**[10:15]:** symmetric means a transpose equals a but not no good if a is complex so what do we CH what do we instead if I that applies perfectly to real matrices but now if my matrices are complex I want to take the transpose and the conjugate to equal a so there is that's the the right complex version of symmetry the the Symmetry now means when I transpose it flip across the diagonal and take conjugate so for example here would be an example on the diagonal it better be real because when I flip it the diagonal is still there and it has to and then when I take the complex conjugate it has to be still there so it better be a real number let me say two and five what about entries off the diagonal if this entry is say 3 + I then this entry had better be because I want whatever this when I

**[11:39]:** transpose it'll show up here and I conjugate so I need 3 minus I there so there's a matrix with that's that's that cor that corresponds the Symmetry but it's complex and those matrices are called herian matri mat herian matrices AAL a fine okay that's and those matrices have real igen values and they have perpendicular igen vectors what does perpendicular mean perpendicular means the inner product so let's go on to

**[12:27]:** perpendicular well when I had perpendicular vectors for example they were like q1 Q2 up to qn that's my Q is my letter that I use for perpendicular actually I usually I I I also mean unit length so those are perpendicular unit vectors but now what is so it's a orthonormal basis I'll still use those words but how do I compute perpendicular how do I check perpendicular this means that the inner product of Qi with QJ but now I not only transpose I must conjugate right to get zero if I is not J and one if I is J so it's a unit Vector meaning unit length orthogonal all the angles are right angles but these are angles in in complex n dimensional space so it's q1 q1 Qi bar transpose or for short qih QJ so it will still be true so let me again I'll create a matrix out of those guys The Matrix

**[13:51]:** will have these qes in its columns Q2 to qn

**[14:00]:** and I want to turn that into Matrix language just like before what does that mean that means I want all these inner products so I take these Columns of Q multiply by their rows so it was it used to be Q it used to be Q transpose qals I right this was an orthogonal

**[14:26]:** Matrix but what's changed these are now complex vectors their inner products are involve conjugating the first Factor so it's not it's the conjugate of Q transpose it's Q Bar transpose Q qh so can I call this let me call it qh Q which is I so that's our new you you see I'm just translating and the the book on one page gives a little like dictionary of the WR words in the real case RN and the corresponding words in the complex case for the vector space CN of course CN is a vector space the numbers we multiply are now complex numbers we just moving in the complex n dimensional space okay now actually I have to say we changed the word SYM symmetric to Hermes for those matrices people also change this word orthogonal into another word that happens to be

**[15:47]:** unitary as a word that applies the signals that we might be dealing with a complex Matrix here so what's a unitary Matrix it's just like an orthogonal matrix it's a square n byn Matrix with orthonormal columns perpendicular columns unit vectors unit vectors computed by and and and perpendicularity computed by remembering that there's a conjugate as well as a transpose okay so those are the words now I'm ready ready to get into the substance of the lecture which is the most famous complex Matrix which happens to be uh one of these guys it it has orthogonal columns and it's named after forier because it comes into the forier transform so it's the Matrix that's all around us okay let me tell tell you what it is first of all in the N byn case then often I'll let N be four because four is a good size to work with but here's the N byn 4A

**[17:16]:** Matrix its first column is the vector of ones it's n byn of course its second column is the Powers the actually better if I move from the math department to e for this one half hour and then please let me move back again okay what's the difference between those two departments it's just uh math starts counting with one and uh electrical engineers start counting at zero actually they're probably right so anyway well give them humor them so this is really the zeroth column and the First Column up to the N minus one that's the one inconvenience spot in electrical engineering all these Expressions start at zero no problem but they end at n minus one well that's uh that's the difficulty that course six has so what's they're the powers of a number that I'm going to call W W 2 W Cub W to the now what is the W here what's the power this was the 0th power first Power second

**[18:38]:** power this will be n minus first Power that's the column what's the next column it's the powers of w 2ar w 4th W to the 6th W to the 2 N minus1 and then more columns and more columns more columns and what's the last column it's the powers of let's see actually if we look along rows this Matrix is symmetric it's symmetric in the old not quite perfect way not perfect because these numbers are complex and so it's that first row is all ones one w w s up to W the N minus one that's the the the last column is the powers of w the N minus1 so this guy matches that and finally we get W to something here I guess we could actually figure out what that something is what are the entries of this Matrix the IJ entry of this Matrix am I going to you going to allow me to let I go from 0 to n minus one so I and J go from Z to n minus1 so the one the Z 0 entry is a one

**[20:10]:** it's just the same W guy to the power I times

**[20:21]:** J let's see I'm jumping into formulas here and I have to tell you what w is and then you know everything about this Matrix so w is well should we finish here what was this this is the n minus one n minus1 entry this is W to the nus1 squared everything's looking like a mess here because we have not too bad because all the entries are powers of w there none of them are zero this is a full Matrix but W is a very special number W is the special number whose n power is one in fact well actually there are n numbers like that one of them is one of course but the one we the w we want is the angle is 2 pi over

**[21:26]:** n is that what I mean n over 2 pi No 2 pi over n w is e to the I and the angle is 2 pi over M right where is this W in the complex plane it's it's on the unit circle right this is It's the cosine of 2 piun / n + I * the S of 2 piun / n but actually forget this it's never good to work with the real and imaginary Parts the rectangular coordinates when we're taking powers to to take that to the tenth power we can't see what we're doing to take this form to the tenth power we see immediately what we're go doing it would be e to the I 20 pi/ n so when our Matrix is full of powers so it's it's this formula and where is this on the complex plane here are the real numbers here's the imaginary axis here's the unit circle

**[22:38]:** of radius one and this number is on the unit circle at this angle which is 1 nth of the full way round so if I drew for example Nal 6 this would be e 2 I 2 pi over 6 it would be 1 16 of the way round it' be

**[23:02]:** 60° and where is W2 so I I I my w is e to the 2 pi I over 6 in this case in the 6 by for the 6x6 48 transform it's totally constructed out of this number and its powers so what are its powers well its powers are on the unit circle right because when I Square square a number a complex number I Square its absolute value which gives me one again all the powers have are on the unit circle and they the angle gets doubled to 120 so there's W2 there's W Cub there's W 4th there's W 5th and there is W 6th as we hoped W the Six coming back to one so those are the the six can I say this on TV the six six roots of one and it's this one that primitive one we say the first one which is W okay so what let me change let

**[24:17]:** me I said I would probably switch to n equal 4 what's W for that it's the fourth root of one W to the 4th will be one W will be e to the 2 pi I over 4

**[24:37]:** now what's that this is e to the I pi over 2 this is a quarter of the way round the unit circle and that's exactly I a quarter of the way round and sure enough the powers are i i s which is -1 I cubed which is - I and finally I 4th which is one right so there is w w^2 w Cub W 4th I'm really ready to write down this Fier Matrix for the 4x4 case just so we see that clearly let me do it here F4 is all right one one one one one one one W it's i i 2 that's minus one I cubed is minus I I I could write i^ s and I Cub why don't I just so we see the pattern for sure I 2 I cubed I 2 I cubed I4 I6 i4th I6 and I 9th you see the exponents fall in this nice the

**[26:02]:** exponent is the row number times the column number always starting at zero okay and now I can put in those numbers if you like one one one one 1 i - one - I 1 - one 1 - one and 1 - i - 1 I no yes

**[26:37]:** right what's why do I think that Matrix is so remarkable it's the 4x4 Matrix that comes into the 4o 4A transform when we want to find the for transform the 44A transform of a vector with four components we want to multiply by this F4 or we want to multiply by F4 inverse one way we're taking the transform one way we're taking the inverse transform actually they're so close that it's easy to confuse the two the inverse of this Matrix will be a nice Matrix also so and that's of course what makes it that that I guess Fier knew that he knew the inverse of this Matrix as you'll see it just comes from the fact that the columns are orthogonal from the fact that the columns are orthogonal we will quickly figure out what is the inverse but for8 didn't know didn't notice I think gaus noticed it but didn't make a point of it and then it turned out to be really

**[28:00]:** important was the fact that this Matrix is so special that you can break it up into nice pieces with lots of zeros factors that have lots of zeros and multiply by it or by its inverse very very fast okay but how did it get into this lecture first because the columns are orthogonal can I just check that the columns of this Matrix are orthogonal so the inner product of that column with that column is zero the inner product of column one with column 3 is zero how about the inner product of two and four can I take the inner product of column two with column four or even the inner product of two with three let's let's see does that let me do two and

**[29:14]:** four okay what oh I see

**[29:23]:** yes see I believe that those two column s are orthogonal so let me take their end product and hope to get zero okay now if you hadn't listened to the first half of this lecture when you took the inner product of that with that you would have multiplied one by one I by minus I and that would have given you one Min -1 by minus1 would have given you another one - I by I would have been minus i^ 2 that's another one

**[30:00]:** so do I conclude that the inner product of columns I said columns two and four that's because I forgot those are columns one and three I'm interested in their inner product and I'm hoping it's zero but it doesn't look like zero nevertheless it is zero those columns are perpendicular why because the inner product we conjugate you remember that one the vectors in the inner product has to get conjugated so when I conjugate it it changes that I to a minus I changes this to a plus I changes those that second sign and that fourth sign and I do get zero so those columns are orthogonal so columns are orthogonal they're not quite orthonormal but I could fix that easily they all those columns have length two length squared is four like this the four I had there this length squar 1+ 1 squ 1 squ 1 squ 1 squ is four square root is two so if I really wanted them suppose I really wanted to fix life up perfectly I could divide by two and now I have columns

**[31:25]:** that are actually orthonormal

**[31:33]:** so what so I can invert right away right orthonormal columns means now I'm keeping this one/ half in here for the moment means F4 herian can I use that conjugate transpose time F4 is

**[31:55]:** I so I see what the inverse is the inverse of f4 is it's just like a or orthogonal Matrix the inverse is the transpose here the inverse is the conjugate transpose so fine that that tells me that anything good that I learn about F4 I'll know the same I'll know a similar fact about its inverse because its inverse is just its conjugate transpose okay now so what's good well first The Columns are orthogonal that's a key fact that's the thing that makes the inverse easy but what property is it that leads to the fast 4A transform so now I'm going to talk in these last minutes about the fast 4A transform what here's the idea F six our 6x6 Matrix will there's a neat connection to F3 half as big there's a connection of f8 to F4 there's a connection of f64 to F32 shall I write down what that connection is what's the connection

**[33:12]:** of f64 to F32 so f64 is a 64x 64 Matrix whose W is the 64th root of 1 so it's 16 4 of the way around in f64 and and F32 is a 32x 32 Matrix remember they're different sizes and the W in that 32x 32 Matrix is the 32nd root of one which is twice as far that see that key Point that's the that's how 32 and 64 are connected in the W's the W for 64 is is 164 of the way so all I'm saying is that if I Square the W w64 that's what I'm using for the one over W6 this is w n is e to the i 2 pi/ N so w 64 is 164 of the way round it when I square that what do I get but w32 right if I Square this Matrix I double the angle if I Square this number I double the angle I

**[34:34]:** get uh the the w32 so somehow there's a little hope here to connect f64 with F32 and here's the connection okay let me let me go back uh yeah let me I'll do it here

**[34:58]:** here's the connection f64 the 64x 64 fora matrix it's connected to two copies of F32 let me leave a little space for the connection so this is 64x 64 here's a matrix of that same size because it's got two copies of F32 and two zero matrices those zero matrices are the key because when I multiply by this Matrix just as it is regular multiplication I would take need 64 I I would have 64 squared little multiplications to do but this Matrix is half zero well of course the two aren't equal I'm going to put an equal sign but there has to be some fix up factors one there and one there to make it true the beauty is that these fix up factors will be really almost all zeros so that as soon as we get this formula right we've got a great idea for how to get from the 6 from the 64 squared

**[36:18]:** calculations so this original originally we have 64 squared calculations from there but this one with will give us this is this will we don't need that many we only need 2 * 32 sared because we've got that twice and plus the fix up so I have to tell you what's in this fix up Matrix the one on the right is actually a permutation Matrix a very simple odds and evens permutation Matrix the the the ones show up I haven't put enough ones I really need a 32 of these guys a double space and

**[37:08]:** then you see it's a it's a permutation Matrix what it does shall I call it P for permutation Matrix so what that P does when it multiplies a vector it takes the odd the even numbered component onon first and then the odds you see this this one skipping every time is going to pick out x0 X2 X4 X6 and then below that will come we will pick out X1 X3 X5 and of course uh that can be hardwired in the computer to be instantaneous so that says so far what have we said we're saying that the 64x 64 forier Matrix is really separated it into separate your vector into the odd into the even components and the odd components then do a 32 size 48 transform on those separately and then put the pieces together again so the pieces putting them together turns out to be I and

**[38:22]:** a diagonal matrix and I and a minus that same diagonal matrix so the fix up cost is really the cost of multiplying by D this diagonal matrix because there's essentially no cost in in the I part or in the permutation part so really it's the fix up cost is essentially because D is diagonal is 32 multiplications

**[38:59]:** that's the there you seeing of course we didn't check the formula or we didn't even say what D is yet but I will this diagonal matrix D is powers of w 1 W w^2 down to W to the

**[39:18]:** 31st so you see that when I to do a multiplication by D I need to do 32 multiplications there they are then but the the other the more serious work is to do the F32 twice on the separately on the even numbered and odd numbered components so twice 32 squar so 64 squar is gone now and that's the new count okay great but what next so that's we now have the key idea we would have to check the algebra but it's just uh checking a lot of sums that come out correctly this is right the right way to see the fast for transform or one right way to see it then you got to see what's the next idea the next idea is to break the 32s down break those 32s down so we have this factor and now we have the F32 but that breaks into some guy here f30 F6 F 16 F-16

**[40:37]:** each each F32 is breaking into two copies of F-16 and then we have a permutation and then the so this is a like this was a 64 size permutation this is a 32 size permutation ah I guess I've got it twice is I'm I'm just using the same idea recursively recursion is the key word that on each of those F32 so here's 0 0 it's just to get

**[41:12]:** F32 this is the odd even permutations so you see we're we're the combination of those permutations what's it doing this guy separates into odds and into evens and odds and then this guy separates the evens into the ones the numbers of mult the even evens which means 0486 and even odds which means 2 6 10 14 and then OD evens and OD odds you see together these permutations then break it break our Vector down down into X even even and three other pieces those are the four pieces that separately get multiplied by F16 separately fixed up by these I's and D's and I's and minus D's so this count is now reduced this count is now what's it reduced to so that's going to be gone cuz 32 squ that's that's the change I'm making right the 32 squar so it's this that's now reduced

**[42:35]:** so I still have two times it but now what's 32 squar it's gone in favor of two 16 squar + 16 that's and that that was and and then the original 32 to fix

**[43:00]:** maybe you see what's happening even easier than this formula is what's when I do the recursion more and more times I get simpler and simpler factors in the middle eventually I'll be down to two point or one point for a transforms but I get more and more factors piling up on the right and left on the right I'm just getting permutation matrices on the left I'm getting these guys these I's and D's so that there was a 32 there and a each one of these is costing 32 each one of those is costing 32 and how many will there be see you see the 32 for this original fix up because D had 32 numbers 32 for this next fix up because D is 16 and 16 more I keep going so the count in the middle goes down to zip but these fix up counts are all that I'm left with and how many

**[44:05]:** factors how many fix UPS have I got log in from 64 one step to 32 one step to 16 one step to eight four 2 and one six steps so I have six fed up six fix up factors finally I get to six time the 32 that's my final count instead of 642 this is log to the base 2 of 64 * 64 actually half of 64 so actually the final count is n log to the base 2 of n that's the 32 ah a half so can I put a box around that wonderful extremely important and satisfying conclusion that the fast 4A transform multiplies by an N byn Matrix but it does it not in N squ steps but in 1 12 n log n steps and if we just com complete by doing a count let's suppose suppose uh a typical case would be 2 to the 10th now n^2 is bigger than

**[45:39]:** a

**[45:43]:** million so it's 1,24 * 1,24 but what is n what is 1 12 what is the the new count done the right way it's n the 1024 time 12 and what's the logarithm it's 10 so times 10/ 2 so it's five * it's 5 * 1,24 where this one was 1,24 *

**[46:20]:** 1,24 we've reduced the calculation by a factor of 200 just by factoring The Matrix tricks properly this was a th000 * n we're now down to 5 * n so we can do 200 48 transforms where before we could do one and in real scientific calculations where 4 transforms are happening all the time we're saving a factor of 200 in one of the major steps of modern scientific Computing so that's the idea of the fast for a transform and you see the whole thing hinged on being a special Matrix with orthonormal columns okay that's actually it for complex numbers I'm back next time really to to real numbers uh igen values and I vectors and the key idea of positive definite Matrix is going to show up what's a positive definite Matrix and it's terrific that this course is going to reach positive definiteness because those are the matrixes that you see the most in

**[47:39]:** applications okay see you next time thanks
