(10 points) Let be a primitive nth root of unity. The fast Fourier trans- form implements the multiplication with the matrix F = (wij)i,j inlo..n-1]. Show that the inverse of the F is given by Hint : xn-1-(z-1)(zn-l + . . . +x + 1), so any power we1 must be a root of -+++1. ] Thus, the inverse FFT, called IFFT, is nothing but the FFT using w instead of w, and multiplying the result with 1