= Fourier diagonalization of a circulant matrix
{c}
{title2=$C=F^{-1}\operatorname{diag}(Fc)F$}
Use the negative-exponential forward <discrete Fourier transform> and the $1/N$-normalized <inverse discrete Fourier transform>:
$$
F_{kn}=e^{-2\pi ikn/N},
\qquad
(F^{-1})_{nk}=\frac1N e^{2\pi ink/N}.
$$
For the circulant <matrix> with first column $c$, the <discrete Fourier mode> $w^{(k)}_n=e^{2\pi ikn/N}$ is an <eigenvector> with <eigenvalue>
$$
\boxed{\lambda_k=\sum_{\ell=0}^{N-1}c_\ell e^{-2\pi ik\ell/N}=(Fc)_k.}
$$
Indeed, substitution into <circular convolution> gives
$$
(Cw^{(k)})_n
=\sum_{\ell=0}^{N-1}c_\ell e^{2\pi ik(n-\ell)/N}
=w^{(k)}_n\lambda_k.
$$
The columns of $F^{-1}$ are $w^{(k)}/N$, so the <diagonalization of a matrix> takes the form
$$
C=F^{-1}\operatorname{diag}(\lambda_0,\ldots,\lambda_{N-1})F.
$$
The <roots of unity> give <orthogonality> of these <eigenvectors>; dividing each $w^{(k)}$ by $\sqrt N$ makes the <basis> <orthonormal>. Consequently, every complex circulant <matrix> is a <normal matrix>, including ones that are not <Hermitian matrices>.
The sign convention matters. For $c=(1,2,0,0)^T$, the circulant <matrix> is
$$
C=\begin{pmatrix}
1&0&0&2\\
2&1&0&0\\
0&2&1&0\\
0&0&2&1
\end{pmatrix},
\qquad
(\lambda_0,\lambda_1,\lambda_2,\lambda_3)=(3,1-2i,-1,1+2i).
$$
Changing the direction of the shift or the sign in the <discrete Fourier transform> changes which complex <eigenvalue> goes with which <discrete Fourier mode>. A real symmetric example alone would conceal that distinction.
For a <linear system> $Cx=b$, put $\widehat x=Fx$ and $\widehat b=Fb$. The equation becomes $N$ independent scalar equations
$$
\lambda_k\widehat x_k=\widehat b_k.
$$
If every $\lambda_k$ is nonzero, divide to find the unique <vector> $x$ and apply the <inverse discrete Fourier transform>. If some $\lambda_k=0$, a <vector> $x$ satisfying the <linear system> exists exactly when $\widehat b_k=0$ at every such index; the corresponding $\widehat x_k$ remain free. This is a concrete version of the <Fredholm alternative> in a finite-dimensional setting.
With an appropriate <Fast Fourier transform>, multiplication or a compatible solve takes $O(N\log N)$ arithmetic operations, instead of forming a dense <matrix> and applying general <Gaussian elimination>. The gain comes from the periodic structure; an arbitrary <matrix> does not have this shared <basis> of <discrete Fourier modes>.https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-31-eigenvectors-of-circulant-matrices-fourier-matrix/[Strang, MIT 18.065 Lecture 31: Fourier eigenvectors and fast computation]{ref}
Back to article page
