An $O(n)$ algorithm to FFT-evaluate an FFT evaluation This question is from a practice exam in my algorithms class. I'm posting the question and the answer listed in that practice exam:


  Let $W$ be an $n\times n$ matrix whose $(i,j)$-th entry is $\omega_n^{ij}$, where $\omega_n$ is a principal $n$th root of unity. Let $X=(X_0,\dots,X_{n-1})$ be an $n$-vector. The product $W \times X$ can be computed in $O(n\log n)$ time. Let $FFT(X)$ denote the vector that results by applying the FFT evaluation algorithm to the vector $X$. 
  
  Describe an $O(n)$ algorithm to compute $FFT(FFT(x))$.
  
  Answer: $FFT(FFT(x))$ is $W^2\times X$
  $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, and $n$ otherwise.


I'm confused about everything:
1. How does this run in $O(n)$? To compute $(W^2)_{jk}$ I'm already  iterating through $n^2$ elements....
2. Why is $FFT(FFT(x)) = W^2\times X$?
3. Why is $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, $n$ otherwise?

I would appreciate an answer that isn't too advanced as my math skills are limited to basic undergrad math classes of an engineering major.
Let's answer your questions one by one.


You don't compute $W^2$ by squaring $W$ algorithmically. Rather, you compute $W^2$ "on paper", and you find out a formula for $W^2$. Given this formula, you can check that
$$ (W^2 X)_j = \sum_{k=0}^{n-1} (W^2)_{jk} X_k = nX_{-j}, $$
where $-j$ is the unique $k$ such that $j+k$ is a multiple of $n$. For example, if $n = 5$ then the correspondence between $j$ and $k$ is
$$
\begin{array}{c|c}
j &amp; k \\\hline 0 &amp; 0 \\ 1 &amp; 4 \\ 2 &amp; 3 \\ 3 &amp; 2 \\ 4 &amp; 1
\end{array}
$$
Let $Y = W^2X$. Then $Y_j = nX_{-j}$, and so we can compute $Y$ from $X$ in linear time $O(n)$.
Since $FFT(X) = W\times X$, $FFT(FFT(X)) = W\times FFT(X) = W \times (W \times X) = (W \times W) \times X = W^2 \times X$.
This is a calculation:
$$
\begin{align*}
W^2_{jk} &amp;= \sum_{i=0}^{n-1} W_{ji} W_{ik} \\ &amp;= \sum_{i=0}^{n-1} \omega_n^{ji} \omega_n^{ik} \\ &amp;= \sum_{i=0}^{n-1} \omega_n^{i(j+k)} \\ &amp;= \sum_{i=0}^{n-1} (\omega_n^{j+k})^i.
\end{align*}
$$
If $j+k$ is a multiple of $n$ then $\omega_n^{j+k} = 1$ and so
$$ W^2_{jk} = \sum_{i=0}^{n-1} 1^{j+k} = \sum_{i=0}^{n-1} 1 = n. $$
Otherwise, $\omega_n^{j+k} \neq 1$ and so we can use the formula for the sum of a geometric series to conclude
$$ W^2_{jk} = \sum_{i=0}^{n-1} (\omega_n^{j+k})^i = \frac{(\omega_n^{j+k})^n - 1}{\omega_n^{j+k} - 1} = 0 $$
since $\omega_n^{(j+k)n} = (\omega_n^n)^{j+k} = 1^{j+k} = 1$.