Exercise involving DFT
The fourier matrix is a transformation matrix where each component is defined as where . The indices of the matrix range from 0 to (i.e. )
As such we can write the Fourier transform of a complex vector v as , which means that
Assume that n is a power of 2. I need to prove that for all odd , every and every complex vectors v, if , then for all it is the case that:
I was able to prove it for and , so I tried an inductive approach. This doesn't seem to be the best way to go and I am stuck at the inductive step and I don't think I can go any further which indicates that this isn't the right approach.
Note that I am not looking for a full solution, just looking for a hint.