---- > [!definition] Definition. ([[circulant matrix]]) > A **circulant matrix** is a square [[matrix]] in which each row is a shifted (circularly to the right by one column) version of the previous row. > [!equivalence] > - A $N \times N$ [[matrix]] is **circulant** iff its elements $a_{ij}$ have the form $a_{ij}=f(i-j \text{ mod }N)$ for some function $f:\{ 0,\dots,N-1 \} \to \mathbb{F}$. > - A [[matrix]] is **circulant** [[convolution iff circulant|iff it is the matrix of a discrete]] [[convolution]]. > [!note] Remark. > [[circulant matrix|Circulant matrices]] are [[simultaneously diagonalizable|simultaneously diagonalized]] in the [[orthonormal basis|orthonormal]] fourier [[basis]], the [[Complex Spectral Theorem|unitary eigendecomposition]] being $\begin{align} > C= Q \Lambda Q', \Lambda= & \text{diag}\{ \lambda_{k} \}_{k=0}^{N-1}, \lambda_{k}= \sum_{n=0}^{N-1}c_{n} z_{k}^{n} \\ > Q = & \frac{1}{\sqrt{ N }} \begin{bmatrix} > 1 & \dots & 1 & \dots & 1 \\ > 1 & \dots & w_{k} & \dots & w_{N-1} \\ > \vdots & \dots & \vdots & \dots & \vdots \\ > 1 & \dots & w_{k}^{N-2} & \dots & w_{N-1}^{N-2} \\ > 1 & \dots & w_{k}^{N-1} & \dots & w_{N-1}^{N-1} > \end{bmatrix}, > \end{align}$ > where $w_{k}=e^{2\pi i k / N}$ and $z_{k}=e^{-2\pi i k / N}$, $k=0,\dots,N-1$. Hence to find [[eigenvalue|eigenvalues]] of $C$, take $\texttt{fft(C[:, 1])}$. > [!basicexample] > $\begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{bmatrix}$ ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```