Circulant matrix

An ${\displaystyle n\times n}$  circulant matrix ${\displaystyle C}$  takes the form $${\displaystyle C={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{n-1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-2}&&\ddots &\ddots &c_{n-1}\\c_{n-1}&c_{n-2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}}$$  or the transpose of this form (by choice of notation). If each ${\displaystyle c_{i}}$  is a ${\displaystyle p\times p}$  square matrix, then the ${\displaystyle np\times np}$  matrix ${\displaystyle C}$  is called a block-circulant matrix.

A circulant matrix is fully specified by one vector, ${\displaystyle c}$ , which appears as the first column (or row) of ${\displaystyle C}$ . The remaining columns (and rows, resp.) of ${\displaystyle C}$  are each cyclic permutations of the vector ${\displaystyle c}$  with offset equal to the column (or row, resp.) index, if lines are indexed from ${\displaystyle 0}$  to ${\displaystyle n-1}$ . (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of ${\displaystyle C}$  is the vector ${\displaystyle c}$  shifted by one in reverse.

Different sources define the circulant matrix in different ways, for example as above, or with the vector ${\displaystyle c}$  corresponding to the first row rather than the first column of the matrix; and possibly with a different direction of shift (which is sometimes called an anti-circulant matrix).

The polynomial ${\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}$  is called the associated polynomial of the matrix ${\displaystyle C}$ .

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)^{T},\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 discrete Fourier transform matrix of order ${\displaystyle n}$  is defined as by

$${\displaystyle F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2\pi i/n\cdot jk},\,{\text{for }}0\leq j,k\leq n-1.}$$  There are important connections between circulant matrices and the DFT matrices. In fact, it can be shown that $${\displaystyle C=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]

• Let ${\displaystyle p(x)}$  be the (monic) characteristic polynomial of an ${\displaystyle n\times n}$  circulant matrix ${\displaystyle C}$ . Then the scaled derivative ${\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).

Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform.

Consider vectors in ${\displaystyle \mathbb {R} ^{n}}$  as functions on the integers with period ${\displaystyle n}$ , (i.e., as periodic bi-infinite sequences: ${\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }$ ) or equivalently, as functions on the cyclic group of order ${\displaystyle n}$  (denoted ${\displaystyle C_{n}}$  or ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ) geometrically, on (the vertices of) the regular ${\displaystyle n}$ -gon: this is a discrete analog to periodic functions on the real line or circle.

Then, from the perspective of operator theory, a circulant matrix is the kernel of a discrete integral transform, namely the convolution operator for the function ${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$ ; this is a discrete circular convolution. The formula for the convolution of the functions ${\displaystyle (b_{i}):=(c_{i})*(a_{i})}$  is

${\displaystyle b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}}$ 

(recall that the sequences are periodic) which is the product of the vector ${\displaystyle (a_{i})}$  by the circulant matrix for ${\displaystyle (c_{i})}$ .

The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.

The ${\displaystyle C^{*}}$ -algebra of all circulant matrices with complex entries is isomorphic to the group ${\displaystyle C^{*}}$ -algebra of ${\displaystyle \mathbb {Z} /n\mathbb {Z} .}$ 

For a symmetric circulant matrix ${\displaystyle C}$  one has the extra condition that ${\displaystyle c_{n-i}=c_{i}}$ . Thus it is determined by ${\displaystyle \lfloor n/2\rfloor +1}$  elements. $${\displaystyle C={\begin{bmatrix}c_{0}&c_{1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{2}&&\ddots &\ddots &c_{1}\\c_{1}&c_{2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}.}$$ 

The eigenvalues of any real symmetric matrix are real. The corresponding eigenvalues ${\displaystyle {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c}$  become: $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+c_{n/2}e^{-\pi i\cdot k}+2\sum _{j=1}^{{\frac {n}{2}}-1}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+c_{n/2}\omega _{k}^{n/2}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{n/2-1}\Re \omega _{k}^{n/2-1}\end{array}}}$$  for ${\displaystyle n}$  even, and $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+2\sum _{j=1}^{\frac {n-1}{2}}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{k}^{(n-1)/2}\end{array}}}$$  for ${\displaystyle n}$  odd, where ${\displaystyle \Re z}$  denotes the real part of ${\displaystyle z}$ . This can be further simplified by using the fact that ${\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)}$  and ${\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}}$  depending on ${\displaystyle k}$  even or odd.

Symmetric circulant matrices belong to the class of bisymmetric matrices.

The complex version of the circulant matrix, ubiquitous in communications theory, is usually Hermitian. In this case ${\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2}$  and its determinant and all eigenvalues are real.

If n is even the first two rows necessarily takes the form $${\displaystyle {\begin{bmatrix}r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}\\\dots \\\end{bmatrix}}.}$$  in which the first element ${\displaystyle r_{3}}$  in the top second half-row is real.

If n is odd we get $${\displaystyle {\begin{bmatrix}r_{0}&z_{1}&z_{2}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&z_{2}^{*}\\\dots \\\end{bmatrix}}.}$$ 

Tee^[5] has discussed constraints on the eigenvalues for the Hermitian condition.

Given a matrix equation

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

where ${\displaystyle C}$  is a circulant 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/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.

• Gray, R.M. (2006). Toeplitz and Circulant Matrices: A Review (PDF). Vol. 2. Now. pp. 155–239. doi:10.1561/0100000006. ISBN 978-1-933019-68-0 – via Stanford University. {{cite book}}: |journal= ignored (help)
• IPython Notebook demonstrating properties of circulant matrices