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.

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

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

Bearbeiten

Eine quadratische Matrix heißt zyklisch, wenn sie mit Zahlen   die Gestalt

 

besitzt. Jede Spalte erhält man durch zyklisches Verschieben der links davon stehenden, daher werden auch die Zeilen zyklisch verschoben.

Eigenschaften

Bearbeiten

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

 

denn es gilt für die oben eingeführte Matrix

 

mit dem Polynom   vom Grad  . Denn in der Matrix   sind die Einsen jeweils um   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  . Die Matrix   ist eine spezielle Begleitmatrix, ihr charakteristisches Polynom ist das Polynom

 

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

 

Der  -te Eigenvektor hat die Form   und alle Eigenvektoren bilden zusammen eine Vandermonde-Matrix   (siehe Artikel Begleitmatrix). Diese Vandermonde-Matrix ist dann auch die Eigenvektormatrix von  , während die Eigenwerte von   die Werte   besitzen.

Querverbindungen

Bearbeiten

Das Produkt der zyklischen Matrix   mit einem Vektor   ist

 

Dabei sei verabredet, dass Indizes außerhalb von   zyklisch wieder in diesen Indexbereich abgebildet werden (durch Modulo-Rechnung:  ). Damit hat dieses Matrix-Vektor-Produkt die Form einer diskreten Faltungs-Operation und daher kann das Produkt   mit der Matrix oder mit ihrer Inversen   für große   mit Hilfe der Schnellen Fourier-Transformation (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist  .

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen

Bearbeiten

Gegeben sei ein Gleichungssystem der Form

 

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

 

wobei allerdings   unbekannt ist. Der Vektor   ist die erste Zeile von  . Dann kann man schreiben:

 ,

wobei bei dem Produkt der Fourier-Koeffizienten   die Vektoren komponentenweise miteinander multipliziert werden. Die Fourier-Transformierte   der Lösung erhält man daher durch komponentenweise Division, und die Rücktransformation liefert dann die Lösung selbst:

 

Dieser Ansatz ist bedeutend schneller als das Gaußsche Eliminationsverfahren, besonders wenn eine schnelle Fourier-Transformation verwendet wird.

Literatur

Bearbeiten
Bearbeiten