Deriving the discrete Fourier transform

Source: The Discrete Fourier Transform: Most Important Algorithm Ever?, Reducible, 29:23, uploaded 2023-01-23.

The video derives the DFT by deliberately inventing a plausible but broken cosine transform, testing it, finding its phase failure, and repairing it with sine, complex numbers, and the unit circle. The result is a change of basis: project a finite sequence onto discrete complex sinusoids, and the resulting coordinates describe frequency and phase.

Why a frequency representation is useful

A chord can be drawn as amplitude over time or described by its component notes. Both representations contain the same signal, but the second makes an equaliser possible: reduce or increase selected frequency regions rather than editing each time sample. The DFT is the finite computational bridge between those views.

From samples to analysis frequencies

Computers cannot hold a value for every real-valued instant, so a continuous signal becomes a uniformly sampled sequence. The video tests a 7 Hz cosine. Seven samples can accidentally land on every peak and look constant. Fourteen can also align pathologically. More than twice the highest frequency is required; fifteen uniform samples guarantee representation of the 7 Hz component under the stated assumptions.

This is the Shannon–Nyquist condition. For $N$ samples across the chosen interval, frequencies at or above $N/2$ cannot be uniquely represented. A 44.1 kHz audio rate is consequently sufficient for the conventional human-audible range below roughly 20 kHz, provided out-of-band energy is removed before sampling.

The samples form a vector. The desired output is another representation in which a pure 2 Hz cosine creates a strong value at 2 Hz and zero at unrelated frequencies. That makes the unknown operation a similarity measure.

Similarity as projection

A dot product supplies the first candidate. Sample a cosine at the same times as the signal and take their dot product. Matching waves align and reinforce. Most arbitrary frequencies leave a nonzero residue, but waves completing an integer number of cycles within the window cancel cleanly. Those integer-cycle waves become the analysis frequencies.

Placing the sampled analysis waves in matrix rows computes every comparison through one matrix–vector product. The desired matrix must satisfy three properties:

1. A matching frequency produces a nonzero coefficient.
2. Different analysis frequencies are orthogonal and produce zero.
3. The transform is invertible, so the samples can be recovered.

Invertibility also explains why $N$ time samples need $N$ basis coordinates.

The deliberately fake Fourier transform

The cosine matrix almost works and exposes two problems. First, frequencies above the Nyquist boundary produce identical sample patterns. Rows repeat, so the matrix is neither orthogonal nor invertible. Displaying only the first half avoids showing some redundancy but does not repair the transform.

The video continues anyway because a wrong design can reveal its missing requirement. With sixteen samples, the cosine transform correctly tracks amplitude, moves its peak when frequency changes, captures a vertical offset at zero frequency, and handles sums because matrix multiplication is linear.

It fails on sine. A sine and cosine of the same frequency are orthogonal, so a pure sine appears to contain no frequency at all. More generally, shifting a cosine’s phase changes the reported strength even though its frequency and amplitude have not changed.

Repairing phase with two coordinates

A second matrix of sine analysis waves solves the complementary cases and breaks the cosine cases. Used together, the cosine dot product becomes one coordinate and the sine dot product another. As the input phase moves, the coordinate pair traces a circle: one component falls as the other rises.

The radius remains constant, so its magnitude measures frequency strength independently of phase. The angle around the circle records the phase that the failed transform discarded.

Computing two real matrices and manually joining every coordinate pair is cumbersome. A point on the unit circle is naturally one complex number whose real part is cosine and imaginary part is sine. Euler’s formula combines them:

For ten samples, analysis frequency zero repeats one point on the circle; frequency one makes one circuit; frequency two makes two circuits; and so on. Each DFT row samples the unit circle at the angular rate of its analysis frequency.

The resulting DFT

The analysis equation is

The matrix of these complex exponentials is orthogonal up to normalisation and therefore meets the original requirements. The magnitude of $X[k]$ describes how strongly frequency bin $k$ is present; its angle describes phase. Varying the input phase leaves the magnitude peak fixed while rotating that coefficient in the complex plane.

For a real cosine, the full DFT still contains two peaks. One complex exponential rotates in the positive-frequency direction and the other in the negative direction. Their imaginary parts cancel, producing the real-valued wave. This conjugate symmetry extends to every real input.

The inverse DFT reconstructs the samples:

The direct implementation is a matrix–vector product. The FFT computes the same coefficients by exploiting structure; it is not a different frequency transform.

Practical consequences beyond the derivation

• The DFT matrix contains mutually orthogonal complex sinusoidal basis vectors.
• A real-valued input produces a conjugate-symmetric spectrum.
• A discontinuity between the last and first sample creates leakage because the DFT treats the window as one period.
• Zero padding samples the same spectrum more densely but adds no frequency information.

The last two consequences are standard DFT implications rather than movements developed in detail by this video. The video’s distinctive contribution is the failure-driven route from cosine similarity to a phase-complete complex basis.

Further reading / references

• Brian McFee, Digital Signals Theory, introduction to the DFT.
• Brian McFee, Shannon–Nyquist sampling.
• 3Blue1Brown, Fourier transform intuition.