An $O(n)$ algorithm to FFT-evaluate an FFT evaluation
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$.