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.
$\endgroup$ 13 Answers
$\begingroup$Some references:
the videos of Gilbert Strang (MIT, around 1999) on this subject.
More far reaching:
etc.
$\endgroup$ 2 $\begingroup$The permutation matrix P for FFT of $F_8$ is $ P=\begin{bmatrix} 1&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&0&1&0\\ 0&1&0&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&0&1 \end{bmatrix} $
$\endgroup$ 1 $\begingroup$To see this thing "at work" and illustrate Florian's answer (+1), let me put in English what the $1$'s in each row are doing, perhaps by focusing on the first (in red), second (also in red) and fifth rows (in blue):
$$\bf P=\begin{bmatrix} \color{red}1&0&0&0&0&0&0&0\\ 0&0&\color{red}1&0&0&0&0&0\\ 0&0&0&0&\color{red}1&0&0&0\\ 0&0&0&0&0&0&\color{red}1&0\\ 0&\color{blue}1&0&0&0&0&0&0\\ 0&0&0&\color{blue}1&0&0&0&0\\ 0&0&0&0&0&\color{blue}1&0&0\\ 0&0&0&0&0&0&0&\color{blue}1 \end{bmatrix}$$
Say we multiply $\bf{Px},$ where $\bf x$ is a vector simply enumerating the integers $0,1,2,3,\dots,7,$ i.e. $\small\begin{bmatrix}0&1&2&3&4&5&6&7\end{bmatrix}^\top$ - in this case each integer representing the vector element order - then we can see that the first operation (in the typical mechanics of matrix multiplication) will be dotting the first row in the matrix $\bf P,$ i.e. $\small\begin{bmatrix} \color{red}1&0&0&0&0&0&0&0\end{bmatrix}$ with the vector $\bf x,$ which will select the first element (even) in the vector, i.e. $0.$ The next operation will dot the second row of the matrix $\bf P$ with the vector $\bf x,$ selecting its third element (even), i.e. $2.$ And so forth and so on, until we get to the fifth row, $\small\begin{bmatrix}0&\color{blue}1&0&0&0&0&0&0\end{bmatrix},$ which will start off the process of selecting the second element (odd) of the matrix, i.e. $1.$
Here it is:
> p = matrix(c( 1,rep(0,7),
+ rep(0,2),1,rep(0,5),
+ rep(0,4),1,rep(0,3),
+ rep(0,6),1,rep(0,1),
+ rep(0,1),1,rep(0,6),
+ rep(0,3),1,rep(0,4),
+ rep(0,5),1,rep(0,2),
+ rep(0,7),1 ),8,8,1)
> (v = c(0:7))
[1] 0 1 2 3 4 5 6 7 # Vector [0 1 2 3 4 5 6 7]
> as.vector(t(p %*% v))
[1] 0 2 4 6 1 3 5 7 # Vector [0 2 4 6 1 3 5 7] even / odd separated.So in the case of $\bf {F}_{64},$ for example, multiplying the signal in the original domain in a vector $\bf x,$ the $64^2$ elementary multiplications can reduced to $2\times 32^2$ by making the matrix sparse:
$$\begin{bmatrix}\bf F_{64}\end{bmatrix}=\color{gray}{\begin{bmatrix}\bf I& \bf D\\\bf I&\bf {-D}\end{bmatrix}}\begin{bmatrix}\bf F_{32}&0\\0&\bf F_{32}\end{bmatrix}\begin{bmatrix}\bf P_{64}\end{bmatrix}$$
with
$$\small \bf D = \begin{bmatrix} 1 &0&0&0&0&\cdots&0\\ 0 &w&0&0&0&\cdots&0\\ 0&0&w^2&0&0&\cdots&0\\ 0&0&0&w^3&0&\cdots&0\\ 0&0&0&0&w^4&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots\\ 0&0&0&0&0&\cdots&w^{31} \end{bmatrix}$$
This is explained here by Professor Strang.
$\endgroup$
