BIGpedia - Circulant matrix - Encyclopedia and Dictionary Online

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 circulant matrices

4 External link

Definition

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

$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}$

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 $A B = B A$ .

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.

C = W Λ 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

C is an N by N circulant matrix
W is the Fourier transform matrix
$Λ$ is a diagonal matrix of eigenvalues $λ k .$

The last term, $\Pi_{k=1}^{N} \lambda_k$ , is the same thing as multiplication of the spectral values.

Solving 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 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

$n \mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = n \mathcal{F}_{n}(c) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})$

so that

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

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

Categories: Numerical linear algebra | Matrices