Root of Unity - Orthogonality

Orthogonality

From the summation formula follows an orthogonality relationship: for j = 1, ···, n and j ' = 1, ···, n

where is the Kronecker delta and z is any primitive nth root of unity.

The matrix whose th entry is

defines a discrete Fourier transform. Computing the inverse transformation using gaussian elimination requires O(n3) operations. However, it follows from the orthogonality that U is unitary. That is,

and thus the inverse of U is simply the complex conjugate. (This fact was first noted by Gauss when solving the problem of trigonometric interpolation). The straightforward application of U or its inverse to a given vector requires O(n2) operations. The fast Fourier transform algorithms reduces the number of operations further to O(n log n).