Exercise involving DFT The fourier matrix is a transformation matrix where each component is define

Question

Exercise involving DFT
The fourier matrix is a transformation matrix where each component is defined as

F_{a b} = ω^{a b}

where

ω = e^{2 π i / n}

. The indices of the matrix range from 0 to

n - 1

(i.e.

a, b \in {0, . . ., n - 1}

)
As such we can write the Fourier transform of a complex vector v as

\hat{v} = F v

, which means that

{\hat{v}}_{f} = \sum_{a \in {0, . . ., n - 1}} ω^{a f} v_{a}

Assume that n is a power of 2. I need to prove that for all odd

c \in {0, . . ., n - 1}

, every

d \in {0, . . ., n - 1}

and every complex vectors v, if

w_{b} = v_{c b + d}

, then for all

f \in {0, . . ., n - 1}

it is the case that:

{\hat{w}}_{c f} = ω^{- f d} {\hat{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.

Answer 1

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

n = 2^{r}

(for some positive integer r ), and so, as k ranges from 0 to

2^{r} - 1

in the sum

{\hat{ω}}_{c f} = \sum_{k = 0}^{2^{r} - 1} e^{\frac{2 π i k c f}{2^{r}}} v_{c k + d (\mod 2^{r})},

the residues of ck mod

2^{r}

will range over the same set of values, but in a different order. For each

k \in {0, 1, \dots,

there is a (unique) integer

u_{k}

with

0 \leq

such that

c k = u_{k} + z_{k} 2^{r}

for some integer

z_{k}

, and u will be a permutation on the set of integers

{0, 1, \dots, 2^{r} - 1}

.
Step 2
We then have

\begin{aligned} \sum_{k = 0}^{2^{r} - 1} e^{\frac{2 π i k c f}{2^{r}}} v_{c k + d (\mod 2^{r})} & = \sum_{k = 0}^{2^{r} - 1} e^{\frac{2 π i (u_{k} + z_{k} 2^{r}) f}{2^{r}}} v_{u_{k} + z_{k} 2^{r} + d (\mod 2^{r})}, \\ = \sum_{k = 0}^{2^{r} - 1} e^{\frac{2 π i u_{k} f}{2^{r}}} v_{u_{k} + d (\mod 2^{r})}, \\ = \sum_{t = 0}^{2^{r} - 1} e^{\frac{2 π i t f}{2^{r}}} v_{t + d (\mod 2^{r})}, \end{aligned}

the last expression being obtained by rearranging the order of summation.

Exercise involving DFT The fourier matrix is a transformation matrix where each component is define

Want to know more about Discrete math?

Answers (1)

Not exactly what you’re looking for?

Relevant Questions