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

Question

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{equation} \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 \end{equation}

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$?

Answer 1

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\;.$$