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 n\times n matrix \ C of the form

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

is called a circulant matrix.

A circulant matrix is fully specified by one vector, \ c. This appears in the first column of \ C. The other columns are rotations of it. The last row of \ C is \ c in reverse order, and the other rows are rotations of it.

[edit] Properties

The set of n\times 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 \ AB = BA.

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.

\ C = W \Lambda W^{-1} by eigendecomposition
\operatorname{det}(C) = \operatorname{det}\left(W \Lambda W^{-1}\right)
\operatorname{det}(C) = \operatorname{det}\left(W\right) \operatorname{det}\left(\Lambda\right) \operatorname{det}\left(W^{-1}\right)
\operatorname{det}(C) = \operatorname{det}\left(\Lambda\right) = \prod_{k=1}^{n} \lambda_k

where

The last term, \prod_{k=1}^{n} \lambda_k, is the product of the spectral values.

[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 \ C, and the vectors \ c, \ x and \ b 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

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

[edit] External links