Circulant matrix

In linear algebra is called a matrix as cyclical or circulant if its rows and columns meet a certain Permutationsbedingung. Due to the below link with the discrete fast Fourier transform cyclic matrices find applications in fast solution methods such as for Toeplitz matrices.

A circulant matrix is a special Toeplitz matrix, wherein each row vector is shifted relative to the overlying row vector for an entry to the right. In other words, it is an example of a Latin square if all rows are distinct elements. Systems of equations with circulant matrices can be solved by discrete Fourier transform simple.

Definition

A square matrix is called cyclic if it numbers the shape

Possesses. Each column is obtained by cyclically shifting the left of it are, therefore, also the rows are cyclically shifted. Cyclic matrices are special Toeplitz matrix in which the elements are connected at and above the main diagonal.

Properties

All cyclic ( circulant ) matrices are polynomials of simple cyclic matrix

Because it applies to the above introduced matrix

The polynomial of degree. Because the ones in the matrix are shifted respectively to positions down (cyclic, coming up back in ). Because of this property, all have the same cyclic matrices of eigenvectors based, namely the base. The matrix is a special companion matrix, its characteristic polynomial is the cyclotomic

Therefore, the matrix has distinct eigenvalues ​​exactly lying on the complex unit circle at the same distance,

The -th eigenvector has the form and all the eigenvectors form a Vandermonde matrix ( see Article companion matrix ). This Vandermonde matrix is ​​then the eigenvector matrix of, while having the values ​​of the eigenvalues ​​.

Cross-connections

The product of the cyclic matrix by a vector is

It was agreed that indexes are mapped outside of cyclically again in this index range ( by modulo calculation: ). Thus, this matrix-vector product in the form of a discrete convolution operation, and therefore the product of the matrix or its inverse for large by means of the Fast Fourier Transform (FFT) can be carried out rapidly, in particular when the dimension is a power.

Solving systems of equations with cyclic / circulant matrices

Given a system of equations of the form

With the above circulant square matrix of size. Then, the equation corresponds to a cyclic convolution:

However, being unknown. The vector is the first line of. Then we can write:

Wherein, in the product of the Fourier coefficients: the vectors are multiplied by each other as components. The Fourier transform of the solution thus obtained by component-wise division, and the inverse transform then yields the solution itself:

This approach is much faster than the Gauss elimination method, particularly when a fast Fourier transform is used.