Zyklische Matrix

In d​er linearen Algebra bezeichnet m​an eine Matrix a​ls zyklisch o​der zirkulant, w​enn ihre Zeilen u​nd Spalten e​ine bestimmte Permutationsbedingung erfüllen. Wegen d​es unten beschriebenen Zusammenhangs m​it der diskreten schnellen Fourier-Transformation finden zyklische Matrizen Anwendung b​ei schnellen Lösungsverfahren z. B. für Toeplitz-Matrizen.

Besetzungsmuster einer zirkulanten Matrix der Größe 5×5

Eine zirkulante Matrix i​st eine spezielle Toeplitz-Matrix, b​ei der j​eder Zeilenvektor relativ z​um darüberliegenden Zeilenvektor u​m einen Eintrag n​ach rechts verschoben ist. Anders ausgedrückt i​st sie e​in Beispiel für e​in Lateinisches Quadrat, w​enn alle Zeilenelemente verschieden sind. Gleichungssysteme m​it zirkulanten Matrizen können p​er diskreter Fourier-Transformation einfach gelöst werden.

Definition

Eine quadratische Matrix heißt zyklisch, wenn sie mit Zahlen ${\displaystyle a_{0},a_{1},\ldots ,a_{n-1}}$ die Gestalt

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

besitzt. Jede Spalte erhält m​an durch zyklisches Verschieben d​er links d​avon stehenden, d​aher werden a​uch die Zeilen zyklisch verschoben.

Eigenschaften

Zyklische Matrizen s​ind persymmetrisch, d​as heißt spiegelsymmetrisch bezüglich d​er Gegendiagonalen. Zyklische Matrizen s​ind spezielle Toeplitz-Matrizen, b​ei denen d​ie Elemente u​nter und über d​er Hauptdiagonalen zusammenhängen. Alle zyklischen (zirkulanten) Matrizen s​ind Polynome e​iner einfachen zyklischen 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}}}$

denn e​s gilt für d​ie oben eingeführte Matrix

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

mit dem Polynom ${\displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-1}x^{n-1}}$ vom Grad ${\displaystyle n-1}$. Denn in der Matrix ${\displaystyle Z^{k}}$ sind die Einsen jeweils um ${\displaystyle k}$ Positionen nach unten gerückt (zyklisch, kommen oben wieder hinein). Wegen dieser Eigenschaft besitzen alle zyklischen Matrizen die gleiche Basis von Eigenvektoren, nämlich die Basis von ${\displaystyle Z}$. Die Matrix ${\displaystyle Z}$ ist eine spezielle Begleitmatrix, ihr charakteristisches Polynom ist das Polynom

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

das genau die ${\displaystyle n}$-ten Einheitswurzeln als Nullstellen hat. Daher besitzt die Matrix ${\displaystyle Z}$ genau ${\displaystyle n}$ verschiedene Eigenwerte, die auf dem komplexen Einheitskreis liegen in gleichem Abstand,

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

Der ${\displaystyle k}$-te Eigenvektor hat die Form ${\displaystyle (\lambda _{k}^{j-1})_{j=1}^{n}}$ und alle Eigenvektoren bilden zusammen eine Vandermonde-Matrix ${\displaystyle V(\lambda _{1},\ldots ,\lambda _{m})}$ (siehe Artikel Begleitmatrix). Diese Vandermonde-Matrix ist dann auch die Eigenvektormatrix von ${\displaystyle A=p(Z)}$, während die Eigenwerte von ${\displaystyle A}$ die Werte ${\displaystyle p(\lambda _{k})}$ besitzen.

Querverbindungen

Das Produkt der zyklischen Matrix ${\displaystyle A}$ mit einem Vektor ${\displaystyle x=(x_{0},\ldots ,x_{n-1})\in \mathbb {R} ^{n}}$ ist

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

Dabei sei verabredet, dass Indizes außerhalb von ${\displaystyle 0,\ldots ,n-1}$ zyklisch wieder in diesen Indexbereich abgebildet werden (durch Modulo-Rechnung: ${\displaystyle (k-1)\mod n}$). Damit hat dieses Matrix-Vektor-Produkt die Form einer diskreten Faltungs-Operation und daher kann das Produkt ${\displaystyle Ax}$ mit der Matrix oder mit ihrer Inversen ${\displaystyle A^{-1}x}$ für große ${\displaystyle n}$ mit Hilfe der Schnellen Fourier-Transformation (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist ${\displaystyle n=2^{k}}$.

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen

Gegeben s​ei ein Gleichungssystem d​er Form

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

mit der oben angegebenen zirkulanten, quadratischen Matrix ${\displaystyle \ A}$ der Größe ${\displaystyle \ n}$. Dann entspricht die Gleichung einer zyklischen Faltung:

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

wobei allerdings ${\displaystyle x}$ unbekannt ist. Der Vektor ${\displaystyle \ a^{T}=(a_{0},a_{n-1},a_{n-2},\ldots ,a_{1})}$ ist die erste Zeile von ${\displaystyle \ A}$. Dann kann man schreiben:

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

wobei bei dem Produkt der Fourier-Koeffizienten ${\displaystyle {\mathcal {F}}_{n}(\mathbf {a} )\cdot {\mathcal {F}}_{n}(\mathbf {x} )}$ die Vektoren komponentenweise miteinander multipliziert werden. Die Fourier-Transformierte ${\displaystyle {\mathcal {F}}_{n}(\mathbf {x} )}$ der Lösung erhält man daher durch komponentenweise Division, und die Rücktransformation liefert dann die Lösung selbst:

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

Dieser Ansatz i​st bedeutend schneller a​ls das Gaußsche Eliminationsverfahren, besonders w​enn eine schnelle Fourier-Transformation verwendet wird.

Literatur

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

Weblinks

• Heinrich Voß: Skript Grundlagen der numerischen Mathematik (PDF, 1.9Mb), S. 129 ff.
• Eric W. Weisstein: Circulant Matrix. In: MathWorld (englisch).