Circulant matrix
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] Definition
An matrix of the form
is called a circulant matrix.
A circulant matrix is fully specified by one vector, . This appears in the first column of . The other columns are rotations of it. The last row of is in reverse order, and the other rows are rotations of it.
[edit] Properties
The set of circulant matrices forms an n-dimensional vector space.
Circulant matrices form a commutative algebra, since for any two given circulant matrices and , the sum is circulant, the product is circulant, and .
The eigenvectors of a circulant matrix of given size are the columns of the discrete Fourier transform matrix of the same size. Consequently, the eigenvalues of a circulant matrix can be readily calculated by a Fast Fourier transform (FFT).
If an FFT of the first row of a circulant matrix is performed then the determinant of the circulant matrix is the product of the spectral values.
- by eigendecomposition
where
- C is an circulant matrix
- W is the unitary discrete Fourier transform matrix
- Λ is a diagonal matrix with eigenvalues λk.
The last term, , is the product of the spectral values.
[edit] Solving linear equations with circulant matrices
Given a matrix equation
where is a circulant square matrix of size we can write the equation as the cyclic 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.
[edit] Application 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.