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}$
Thank you in advance.
 A: 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}_{ij} = 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.
