Why the columns of the Fast Fourier Transform are orthogonal

The Fast Fourier Transform is an algorithm based on a complex matrix, which we’ll call F. It’s defined as follows:

F=\begin{bmatrix}1 & 1 & 1 &\cdots & 1 \\1 & w & w^2 & \cdots & w^{n-1}\\1 & w^2 & w^4 & \cdots & w^{2(n-1)} \\\cdots & \cdots & \cdots & \cdots & \cdots\\1 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-1)^2}\end{bmatrix}

More briefly we have that element f_{ij} of F is equal to w^{ij}, with 0<=i,j<=n-1,
where w is the complex number: w=e^{i\frac{2\pi}{n}}.

We want to show why any column of F is orthogonal to any other.

Consider 2 generic columns: C_j and C_k of F, with j<k. The inner product between them is: <C_j, C_k>=\overline{C_j}^TC_k, where with \overline{C_j}^T we mean the transposed conjugate of C_j.

It can be developed as follows:

<C_j, C_k>=\sum_{h=0}^{n-1} \overline{w^{hj}}w^{hk}=\sum_{h=0}^{n-1} (\overline{w^j})^h(w^jw^{k-j})^h}=\sum_{h=0}^{n-1} (\overline{w^j})^h(w^j)^h(w^{k-j})^h}=\sum_{h=0}^{n-1} (w^{k-j})^h}

where (\overline{w^j})^h(w^j)^h = 1 because (w^j)^h 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:

<C_j, C_k>=\sum_{h=0}^{n-1} (e^{i\frac{2\pi(k-j)}{n}})^h}

Consider the set of the elements of that sum. What happens if we rotate each of them of an angle \frac{2\pi(k-j)}{n}? 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.

Leave a Reply

Your email address will not be published. Required fields are marked *