Fast Fourier Transform as Matrix Factorization

I'm given a vector of length 4 and three matrices that correspond to a Fast Fourier Transform, I'm not exactly sure which one, but I guess it's supposed to be the Cooley-Tukey algorithm.

Here is the matrix factorization:

$$ \left ( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right ) \left ( \begin{matrix} 1 & \epsilon^0 & 0 & 0 \\ 1 & \epsilon^2 & 0 & 0 \\ 0 & 0 & 1 & \epsilon \\ 0 & 0 & 1 & \epsilon^3 \end{matrix} \right ) \left ( \begin{matrix} 1 & 0 & \epsilon^0 & 0 \\ 0 & 1 & 0 & \epsilon^0 \\ 1 & 0 & \epsilon^2 & 0\\ 0 & 1 & 0 & \epsilon^2 \end{matrix} \right ) $$

, where $\epsilon = e^{\frac{-j2\pi }{N}}$.

Now I'm supposed to say which operations each matrix corresponds to.

I think what should be done using these matrix factorizations is executing the recursive steps of the cooley-tukey algorithm. So that the matrix on the right should correspond to the 2-DFT of the even and odd elements of the input vector. Then the matrix in the middle should correspond to the 4-DFT, once again splitting up the even and odd parts, where the input now is the result of the first matrix multiplication. And the matrix on the left makes sure the order of the transformed vector corresponds to that of the DFT result.

However, if I actually do a 2-DFT on an input $s = (s_1, s_2, s_3, s_4)$, I don't obtain the same result as when I do the matrix product of s with the right matrix.

Can anybody help me out and tell me what these matrices do, please?

I'll try to explain the FFT algorithmn, and let you find which errors your teacher made.

• input : $x \in \mathbb{C}^n$ where $n$ is a power of $2$, output : $X \in \mathbb{C}^n$ its discrete Fourier transform (DFT) $$X(k) = \sum_{n=0}^{N-1} x(n) e^{-2 i \pi n k / N}$$

• the naive algorithm takes $N^2$ multiplications/additions but we will do it in $2N \ln N$ operations by a divide and conquer strategy

• 1st matrix : transform $x(n)$ into two downsampled vectors $$y_0(n) = x(2n) \qquad\qquad y_1(n) = x(2n+1)$$

• 2n matrix : recursively apply the algorithm to calculate the DFT of those two vectors so that

$$Y_0(k) = \sum_{n=0}^{N/2-1} y_0(n) e^{-2 i \pi n k / (N/2)} \qquad\qquad Y_1(k) = \sum_{n=0}^{N/2-1} y_1(n) e^{-2 i \pi n k / (N/2)}$$

• 3rd matrix : $N/2$-periodize the two obtained DFT so that $Y_0(k)=Y_0(k+N/2)$ and $Y_1(k)=Y_1(k+N/2)$, then mix them to obtain the whole DFT

$$ \begin{array}{lll}Y_0(k) + e^{-2 i \pi k / N} Y_1(k) &=& \sum_{n=0}^{N/2-1} x(2n) e^{-2 i \pi n k / (N/2)} + e^{-2 i \pi k / N} \sum_{n=0}^{N/2-1} x(2n+1) e^{-2 i \pi n k / (N/2)} \\ &=& \sum_{n=0}^{N/2-1} x(2n) e^{-2 i \pi 2 n k / N} + e^{-2 i \pi k / N} \sum_{n=0}^{N/2-1} x(2n+1) e^{-2 i \pi 2n k / N}\\ &=& X(k)\end{array}$$