Circulant matrix

The normalized eigenvectors of a circulant matrix are the Fourier modes, namely,

$${\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right),\quad j=0,1,\ldots ,n-1,}$$

where ${\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}$ is a primitive ${\displaystyle n}$-th root of unity and ${\displaystyle i}$ is the imaginary unit.

(This can be understood by realizing that multiplication with a circulant matrix implements a convolution. In Fourier space, convolutions become multiplication. Hence the product of a circulant matrix with a Fourier mode yields a multiple of that Fourier mode, i.e. it is an eigenvector.)

The corresponding eigenvalues are given by

$${\displaystyle \lambda _{j}=c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j},\quad j=0,1,\dots ,n-1.}$$

As a consequence of the explicit formula for the eigenvalues above, the determinant of a circulant matrix can be computed as:

$${\displaystyle \det(C)=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j}).}$$

Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is

$${\displaystyle \det(C)=\prod _{j=0}^{n-1}(c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j})=\prod _{j=0}^{n-1}f(\omega ^{j}).}$$

The rank of a circulant matrix ${\displaystyle C}$ is equal to ${\displaystyle n-d}$, where ${\displaystyle d}$ is the degree of the polynomial ${\displaystyle \gcd(f(x),x^{n}-1)}$.[2]

• Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic permutation matrix ${\displaystyle P}$:
  $${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}$$

  
  where ${\displaystyle P}$ is given by the companion matrix
  $${\displaystyle P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\cdots &0&1&0\end{bmatrix}}.}$$

  
• The set of ${\displaystyle n\times n}$ circulant matrices forms an ${\displaystyle n}$-dimensional vector space with respect to addition and scalar multiplication. This space can be interpreted as the space of functions on the cyclic group of order ${\displaystyle n}$, ${\displaystyle C_{n}}$, or equivalently as the group ring of ${\displaystyle C_{n}}$.
• Circulant matrices form a commutative algebra, since for any two given circulant matrices ${\displaystyle A}$ and ${\displaystyle B}$, the sum ${\displaystyle A+B}$ is circulant, the product ${\displaystyle AB}$ is circulant, and ${\displaystyle AB=BA}$.
• For a nonsingular circulant matrix ${\displaystyle A}$, its inverse ${\displaystyle A^{-1}}$ is also circulant. For a singular circulant matrix, its Moore–Penrose pseudoinverse ${\displaystyle A^{+}}$ is circulant.
• The matrix ${\displaystyle U}$ that is composed of the eigenvectors of a circulant matrix is related to the discrete Fourier transform and its inverse transform:
  $${\displaystyle U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\frac {1}{\sqrt {n}}}F_{n}^{-1},{\text{ where }}F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2jk\pi i/n},\,{\text{for }}0\leq j,k<n.}$$

  
  Consequently the matrix ${\displaystyle U_{n}}$ diagonalizes ${\displaystyle C}$. In fact, we have
  $${\displaystyle C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}={\frac {1}{n}}F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}$$

  
  where ${\displaystyle c}$ is the first column of ${\displaystyle C}$. The eigenvalues of ${\displaystyle C}$ are given by the product ${\displaystyle F_{n}c}$. This product can be readily calculated by a fast Fourier transform.[3] Conversely, for any diagonal matrix ${\displaystyle D}$, the product ${\displaystyle F_{n}^{-1}DF_{n}}$ is circulant.
• Let ${\displaystyle p(x)}$ be the (monic) characteristic polynomial of an ${\displaystyle n\times n}$ circulant matrix ${\displaystyle C}$, and let ${\displaystyle p'(x)}$ be the derivative of ${\displaystyle p(x)}$. Then the polynomial ${\textstyle {\frac {1}{n}}p'(x)}$ is the characteristic polynomial of the following ${\displaystyle (n-1)\times (n-1)}$ submatrix of ${\displaystyle C}$:
  $${\displaystyle C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{3}&c_{2}\\c_{1}&c_{0}&c_{n-1}&&c_{3}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-3}&&\ddots &\ddots &c_{n-1}\\c_{n-2}&c_{n-3}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}}$$

  
  (see [4] for the proof).

Given a matrix equation

$${\displaystyle C\mathbf {x} =\mathbf {b} ,}$$

where ${\displaystyle C}$ is a circulant square matrix of size ${\displaystyle n}$ we can write the equation as the circular convolution

$${\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,}$$

where ${\displaystyle \mathbf {c} }$ is the first column of ${\displaystyle C}$, and the vectors ${\displaystyle \mathbf {c} }$, ${\displaystyle \mathbf {x} }$ and ${\displaystyle \mathbf {b} }$ are cyclically extended in each direction. Using the circular convolution theorem, we can use the discrete Fourier transform to transform the cyclic convolution into component-wise multiplication

$${\displaystyle {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}$$

so that

$${\displaystyle \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\!\nu \in \mathbb {Z} }\right]^{\rm {T}}.}$$

This algorithm is much faster than the standard Gaussian elimination, especially if a fast Fourier transform is used.

In graph theory, a graph or digraph whose adjacency matrix is circulant is called a circulant graph (or digraph). Equivalently, a graph is circulant if its automorphism group contains a full-length cycle. The Möbius ladders are examples of circulant graphs, as are the Paley graphs for fields of prime order.