1.2 Fourier conventions and the finite proof chain
On this page · Permalink · Source line 103
Let \(q\) be a positive integer. Write \(I_q=\{0,1,\ldots,q-1\}\), interpreting indices modulo \(q\), and put
A signal is a vector \(x:I_q\to\mathbb C\). We write \(\operatorname{Id}_q\) for the identity matrix of dimension \(q\), and \(I\) for an identity matrix when its dimension is clear. Our inner product is conjugate-linear in the first argument:
The unscaled negative-sign discrete Fourier transform is
The positive-sign normalized Fourier matrix is
Thus \(F_q\) synthesizes a signal from normalized frequency coordinates, while \(F_q^\dagger x=\widehat{x}/\sqrt q\) analyzes it. This convention explains all signs and all square-root factors below. The negative-sign transform and the positive-sign synthesis are adjoints of one another.
Theorem QA01: The order of a finite phase
For \(a\in I_q\), the multiplicative order of \(\zeta_q^a\) is
Proof
The equation \((\zeta_q^a)^t=1\) holds exactly when \(q\) divides \(at\). Write \(g=\gcd(a,q)\), \(q=gq'\), and \(a=ga'\), with \(\gcd(a',q')=1\). The divisibility condition is \(q'\mid a't\), which is equivalent to \(q'\mid t\). Its smallest positive solution is \(t=q'\). This includes \(a=0\): then \(g=q\) and the order is one. \(\square\)
Theorem QA02: Character orthogonality
For any integer \(h\),
Proof
If \(q\mid h\), every summand is one. Otherwise \(r=\zeta_q^h\ne1\) and \(r^q=1\). Multiplying the sum by \(1-r\) gives \(1-r^q=0\), so the sum is zero. This argument also covers \(q=1\), where only the first case occurs. \(\square\)
Theorem QA03: Unitarity, inversion, and Parseval
For every positive \(q\),
Consequently,
Proof
The \((a,b)\) entry of the first matrix product is
By QA02 it is one when \(a=b\) and zero otherwise. The \((n,m)\) entry of the second product is the same orthogonality sum with indices interchanged. Since \(F_q^\dagger x=\widehat{x}/\sqrt q\), the identity \(F_qF_q^\dagger x=x\) is the displayed inverse formula. Finally, a unitary matrix preserves inner products:
Replacing \(F_q^\dagger x\) by \(\widehat{x}/\sqrt q\) proves Parseval. \(\square\)
These proofs use finite sums, ordinary complex multiplication, and the positive real square root of \(q\). No asymptotic approximation enters. At \(q=1\) the Fourier matrix is the one-by-one identity, and all identities have their literal scalar meanings.