Circulant matrix

Encyclopedia : C : CI : CIR : Circulant matrix

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

1 Definition
2 Properties
3 Solving linear equations with circulant matrices
4 Application in graph theory
5 External link

Definition

An [n\times n] matrix C of the form

[C=\beginc_1 & c_2 & c_3 & \dots & c_n \\c_n & c_1 & c_2 & & c_ \\c_ & c_n & c_1 & & c_ \\\vdots & & & \ddots & \vdots \\c_2 & c_3 & c_4 & \dots & c_1\end]

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 [AB = BA].

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

[\mathbf \mathbf = \mathbf]

where C is a circulant square matrix of size n we can write the equation as the cyclic convolution

[\mathbf * \mathbf = \mathbf]

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

[\mathcal_(\mathbf * \mathbf) = \mathcal_(\mathbf) \mathcal_(\mathbf) = \mathcal_(\mathbf)]

so that

[\mathbf = \mathcal_^ \left [ left (frac_n(mathbf))_}_n(mathbf))_} right )_}right ].]

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.

External link

[Toeplitz and Circulant Matrices: A Review, by R. M. Gray]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.