In linear algebra, a circulant matrix is a square matrix in which all rows are composed of the same elements and each row is rotated one element to the right relative to the preceding row. It is a particular kind of Toeplitz matrix.
or the transpose of this form (by choice of notation). If each is a square matrix, then the matrix is called a block-circulant matrix.
A circulant matrix is fully specified by one vector, , which appears as the first column (or row) of . The remaining columns (and rows, resp.) of are each cyclic permutations of the vector with offset equal to the column (or row, resp.) index, if lines are indexed from to . (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of is the vector shifted by one in reverse.
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 (which is sometimes called an anti-circulant matrix).
The polynomial is called the associated polynomial of the matrix .
Propertiesedit
Eigenvectors and eigenvaluesedit
The normalized eigenvectors of a circulant matrix are the Fourier modes, namely,
(This can be understood by realizing that multiplication with a circulant matrix implements a convolution. In Fourier space, convolutions become multiplication. Hence the product of a circulant matrix with a Fourier mode yields a multiple of that Fourier mode, i.e. it is an eigenvector.)
The matrix that is composed of the eigenvectors of a circulant matrix is related to the discrete Fourier transform and its inverse transform:
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] Conversely, for any diagonal matrix , the product is circulant.
Let be the (monic) characteristic polynomial of an circulant matrix . Then the scaled derivative is the 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 (denoted or ) geometrically, on (the vertices of) the regular -gon: this is a discrete analog to periodic functions on the real line or circle.
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[5] has discussed constraints on the eigenvalues for the Hermitian condition.
Applicationsedit
In linear equationsedit
Given a matrix equation
where is a circulant 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