(10 points) Let w be a primitive nth root of unity. The fast Fourier trans- form...

Transcribed Image Text:

(10 points) Let w be a primitive nth root of unity. The fast Fourier trans- form implements the multiplication with the matrix (w)ij in[0..n-1] F Show that the inverse of the F is given by 1 (w i,k in0..-1] F-1 [Hint: 1 (x- 1)(-1 root of n-1 but the FFT using w x1), so any power w 1 must be a +x1. Thus, the inverse FFT, called IFFT, is nothing instead of w, and multiplying the result with 1/n. (10 points) Let w be a primitive nth root of unity. The fast Fourier trans- form implements the multiplication with the matrix (w)ij in[0..n-1] F Show that the inverse of the F is given by 1 (w i,k in0..-1] F-1 [Hint: 1 (x- 1)(-1 root of n-1 but the FFT using w x1), so any power w 1 must be a +x1. Thus, the inverse FFT, called IFFT, is nothing instead of w, and multiplying the result with 1/n.