What does the inverse FFT matrix look like without using negative powers

354 Views Asked by At

Edit: I know screen readers can't read images but I think this image adds more context regarding my notation which @Ian clarifies in the comments.

myImage This is from the Graduate Algorithms course on Udacity with Georgia Tech using FFT for polynomial multiplication.

First row is all 1's. Second row is $1, W_n^{-1}$, ... $W_n^{-(n-1)}$ that can be rewritten not using negative powers as $1, W_n^{n-1}, W_n^{n-2},...,W_n^1$ The third row I can start but not finish: $1, W_n^{n-2}, W_n^{n-4},...,$

The last term in the third row with negative exponents is $W_n^{-2(n-1)}$ so I tried to use my limited algebra skills in figuring out what multiplied by $W_n^{2(n-1)}$ would equal $W_n^n = W_n^0$?

I let $2(n-1) + x = n$ and got $x = -n +2$ so I have for that last term in the third row, $W_n^{-2n+2}$ which can be rewritten as $W_n^{-2(n+1)}$ but I cannot visualize where this Omega would be on the unit circle on the complex plane where as for the second row I can clearly see that it starts at the last Omega and goes around clock-wise.

1

There are 1 best solutions below

1
On

I followed @Ian's advice and tried for $n=8$

The last element of row 3 is $W_8^{2(8-1)}$ which is $W_8^{14}$ which on the unit circle on the complex plane is at $-i$ or in polar coordinates $(1, 6pi/4)$. Multiply this by $(1, 8pi/4)$ since $W_8^8$ is at 1 or $(1, 2pi)$ which gives me $(1, 14pi/4)$ which is at positive $i$. So the final term of the row 3 can be rewritten as $W_n^2$.