# How can we prove that the discrete Fourier transforms preserves the inner product up to a constant factor?

Let $d\in\mathbb N$, $\omega\in\mathbb C$ be a primitive $n$-th root of unity and $$\operatorname{DFT}_\omega:\mathbb C^d\to\mathbb C^d\;,\;\;\;z\mapsto\left(f_z\left(\omega^0\right),\ldots,f_z\left(\omega^{d-1}\right)\right)^T$$ with $$f_z(w):=\sum_{k=0}^{d-1}z_kw^k\;\;\;\text{for }z=\left(z_0,\ldots,z_{d-1}\right)^T\text{ and }w\in\mathbb C\;.$$

How can we show that $\operatorname{DFT}_\omega$ preserves the inner product up to a constant factor?

I've tried the following: Let $z,w\in\mathbb C^d$ $\Rightarrow$

$$\begin{split} \langle\operatorname{DFT}_\omega z,\operatorname{DFT}_\omega w\rangle&=\sum_{j=0}^{d-1}f_z(\omega^j)f_w(\omega^j)\\ &=\sum_{j=0}^{d-1}\left(\sum_{k=0}^{d-1}z_k\omega^{jk}\right)\sum_{\ell=0}^{d-1}w_\ell\omega^{j\ell}\\ &=\sum_{k,\ell=0}^{d-1}z_kw_\ell\sum_{j=0}^{d-1}\omega^{j(k+\ell)} \end{split}\tag 1$$

Now, I suppose we need to use that $$\sum_{k=0}^{d-1}\omega^{k\ell}=0\;\;\;\text{for all }\ell\in\left\{1,\ldots,d-1\right\}\;.\tag 2$$ However, that seems to be complicated in $(1)$, since it reads $$\sum_{j=0}^{d-1}\omega^{j(k+\ell)}=0\;\;\;\text{for all }k+\ell\text{ mod }d\in\left\{1,\ldots,d-1\right\}\;,$$ i.e. the sum is $\ne 0$ (equal to $d$) if and only if $$k+l\text{ mod }d=0\Rightarrow k+\ell=\lambda d\;\;\;\text{for some }\lambda\in\mathbb N_0\;.$$ Since $$\lambda d=k+\ell\le d^2-2d+1\Rightarrow \lambda\le d-2+\frac 1d\;,$$ we could conclude that $$\langle\operatorname{DFT}_\omega z,\operatorname{DFT}_\omega w\rangle=d\sum_{k+\ell=\lambda d:\lambda\in\left\{0,\ldots,d-2\right\}}z_kw_\ell\;,\tag 3$$ if $d>1$. I don't know how I need to simplify $(3)$ and we need to consider $d=1$ separately.

I'm quite sure that I'm thinking way too complicated. So, how can we show that $$\langle\operatorname{DFT}_\omega z,\operatorname{DFT}_\omega w\rangle=c\langle z,w\rangle\tag 4$$ for some $c\in\mathbb C$?

• I haven't looked at all of the details, but a few points. Firstly, the inner product in $\mathbb C^d$ is $\langle z,w\rangle =\sum_{k=1}^dz_k\bar w_k$. Secondly, the discrete Fourier transform is a linear map, so it suffices to show that $\|\text{DFT}_\omega z\|^2=c\|z\|^2$. This might simplify some of the arguments. Commented Feb 26, 2016 at 18:24
• @Jason Yeah, I know that. I just wanted to comment "What am I doing here?" ;) I will provide an answer in a few minutes. There is a much simpler solution. Commented Feb 26, 2016 at 18:38
• @Jason I've provided the answer. Commented Feb 26, 2016 at 19:49

It's easy to verify that $$V_\omega:=\begin{pmatrix} \omega^{0\cdot 0}&\cdots&\omega^{0\cdot (d-1)}\\\vdots&\ddots&\vdots\\\omega^{(d-1)\cdot 0}&\cdots&\omega^{(d-1)\cdot (d-1)} \end{pmatrix}$$ is the transformation matrix of $\operatorname{DFT}_\omega$ and $$V_\omega^{-1}=\frac 1dV_{\omega^{-1}}\;.$$ Since $|\omega|=1$, we obtain $\omega^{-1}=\overline\omega$ and hence $$\tilde V_\omega^{-1}=\sqrt dV_\omega^{-1}=\frac 1{\sqrt d}V_{\omega^{-1}}=\tilde V_{\omega^{-1}}=\tilde V_{\overline\omega}=\overline{\tilde V_\omega}$$ where $$\tilde V_\omega:=\frac 1{\sqrt d}V_\omega\;.$$ Since $V_\omega$ (and thereby $\tilde V_\omega$) is symmetric, $\tilde V_\omega$ is unitary. Since a unitary matrix preserves the inner product, we can conclude that $$\langle\operatorname{DFT}_\omega z,\operatorname{DFT}_\omega w\rangle=\langle\sqrt d\tilde V_\omega z,\sqrt d\tilde V_\omega w\rangle=d\langle\tilde V_\omega z,\tilde V_\omega w\rangle=d\langle z,w\rangle\;.$$
• Quick note: $\omega$ is not unique up to complex conjugation. Indeed, if $d$ is prime then any root of unity not equal to $1$ is primitive. This doesn't matter too much, though. Commented Feb 26, 2016 at 19:52
• @Jason What I've meant is the following: Let $R$ be an unitary ring and $\omega\in R$ be a primitive $d$-th root of unity. Then, $\omega^1,\ldots,\omega^n$ are pairwise distinct and are the only $d$-th roots of unity, since $R\ni z\mapsto z^n-1$ has at most $n$ distinct roots. Maybe you can rephrase why it's no loss to assume $\omega=e^{-{\rm i}\frac{2\pi}d}$. Commented Feb 26, 2016 at 19:57
• You don't need to. The fact that $\omega^{-1}=\bar\omega$ is equivalent to the fact that $|\omega|=1$, which is certainly necessary for $\omega^d=1$. Commented Feb 26, 2016 at 20:01