LINEAR-ALGEBRA · Interactive Practice

Why Inverting the Fourier Matrix Is Almost Free

IKey Formulas

Formula	Name	Description
$w = e^{2\pi i / n}$	Primitive $n$ -th root of unity	Smallest $n$ with $w^n = 1$
$(F_n)_{ij} = w^{ij}$	Fourier matrix entry	Indices $i,j = 0, \ldots, n-1$
$\langle u, v \rangle = \sum_k \overline{u_k}\, v_k$	Hermitian inner product	Conjugate first, then multiply
$F_n^{-1} = \frac{1}{n} F_n^{H}$	Inverse of Fourier matrix	Conjugate transpose, scaled by $1/n$

IIVisualization 1 — Roots of Unity

The powers of $w = e^{2\pi i/n}$ land on $n$ equally spaced points of the unit circle.

n 4 power k 0

💡 Multiplying by $w$ rotates by $2\pi/n$ ; after $n$ steps you return to $w^n = w^0 = 1$ — the cyclic symmetry that fills $F_n$ .

IIIVisualization 2 — The Fourier Matrix Entries

Every entry $(F_n)_{ij} = w^{ij}$ is a power of $w$ ; row 0 and column 0 are all ones.

matrix size n 4

IVVisualization 3 — Inner Product Between Columns

Distinct columns of $F_4$ are orthogonal — inner product $0$ ; a column with itself gives $n = 4$ .

column

j_1

column

j_2

💡 Distinct columns cancel to $0$ and equal columns give $n$ , so $F_n^H F_n = nI$ and $F_n^{-1} = \tfrac{1}{n} F_n^H$ .

VQuiz Questions

Question 1

Let $w = e^{2\pi i/4} = i$ be the primitive 4th root of unity. What is $w^6$ ?

✅ Correct! $w^6 = w^{6 \bmod 4} = w^2 = -1$ .

❌ Not quite. Reduce the exponent mod 4 first, since $w^4 = 1$ .

Show solution

Solution:

Since $w^4 = 1$ , we can reduce the exponent modulo 4: $w^6 = w^{6 \bmod 4} = w^2 = i^2 = -1$

This is exactly how we fill in the entries of the Fourier matrix: any power of $w$ can be reduced to $w^0, w^1, w^2,$ or $w^3$ .

Question 2

Consider columns 1 and 3 of $F_4$ :

$u = (1, i, -1, -i)$ and $v = (1, -i, -1, i)$ .

Using the Hermitian inner product $\langle u, v \rangle = \sum_k \overline{u_k} v_k$ , what is $\langle u, v \rangle$ ?

✅ Correct! Distinct columns of $F_n$ are orthogonal under the Hermitian inner product.

❌ Not quite. You may have skipped the conjugation step. The Hermitian inner product conjugates the first vector.

❌ Not quite. Conjugate $u$ first, then multiply entrywise and sum.

Show solution

Solution:

First conjugate $u$ : $\bar{u} = (1, -i, -1, i)$ .

Now multiply entry-wise with $v = (1, -i, -1, i)$ and sum:

$\langle u, v \rangle = (1)(1) + (-i)(-i) + (-1)(-1) + (i)(i)$ $= 1 + i^2 + 1 + i^2 = 1 - 1 + 1 - 1 = 0$

The columns are orthogonal under the Hermitian inner product. This is the key fact behind $F_n^H F_n = nI$ .

Question 3

True or False: For the $4 \times 4$ Fourier matrix $F_4$ , the matrix $F_4^H F_4$ equals $4I$ (four times the identity).

✅ Correct! This is exactly why $F_4^{-1} = \frac{1}{4}F_4^H$ .

❌ Not quite. Each column has squared length 4, and distinct columns are orthogonal, so $F_4^H F_4$ is diagonal with 4s on the diagonal.

❌ Not quite. Try again — the hints above can help.

Show solution

Solution:

The entry $(F_4^H F_4)_{ij}$ is the Hermitian inner product of column $i$ with column $j$ of $F_4$ .

Diagonal ( $i = j$ ): each column has squared length $|1|^2 + |i|^2 + |-1|^2 + |-i|^2 = 4$ .
Off-diagonal ( $i \ne j$ ): distinct columns are orthogonal, so the inner product is $0$ .

Therefore $F_4^H F_4 = 4I$ , and dividing by 4 gives: $F_4^{-1} = \frac{1}{4} F_4^H$

Question 4

For a general $n \times n$ Fourier matrix $F_n$ , what is $F_n^{-1}$ ?

✅ Correct! Since $F_n^H F_n = nI$ , the inverse is $\frac{1}{n}F_n^H$ .

❌ Close, but missing the scale factor. Each column has squared length $n$ , not 1, so we need the $1/n$ factor.

❌ Not quite. The key relation is $F_n^H F_n = nI$ . Solve for $F_n^{-1}$ .

Show solution

Solution:

The columns of $F_n$ are mutually orthogonal under the Hermitian inner product, and each has squared length $n$ (since $|w^{kj}|^2 = 1$ for each of the $n$ entries).

Therefore: $F_n^H F_n = nI \implies F_n^{-1} = \frac{1}{n} F_n^H$

This is why the inverse Discrete Fourier Transform is essentially the same as the forward DFT — just conjugate and divide by $n$ . No Gaussian elimination needed. This same orthogonality powers the Fast Fourier Transform, JPEG compression, and PDE solvers.

Solved: 0 / 4