Proof that polynomial evaluated at roots of unity is DFT [closed]

Question

Hello All,

I hope I am not abusing the forum here.

I am just trying to understand the efficient implementations of the fast fourier transform. My reading and searching has led me to understand that evaluating a n degree polynomial at the $n^{th}$ roots of unity will lead to the discrete fourier transform.

That is, evaluating '$p(x) = a_o + a_1x + a_2x^2+... $' at the N roots of unity '$\omega_N^n $' will lead to a N element vector $\chi = p(\omega_N^0), p(\omega_N^1), .. p(\omega_N^{N-1})$ which is the DFT of $p$.

I have tried to derive this relationship starting at the definition of the DFT: $\chi_n = \Sigma_{k=0}^{N-1} x_k \omega_N^{kn}$, but I have not been able to extract the stated result.

All the reading I have done so far, mainly in computer science sources, states this as fact without any proof.

Can anybody point out what I am missing, or point me in the direction of a proof or full description?

Thanks,

Answer 1

You can look at my linear algebra lecture notes http://www.math.purdue.edu/~eremenko/dvi/fft2.pdf and .../fft.pdf

Answer 2

Well, there isn't much to derive, if we identify the polynomial $f(x)=\Sigma_{i=0}^{n-1}f_ix^i \in R[x]$ of degree less than $n$ with its coefficient vector $(f_0,f_1,\dots,f_{n-1})\in R^n$, then its DFT is defined as the linear map $DFT:R^n\to R^n$, $(f_0,\dots,f_{n-1})\mapsto\left(f(1),f(\omega),f(\omega^2),\dots,f(\omega^{n-1})\right)$.

So, if we evaluate $f$ at $\omega^k$, we get $f(\omega^k)=\Sigma_{i=0}^{n-1}f_i(\omega^k)^i$.

In your notation $a_i$ should corresponds to $x_i$.