2
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ 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/… $\endgroup$ Jan 12, 2021 at 3:54
  • $\begingroup$ That's nice as a hint, but I still don't see how mathematically I show it, and also how do I calculate all the powers including 2 and 3 ? $\endgroup$
    – Ilya.K.
    Jan 12, 2021 at 4:39

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .