circulant matrix

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted on 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.

Definition

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

AB = BA

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

C is an N by N circulant matrix
W is the Fourier transform matrix
$\Lambda$ is a diagonal matrix of eigenvalues $\lambda_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 ( \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

<< Previous

Word Browser

Next >>

roundtable access
david berg
apple maggot
keith r. wright
labyrinthitis
star city, moscow
colonial heads of mali
soulmate
yeon gaesomun
d a d
heads of government of mali

danny invincible
germanism
domotic maid
yosakoi festival
endophyte
jean mermoz
bo gritz
velebit caves
velebit
jim corbett (hunter)
bashkardi

a. a. englander
butyl
khao yai national park
william michael rossetti
parliamentary borough
borough constituency
trivial name
godzilla (video game)
the growth of biological thought
the chinese high school
polytechnic university of puerto rico

1982, janine
hem
barad nimras
giuliano zaccardelli
marie
jose miguel class
pepe de luca
flacq
marquis who's who
vittorio bottego
antnio mascarenhas monteiro