The Discrete Fourier Matrix as a Unitary Operator

The Fourier Matrix and Its Normalization

The discrete Fourier matrix changes a vector into a list of weighted sums of its coordinates. The weights are complex roots of unity, so the transformation records different oscillatory patterns in the original data. The normalization is essential: it makes the transformation preserve lengths and inner products, rather than changing their scale. We will verify this directly, then use the resulting identities to understand its action and its eigenvalues.

Work over \(\mathbb{C}\), and let \(N\in\mathbb{N}\). Set \(\omega_N=e^{2\pi i/N}\), so \(\omega_N^N=1\). Index the rows and columns from \(0\) to \(N-1\), and define the normalized discrete Fourier matrix \(\mathbf{F}_N\in\mathbb{C}^{N\times N}\) by

Here \(i^2=-1\). The conjugate transpose \(\mathbf{A}^*\) is obtained by transposing a matrix and taking the complex conjugate of every entry. A square complex matrix \(\mathbf{U}\) is unitary if \(\mathbf{U}^*\mathbf{U}=\mathbf{I}\). In this course the inner product is linear in its first slot: \(\langle\mathbf{x},\mathbf{y}\rangle=\sum_j x_j\overline{y_j}\). This convention matters when interpreting entries of a matrix product.

The key computation is the sum of powers of a root of unity. For any integer \(r\),

If \(N\) divides \(r\), then every term is \(1\). Otherwise \(z=\omega_N^r\ne1\), while \(z^N=1\), and the finite geometric sum is \((1-z^N)/(1-z)=0\). This also covers \(N=1\): the only possible index difference is \(0\), and the sum is \(1\).

Why the Columns Are Orthonormal

Proof. Let \(\mathbf{f}_k\) denote column \(k\) of \(\mathbf{F}_N\). The \((k,\ell)\)-entry of \(\mathbf{F}_N^*\mathbf{F}_N\) is

By the root-of-unity sum, this entry is \(1\) if \(N\) divides \(\ell-k\), and \(0\) otherwise. Since \(k,\ell\) are between \(0\) and \(N-1\), divisibility occurs exactly when \(k=\ell\). Thus \(\mathbf{F}_N^*\mathbf{F}_N=\mathbf{I}_N\), proving unitarity. Under the specified inner-product convention, the displayed entry is \(\langle\mathbf{f}_{\ell},\mathbf{f}_k\rangle\), not \(\langle\mathbf{f}_k,\mathbf{f}_{\ell}\rangle\); both are \(1\) when \(k=\ell\) and \(0\) otherwise. Therefore the columns are orthonormal. \(\square\)

For any complex matrix \(\mathbf{A}\) with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\), the same entry calculation gives \((\mathbf{A}^*\mathbf{A})_{k\ell}=\langle\mathbf{a}_{\ell},\mathbf{a}_k\rangle\) with this convention. In the Fourier case, the root-of-unity sum makes this product the identity. Because \(\mathbf{F}_N\) is square, one can also check \(\mathbf{F}_N\mathbf{F}_N^*=\mathbf{I}_N\) directly by the same sum over the column index. Consequently \(\mathbf{F}_N^{-1}=\mathbf{F}_N^*\): applying the conjugate transpose recovers the original vector.

Computing the Transform

If \(\mathbf{x}=(x_0,\dots,x_{N-1})^{\top}\), matrix multiplication gives the \(j\)-th output coordinate as

Thus each output coordinate is a particular weighted sum of all input coordinates. The zeroth output is especially simple: \((\mathbf{F}_N\mathbf{x})_0=N^{-1/2}\sum_k x_k\), since \(\omega_N^0=1\). The other rows use successive powers of the root of unity. Unitarity says that these changes of coordinates preserve inner products, including lengths, even though individual coordinates generally change.

Preservation of length provides another check. The input in this example has squared length \(1+1+1+0=3\). The output has squared length \((1+1+1+9)/4=3\), as unitarity requires.

Reversal Symmetry and Eigenvalues

The square of the Fourier matrix has a particularly simple action. Let \(\rho(j)\) be the unique index in \(\{0,\dots,N-1\}\) congruent to \(-j\) modulo \(N\). The index \(0\) stays fixed, and when \(N\) is even the index \(N/2\) is fixed as well, since \(-N/2\equiv N/2\pmod N\). All remaining indices are paired with their reversals.

Proof. By the definition of matrix multiplication, for each \(j\),

The inner sum is \(N\) exactly when \(N\) divides \(j+\ell\), and is \(0\) otherwise. Among the indices \(0,\dots,N-1\), exactly one \(\ell\) satisfies that divisibility condition: \(\ell=\rho(j)\). Hence the coordinate is \(x_{\rho(j)}\). Applying this reversal twice returns every coordinate to its original index, so \(\mathbf{F}_N^4\mathbf{x}=\mathbf{x}\) for every \(\mathbf{x}\), which proves \(\mathbf{F}_N^4=\mathbf{I}_N\). \(\square\)

Proof. By definition, an eigenvalue \(\lambda\) has a nonzero eigenvector \(\mathbf{v}\) such that \(\mathbf{F}_N\mathbf{v}=\lambda\mathbf{v}\). Since \(\mathbf{F}_N\) is unitary, it preserves lengths. Therefore \(\|\mathbf{v}\|=\|\mathbf{F}_N\mathbf{v}\|=\|\lambda\mathbf{v}\|=|\lambda|\|\mathbf{v}\|\). Because \(\mathbf{v}\ne\mathbf{0}\), its length is positive, and division gives \(|\lambda|=1\). Applying the fourth-power identity to \(\mathbf{v}\) also gives \(\mathbf{v}=\mathbf{F}_N^4\mathbf{v}=\lambda^4\mathbf{v}\). Since \(\mathbf{v}\ne\mathbf{0}\), this implies \(\lambda^4=1\). The complex solutions of this equation are \(1,-1,i,-i\). \(\square\)

This is a constraint, not a claim that all four values must occur for every \(N\). The order of the Fourier matrix and its eigenspaces determine which values actually appear. The calculation only requires that any eigenvalue it does have must satisfy both conditions.

Common Pitfall: Transpose Is Not Conjugate Transpose

For complex matrices, replacing \(\mathbf{F}_N^*\) by the ordinary transpose \(\mathbf{F}_N^{\top}\) loses the conjugation needed for unitarity. For example, in \(\mathbf{F}_4\), column \(1\) is \(\frac12(1,i,-1,-i)^{\top}\). Its ordinary bilinear self-product is

not \(1\). The incorrect calculation \(\mathbf{F}_4^{\top}\mathbf{F}_4=\mathbf{I}_4\) therefore fails even on a diagonal entry. With conjugation, the corresponding entry is \(\frac14(1+|i|^2+|-1|^2+|-i|^2)=1\), exactly as required. The conjugate transpose is essential because complex orthogonality uses conjugated coordinates.

The practical value of these identities is twofold. First, the Fourier matrix provides a reversible transform that preserves lengths and inner products, which makes it a natural change of coordinates for complex data. Second, its reversal-square identity gives eigenvalue information without needing to compute a characteristic polynomial. Whenever an eigenvector calculation is attempted, the modulus-one and fourth-root conditions provide immediate checks on a proposed eigenvalue.