Circulant matrix
From Free net encyclopedia
In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted one 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.
Contents |
Definition
An <math>n\times n</math> matrix C of the form
- <math>
C= \begin{bmatrix} c_1 & c_2 & c_3 & \dots & c_n \\ c_n & c_1 & c_2 & & c_{n-1} \\ c_{n-1} & c_n & c_1 & & c_{n-2} \\ \vdots & & & \ddots & \vdots \\ c_2 & c_3 & c_4 & \dots & c_1 \end{bmatrix} </math>
is called a circulant matrix.
Properties
Circulant matrices form an algebra, since for any two given circulant matrices A and B, the sum A + B is circulant, the product AB is circulant, and <math>AB = BA</math>.
The matrix of eigenvectors of a circulant matrix is the matrix of the discrete Fourier transform of same dimension. Consequently, the eigenvalues of a circulant matrix can be readily calculated by the Fast Fourier transform (FFT).
Solving linear equations with 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 column 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>\mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})</math>
so that
- <math>\mathbf{x} = \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>
This algorithm is much faster than the standard Gaussian elimination, especially if a fast Fourier transform is used.
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.