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. Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (or linear spaces), linear transformations, and systems of linear equations. ... In the mathematical discipline of linear algebra, a Toeplitz matrix, named after Otto Toeplitz, or diagonal constant matrix is a special kind of matrix where each descending diagonal from left to right is constant. ... A Latin square is an n × n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column. ... Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ...

Definition

An matrix C of the form

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. Algebra is a branch of mathematics, which studies structure and quantity. ...

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). In linear algebra, the eigenvectors (from the German eigen meaning inherent, characteristic) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ... The Fourier transform, named after Joseph Fourier, is an integral transform that re-expresses a function in terms of sinusoidal basis functions, i. ... In linear algebra, a scalar λ is called an eigenvalue (in some older texts, a characteristic value) of a linear mapping A if there exists a nonzero vector x such that Ax=λx. ... A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...

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. In linear algebra, a determinant is a function depending on n that associates a scalar det(A) to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...

C = WΛW ^{− 1} by eigendecomposition

where

• C is an N by N circulant matrix
• W is the unitary discrete Fourier transform matrix
• Λ is a diagonal matrix of eigenvalues λ_k.

The last term, , is the same thing as multiplication of the spectral values. In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ...

Solving circulant matrices

Given a matrix equation

where C is a circulant square matrix of size n we can write the equation as the cyclic convolution For the computer science usage see convolution (computer science) . In mathematics and in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version...

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 In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ...

so that

Depending on the fast Fourier transform used this algorithm is much faster than the standard Gaussian elimination. A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan (for many, Gaussian elimination is regarded as the front half of the complete Gauss-Jordan elimination), is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining...

External link

Toeplitz and Circulant Matices: A Review, by R. M. Gray