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
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  circulant matrix  takes the form
A circulant matrix is fully specified by
one vector, , which appears as the first
column of . The remaining columns of 
are each cyclic permutations of the
vector  with offset equal to the column
index. The last row of  is the vector 
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.
The polynomial  is called the associated
polynomial of matrix .
Properties 
= Eigenvectors and eigenvalues =
The normalized eigenvectors of a
circulant matrix are given by
where  are the n-th roots of unity and 
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 circulant matrix can be
computed as:
Since taking transpose does not change
the eigenvalues of a matrix, an
equivalent formulation is
= Rank =
The rank of circulant matrix  is equal
to , where  is the degree of .
= Other properties =
We have
where P is the 'cyclic permutation'
matrix, a specific permutation matrix
given by
The set of  circulant matrices forms an
n-dimensional vector space; this can be
interpreted as the space of functions on
the cyclic group of order n,  or
equivalently the group ring.
Circulant matrices form a commutative
algebra, since for any two given
circulant matrices  and , the sum  is
circulant, the product  is circulant,
and .
The matrix U that is composed of the
eigenvectors of a circulant matrix is
related to the Discrete Fourier
transform and its Inverse transform:
Thus, the matrix  diagonalizes C. In
fact, we have
where  is the first column of . Thus,
the eigenvalues of  are given by the
product . 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  as functions on the
integers with period n, or equivalently,
as functions on the cyclic group of
order n, geometrically, on 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  this is a discrete circular
convolution. The formula for the
convolution of the functions  is
which is the product of the vector of 
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
where  is a circulant square matrix of
size  we can write the equation as the
circular convolution
where  is the first column of , and the
vectors ,  and  are cyclically extended
in each direction. Using the results of
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. 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 
External links 
R. M. Gray, Toeplitz and Circulant
Matrices: A Review
Weisstein, Eric W., "Circulant matrix",
MathWorld.
