# Circulant matrix

In linear algebra, a circulant matrix is a square matrix in which each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplitz matrix.

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 $C_{n}$ 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

An $n\times n$ circulant matrix $C$ takes the form

$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}}$ or the transpose of this form (by choice of notation).

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

Different sources define the circulant matrix in different ways, for example as above, or with the vector $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 $f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}$ is called the associated polynomial of matrix $C$ .

## Properties

### Eigenvectors and eigenvalues

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

$v_{j}={\frac {1}{\sqrt {n}}}(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}),\quad j=0,1,\ldots ,n-1,$ where $\omega =\exp \left({\tfrac {2\pi i}{n}}\right)$ is a primitive $n$ -th root of unity and $i$ is the imaginary unit.

(This can be understood by realizing that a circulant matrix implements a convolution.)

The corresponding eigenvalues are then given by

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

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

$\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

$\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}).$ ### Rank

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

### Other properties

• Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic permutation matrix $P$ :
$C=c_{0}I+c_{1}P+c_{2}P^{2}+\ldots +c_{n-1}P^{n-1}=f(P),$ where $P$ is 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}}.$ • The set of $n\times n$ circulant matrices forms an $n$ -dimensional vector space with respect to their standard addition and scalar multiplication. This space can be interpreted as the space of functions on the cyclic group of order n, $C_{n}$ , or equivalently as the group ring of $C_{n}$ .
• Circulant matrices form a commutative algebra, since for any two given circulant matrices $A$ and $B$ , the sum $A+B$ is circulant, the product $AB$ is circulant, and $AB=BA$ .
• The matrix $U$ that is composed of the eigenvectors of a circulant matrix is related to the discrete Fourier transform and its inverse transform:
$U_{n}^{*}={\frac {1}{\sqrt {n}}}F_{n},\quad {\text{and}}\quad U_{n}={\frac {1}{\sqrt {n}}}F_{n}^{-1},\quad {\text{where}}\quad F_{n}=(f_{jk})\quad {\text{with}}\quad f_{jk}=e^{-2jk\pi i/n},\quad {\text{for}}\quad 0\leq j,k Consequently the matrix $U_{n}$ diagonalizes $C$ . In fact, we have
$C=U_{n}\operatorname {diag} (F_{n}c)U_{n}^{*}={\frac {1}{n}}F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},$ where $c$ is the first column of $C$ . The eigenvalues of $C$ are given by the product $F_{n}c$ . This product can be readily calculated by a fast Fourier transform.
• Let $p(x)$ be the (monic) characteristic polynomial of an $n\times n$ circulant matrix $C$ , and let $p'(x)$ be the derivative of $p(x)$ . Then the polynomial ${\frac {1}{n}}p'(x)$ is the characteristic polynomial of the following $(n-1)\times (n-1)$ submatrix of $C$ :
$C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\dots &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}&\dots &c_{1}&c_{0}\\\end{bmatrix}}$ (see for proof).

## 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 $(a_{i})$ by the circulant matrix for $(c_{i})$ .

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

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

## Symmetric circulant matrices

For a symmetric circulant matrix $C$ one has the extra condition that $c_{n-i}=c_{i}$ . Thus it is determined by $\lfloor n/2\rfloor +1$ elements.

$C={\begin{bmatrix}c_{0}&c_{1}&\dots &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}&\dots &c_{1}&c_{0}\\\end{bmatrix}}.$ The eigenvalues of any real symmetric matrix are real. The corresponding eigenvalues become:

$\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\ldots +2c_{n/2-1}\Re \omega _{j}^{n/2-1}+c_{n/2}\omega _{j}^{n/2}$ for $n$ even, and

$\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\ldots +2c_{(n-1)/2}\Re \omega _{j}^{(n-1)/2}$ for odd $n$ , where $\Re z$ denotes the real part of $z$ . This can be further simplified by using the fact that $\Re \omega _{j}^{k}=\cos(2\pi jk/n)$ .

## Complex symmetric circulant matrices

The complex version of the circulant matrix, ubiquitous in communications theory, is usually Hermitian. In this case $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

${\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 $r_{3}$ in the top second half-row is real.

If n is odd we get

${\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 has discussed constraints on the eigenvalues for the complex symmetric condition.

## Applications

### In linear equations

Given a matrix equation

$\mathbf {C} \mathbf {x} =\mathbf {b} ,$ where $C$ is a circulant square matrix of size $n$ we can write the equation as the circular convolution

$\mathbf {c} \star \mathbf {x} =\mathbf {b} ,$ where $c$ is the first column of $C$ , and the vectors $c$ , $x$ and $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

${\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]^{\rm {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.