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 can be quickly solved using the discrete Fourier transform.

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

[edit] Definition

An $n\times n$ matrix C of the form

$C= \begin{bmatrix} c_0 & c_{-1} & \dots & c_{2-n} & c_{1-n} \\ c_{1-n} & c_0 & c_{-1} & & c_{2-n} \\ \vdots & c_{1-n}& c_0 & \ddots & \vdots \\ c_{-2} & & \ddots & \ddots & c_{-1} \\ c_{-1} & c_{-2} & \dots & c_{1-n} & c_0 \\ \end{bmatrix}$

is called a circulant matrix.

[edit] Properties

The set of n×n circulant matrices forms an n dimensional vector space.

Circulant matrices form a commutative algebra, since for any two given circulant matrices A and B, the sum A + B is circulant, the product AB is circulant, and $A B = B A$ .

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).

[edit] Solving linear equations with circulant matrices

Given a matrix equation

$\mathbf{C} \mathbf{x} = \mathbf{b}$

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

$\mathbf{c} * \mathbf{x} = \mathbf{b}$

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{F}_{n}(\mathbf{c} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})$

so that

$\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 ].$

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.