Given: $$F_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)}\\ \end{bmatrix}, $$
where $D = $ diag($1,\omega,\omega^2,...,\omega^N$). We note that $\omega^N = 1$, so $\omega^{N/2} = -1 $.
What is meant by odd-even permutation in this context?
Available notes on FFT online are generally highly condensed, thus they are very difficult to decipher. Using $F_4$ as a template, i've found that permutation matrices $P$ such that $P F$ is row sorted into odd powers of $\omega$ and then even powers of $\omega$, and visa versa, don't ostensibly work.
I additionally am not sure how you can convert the consecutive $F_{N/2}$ matrices on the top of the second matrix into rows that span to all necessary powers of $\omega$.
Thank you.
Some references:
the videos of Gilbert Strang (MIT, around 1999) on this subject.
https://math.berkeley.edu/~berlek/classes/CLASS.110/LECTURES/FFT
https://www.ma.utexas.edu/users/gilbert/REU/REUNewApp2Sum06.pdf
More far reaching:
http://www.cs.cornell.edu/~bindel/class/cs5220-s10/slides/fft.pdf
etc.