A computer receives a finite list, while a periodic function has infinitely many Fourier coefficients. The discrete Fourier transform (DFT) is an exact change of coordinates for the list. It does not automatically recover all coefficients of the function that produced the list: frequencies differing by a multiple of the sample count are indistinguishable on the grid.
We first prove the finite algebra with a fixed normalization. Then we derive a fast factorization and an aliasing formula under a hypothesis that permits sampling the continuous Fourier series. The real-line bandlimited sampling theorem is a different setting; here every frequency is an integer and indices are taken modulo the finite sample count.
Finite Fourier coordinates
Definition 1.11.1
(Discrete Fourier transform)
For set . For a vector , its discrete Fourier transform is the vector with
Indices are understood modulo when used outside this range.
The key finite orthogonality identity is
For unequal residues, the ratio is and the sum is ; for equal residues every term is one. The same identity holds when the summed index is named rather than .
Theorem 1.11.2
(DFT inversion, Parseval and circular convolution)
With the normalization above,
Define circular convolution by
Its DFT is the pointwise product .
Proof
(Orthogonality and periodicity of the exponentials)
Substitution and finite rearrangement give . Similarly . Thus the DFT matrix divided by is unitary.
For convolution, put modulo and rearrange the finite sums:
Proof X-ray
Where each identity comes from
Inversion and Parseval each use the orthogonality relation (1) once, summed over the frequency index : for inversion the exponent difference is , for Parseval it is . In both cases only the diagonal terms survive, each contributing , which the factor cancels.
The convolution identity does not use orthogonality at all. Its key move is the reindexing modulo , which is legitimate only because depends on modulo : gives even when . This is exactly where the convolution must be circular; an ordinary convolution would place the wrapped terms at the wrong index. All sums are finite, so every rearrangement is free. The aliasing proof below differs precisely there, since substituting an infinite series into the DFT sum requires absolute convergence.
The appears in the inverse and Parseval formulas, not in this definition of convolution. A unitary normalization, dividing the transform by , would distribute the factors differently and introduce into the convolution identity.
Concept lensAlgebraic
Circulant matrices are diagonalized by the DFT
Convolution with a fixed is the linear map given by the circulant matrix . For each put . Substituting modulo ,
So the vectors , which are orthogonal by (1), are common eigenvectors of every circulant matrix, with eigenvalues . The convolution theorem is the statement that the DFT is the change of basis to these eigenvectors: in the new coordinates convolution becomes multiplication by a diagonal matrix.
A radix-two factorization
Let . Split the data into even and odd indices, and form the length- transforms
For ,
Indeed and . Also and , while replacing by reverses the odd prefactor. When , apply the same split recursively until length one. With and twiddle factors precomputed or counted in the linear work per level, the arithmetic count satisfies , hence complex operations, compared with for evaluating every sum directly. This counts arithmetic operations under the usual model; it is not a rounding-error guarantee.
Worked example 1.11.3
(A four-point transform)
For and ,
For example, the even subsequence has transform , and the odd subsequence has transform . Formula (2) gives , , and , . Parseval checks the scaling: and .
Worked example 1.11.4
(Circular versus ordinary convolution)
With and , circular convolution is . It agrees here with the ordinary finite convolution because its support fits without wrapping. By contrast, convolving with circularly gives : index wraps to zero modulo four.
More generally, sequences of lengths and , padded with zeros to length , have circular convolution equal to their ordinary linear convolution in indices , followed by zeros: each nonzero index sum is at most , so none wraps. Without enough padding, terms whose indices differ by are added together.
Sampling a periodic Fourier series
Let be a continuous -periodic function whose actual Fourier coefficients are absolutely summable, so that
Its Fourier series converges uniformly, and Fourier uniqueness identifies the sum with . Sample and let be times the DFT of . A signed frequency is compared with bin ; bins above can represent negative frequencies.
Theorem 1.11.5
(Exact aliasing formula)
For every integer ,
In particular, if is a trigonometric polynomial supported in and , each such coefficient is recovered as for . At the two endpoint frequencies and collide.
Proof
(Sampling identifies residue classes)
Absolute uniform convergence permits substitution of the Fourier series into the finite DFT sum:
The inner sum is one when and zero otherwise, by (1). This proves (3). If and , the nonzero difference has absolute value below , so two different supported frequencies cannot share a residue. When , , so that conclusion fails.
A useful quantitative version follows from (3). If for some , the coefficients are absolutely summable; for a signed representative ,
Indeed for . The finite constant depends on , and this is an absolute error bound. Near , an aliased coefficient can be of the same order as the target; even away from that region, no relative accuracy follows without a lower bound on the target coefficient. It does not reconstruct frequencies absent from the samples without a prior assumption.
Worked example 1.11.6
(A high frequency masquerades as a low one)
Sample at eight equally spaced points. Since , the sampled values of equal those of . The data are also produced by , although between samples. The DFT cannot distinguish these functions without additional information about their frequencies.
The explorer below lets you choose the sample count and up to four terms, and compares the exact prediction with a direct DFT, together with the alias that has the same samples.
Counterexample mode
A boundary frequency can disappear on the grid
For even , the nonzero function satisfies
for every sample. Its entire sample vector and DFT coincide with those of the zero function. The modes and are distinct continuous frequencies but the same residue modulo . If a trigonometric polynomial is supported in , its Nyquist bin is . In particular samples to , while the sine part disappears. Assigning that single bin to two endpoint frequencies requires an additional convention. The strict inequality cannot be replaced by .
An arbitrary equivalence class cannot be sampled at prescribed points: changing its values on the finite grid changes the samples but not its Fourier coefficients. Absolute coefficient summability is a convenient sufficient condition for (3), not a claim that it is necessary in every possible formulation.
Common mistakes
Common mistake
(Reading a bin above as a high frequency)
Sample at points. By (3), and every other bin is zero. Reading bin as the frequency suggests , which has the same samples, since , but oscillates seven times per period between them. A bin determines a residue class modulo , not a frequency. The usual convention picks the representative with ; this is an assumption about the data, and at even that convention is ambiguous.
Common mistake
(Comparing the unnormalized DFT with Fourier coefficients)
The aliasing formula (3) is stated for , not for . For the constant function , the samples are all one, so while . Omitting the factor makes every recovered coefficient times too large; with a unitary normalization the factor is instead, and it must be tracked in the same way.
Exercises
Quick check
(Compute the four-point DFT of and verify Parseval.)
Solution · Answer
, so . Both sides of Parseval equal two: .
Quick check
(Compute the circular convolution of with itself at length four. Compare it with the ordinary convolution after padding the effective length-three lists to length five.)
Solution · Answer
The ordinary convolution is . At length four its indices zero and four combine, giving . Padding the effective length-three lists to length five gives without wraparound.
Quick check
(For sampled at eight points, find the two nonzero normalized DFT coefficients for .)
Solution · Answer
. Modulo eight these frequencies are and , so and the other vanish.
Quick check
(Let . What is the smallest integer satisfying the sufficient no-collision condition with ? Why is this a sufficient condition rather than a claim that every smaller grid must fail for this particular function?)
Solution · Answer
The sufficient condition is , so the smallest integer is seven. It guarantees distinct residues for every frequency in . If the support is known, and also give three distinct residues. For , the sampled sine vanishes, so the data coincide with those of the constant . Without a support restriction, even the smaller noncolliding grids do not give general uniqueness.