Cyclic matrix

Occupation pattern of a circulating matrix of size 5 × 5

In linear algebra , a matrix is said to be cyclic or circular if its rows and columns meet a certain permutation condition. Because of the connection with the discrete fast Fourier transform described below, cyclic matrices are used in fast solution methods, e.g. B. for Toeplitz matrices .

A circular matrix is ​​a special Toeplitz matrix in which each row vector is shifted one entry to the right relative to the row vector above it. In other words, it is an example of a Latin square when all the line elements are different. Systems of equations with circulating matrices can easily be solved using discrete Fourier transformation .

definition

A square matrix is ​​called cyclic if it has the shape with numbers ${\displaystyle a_{0},a_{1},\ldots ,a_{n-1}}$

${\displaystyle A:={\begin{pmatrix}a_{0}&a_{n-1}&a_{n-2}&\ldots &a_{1}\\a_{1}&a_{0}&a_{n-1}&\ldots &a_{2}\\a_{2}&a_{1}&a_{0}&\ldots &a_{3}\\&\ddots &\ddots &\ddots \\a_{n-1}&a_{n-2}&a_{n-3}&\ldots &a_{0}\end{pmatrix}}}$

owns. Each column is obtained by cyclically shifting the one to the left, therefore the lines are also shifted cyclically.

properties

Cyclic matrices are persymmetric , that is, mirror-symmetric with respect to the opposite diagonals . Cyclic matrices are special Toeplitz matrices in which the elements below and above the main diagonal are connected. All cyclic (circulant) matrices are polynomials of a simple cyclic matrix

${\displaystyle Z:={\begin{pmatrix}0&0&0&\ldots &0&1\\1&0&0&\ldots &0&0\\0&1&0&\ldots &0&0\\&&\ddots &\ddots &\ddots \\0&0&0&\ldots &1&0\end{pmatrix}}}$

because it applies to the matrix introduced above

${\displaystyle A=a_{0}I+a_{1}Z+a_{2}Z^{2}+\ldots +a_{n-1}Z^{n-1}=p(Z)}$

with the polynomial of degree . Because in the matrix the ones have moved down by positions (cyclically, come back in at the top). Because of this property, all cyclic matrices have the same basis of eigenvectors , namely the basis of . The matrix is a special accompanying matrix ; its characteristic polynomial is the polynomial ${\displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-1}x^{n-1}}$ ${\displaystyle n-1}$ ${\displaystyle Z^{k}}$ ${\displaystyle k}$ ${\displaystyle Z}$ ${\displaystyle Z}$

${\displaystyle \!\,\det(\lambda I-Z)=\lambda ^{n}-1,}$

that has exactly the -th roots of unity as zeros. Therefore the matrix has exactly different eigenvalues , which lie on the complex unit circle at the same distance, ${\displaystyle n}$ ${\displaystyle Z}$ ${\displaystyle n}$

${\displaystyle \lambda _{k}=e^{2\pi i(k-1)/n},\ k=1,\ldots ,n.}$

The -th eigenvector has the form and all eigenvectors together form a Vandermonde matrix (see article accompanying matrix ). This Vandermonde matrix is ​​then also the eigenvector matrix of , while the eigenvalues ​​of have the values . ${\displaystyle k}$ ${\displaystyle (\lambda _{k}^{j-1})_{j=1}^{n}}$ ${\displaystyle V(\lambda _{1},\ldots ,\lambda _{m})}$ ${\displaystyle A=p(Z)}$ ${\displaystyle A}$ ${\displaystyle p(\lambda _{k})}$

Cross connections

The product of the cyclic matrix with a vector is ${\displaystyle A}$ ${\displaystyle x=(x_{0},\ldots ,x_{n-1})\in \mathbb {R} ^{n}}$

${\displaystyle Ax={\Big (}\sum _{j=0}^{n-1}a_{k-j}x_{j}{\Big )}_{k=0}^{n-1}.}$

It should be agreed that indices outside of this are cyclically mapped back into this index area (by modulo calculation:) . This matrix-vector product has the form of a discrete convolution operation and therefore the product with the matrix or with its inverse for large can be carried out quickly with the help of the Fast Fourier Transform (FFT), especially if the dimension is a power of two . ${\displaystyle 0,\ldots ,n-1}$ ${\displaystyle (k-1)\mod n}$ ${\displaystyle Ax}$ ${\displaystyle A^{-1}x}$ ${\displaystyle n}$ ${\displaystyle n=2^{k}}$

Solving systems of equations with cyclic / circulant matrices

A system of equations of the form is given

${\displaystyle \ \mathbf {A} \mathbf {x} =\mathbf {b} ,}$

with the above circulating, square matrix of size . Then the equation corresponds to a cyclic convolution : ${\displaystyle \ A}$ ${\displaystyle \ n}$

${\displaystyle \ \mathbf {a} *\mathbf {x} =\mathbf {b} ,}$

although is unknown. The vector is the first line of . Then you can write: ${\displaystyle x}$ ${\displaystyle \ a^{T}=(a_{0},a_{n-1},a_{n-2},\ldots ,a_{1})}$ ${\displaystyle \ A}$

${\displaystyle \ {\mathcal {F}}_{n}(\mathbf {a} *\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {a} )\cdot {\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}$,

where in the case of the product of the Fourier coefficients, the vectors are multiplied with one another component by component. The Fourier transform of the solution is therefore obtained by dividing it component-wise, and the inverse transform then yields the solution itself: ${\displaystyle {\mathcal {F}}_{n}(\mathbf {a} )\cdot {\mathcal {F}}_{n}(\mathbf {x} )}$ ${\displaystyle {\mathcal {F}}_{n}(\mathbf {x} )}$

${\displaystyle \ \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {a} ))_{\nu }}}\right)_{\nu \in \mathbf {Z} }\right].}$

This approach is significantly faster than the Gaussian elimination method , especially when a fast Fourier transform is used.

literature

• Robert M. Gray : Toeplitz and Circulant Matrices: A Review . Now Publishers (new edition), 2006, ISBN 9781933019239
• Philipp J. Davis : Circulant Matrices . Wiley, 1979

Web links

• Heinrich Voß: Script Fundamentals of Numerical Mathematics (PDF, 1.9Mb) , p. 129 ff.
• Eric W. Weisstein : Circulant Matrix . In: MathWorld (English).