Zyklische Matrix

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 $a_0,a_1,\ldots,a_{n-1}$ die Gestalt

$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. Zyklische Matrizen sind spezielle Toeplitz-Matrizen, bei denen die Elemente unter und über der Hauptdiagonalen zusammenhängen.

Eigenschaften

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

$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_1x+a_2x^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 Kreisteilungspolynom

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

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 $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(λ_k) besitzen.

Querverbindungen

Das Produkt der zyklischen Matrix A mit einem Vektor $x=(x_0,\ldots,x_{n-1})\in\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 $0,\ldots,n-1$ zyklisch wieder in diesen Indexbereich abgebildet werden (durch Modulo-Rechnung: $(k-1)\mod n$). Damit hat dieses Matrix-Produkt die Form einer diskreten Faltungs-Operation und daher kann das Produkt Ax mit der Matrix oder mit ihrer Inversen A ^{− 1}x für große n mit Hilfe der Schnellen Fourier-Transformation (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist n = 2^k.

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen

Gegeben sei ein Gleichungssystem der Form

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

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

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

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

$\ \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 $\mathcal{F}_{n}(\mathbf{a})\cdot\mathcal{F}_{n}(\mathbf{x})$ die Vektoren komponentenweise miteinander multipliziert werden. Die Fourier-Transformierte $\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:

$\ \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.

Weblinks

• Heinrich Voss: Skript Grundlagen der numerischen Mathematik (PDF, 1.9Mb), S. 129 ff.