An circulant matrix takes the form or the transpose of this 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, if lines are indexed from 0 to. The last row of is the vector 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 corresponding to the first row rather than the first column of the matrix; and possibly with a different direction of shift. The polynomial is called the associated polynomial of matrix.
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 is equal to, where is the degree of.
Let be the characteristic polynomial of an circulant matrix, and let be the derivative of. Then the polynomial is the characteristic polynomial of the following submatrix of :
.
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, or equivalently, as functions on the cyclic group of order geometrically, on the regular -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 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 determined by elements. The eigenvalues of any real symmetric matrix are real. The corresponding eigenvalues become: for even, and for odd, where denotes the real part of. This can be further simplified by using the fact that.
Complex symmetric circulant matrices
The complex version of the circulant matrix, ubiquitous in communications theory, is usually Hermitian. In this case 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 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 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 so that This algorithm is much faster than the standard Gaussian elimination, especially if a fast Fourier transform is used.
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.
