The canonical finite DFT diagonalizes every circulant

Let $N\ge 1$, $c\in {\mathbb{C}}^N$, and let $C(c)$ be the circulant of Toeplitz, circulant, and finite-index conventions for structured solvers. Put ${\lambda }_k:={\sum }_{j=0}^{N-1}{c}_j{e}^{-2\pi ikj\mathrm{/}N}=\sqrt{N}({\mathcal{F}}_{N}c)(k),0\le k<N\mathrm{.}$ Then $C(c)={\mathcal{F}}_N^{-1}\mathrm{diag}({\lambda }_0,\dots ,{\lambda }_{N-1}){\mathcal{F}}_N\mathrm{.}$ Consequently, $C(c)$ is invertible exactly when every ${\lambda }_k\mathrm{\ne }0$. For $b\in {\mathbb{C}}^N$, $C(c)x=b$ is solvable exactly when $({\mathcal{F}}_{N}b)(k)=0$ for every zero mode ${\lambda }_k=0$; on nonzero modes every solution has $({\mathcal{F}}_{N}x)(k)=({\mathcal{F}}_{N}b)(k)\mathrm{/}{\lambda }_k$, while its zero-mode coordinates are free.

The square records the identity ${\mathcal{F}}_{N}C(c)=\mathrm{diag}(\lambda ){\mathcal{F}}_N$; the two paths send each input vector to the same Fourier-coordinate vector. The proof below establishes this identity from the finite convolution sums.

diagram failed to render:
\begin{tikzcd}
\mathbb C^N \arrow[r,"C(c)"] \arrow[d,"\mathcal F_N"'] & \mathbb C^N \arrow[d,"\mathcal F_N"] \\
\mathbb C^N \arrow[r,"\operatorname{diag}(\lambda)"] & \mathbb C^N
\end{tikzcd}