 # Exercise involving DFT The fourier matrix is a transformation matrix where each component is define groupweird40 2022-05-23 Answered
Exercise involving DFT
The fourier matrix is a transformation matrix where each component is defined as ${F}_{ab}={\omega }^{ab}$ where $\omega ={e}^{2\pi i/n}$. The indices of the matrix range from 0 to $n-1$ (i.e. $a,b\in \left\{0,...,n-1\right\}$)
As such we can write the Fourier transform of a complex vector v as $\stackrel{^}{v}=Fv$, which means that
${\stackrel{^}{v}}_{f}=\sum _{a\in \left\{0,...,n-1\right\}}{\omega }^{af}{v}_{a}$
Assume that n is a power of 2. I need to prove that for all odd $c\in \left\{0,...,n-1\right\}$, every $d\in \left\{0,...,n-1\right\}$ and every complex vectors v, if ${w}_{b}={v}_{cb+d}$, then for all $f\in \left\{0,...,n-1\right\}$ it is the case that:
${\stackrel{^}{w}}_{cf}={\omega }^{-fd}\phantom{a}{\stackrel{^}{v}}_{f}$
I was able to prove it for $n=2$ and $n=4$, 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.
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Crevani9a
Step 1
You need to use the fact that n is a power of 2 . I believe a key observation is that because c is odd, it is a unit in the ring of integers mod (for some positive integer r ), and so, as k ranges from 0 to in the sum

the residues of ck mod will range over the same set of values, but in a different order. For each there is a (unique) integer with such that for some integer , and u will be a permutation on the set of integers .
Step 2
We then have
the last expression being obtained by rearranging the order of summation.