Zyklische Matrix

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

In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant, wenn ihre Zeilen und Spalten eine bestimmte Permutationsbedingung erfüllen. Wegen des unten beschriebenen Zusammenhangs mit der diskreten schnellen Fourier-Transformation finden zyklische Matrizen Anwendung bei schnellen Lösungsverfahren z. B. für Toeplitz-Matrizen.

Eine zirkulante Matrix ist eine spezielle Toeplitz-Matrix, bei der jeder Zeilenvektor relativ zum darüberliegenden Zeilenvektor um einen Eintrag nach rechts verschoben ist. Anders ausgedrückt ist sie ein Beispiel für ein Lateinisches Quadrat, wenn alle Zeilenelemente verschieden sind. Gleichungssysteme mit zirkulanten Matrizen können per diskreter Fourier-Transformation einfach gelöst werden.

Definition

Eine quadratische Matrix heißt zyklisch, wenn sie mit Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_0,a_1,\ldots,a_{n-1}} die Gestalt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 man durch zyklisches Verschieben der links davon stehenden, daher werden auch die Zeilen zyklisch verschoben.

Eigenschaften

Zyklische Matrizen sind persymmetrisch, das heißt spiegelsymmetrisch bezüglich der Gegendiagonalen. Zyklische Matrizen sind spezielle Toeplitz-Matrizen, bei denen die Elemente unter und über der Hauptdiagonalen zusammenhängen. Alle zyklischen (zirkulanten) Matrizen sind Polynome einer einfachen zyklischen Matrix

$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 es gilt für die oben eingeführte Matrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=a_0I+a_1Z+a_2Z^2+\ldots+a_{n-1}Z^{n-1}=p(Z)}

mit dem Polynom $p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-1}x^{n-1}$ vom Grad $n-1$. Denn in der Matrix $Z^{k}$ sind die Einsen jeweils um $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 $Z$. Die Matrix $Z$ ist eine spezielle Begleitmatrix, ihr charakteristisches Polynom ist das Polynom

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

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

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

Der $k$-te Eigenvektor hat die Form $(\lambda _{k}^{j-1})_{j=1}^{n}$ und alle Eigenvektoren bilden zusammen eine Vandermonde-Matrix Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle V(\lambda _{1},\ldots ,\lambda _{m})} (siehe Artikel Begleitmatrix). Diese Vandermonde-Matrix ist dann auch die Eigenvektormatrix von $A=p(Z)$, während die Eigenwerte von $A$ die Werte $p(\lambda _{k})$ besitzen.

Querverbindungen

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

$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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 0,\ldots ,n-1} zyklisch wieder in diesen Indexbereich abgebildet werden (durch Modulo-Rechnung: $(k-1)\mod n$). Damit hat dieses Matrix-Vektor-Produkt die Form einer diskreten Faltungs-Operation und daher kann das Produkt Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle Ax} mit der Matrix oder mit ihrer Inversen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^{-1}x} für große Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} mit Hilfe der Schnellen Fourier-Transformation (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=2^k} .

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen

Gegeben sei ein Gleichungssystem der Form

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ \mathbf{A} \mathbf{x} = \mathbf{b}, }

mit der oben angegebenen zirkulanten, quadratischen Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ A} der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ n} . Dann entspricht die Gleichung einer zyklischen Faltung:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ \mathbf{a} * \mathbf{x} = \mathbf{b},}

wobei allerdings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} unbekannt ist. Der Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ a^T=(a_0,a_{n-1},a_{n-2},\ldots,a_1)} ist die erste Zeile von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ A} . Dann kann man schreiben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{F}_{n}(\mathbf{a})\cdot\mathcal{F}_{n}(\mathbf{x})} die Vektoren komponentenweise miteinander multipliziert werden. Die Fourier-Transformierte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 ist bedeutend schneller als das Gaußsche Eliminationsverfahren, besonders wenn 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).