26. Complex Matrices; Fast Fourier Transform
Watch on YouTube →
Overview
The lecture develops the complex-vector rules needed to understand the Fourier matrix: conjugate transpose defines inner products, Hermitian matrices generalize real symmetric matrices, and unitary matrices generalize orthogonal matrices. It then derives the Fast Fourier Transform by recursively factoring Fourier matrices into smaller transforms, permutations, and diagonal twiddle-factor matrices, reducing the operation count from O(n²) to O(n log₂ n).
Key takeaways
- For complex vectors, the correct squared length is zᴴz = Σ |zᵢ|²; ordinary transposition can produce invalid results such as zero for the nonzero vector (1, i).
- Hermitian matrices satisfy Aᴴ = A and have real eigenvalues, while unitary matrices satisfy QᴴQ = I and preserve lengths and inner products.
- The Fourier matrix has entries Wⁱʲ, where W = e^(2πi/n); its root-of-unity structure produces orthogonal columns and a simple inverse after normalization.
- The FFT factors an even-sized Fourier transform into smaller transforms on even and odd input indices, plus a permutation and diagonal twiddle factors.
- For n = 1024, the lecture's FFT count of 5,120 multiplications is roughly 200 times smaller than the more than one million operations required by direct dense multiplication.
Chapters
- Real matrices can have complex eigenvalues and eigenvectors, so linear algebra needs rules for complex vectors and matrices.
- The Fourier matrix is a full complex matrix with orthogonal columns, used to compute Fourier transforms.
- The Fast Fourier Transform reduces matrix multiplication work from n² operations to a count proportional to n log₂ n.
- For z in Cⁿ, zᵀz can fail as a length measure: the vector (1, i) gives 1 + i² = 0.
- Using conjugates gives zᴴz = Σ |zᵢ|², which is positive for every nonzero vector.
- The vector (1, i) has squared length 2 and length √2 under this definition.
- The complex inner product is yᴴx, the conjugate transpose of the first vector times the second.
- A Hermitian matrix satisfies Aᴴ = A; its diagonal entries are real, and opposite off-diagonal entries are complex conjugates.
- Hermitian matrices have real eigenvalues and orthogonal eigenvectors when orthogonality is measured with the complex inner product.
- A complex matrix Q with orthonormal columns satisfies QᴴQ = I and is called unitary.
- The n by n Fourier matrix uses powers of W, with entry in row i and column j equal to Wⁱʲ for indices from 0 to n − 1.
- W = e^(2πi/n) is a primitive nth root of unity, so Wⁿ = 1 and its powers lie on the unit circle.
- Using zero-based indexing makes the matrix pattern and the exponent i j explicit.
- For n = 4, W = e^(2πi/4) = i, whose powers cycle through i, −1, −i, and 1.
- The entries of F₄ are powers of i, with exponents given by the products of row and column indices.
- The four-point matrix illustrates how the same root-of-unity pattern generates every entry of a Fourier matrix.
- The columns of F₄ are orthogonal when the inner product correctly conjugates one column.
- Each unscaled F₄ column has squared length 4, so dividing the matrix by 2 makes its columns orthonormal.
- For the normalized matrix, the inverse is its conjugate transpose, just as an orthogonal matrix is inverted by transposition.
- The root for F₆₄ squares to the root used by F₃₂, linking the two matrix sizes.
- A permutation rearranges the input into even-indexed and odd-indexed components, then two F₃₂ transforms process those halves.
- A diagonal matrix of powers W⁰ through W³¹ supplies the twiddle factors; this costs 32 multiplications instead of 64² dense-matrix operations.
- Applying the same factorization recursively breaks each F₃₂ into two F₁₆ transforms, then continues toward smaller sizes.
- Successive permutations separate index groups such as even-even, even-odd, odd-even, and odd-odd components.
- At each level, smaller Fourier transforms are combined with diagonal twiddle-factor matrices and index permutations.
- For sizes that are powers of two, the lecture counts about (n/2) log₂ n multiplications, rather than n².
- At n = 1024, this estimate is 5,120 operations versus more than 1,048,000 for direct multiplication, roughly a 200-fold reduction.
- The speedup makes repeated Fourier transforms practical in scientific computing and other applications that depend on frequency analysis.
Transcript excerpt
0:08 Okay. This is a lecture where complex numbers come in. It's a -- complex numbers have slipped into this course because even a real matrix can have complex eigenvalues. So we met complex numbers there as the eigenvalues and complex eigenvectors. And we -- or -- this is probably the last -- we have a lot of other things to do about eigenvalues and eigenvectors. And that will be mostly real. But at one point somewhere, we have to see what you do when the numbers become complex numbers. What happens when the vectors are complex, when the matrixes are complex, when the --
0:57 what's the inner product of two, the dot 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 matrixes? It comes in the Fourier matrix. So the Fourier matrix, which I'll describe, is a complex matrix. It's certainly the most important complex matrix. It's the matrix that we need in Fourier transform. And the -- really, the special thing that I want to tell you about is what's called the fast Fourier transform, and everybody refers to it as the FFT and it's in all
1:48 computer and it's used -- it's being used as we speak in a thousand places, because it has, like, transformed whole industries to be able to do the Fourier transform fast, which means multiplying -- how do I multiply fast by that matrix -- by that n by n matrix? Normally, multiplications by an n by n matrix -- would normally be n squared multiplications, because I've got n squared entries and none of them is zero. This is a full matrix. And it's a matrix with orthogonal columns.
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MIT OpenCourseWare.