Inlinear algebra, acirculant matrix is asquare matrix in which all rows are composed of the same elements and each row is rotated one element to the right relative to the preceding row. It is a particular kind ofToeplitz matrix.

Innumerical analysis, circulant matrices are important because they arediagonalized by adiscrete Fourier transform, and hencelinear equations that contain them may be quickly solved using afast Fourier transform.^[1] They can beinterpreted analytically as theintegral kernel of aconvolution operator on thecyclic group${\displaystyle C_n}$ and hence frequently appear in formal descriptions of spatially invariant linear operations. This property is also critical in modern software defined radios, which utilizeOrthogonal Frequency Division Multiplexing to spread thesymbols (bits) using acyclic prefix. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in thefrequency domain.

Incryptography, a circulant matrix is used in theMixColumns step of theAdvanced Encryption Standard.

An${\displaystyle n\times n}$circulant matrix${\displaystyle C}$ takes the formor thetranspose of this form (by choice of notation). If each${\displaystyle c_i}$ is a${\displaystyle p\times p}$ squarematrix, then the${\displaystyle np\times np}$ matrix${\displaystyle C}$ is called ablock-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 eachcyclic 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 ananti-circulant matrix).

Thepolynomial${\displaystyle f(x)=c_0+c_{1}x+\cdots +c_{n-1}{x}^{n-1}}$ is called theassociated polynomial of the matrix${\displaystyle C}$.

The normalizedeigenvectors of a circulant matrix are the Fourier modes, namely,$${\displaystyle v_j=\frac{1}{\sqrt{n}}{\left(1,{\omega }^j,{\omega }^{2j},\dots ,{\omega }^{(n-1)j}\right)}^T,j=0,1,\dots ,n-1,}$$where${\displaystyle \omega =\exp \left(\frac{2\pi i}{n}\right)}$ is a primitive${\displaystyle n}$-throot of unity and${\displaystyle i}$ is theimaginary 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 correspondingeigenvalues are given by$${\displaystyle {\lambda }_j=c_0+c_1{\omega }^{-j}+c_2{\omega }^{-2j}+\cdots +c_{n-1}{\omega }^{-(n-1)j},j=0,1,\dots ,n-1.}$$

As a consequence of the explicit formula for the eigenvalues above, thedeterminant of a circulant matrix can be computed as:$${\displaystyle detC=\prod _{j=0}^{n-1}(c_0+c_{n-1}{\omega }^j+c_{n-2}{\omega }^{2j}+\cdots +c_1{\omega }^{(n-1)j}).}$$Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is$${\displaystyle detC=\prod _{j=0}^{n-1}(c_0+c_1{\omega }^j+c_2{\omega }^{2j}+\cdots +c_{n-1}{\omega }^{(n-1)j})=\prod _{j=0}^{n-1}f({\omega }^j).}$$

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

• Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclicpermutation matrix${\displaystyle P}$:$${\displaystyle C=c_{0}I+c_{1}P+c_2{P}^2+\cdots +c_{n-1}{P}^{n-1}=f(P),}$$ where${\displaystyle P}$ is given by thecompanion matrix
• Theset of${\displaystyle n\times n}$ circulant matrices forms an${\displaystyle n}$-dimensionalvector space with respect to addition and scalar multiplication. This space can be interpreted as the space offunctions on thecyclic group oforder${\displaystyle n}$,${\displaystyle C_n}$, or equivalently as thegroup ring of${\displaystyle C_n}$.
• Circulant matrices form acommutative 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 anonsingular circulant matrix${\displaystyle A}$, itsinverse${\displaystyle A^{-1}}$ is also circulant. For a singular circulant matrix, itsMoore–Penrose pseudoinverse${\displaystyle A^{+}}$ is circulant.
• Thediscrete 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\le j,k\le 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}\mathrm{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 afast Fourier transform.^[3]

• Let${\displaystyle p(x)}$ be the (monic)characteristic polynomial of an${\displaystyle n\times n}$ circulant matrix${\displaystyle C}$. Then the scaledderivative$\frac{1}{n}{p}^{\prime }(x)$ is the characteristic polynomial of the following${\displaystyle (n-1)\times (n-1)}$ submatrix of${\displaystyle C}$: (see^[4] for theproof).

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

Consider vectors in${\displaystyle {\mathbb{R}}^n}$ as functions on theintegers 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 thecyclic group of order${\displaystyle n}$ (denoted${\displaystyle C_n}$ or${\displaystyle \mathbb{Z}/n\mathbb{Z}}$) geometrically, on (the vertices of) theregular${\displaystyle n}$-gon: this is a discrete analog to periodic functions on thereal line orcircle.

Then, from the perspective ofoperator theory, a circulant matrix is the kernel of a discreteintegral transform, namely theconvolution operator for the function${\displaystyle (c_0,c_1,\dots ,c_{n-1})}$; this is a discretecircular convolution. The formula for the convolution of the functions${\displaystyle (b_i):=(c_i)\ast (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^{\ast }}$-algebra of all circulant matrices withcomplex entries isisomorphic to the group${\displaystyle C^{\ast }}$-algebra of${\displaystyle \mathbb{Z}/n\mathbb{Z}.}$

For asymmetric 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.

The eigenvalues of anyreal symmetric matrix are real.The corresponding eigenvalues${\displaystyle \overrightarrow{\lambda }=\sqrt{n}\cdot F_n^{†}c}$ become:for${\displaystyle n}$even, andfor${\displaystyle n}$odd, where${\displaystyle \mathrm{\Re }z}$ denotes thereal part of${\displaystyle z}$.This can be further simplified by using the fact that${\displaystyle \mathrm{\Re }{\omega }_k^j=\mathrm{\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 ofbisymmetric matrices.

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

Ifn is even the first two rows necessarily takes the formin which the first element${\displaystyle r_3}$ in the top second half-row is real.

Ifn is odd we get

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 thecircular 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 thecircular convolution theorem, we can use thediscrete 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]}^{\mathrm{T}}.}$$

This algorithm is much faster than the standardGaussian elimination, especially if afast Fourier transform is used.

Ingraph theory, agraph ordigraph whoseadjacency matrix is circulant is called acirculant graph/digraph. Equivalently, a graph is circulant if itsautomorphism group contains a full-length cycle. TheMöbius ladders are examples of circulant graphs, as are thePaley graphs forfields ofprime order.

• Gray, R.M. (2006)."Toeplitz and circulant matrices: A review"(PDF).Foundations and Trends in Communications and Information Theory.2 (3):155–239.doi:10.1561/0100000006.
• IPython Notebook demonstrating properties of circulant matrices

• Numerical linear algebra
• Matrices (mathematics)
• Latin squares
• Determinants

• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata