3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Let's answer your questions one by one.

  1. 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 & k \\\hline 0 & 0 \\ 1 & 4 \\ 2 & 3 \\ 3 & 2 \\ 4 & 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)$.

  2. 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$.

  3. This is a calculation: $$ \begin{align*} W^2_{jk} &= \sum_{i=0}^{n-1} W_{ji} W_{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{ji} \omega_n^{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{i(j+k)} \\ &= \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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.