# power of the DFT matrix

I don't know if it was asked before, didn't find anything using the search.

How do I compute the power of the DFT matrix:

$$DFT^k$$ for $$k \in \mathbb{N}$$

• It's a nice exercise to show that the fourth power of the DFT matrix, suitably normalized, is $I$. This is mentioned, for example, on Wikipedia: en.wikipedia.org/wiki/… Jan 12, 2021 at 3:54
Maybe I am a bit late but I looked at the same problem today. Here is my approach. The powers of the $$DFT^{k}$$ matrix are trivial for $$k \geq 5$$. In particular the case $$k=2$$ is the relevant one. All the other follow from it. In particular, we will find $$DFT^{2}= \begin{bmatrix} 1 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & \ldots & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & \ldots & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & \ldots & 1 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 1 & \ldots & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ \end{bmatrix}.$$ This can be shown by looking at the entries of $$DFT^{2}$$. Since $$DFT$$ is symmetric we know the $$ij^{th}$$-entry of $$DFT^{2}$$ is given by $$DFT^{2}_{lj} = v_{l}^{T}v_{j}$$, where $$v_{l}$$ is the $$l^{th}$$ column of $$DFT$$. By simple calculations we find, $$DFT^{2}_{lj} = v_{l}^{T}v_{j}= \begin{cases} 1&(l+j)\mod{N} = 0\\ 0&else \end{cases}.$$ Now we show our claim.
$$1^{st}$$ case: $$(l+j)\mod{N} = 0$$ $$DFT^{2}_{lj} = \sum_{n=0}^{N-1}\frac{1}{\sqrt{N}}e^{\frac{2\pi i}{N}}\frac{1}{\sqrt{N}}e^{\frac{2\pi i}{N}kj}=\frac{1}{N}\sum_{n=0}^{N-1}e^{\frac{2\pi i}{N}k(l+j)}=\frac{1}{N}\sum_{n=0}^{N-1}e^{\frac{2\pi i}{N}k0}= \frac{1}{N}\sum_{n=0}^{N-1}1=1.$$ Now we look at the second case.
$$2^{nd}$$ case: $$(l+j)\mod{N} \neq 0$$ \begin{align*} DFT^{2}_{lj} &= \sum_{n=0}^{N-1}\frac{1}{\sqrt{N}}e^{\frac{2\pi i}{N}}\frac{1}{\sqrt{N}}e^{\frac{2\pi i}{N}kj}=\frac{1}{N}\sum_{n=0}^{N-1}e^{\frac{2\pi i}{N}k(l+j)}=\frac{1}{N}\sum_{n=0}^{N-1}\left(e^{\frac{2\pi i}{N}(l+j)}\right)^{k}=\frac{1}{N}\frac{1-\left(e^{\frac{2\pi i}{N}(l+j)}\right)^{N}}{1-e^{\frac{2\pi i}{N}(l+j)}}\\ &= \frac{1}{N}\frac{1-e^{\frac{2\pi i}{N}(l+j)N}}{1-e^{\frac{2\pi i}{N}(l+j)}}=\frac{1}{N}\frac{1-e^{2\pi i(l+j)}}{1-e^{\frac{2\pi i}{N}(l+j)}}=\frac{1}{N}\frac{1-1}{1-e^{\frac{2\pi i}{N}(l+j)}}=0. \end{align*} Thus we found out claimed form of $$DFT^2$$. This is a permutaion matrix. Thus the shape of $$DFT^{3}$$ become clear. Furthermore, it is now trivial to show that $$DFT^{4}=\mathit{I}_{N}$$. Hence, for general $$k \in \mathbb{N}$$: $$DFT^{k}=DFT^{k \mod{4}}$$. This finishes the proof.