LINEAR-ALGEBRA

How a Matrix Cuts Itself in Half: The FFT's Recursive Magic

IKey Formulas

Formula	Name	Description
$w_n = e^{2\pi i / n}$	Primitive $n$ -th root of unity	Entries of $F_n$ are powers of $w_n$
$(w_n)^2 = w_{n/2}$	Squaring identity	Links $F_n$ to $F_{n/2}$
$F_n = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{n/2} & 0 \\ 0 & F_{n/2} \end{bmatrix} P$	FFT factorization	Three-factor split
$T(n) = \tfrac{n}{2}\log_2 n$	FFT cost	vs. $n^2$ naive

IISquaring the roots of unity

Squaring each $n$ -th root doubles its angle, collapsing the $n$ points onto the $n/2$ -th roots.

n 8 square

💡 So $F_{n/2}$ hides inside $F_n$ — the same $n/2$ roots reappear, which is exactly the smaller transform.

IIINaive cost vs FFT cost

How does $n^2$ compare with $\tfrac{n}{2}\log_2 n$ as the transform size $n$ grows?

log₂ n 1,024

💡 The gap widens without bound, so a million-point transform that is hopeless naively runs in real time via the FFT.

IVThe recursion tree

Each split doubles the blocks and halves their size, so every level costs the same $n/2$ .

n depth

VQuiz Questions

Question 1

Let $w_{64} = e^{2\pi i / 64}$ be the primitive 64th root of unity. What does $(w_{64})^2$ equal?

✅ Correct! Squaring doubles the angle, which halves the order.

❌ Not quite. Recall: squaring $e^{i\theta}$ gives $e^{i \cdot 2\theta}$ . Doubling the angle in $2\pi/n$ form gives $2\pi/(n/2)$ .

Show solution

Solution:

Squaring an exponential doubles the angle: $(w_{64})^2 = \left(e^{2\pi i / 64}\right)^2 = e^{4\pi i / 64} = e^{2\pi i / 32} = w_{32}.$

This is the linchpin identity of the FFT: $(w_n)^2 = w_{n/2}$ . It guarantees that $F_{n/2}$ is hiding inside $F_n$ .

Question 2

For $n = 1024$ , how many complex multiplications does one application of the FFT factorization (one level of splitting) save compared to the naive $n^2$ method?

Hint: one level costs $2 \cdot (n/2)^2 + n/2$ multiplications.

✅ Correct! One split gives about a 2× speedup; the dramatic gains come from applying it recursively.

❌ Not quite. Compute $2(n/2)^2 + n/2$ vs $n^2$ — the ratio is approximately $1/2$ .

Show solution

Solution:

Naive cost: $n^2 = 1024^2 = 1{,}048{,}576$ .

One-step FFT cost: $2 \cdot (n/2)^2 + n/2 = 2 \cdot 512^2 + 512 = 524{,}288 + 512 = 524{,}800$ .

That's roughly half the original work — about a 2× speedup from a single application of the factorization. The big speedups come from applying the factorization recursively, all the way down.

Question 3

Using the full recursive FFT, how many complex multiplications are needed for $n = 1024$ ?

✅ Correct! $(1024/2)\cdot \log_2(1024) = 512 \cdot 10 = 5{,}120$ .

❌ Not quite. Use the formula $(n/2)\log_2 n$ with $\log_2(1024) = 10$ .

Show solution

Solution:

The FFT cost is $\tfrac{n}{2}\log_2 n$ .

For $n = 1024$ : $\frac{1024}{2} \cdot \log_2(1024) = 512 \cdot 10 = 5{,}120.$

Compared to the naive $n^2 = 1{,}048{,}576$ , this is about a 205× speedup.

Question 4

True or False: The FFT computes a different (approximate) transform than the naive matrix-vector product, trading accuracy for speed.

✅ Correct! The factorization is an exact algebraic identity — same DFT, faster computation.

❌ Not quite. The FFT is an exact algorithm, not an approximation. It computes the very same DFT.

Show solution

Solution:

The FFT computes exactly the same discrete Fourier transform as the naive method — the same matrix $F_n$ , the same output, the same numbers down to floating-point round-off. Only the route changes.

The factorization $F_n = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{n/2} & 0 \\ 0 & F_{n/2} \end{bmatrix} P$ is an exact algebraic identity, not an approximation. The permutation $P$ costs zero multiplications (it's pointer arithmetic), so the only floating-point work is in the twiddle multiplies and the recursive sub-FFTs.

Solved: 0 / 4