Task 1: Create Fourier matrix $F = \{ \omega^{kl}\}_{k,l=0}^{n-1}$, where $\omega = \text{exp}\left(-\frac{2\pi i}{n}\right)$ and check that $\frac{1}{\sqrt{n}} F$ is unitary

Note:

• $\pi= \verb|np.pi|$
• $\verb|1j|$ is the imaginary unit
• Hermitian conjugation cosists of $\verb|np.transpose|$ and $\verb|np.conjugate|$

Task 2: Create a random vector $x$ of size n. Using $\verb|%timeit|$ compare timings of $\verb|np.fft.fft(x)|$ and $\verb|np.dot(F, x)|$. Compare the results using $\verb|np.linalg.norm|$

Task 3: Create a circulant matrix $C$ using $\verb|scipy.linalg.circulant(c)|$, where $c$ is the first column of $C$. Check that $C = F^{-1} \text{diag}(Fc) F$

Note: Choose $c = [1,2,3,...]$

Task 4: Implement fast matvec product $Cx$ (convolution operation) using the fact that $Cx = F^{-1} \text{diag}(Fc) Fx$. Compare timings to direct $Cx$ multiplication

Note: Do not use $\verb|np.dot|$ which is slow! Use only $\verb|np.fft.fft|$ and $\verb|np.fft.ifft|$ fucntions!