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
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 a circulant matrix is equal to , where is the degree of .[2]
Other properties
We have
where is the 'cyclic permutation' matrix, a specific permutation matrix given by
The set of circulant matrices forms an -dimensionalvector 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, , or equivalently as the group ring of .
Circulant matrices form a commutative algebra, since for any two given circulant matrices and , the sum is circulant, the product is circulant, and .
Consequently the matrix diagonalizes. In fact, we have
where is the first column of . The eigenvalues of are given by the product . This product can be readily calculated by a fast Fourier transform.[3]
Let be the monic characteristic polynomial of an circulant matrix , and let be the derivative of . Then the polynomial is the monic characteristic polynomial of the following submatrix of :
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 , (i.e., as periodic bi-infinite sequences: ) or equivalently, as functions on the cyclic group of order ( or ) geometrically, on (the vertices of) the regular -gon: this is a discrete analog to periodic functions on the real line or circle.
which is the product of the vector by the circulant matrix for .
The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.
The -algebra of all circulant matrices with complex entries is isomorphic to the group -algebra of .
Symmetric circulant matrices
For a symmetric circulant matrix one has the extra condition that .
Thus it is defined by elements when is even and elements when is odd.
The eigenvalues of any real symmetric matrix are real.
The corresponding eigenvalues become:
for even, and
for odd .
This can be further simplified by using that .
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 circular convolution theorem, we can use the discrete Fourier transform to transform the cyclic convolution into component-wise multiplication