Zyklische Matrix

Grundidee und Aufbau

Eine zyklische oder zirkulante Matrix ist eine quadratische Matrix, deren Zeilen und Spalten durch festgelegtes zyklisches Verschieben zusammenhängen. Sie ist eine besondere Toeplitz-Matrix: Jeder Zeilenvektor entsteht aus dem darüberstehenden, indem alle Einträge um eine Position nach rechts verschoben werden. Dadurch wiederholt sich das Besetzungsmuster am Rand der Matrix zyklisch.

Mit den Zahlen a_0,a_1,\ldots,a_{n-1} hat sie die Form A=(a_{i-j\bmod n}). In ausgeschriebener erster Zeile stehen a_0,a_{n-1},a_{n-2},\ldots,a_1; die zweite Zeile lautet a_1,a_0,a_{n-1},\ldots,a_2. Jede Spalte entsteht durch zyklisches Verschieben der links danebenstehenden Spalte; entsprechend werden auch die Zeilen zyklisch verschoben.

Sind alle Elemente einer Zeile verschieden, ist eine zirkulante Matrix außerdem ein Beispiel für ein Lateinisches Quadrat.

Darstellung durch die Verschiebungsmatrix

Zyklische Matrizen sind persymmetrisch, also spiegelsymmetrisch bezüglich der Gegendiagonalen. Außerdem sind sie spezielle Toeplitz-Matrizen, bei denen die Einträge oberhalb und unterhalb der Hauptdiagonalen miteinander verbunden sind.

Alle zirkulanten Matrizen lassen sich als Polynom einer einfachen zyklischen Matrix Z schreiben. Diese Matrix verschiebt die Einträge eines Vektors zyklisch; ihre Einsen liegen unterhalb der Hauptdiagonalen und zusätzlich oben rechts. Für A gilt

A=a_0I+a_1Z+a_2Z^2+\ldots+a_{n-1}Z^{n-1}=p(Z),

wobei I die Einheitsmatrix und p(x)=a_0+a_1x+a_2x^2+\ldots+a_{n-1}x^{n-1} ein Polynom vom Grad n-1 ist. In Z^k sind die Einsen jeweils zyklisch um k Positionen nach unten gerückt.

Eigenwerte und Eigenvektoren

Weil jede zyklische Matrix ein Polynom in Z ist, besitzen alle zyklischen Matrizen dieselbe Basis von Eigenvektoren wie Z. Die Matrix Z ist eine spezielle Begleitmatrix. Ihr charakteristisches Polynom ist

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

Seine Nullstellen sind genau die n-ten Einheitswurzeln. Daher hat Z genau n verschiedene Eigenwerte auf dem komplexen Einheitskreis, die gleich weit auseinanderliegen:

\lambda_k=e^{2\pi i(k-1)/n},\quad k=1,\ldots,n.

Der k-te Eigenvektor hat die Form (\lambda_k^{j-1})_{j=1}^{n}. Alle diese Eigenvektoren bilden eine Vandermonde-Matrix V(\lambda_1,\ldots,\lambda_m). Diese ist zugleich Eigenvektormatrix von A=p(Z); die zugehörigen Eigenwerte von A sind p(\lambda_k).

Faltung, Fourier-Transformation und Gleichungssysteme

Für x=(x_0,\ldots,x_{n-1})\in\mathbb{R}^n gilt

Ax=\left(\sum_{j=0}^{n-1}a_{k-j}x_j\right)_{k=0}^{n-1}.

Indizes außerhalb von 0,\ldots,n-1 werden dabei durch Modulo-Rechnung wieder in diesen Bereich zurückgeführt, zum Beispiel mit (k-1)\bmod n. Das Matrix-Vektor-Produkt ist somit eine diskrete Faltung. Deshalb können Ax und, bei vorhandener Inverser, A^{-1}x für große n mithilfe der Schnellen Fourier-Transformation (FFT) schnell berechnet werden; besonders günstig ist n=2^k.

Für ein Gleichungssystem Ax=b mit zirkulanter Matrix ist a^T=(a_0,a_1,\ldots,a_{n-1}) die erste Spalte von A, und die Gleichung entspricht a*x=b. Nach Fourier-Transformation gilt

\mathcal{F}_n(a*x)=\mathcal{F}_n(a)\cdot\mathcal{F}_n(x)=\mathcal{F}_n(b),

wobei die Fourier-Koeffizienten komponentenweise multipliziert werden. Man erhält die Transformierte der Lösung durch komponentenweise Division und danach die Lösung durch Rücktransformation:

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

Dieser Ansatz ist besonders mit FFT bedeutend schneller als das Gaußsche Eliminationsverfahren.