title: Fast Fourier Transform using a Vandermonde Matrix - Evaluation of Co-efficients?
body: <p>Say i'm trying to evaluate the Polynomial:</p>
  
  <pre><code>x^2 + 1
  </code></pre>
  
  <p>Using the Fast Fourier transform method for evaluating co-efficients. Now i can change this into matrix/vector form using the co-effcient as inputs for the fast fourier transform:</p>
  
  <p>so:</p>
  
  <pre><code>x^2 + 1 = &lt;1, 0, 1, 0&gt;
  </code></pre>
  
  <p>This is done by using the coefficient value e.g 1 = 1, 0x^1 = 0, X^2 = 1 and so on</p>
  
  <p>Now we get to the bit where i'm totally confused. I'm meant to use the vandermonde matrix :<a href="http://en.wikipedia.org/wiki/Vandermonde_matrix" rel="nofollow noreferrer">Vandermonde matrix ~ Wiki</a> to evaluate these values into FFT Form using the matrix:</p>
  
  <pre><code>1 1 1 1  
  1 i-1-i
  1-1 1-i
  1-i 1 i
  </code></pre>
  
  <p>The output of</p>
  
  <pre><code>fft(1,0,1,0)
  </code></pre>
  
  <p>is</p>
  
  <pre><code>(2,0,2,0)
  </code></pre>
  
  <p>Now thats the step i don't quite understand, how did we use that matrix to get (2,0,2,0)?</p>