Zassenhaus-Algorithmus

Der Zassenhaus-Algorithmus<ref>Eugene M. Luks, Ferenc Rákóczi, Charles R. B. Wright: Some Algorithms for Nilpotent Permutation Groups. 1996, S. 15 (online [abgerufen am 15. September 2012]). </ref> ist ein Algorithmus zur Bestimmung von Schnitt- und Summenbasen von zwei Untervektorräumen in der Linearen Algebra. Der Algorithmus ist nach dem Mathematiker Hans Zassenhaus benannt, eine fachwissenschaftliche Veröffentlichung des Algorithmus durch Zassenhaus ist jedoch nicht bekannt.<ref>Fischer, S. 210.</ref> Er findet Verwendung in Computeralgebrasystemen.<ref>GAP – Matrices. Abgerufen am 15. September 2012. </ref><ref>MeatAxe – Other Kernel Functions. Ehemals im Vorlage:IconExternal (nicht mehr online verfügbar); abgerufen am 15. September 2012.@1@2 (Seite nicht mehr abrufbar. Suche im Internet Archive (T)) </ref>

Algorithmus

Voraussetzungen

Es sei <math>V</math> ein Vektorraum und <math>U, W</math> zwei endlichdimensionale Untervektorräume von <math>V</math>, von denen jeweils ein Erzeugendensystem bekannt ist:

<math>U = \langle u_1, \ldots, u_n\rangle</math>

und

<math>W = \langle w_1, \ldots, w_k\rangle</math>.

Schließlich benötigt man noch linear unabhängige Vektoren <math>B_1, \ldots, B_m</math>, in denen die Darstellung

und

bekannt ist.

Ziel des Algorithmus

Gesucht sind Basen der Summe <math>U + W</math> und der Schnittmenge <math>U \cap W</math>.

Algorithmus

Man stelle die folgende <math>((n+k) \times (2m))</math>-Matrix als Blockmatrix

<math>\begin{pmatrix}

a_{1,1}&a_{1,2}&\cdots&a_{1,m}&a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,m}&a_{n,1}&a_{n,2}&\cdots&a_{n,m}\\ b_{1,1}&b_{1,2}&\cdots&b_{1,m}&0&0&\cdots&0\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ b_{k,1}&b_{k,2}&\cdots&b_{k,m}&0&0&\cdots&0\\ \end{pmatrix}</math> auf. Mithilfe der Zeilenumformungen führe man diese Matrix über in eine Matrix in Stufenform der folgenden Gestalt:

<math>\begin{pmatrix}

c_{1,1}&c_{1,2}&\cdots&c_{1,m}&*&*&\cdots&*\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ c_{q,1}&c_{q,2}&\cdots&c_{q,m}&*&*&\cdots&*\\ 0&0&\cdots&0&d_{1,1}&d_{1,2}&\cdots&d_{1,m}\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 0&0&\cdots&0&d_{l,1}&d_{l,2}&\cdots&d_{l,m}\\ 0&0&\cdots&0&0&0&\cdots&0\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 0&0&\cdots&0&0&0&\cdots&0\\ \end{pmatrix}</math> Dabei seien die Vektoren <math>(c_{p,1}, c_{p,2}, \ldots, c_{p,m})</math> für <math>p \in \{1, \ldots, q\}</math> und <math>(d_{p,1}, \ldots, d_{p,m})</math> für <math>p\in \{1, \ldots, l\}</math> nicht die Nullvektoren.

Dann ist <math>(y_1, \ldots, y_q)</math> mit

eine Basis von <math>U+W</math> und <math>(z_1, \ldots, z_l)</math> mit

eine Basis von <math>U \cap W</math>.

Korrektheit

Die Korrektheit des Algorithmus basiert auf folgender Erkenntnis: Der Unterraum <math>H:=\{(u,u) | u\in U\}+\{(w,0) | w\in W\} \leq V\times V</math> erfüllt <math>\pi_1(H) = U+W</math> und <math>H\cap(0\times V)=0\times(U\cap W)</math>, wobei <math>\pi_1: V\times V\to V</math> die Projektion auf die erste Komponente sei. Gleichzeitig ist <math>H\cap (0\times V)</math> der Kern der auf <math>H</math> eingeschränkten Projektion. Insbesondere ist <math>\dim(H) = \dim(U+W)+\dim(U\cap W)</math>.

Der Zassenhaus-Algorithmus berechnet eine Basis von <math>H</math>. In den ersten <math>m</math> Spalten der Matrix wird dabei eine Basis <math>y_i</math> von <math>U+W</math> berechnet. Die Zeilen <math>(0,z_i)</math> sind offenbar in <math>H\cap(0\times V)</math> enthalten und wegen der Zeilenstufenform linear unabhängig. Alle von Null verschiedenen Zeilen zusammen, also <math>(y_i,\ast)</math> und <math>(0,z_i)</math> müssen aber eine Basis von <math>H</math> bilden, also stimmt die Anzahl der <math>z_i</math> mit <math>\dim(U\cap W)</math> überein, d. h., es wurde eine Basis von <math>U\cap W</math> berechnet.

Beispiel

Gegeben seien die beiden Untervektorräume <math>U = \left\langle \begin{pmatrix} 1\\ -1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \\ -1 \end{pmatrix} \right\rangle </math> und <math> W = \left\langle \begin{pmatrix} 5 \\ 0 \\ -3 \\ 3 \end{pmatrix}, \begin{pmatrix} 0 \\ 5 \\ -3 \\ -2 \end{pmatrix} \right\rangle </math> des <math>\mathbb{R}^4</math>.

Indem man als <math>(B_1, B_2, B_3, B_4)</math> die Einheitsbasis des <math>\mathbb{R}^4</math> verwendet, muss man die folgende Matrix

<math>

\begin{pmatrix} 1 & -1 &0&1 & & 1 & -1 &0&1 \\ 0&0&1&-1& &0&0&1&-1 \\ \\ 5&0&-3&3& &0&0&0&0 \\ 0&5&-3&-2& &0&0&0&0 \end{pmatrix}</math> mittels elementarer Zeilenumformungen auf Stufenform bringen. Dies liefert schließlich

<math>

\begin{pmatrix} 1 & 0 &0&0& &*&*&*&* \\ 0&1&0&-1& &*&*&*&*\\ 0&0&1&-1& &*&*&*&*\\ \\ 0&0&0&0& &1&-1&0&1 \end{pmatrix} </math>. Demnach ist <math>\left(\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}, \begin{pmatrix} 0\\1\\0\\-1\end{pmatrix}, \begin{pmatrix} 0\\0\\1\\-1\end{pmatrix}\right)</math> eine Basis von <math>U+W</math>, und <math> \left(\begin{pmatrix} 1\\-1\\0\\1\end{pmatrix}\right) </math> ist eine Basis von <math>U \cap W</math>.

Literatur

Gerd Fischer: Lernbuch Lineare Algebra und Analytische Geometrie. Vieweg+Teubner, Wiesbaden 2012, ISBN 978-3-8348-2378-6, S. 207–210, doi:10.1007/978-3-8348-2379-3.

Weblinks

Mathematik-Online-Lexikon: Zassenhaus-Algorithmus. Abgerufen am 15. September 2012.

Einzelnachweise