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 formula_1 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 formula_2 circulant matrix formula_3 takes the form
or the transpose of this form (by choice of notation).
A circulant matrix is fully specified by one vector, formula_5, which appears as the first column (or row) of formula_3. The remaining columns (and rows, resp.) of formula_3 are each cyclic permutations of the vector formula_5 with offset equal to the column (or row, resp.) index, if lines are indexed from 0 to formula_9. (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of formula_3 is the vector formula_5 shifted by one in reverse.
Different sources define the circulant matrix in different ways, for example as above, or with the vector formula_5 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 formula_13 is called the "associated polynomial" of matrix formula_3.
Properties.
Eigenvectors and eigenvalues.
The normalized eigenvectors of a circulant matrix are the Fourier modes, namely,
where formula_16 is a primitive formula_17-th root of unity and formula_18 is the imaginary unit.
The corresponding eigenvalues are then given by
Determinant.
As a consequence of the explicit formula for the eigenvalues above, 
the determinant of a circulant matrix can be computed as:
Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is
Rank.
The rank of a circulant matrix formula_22 is equal to formula_23, where formula_24 is the degree of the polynomial formula_25.
Other properties.
(see for the proof).
Analytic interpretation.
Circulant matrices can be interpreted geometrically, which explains the connection with the discrete Fourier transform.
Consider vectors in formula_58 as functions on the integers with period formula_17, (i.e., as periodic bi-infinite sequences: formula_60) or equivalently, as functions on the cyclic group of order formula_17 (formula_1 or formula_63) geometrically, on (the vertices of) the regular : 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 formula_64; this is a discrete circular convolution. The formula for the convolution of the functions formula_65 is
which is the product of the vector formula_67 by the circulant matrix for formula_68.
The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.
The formula_69-algebra of all circulant matrices with complex entries is isomorphic to the group formula_69-algebra of formula_63.
Symmetric circulant matrices.
For a symmetric circulant matrix formula_3 one has the extra condition that formula_73. 
Thus it is determined by formula_74 elements. 
The eigenvalues of any real symmetric matrix are real.
The corresponding eigenvalues become:
for formula_17 even, and
for formula_17 odd, where formula_80 denotes the real part of formula_81.
This can be further simplified by using the fact that formula_82.
Complex symmetric circulant matrices.
The complex version of the circulant matrix, ubiquitous in communications theory, is usually Hermitian. In this case formula_83 and its determinant and all eigenvalues are real.
If "n" is even the first two rows necessarily takes the form
in which the first element formula_85 in the top second half-row is real.
If "n" is odd we get
Tee has discussed constraints on the eigenvalues for the complex symmetric condition.
Applications.
In linear equations.
Given a matrix equation
where formula_3 is a circulant square matrix of size formula_17 we can write the equation as the circular convolution
where formula_5 is the first column of formula_3, and the vectors formula_5, formula_94 and formula_95 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
so that
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.