How do I fill in the FFT matrix for the nth roots of unity, for example n = 8

Question

I can do this for n=4, $w_4^0 = 1$ $w_4^1 = i$, $w_4^2=-1$, $w_4^3=-i$ but then anything in between my best guess is that I have to find the Cartesian coordinates? Which already does not make sense to me as I'm saying it because that implies two numbers and not one.

But I looked around and saw an equation like $cos(theta) + i sin(theta)$

This is for an algorithms class FFT for polynomial multiplication but in exams, I'd have to do it by hand so I want to use matrices rather than divide every polynomial into A_even and A_odd and recurse.

Sorry but I have no clue how to write a matrix in MathJax.

n = 4 has a matrix like this

[1 1 1 1] [1 -i -1 i] [1 -1 1 -1] [1 i -1 -i]

What does the n=8 matrix look like?

Answer 1

The standard primitive eighth root of unity is the complex number $\frac{\sqrt 2}2+i\frac{\sqrt 2}2$. You can find all other eighth roots of unity by rasing this to a power. Note that its square is simply $i$.