For a certain n, letting w = (1/2)=e-2xi/n, we define the Fourier transform of an n-element...

 

Transcribed Image Text:

For a certain n, letting w = (1/2)=e-2xi/n, we define the Fourier transform of an n-element vector as its product with the nxn matrix whose (j,k) entry-indexed from 0-is wik 1 1 1 1 1 w w w M 1 w w4 w ... 1 03 06 Show for any n, that M is "almost its own inverse", by showing that the product of M with itself, M-M, equals n times the matrix with 1 in the top left corner, and is along the opposite diagonal-for n = 5, the matrix n. 10000 0 0 0 0 1 0001 0 0 0 1 0 0 0 1 0 0 0 (Hint: You will need to consider the dot product of a row of M with a column of M and show that it is either 0 or n, depending on the combination of row and column. The formula for the sum of a geometric series will be useful here. You might show that the element-by-element product of a row and a column of M is itself a row of M, so that all you need to do is analyze the sum of each row of M. Can you explain intuitively why the row sums are what they are?) For a certain n, letting w = (1/2)=e-2xi/n, we define the Fourier transform of an n-element vector as its product with the nxn matrix whose (j,k) entry-indexed from 0-is wik 1 1 1 1 1 w w w M 1 w w4 w ... 1 03 06 Show for any n, that M is "almost its own inverse", by showing that the product of M with itself, M-M, equals n times the matrix with 1 in the top left corner, and is along the opposite diagonal-for n = 5, the matrix n. 10000 0 0 0 0 1 0001 0 0 0 1 0 0 0 1 0 0 0 (Hint: You will need to consider the dot product of a row of M with a column of M and show that it is either 0 or n, depending on the combination of row and column. The formula for the sum of a geometric series will be useful here. You might show that the element-by-element product of a row and a column of M is itself a row of M, so that all you need to do is analyze the sum of each row of M. Can you explain intuitively why the row sums are what they are?)