|
In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted on element to the right relative to the preceding row vector. In other words a circulant matrix is an example of a Latin square. In numerical analysis circulant matrices are important because they can be quickly solved using the discrete fourier transform.
Definition
A <math>m\times n<math> matrix C of the form
- <math>
C=
\begin{bmatrix}
c_0 & c_1 & c_2 & \dots & c_{n-1} \\
c_{n-1} & c_0 & c_1 & & c_{n-2} \\
c_{n-2} & c_{n-1} & c_0 & & c_{n-3} \\
\vdots & & & \ddots & \vdots \\
c_1 & c_2 & c_3 & \dots & c_0
\end{bmatrix}
<math>
is called a circulant matrix.
Properties
Circulant matrices form an algebra, since for any two given circulant matrices A and B then the sum A+B is circulant, product AB is circulant, and <math>AB = BA<math>.
The eigenvectors of a (square) circulant matrix of given size is fixed, that is, the eigenmatrix of a circulant matrix is the Fourier transform matrix of the same size. Consequently, the eigenvalues of a circulant matrix can be readily calculated by the Fast Fourier transform (FFT).
If the FFT of the first row of a circulant matrix is performed then the determinant of the circulant matrix is the multiplication of the spectral values.
- <math>C = W \Lambda W^{-1}<math> by eigendecomposition
- <math>\operatorname{det}(C) = \operatorname{det}\left(W * \Lambda W^{-1}\right)<math>
- <math>\operatorname{det}(C) = \operatorname{det}\left(W\right) \operatorname{det}\left(\Lambda\right) \operatorname{det}\left(W^{-1}\right)<math>
- <math>\operatorname{det}(C) = \operatorname{det}\left(\Lambda\right) = \prod_{k=1}^{N} \lambda_k<math>
where
- C is an N by N circulant matrix
- W is the Fourier transform matrix
- <math>\Lambda<math> is a diagonal matrix of eigenvalues <math>\lambda_k<math>
The last term, <math>\Pi_{k=1}^{N} \lambda_k<math>, is the same thing as multiplication of the spectral values.
Solving circulant matrices
Given a matrix equation
- <math>
\mathbf{C} \mathbf{x} = \mathbf{b}
<math>
where C is a circulant square matrix of size n we can write the equation as the cyclic convolution
- <math>\mathbf{c} * \mathbf{x} = \mathbf{b}<math>
where c is the first row of the circulant matrix C and the vectors c, x and b are cyclically extended in each direction. Using the discrete Fourier transform we can transform the cyclic convolution into component-wise multiplication
- <math>n \mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = n \mathcal{F}_{n}(c) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})<math>
so that
- <math>\mathbf{x} = \frac{1}{n} \mathcal{F}_{n}^{-1}
\left [
\left (
\frac{(\mathcal{F}_n(\mathbf{b})_{\nu}}
{(\mathcal{F}_n(\mathbf{c}))_{\nu}}
\right )_{\nu \in \mathbf{Z}}
\right ]
<math>
Depending on the fast Fourier transform used this algorithm is much faster than the standard Gaussian elimination.
External link
Toeplitz and Circulant Matices: A Review, by R. M. Gray (http://www-ee.stanford.edu/~gray/toeplitz.pdf)
| 
