DFT as a change of basis

The discrete Fourier transform sounds analytic but is, at heart, a single change of basis. It rewrites a signal from the standard basis (one coordinate per time sample) into the Fourier basis (one coordinate per pure frequency). Same vector, new coordinates that reveal how much of each oscillation the signal contains.

Concretely the DFT is multiplication by a matrix F whose entries are roots of unity: F_jk = exp(-2 pi i j k / n). After scaling by 1/sqrt(n) this matrix is unitary, F^* F = I, so the transform is a rotation in complex space: it preserves lengths (Parseval's theorem) and is trivially invertible by its conjugate transpose. The columns of F are the Fourier basis vectors, mutually orthogonal pure frequencies.

Here is the punchline that ties it to eigentheory: the Fourier basis simultaneously diagonalizes every circulant matrix (matrices where each row is a cyclic shift of the one above, the matrix form of convolution). In other words, the Fourier vectors are the shared eigenvectors of all shift-invariant operations, which is exactly why convolution becomes simple multiplication in the frequency domain.

Why it matters: this single fact powers fast filtering, audio and image compression, and the spectral methods for differential equations, all made practical by the FFT, which computes F x in n log n time instead of n^2. The caveat: the DFT assumes the signal is periodic, so abrupt edges leak energy across frequencies (spectral leakage), usually tamed by windowing.