The Fast Fourier Transform is an algorithm based on a complex matrix, which we’ll call F. It’s defined as follows:
More briefly we have that element of is equal to , with ,
where is the complex number: .
We want to show why any column of is orthogonal to any other.
Consider 2 generic columns: and of , with . The inner product between them is: , where with we mean the transposed conjugate of .
It can be developed as follows:
where because has amplitude 1 and if multiplied for its conjugate the result is its amplitude squared, so 1.
We can rewrite the last sum as follows:
Consider the set of the elements of that sum. What happens if we rotate each of them of an angle ? Does the set change? It’s simple to see that it doesn’t! The first becomes the the second, the second becomes the third and so on until the last that becomes the first. Hence also the sum result does not change. But the only complex number that does not change after a rotation is 0.