From a list to a grid
A digital image or a computed solution on a rectangular mesh is an array rather than a single list. Oscillation can occur in either coordinate, or in both at once. A two-dimensional discrete Fourier transform (DFT) describes the same finite array using waves on the grid. Its inverse recovers every entry in exact arithmetic: it does not, by itself, tell us what happened between grid points or outside the observed rectangle.
Let be positive integers and write for complex data with and . The first index labels rows and the second columns. Fix the following convention throughout.
Definition 2.6.1
(Two-dimensional DFT of an array)
The transform of is the array
The frequency indices are residues modulo and respectively.
The zero bin is , so the sample mean is . Some software normalizes the forward transform, or both directions, instead; compare the actual definitions before comparing numerical amplitudes.
Inversion and orthogonality
Theorem 2.6.2
(Inverse transform)
For every array above,
Proof
(Separate the two geometric sums)
Substitute the forward sum and interchange the finite sums. The coefficient of becomes
Each parenthesis is its length when the corresponding difference is divisible by that length, and is zero otherwise, by the finite geometric-sum identity. As and lie in their respective index ranges, both divisibility conditions hold exactly when and . Only that entry survives. This also works if either dimension is one.
The basis wave indexed by is . Its coefficient in the inverse is . Distinct index pairs in the prescribed ranges give orthogonal grid waves. The factor is the squared norm of each wave, and the waves form a basis of the -dimensional complex array space.
Separable computation
The exponential factors into a row-coordinate factor and a column-coordinate factor. First transform each row in the column direction:
The second step transforms each column of . Interchanging these finite sums shows that reversing the order gives the same . In matrix form this is a product with one-dimensional DFT matrices on each side, described below. This tensor-product structure is a computational statement, not an assumption that the data factors into a product of two one-dimensional arrays.
Directly evaluating all output bins from all inputs costs arithmetic operations. Separable direct transforms cost . When suitable one-dimensional FFT algorithms are used on both axes, their combined cost is typically for nontrivial dimensions; precise costs and storage depend on lengths and implementation. An FFT reorganizes the same finite transform, though floating-point results need not be exact.
Worked example 2.6.3
(A 2 by 2 array)
Take . A length-two DFT maps to . Transforming each row gives ; transforming each column gives
For instance, , measuring the signed row contrast, while measures column contrast. The inverse at is . The full inverse recovers the four original entries. Interchanging axis labels would interchange the two off-diagonal coefficients.
Worked example 2.6.4
(Shifting the 2 by 2 array)
Shift the rows of the same array circularly by , : . Row transforms give and , and column transforms then give
Since , the shift should multiply row of by , and indeed only changes sign. Every magnitude is unchanged: a circular shift is invisible in and is carried entirely by phases. The last exercise below proves the general rule.
Counterexample mode
Equal magnitudes do not force a shift
Claim: if for every bin, then is a circular shift of . On a grid let have first row and have first row , both with zero second row. Then
so both spectra have magnitudes in each row. Yet the four column shifts of are , , , , and a row shift would move the nonzero row; is none of these. Equal magnitudes say only that ; shifts are exactly the phases linear in , .
Energy, symmetry and the meaning of bins
Theorem 2.6.5
(Discrete Parseval identity)
With the convention above, .
Proof
(Expand the squared modulus)
Insert the inverse expansion into the left side and expand its squared modulus. Orthogonality in each coordinate eliminates cross terms between distinct frequency pairs. Each surviving basis wave has squared norm , leaving times the sum of squared coefficient magnitudes. The factor would change under another normalization.
Concept lensAlgebraic
The transform as a matrix sandwich
Let be the matrix with entries , and similarly . Both are symmetric, and the one-dimensional geometric-sum identity says . The definition then reads ; the transpose does not conjugate entries. Inversion becomes the matrix identity , and since and are unitary, the Frobenius norm satisfies , which is Parseval. Stacking the columns of into one vector turns the same map into multiplication by the Kronecker product , which is why separable evaluation is exact rather than approximate.
If is real, conjugating the forward formula gives a symmetry of the spectrum.
Theorem 2.6.6
(Conjugate symmetry for real data)
If every is real, then for all
Proof
(Conjugate the forward sum)
Since , conjugating the definition replaces each exponent by . The exponential depends on only modulo , so the result is the transform at .
A bin is necessarily real when it is its own partner in both coordinates. For example, coordinate zero is self-paired, as is the halfway index in an even-length dimension. All other bins occur in conjugate pairs.
Common mistake
(Changing the sign of only one frequency)
Both coordinates change sign together; changing only one need not give the conjugate. For the real array with a single at , . The partner of is , and . But , which is not .
Common mistake
(Real input does not make every coefficient real)
Only self-paired bins are forced to be real. The array has .
Worked example 2.6.7
(Self-paired bins on a 2 by 4 grid)
Let have first row and second row zero. Then for . With both row indices are self-paired, and with the column indices and are, so the four bins with must be real: they equal and . The remaining bins pair as , and indeed . Counting real parameters, four real bins and two conjugate pairs give , matching the eight real entries of .
An upper index such as can represent frequency because these give identical grid samples. If row spacing is , a representative has physical frequency cycles per unit in that coordinate; similarly for columns. Even-length halfway bins have positive and negative representatives that coincide on the grid, so an interpretation must choose a convention. A display may shift the zero bin to the center, but that is a permutation of the spectrum, not a different transform. A transposed image convention may also swap displayed axes; record which index corresponds to which physical direction.
What the grid cannot tell us
For integer , replacing a wave's frequencies by changes neither its grid samples nor its DFT. Thus different continuous waves can have identical data; no transform can distinguish them without extra assumptions. A rectangular crop is treated as one period of a periodic array. An edge mismatch can spread energy over bins, and multiplication by a window changes amplitudes as well as leakage. Padding supplies additional zeros, not new measurements; it changes the array and its frequency grid. When using spectral multiplication for convolution, periodic wraparound occurs unless padding and boundary conventions are chosen for the intended linear operation.
Exercises with solutions
Quick check
(Find the transform of a constant array .)
Each coordinate sum is a geometric sum.
Solution · Answer
Each coordinate sum is zero outside its zero residue. Hence and every other bin is zero. The inverse returns at every point.
Quick check
(On a grid, let . Find its nonzero bin.)
The array is a product of a row factor and a column factor.
Solution · Answer
The row sum is , equal to for and zero for . The column sum is at and zero otherwise. Thus and all other bins vanish. Its inverse coefficient is .
Quick check
(Verify Parseval for the example and explain why summing spectral squares without normalization is wrong here.)
Compare both sums with the factor .
Solution · Answer
The sample energy is . The spectral sum is ; division by gives . The forward transform is not unitary under the selected convention.
Quick check
(Suppose for integers . Relate its transform to .)
Substitute shifted summation indices.
Solution · Answer
Substitute , modulo the respective lengths. These substitutions permute the summation indices, and the exponential separates, yielding . The phase changes but the magnitude does not. Therefore magnitude alone cannot locate an array: any nontrivial circular shift has the same spectrum magnitude.