The inverse discrete Fourier transform $\mathcal{F}_{n}^{-1}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is given by the formula

$$\mathbf{x}=\mathcal{F}_{n}^{-1} \mathbf{y}, \quad \text { where } \quad x_{\ell}=\sum_{j=0}^{n-1} \omega_{n}^{j \ell} y_{j}, \quad \ell=0, \ldots, n-1$$

Here, $\omega_{n}=\exp (2 \pi i / n)$ is the primitive root of unity of degree $n$, and $n=2^{p}, p=1,2, \ldots$

(1) Show how to assemble $\mathbf{x}=\mathcal{F}_{2 m}^{-1} \mathbf{y}$ in a small number of operations if we already know the Fourier transforms of the even and odd portions of $\mathbf{y}$ :

$$\mathbf{x}^{(\mathrm{E})}=\mathcal{F}_{m}^{-1} \mathbf{y}^{(\mathrm{E})}, \quad \mathbf{x}^{(\mathrm{O})}=\mathcal{F}_{m}^{-1} \mathbf{y}^{(\mathrm{O})}$$

(2) Describe the Fast Fourier Transform (FFT) method for evaluating $\mathbf{x}$ and draw a relevant diagram for $n=8$.

(3) Find the costs of the FFT for $n=2^{p}$ (only multiplications count).

(4) For $n=4$, using the FFT technique, find $\mathbf{x}=\mathcal{F}_{4}^{-1} \mathbf{y}, \quad$ for $\quad \mathbf{y}=[1,1,-1,-1], \quad$ and $\quad \mathbf{y}=[1,-1,1,-1]$