= Circulant matrix
{title2=$C_{nj}=c_{(n-j)\bmod N}$}
{wiki}
A circulant <matrix> applies the same rule at every position of a finite ring: moving both the input and output indices one step leaves its entries unchanged. Its first column determines the whole <matrix>. For a length-$N$ <vector> $c$, index rows and columns by $0,\ldots,N-1$ and define
$$
C_{nj}=c_{(n-j)\bmod N}.
$$
The indices use <modular arithmetic>. Thus each column is the previous column shifted down one place, with the last entry wrapping around to the top. Multiplication is exactly <circular convolution>:
$$
(Cx)_n=\sum_{j=0}^{N-1}c_{(n-j)\bmod N}x_j
=\sum_{\ell=0}^{N-1}c_\ell x_{(n-\ell)\bmod N}.
$$
This makes a circulant <matrix> a natural model for a periodic <finite difference> rule or a filter acting on a periodic record. Strang's MIT lecture develops this connection between circulant <matrices>, <circular convolution> and the <discrete Fourier transform>.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: eigenvectors of circulant matrices]{ref}
For example, the first column $c=(2,-1,0,-1)^T$ gives
$$
L=\begin{pmatrix}
2&-1&0&-1\\
-1&2&-1&0\\
0&-1&2&-1\\
-1&0&-1&2
\end{pmatrix},
\qquad (Lx)_n=2x_n-x_{n-1}-x_{n+1}.
$$
Here the indices wrap around modulo four. Each output compares a value with its two neighbors; this is the <Graph Laplacian> of a four-vertex <cycle graph>. A constant input gives zero, while an alternating input gives a large response. The <Fourier diagonalization of a circulant matrix> makes this distinction exact: its four <eigenvalues> are $0,2,4,2$.
\Image[/circulant-fourier-modes.png]
{title=Fourier eigenvectors of the four-point cycle Laplacian}
The plotted <discrete Fourier modes> are complex <vectors>, shown through their real and imaginary parts. Each entry has <modulus> one; the <Euclidean norm> of each length-four <vector> is two. In particular, modes $k=1$ and $k=3$ have the same real part but opposite imaginary parts, so they are distinct <eigenvectors> with the same <eigenvalue>.
The useful surprise is that every length-$N$ circulant <matrix> shares the same <basis> of <eigenvectors>, whatever its first column. One <change of basis> therefore simplifies an entire family of <linear maps>, instead of requiring a separate <eigenvalue> computation for each one. Bamieh's tutorial develops the <discrete Fourier transform> from precisely this simultaneous <diagonalization> problem.https://arxiv.org/abs/1805.05533[Bamieh, Discovering Transforms: A Tutorial on Circulant Matrices, Circular Convolution, and the Discrete Fourier Transform (2018; revised 2022)]{ref}
Back to article page
