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.

For the symmetric graphs, see Circulant graph.

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.[1] They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group ${\displaystyle 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 ${\displaystyle n\times n}$ circulant matrix ${\displaystyle C}$ takes the form

${\displaystyle 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, ${\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 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}$ in reverse order, and the remaining rows are each cyclic permutations of the last row.

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 matrix ${\displaystyle C}$.

Properties

Eigenvectors and eigenvalues

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

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

where ${\displaystyle \omega _{j}=\exp \left(i{\tfrac {2\pi j}{n}}\right)}$ are the ${\displaystyle n}$-th roots of unity and ${\displaystyle 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

${\displaystyle \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,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:

${\displaystyle \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 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 _{j}^{2}+\dots +c_{n-1}\omega _{j}^{n-1})=\prod _{j=0}^{n-1}f(\omega _{j}).}$

Rank

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

Other properties

• We have

${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\ldots +c_{n-1}P^{n-1}=f(P).}$

where ${\displaystyle P}$ is the cyclic permutation matrix, given by

${\displaystyle 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 ${\displaystyle n\times n}$ circulant matrices forms an ${\displaystyle 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, ${\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}$.
• 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},\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<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]

• 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 ${\displaystyle {\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}&\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[4] for proof).

Analytic interpretation

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

Consider vectors in ${\displaystyle \mathbf {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}$ (${\displaystyle C_{n}}$ or ${\displaystyle \mathbf {Z} /n\mathbf {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 \mathbf {Z} /n\mathbf {Z} }$.

Symmetric circulant matrices

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}&\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:

${\displaystyle \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 ${\displaystyle n}$ even, and

${\displaystyle \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 ${\displaystyle n}$, where ${\displaystyle \Re z}$ denotes the real part of ${\displaystyle z}$. This can be further simplified by using the fact that ${\displaystyle \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 ${\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 complex symmetric condition.

Applications

In linear equations

Given a matrix equation

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

References

1. Davis, Philip J., Circulant Matrices, Wiley, New York, 1970 ISBN 0471057711
2. A. W. Ingleton (1956). "The Rank of Circulant Matrices". J. London Math. Soc. s1-31 (4): 445–460. doi:10.1112/jlms/s1-31.4.445.
3. Golub, Gene H.; Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9
4. Kushel, Olga; Tyaglov, Mikhail (July 15, 2016), "Circulants and critical points of polynomials", Journal of Mathematical Analysis and Applications, 439 (2): 634–650, arXiv:1512.07983, doi:10.1016/j.jmaa.2016.03.005, ISSN 0022-247X
5. Tee, G J (2007). "Eigenvectors of Block Circulant and Alternating Circulant Matrices". New Zealand Journal of Mathematics. 36: 195–211.

External links

• R. M. Gray, Toeplitz and Circulant Matrices: A Review
• Weisstein, Eric W. "Circulant Matrix". MathWorld.
• IPython Notebook demonstrating properties of circulant matrices