Try
Four recorded values are x=(1,2,0,−1). We will represent this same four-dimensional vector by weighted circular patterns. This is a finite change of coordinates: it does not add observations or recover information that was never measured.
Recall i²=−1. A quarter-turn clockwise multiplies a complex number by −i, whose successive powers are 1,−i,−1,i, then 1 again. Use these four points on the unit circle as exact weights. For frequency index k=0,1,2,3, multiply coordinate j by (−i)^(j k) and add. The resulting vector is
X=(2,1−3i,0,1+3i).
For instance X₁=1+2(−i)+0(−1)+(−1)i=1−3i. The zero-frequency value X₀=2 is simply the sum of the four inputs. Its value divided by 4 is their mean, 1/2. The complex outputs encode two real quantities each, but for real input the outputs are linked; there are still only four independent real input coordinates.
Predict
Predict whether the transform preserves the sum of squared magnitudes as written. The input has squared norm 1+4+0+1=6. The output has squared norm 4+10+0+10=24. No energy disappeared: this convention scales squared norm by the vector length, 4. Dividing the forward transform by √4 would remove that scaling.
Also predict whether real input forces real output. Our example already disproves this. Instead X₁ and X₃ are conjugates: they have equal real parts and opposite imaginary parts. X₀ and X₂ are real. We will prove this pattern for arbitrary length and explain why odd lengths have only one self-paired frequency.
Experiment
Reproduce the four transforms by multiplying the input against each row of this exact table. Each row is a circular pattern at a different frequency. The rows and columns are indexed starting at zero, not one.
| k | Weights for j=0,1,2,3 | Weighted sum Xₖ | Squared magnitude |
|---|
| 0 | 1, 1, 1, 1 | 2 | 4 |
|---|
| 1 | 1, −i, −1, i | 1−3i | 10 |
|---|
| 2 | 1, −1, 1, −1 | 0 | 0 |
|---|
| 3 | 1, i, −1, −i | 1+3i | 10 |
|---|
Now reconstruct coordinate j=1. Reverse the root’s direction, using powers of i, and divide the weighted sum by 4:
x₁ = [2+i(1−3i)+(−1)·0+(−i)(1+3i)]/4 = 8/4 = 2.
Check the other coordinates yourself: their inverse numerators are 4,0,−4 for j=0,2,3. Change the input to (2,−1,1,0), recompute the table, and retain both the forward coefficients and the reconstructed input. This asymmetric check is more informative than a constant vector, which can conceal a reversed sign.
Understand
Fix a positive integer n. Both coordinate and frequency indices run from 0 to n−1. Let ω=exp(−2πi/n), a clockwise unit-circle step; equivalently ω=cos(2π/n)−i sin(2π/n). The conjugate ω̄ is its inverse, since |ω|=1. Integer powers repeat modulo n. More precisely ω^q=1 exactly when the integer q is divisible by n. This last property makes ω a primitive n-th root of unity.
The forward finite Fourier transform is Xₖ=Σⱼ xⱼω^(j k). The n×n matrix F has row k, column j equal to ω^(j k), so X=Fx. Its adjoint F∗ is its conjugate transpose. We will prove, rather than assume, the inverse formula xⱼ=(1/n)ΣₖXₖω̄^(j k).
One geometric sum supplies the inverse
For any integer q, define S(q)=Σ from j=0 to n−1 of ω^(j q). If n divides q then every summand is 1 and S(q)=n. Otherwise put z=ω^q. Then z≠1 but zⁿ=1. Multiplying the finite sum by 1−z cancels all intermediate powers and gives 1−zⁿ=0. Therefore S(q)=0. Division is justified precisely because z≠1. Negative q cause no problem, and for n=1 the sole summand is 1.
Now compute an entry of F∗F. At row j and column ℓ it is Σₖ ω̄^(j k)ω^(ℓ k)=S(ℓ−j). Within the chosen index range, n divides ℓ−j exactly when j=ℓ. Thus F∗F=nI, where I is the identity matrix. The same entry calculation gives FF∗=nI. Hence F⁻¹=F∗/n, proving the inverse formula and ensuring every complex coefficient vector corresponds to exactly one input vector.
Merely choosing some root with ωⁿ=1 is not enough. At n=4, the choice −1 has order 2, and columns 0 and 2 of its proposed Fourier matrix coincide. That matrix loses information. The primitive-root condition is the reason the orthogonality argument works.
Basis vectors, normalization and energy
Define vₖ by (vₖ)ⱼ=ω̄^(j k)/√n. These are inverse-pattern columns. For coordinate calculations use the scalar vₖ∗x, the conjugate transpose of vₖ times x; this explicitly fixes the convention regardless of which argument an abstract inner-product notation makes linear. The same geometric sum proves vₖ∗vₗ equals 1 when k=ℓ and 0 otherwise. There are n such orthonormal vectors in Cⁿ. They are independent, since taking an inner product against each one forces all coefficients of a zero combination to vanish; n independent vectors span this n-dimensional space.
The coefficient of x along vₖ is vₖ∗x=Xₖ/√n. Therefore the inverse transform is a basis expansion. The normalized forward matrix U=F/√n obeys U∗U=UU∗=I, so it is unitary. The letter U here denotes the normalized Fourier matrix, not an upper triangular elimination factor.
For any two vectors x and y, (Fx)∗(Fy)=x∗F∗Fy=n x∗y. Setting y=x gives Σⱼ|xⱼ|²=(1/n)Σₖ|Xₖ|², the finite Parseval identity. Squared magnitude means conjugate times the number, not its ordinary square. In particular (1−3i)² is not the energy contribution of that coefficient; |1−3i|²=10 is.
This identity also certifies a deliberate approximation. Keep only a subset S of coefficients, setting the others to zero, and reconstruct y. In the orthonormal basis the removed component has squared norm (1/n)Σ over k outside S of |Xₖ|². Any other vector in the span of the retained patterns adds an orthogonal in-span error. The Pythagorean identity therefore makes y the unique closest vector in that span. This is an exact finite-dimensional statement about selected modes, not a claim that those modes best represent an unknown physical signal.
What real input forces
If every xⱼ is real, conjugating the forward sum gives X̄ₖ=Σⱼxⱼω̄^(j k)=X at index (−k modulo n). Conversely suppose these coefficient equalities hold. Conjugate the inverse expression: x̄ⱼ=(1/n)ΣₖX̄ₖω^(j k). Replace X̄ₖ by X at −k and reindex ℓ=−k modulo n. The result is (1/n)ΣₗXₗω̄^(j ℓ)=xⱼ. Thus every input coordinate is real. This proves necessity and sufficiency, not just a pattern in one table.
A mode pairs with itself exactly when 2k=0 modulo n. Index 0 always does; its coefficient is the real coordinate sum, often called DC. If n is even, index n/2 also does and its weights are (−1)ʲ, so this coefficient is real too; it is the alternating or Nyquist mode. If n is odd there is no second self-paired index. All other modes come in two-element conjugate pairs. At n=1 only DC exists; at n=2 both modes are self-paired. Selecting whole conjugate pairs, with either self-paired mode optional, preserves real reconstruction. Selecting only one member generally does not.
Apply
For the changed four-point input (2,−1,1,0), independently compute the transform and reconstruct it. Then retain only frequencies 0 and 2. Predict whether the result remains real and calculate the exact squared error without subtracting all four coordinates.
Review the changed reconstruction and energy
The transform is (2,1+i,4,1−i). Keeping indices 0 and 2 reconstructs (3/2,−1/2,3/2,−1/2), a real vector since both retained modes are self-paired. The removed squared coefficient magnitudes total 2+2=4, so the squared error is 4/4=1. Direct coordinate differences are (1/2,−1/2,−1/2,1/2), confirming that total. The full output squared norm is 24 and the input squared norm is 6.
Repair a faulty inverse next. Expanding two forward transforms gives (F²x)ⱼ=ΣₗxₗΣₖω^(k(ℓ+j))=n x at index (−j modulo n). Therefore using F/n as the inverse reverses indices instead of recovering arbitrary input. At n=4, input (0,1,0,0) would return (0,0,0,1). A constant or reversal-symmetric test could miss this defect. Explain which test you would retain when implementing a transform.
Continue
The finite Fourier transform is an invertible coordinate change with a declared sign and scaling. Its unitary version preserves length exactly; its unnormalized version has the factor n in energy. Later finite computations can reuse these identities to verify convolution formulas and faster algorithms, but an algorithm’s speed does not change the transform’s mathematical definition.
Review complex arithmetic and conjugates or complex quotients and modulus if the circular weights need a refresher. This lesson concerns finite vectors only: continuous Fourier transforms, infinite series convergence and sampling assumptions require separate theorems.
