# Circulant matrix

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence linear equations that contain them may be quickly solved using a fast Fourier transform. They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group $\mathbb {Z} /n\mathbb {Z}$ and hence frequently appear in formal descriptions of spatially invariant linear operations. In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard.

## Definition

$C={\begin{bmatrix}c_{0}&c_{n-1}&\dots &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}&\dots &c_{1}&c_{0}\\\end{bmatrix}}.$ A circulant matrix is fully specified by one vector, $\ c$ , which appears as the first column of $\ C$ . The remaining columns of $\ C$ are each cyclic permutations of the vector $\ c$ with offset equal to the column index. The last row of $\ C$ is the vector $\ c$ in reverse order, and the remaining rows are each cyclic permutations of the last row. Note that different sources define the circulant matrix in different ways, for example with the coefficients corresponding to the first row rather than the first column of the matrix, or with a different direction of shift.

## Properties

### Eigenvectors and eigenvalues

The normalized eigenvectors of a circulant matrix are given by

$v_{j}={\frac {1}{\sqrt {n}}}(1,~\omega _{j},~\omega _{j}^{2},~\ldots ,~\omega _{j}^{n-1})^{T},\quad j=0,1,\ldots ,n-1,$ The corresponding eigenvalues are then given by

$\lambda _{j}=c_{0}+c_{n-1}\omega _{j}+c_{n-2}\omega _{j}^{2}+\ldots +c_{1}\omega _{j}^{n-1},\qquad j=0\ldots n-1.$ ### Determinant

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

$\mathrm {det} (C)=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega _{j}+c_{n-2}\omega _{j}^{2}+\dots +c_{1}\omega _{j}^{n-1}).$ Since taking transpose does not change the eigenvalues of a matrix, an equivalent formulation is

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

• We have
$C=c_{0}I+c_{1}P+c_{2}P^{2}+\ldots +c_{n-1}P^{n-1}=f(P).$ where P is the 'cyclic permutation' matrix, a specific permutation matrix given by
$P={\begin{bmatrix}0&0&\ldots &0&1\\1&0&\ldots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\ldots &0&1&0\end{bmatrix}}.$ $U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\sqrt {n}}F_{n}^{-1},\quad {\text{where}}\quad F_{n}=(f_{jk})\quad {\text{with}}\quad f_{jk}=\mathrm {e} ^{-2jk\pi \mathrm {i} /n},\quad {\text{for}}\quad 0\leq j,k Thus, the matrix $U_{n}$ diagonalizes C. In fact, we have
$C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},$ where $c\!\,$ is the first row of $C\,\!$ . Thus, the eigenvalues of $C$ are given by the product $\ F_{n}c$ . This product can be readily calculated by a Fast Fourier transform.

## Analytic interpretation

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

Consider vectors in $\mathbf {R} ^{n}$ as functions on the integers with period n, (i.e., as periodic bi-infinite sequences: $\dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots$ ) or equivalently, as functions on the cyclic group of order n, ($C_{n}$ or $\mathbf {Z} /n\mathbf {Z}$ ) geometrically, on (the vertices of) the regular 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 $(c_{0},c_{1},\dots ,c_{n-1});$ this is a discrete circular convolution. The formula for the convolution of the functions $(b_{i}):=(c_{i})*(a_{i})$ is

$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 of $a_{i}$ by the circulant matrix.

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

## Applications

### In linear equations

Given a matrix equation

$\ \mathbf {C} \mathbf {x} =\mathbf {b} ,$ $\ \mathbf {c} \star \mathbf {x} =\mathbf {b} ,$ $\ {\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

$\ \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\nu \in \mathbf {Z} }\right]^{T}.$ This algorithm is much faster than the standard Gaussian elimination, especially if a fast Fourier transform is used.

### In graph theory

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.