Zassenhaus-Algorithmus

Der Zassenhaus-Algorithmus^[1] 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.^[2] Er findet Verwendung in Computeralgebrasystemen.^{[3] [4]}

Es sei ${\displaystyle V}${\displaystyle V} ein Vektorraum und ${\displaystyle U,W}${\displaystyle U,W} zwei endlichdimensionale Untervektorräume von ${\displaystyle V}${\displaystyle V}, von denen jeweils ein Erzeugendensystem bekannt ist:

${\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }${\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }

und

${\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle }${\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle }.

Schließlich benötigt man noch linear unabhängige Vektoren ${\displaystyle B_{1},\ldots ,B_{m}}${\displaystyle B_{1},\ldots ,B_{m}}, in denen die Darstellung

${\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}${\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}

und

${\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}}${\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}}

bekannt ist.

Gesucht sind Basen der Summe ${\displaystyle U+W}${\displaystyle U+W} und der Schnittmenge ${\displaystyle U\cap W}${\displaystyle U\cap W}.

Man stelle die folgende ${\displaystyle ((n+k)\times (2m))}${\displaystyle ((n+k)\times (2m))}-Matrix als Blockmatrix

${\displaystyle {\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}}}${\displaystyle {\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}}}

auf. Mithilfe der Zeilenumformungen führe man diese Matrix über in eine Matrix in Stufenform der folgenden Gestalt:

${\displaystyle {\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}}}${\displaystyle {\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}}}

Dabei seien die Vektoren ${\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})}${\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})} für ${\displaystyle p\in \{1,\ldots ,q\}}${\displaystyle p\in \{1,\ldots ,q\}} und ${\displaystyle (d_{p,1},\ldots ,d_{p,m})}${\displaystyle (d_{p,1},\ldots ,d_{p,m})} für ${\displaystyle p\in \{1,\ldots ,l\}}${\displaystyle p\in \{1,\ldots ,l\}} nicht die Nullvektoren.

Dann ist ${\displaystyle (y_{1},\ldots ,y_{q})}${\displaystyle (y_{1},\ldots ,y_{q})} mit

${\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}}${\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}}

eine Basis von ${\displaystyle U+W}${\displaystyle U+W} und ${\displaystyle (z_{1},\ldots ,z_{l})}${\displaystyle (z_{1},\ldots ,z_{l})} mit

${\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}${\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}

eine Basis von ${\displaystyle U\cap W}${\displaystyle U\cap W}.

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

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

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

Indem man als ${\displaystyle (B_{1},B_{2},B_{3},B_{4})}${\displaystyle (B_{1},B_{2},B_{3},B_{4})} die Einheitsbasis des ${\displaystyle \mathbb {R} ^{4}}${\displaystyle \mathbb {R} ^{4}} verwendet, muss man die folgende Matrix

${\displaystyle {\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}}}${\displaystyle {\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}}}

mittels elementarer Zeilenumformungen auf Stufenform bringen. Dies liefert schließlich

${\displaystyle {\begin{pmatrix}1&0&0&0&&*&*&*&*\0円&1&0&-1&&*&*&*&*\0円&0&1&-1&&*&*&*&*\\\0円&0&0&0&&1&-1&0&1\end{pmatrix}}}${\displaystyle {\begin{pmatrix}1&0&0&0&&*&*&*&*\0円&1&0&-1&&*&*&*&*\0円&0&1&-1&&*&*&*&*\\\0円&0&0&0&&1&-1&0&1\end{pmatrix}}}.

Demnach ist ${\displaystyle \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)}${\displaystyle \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)} eine Basis von ${\displaystyle U+W}${\displaystyle U+W}, und ${\displaystyle \left({\begin{pmatrix}1\\-1\0円\1円\end{pmatrix}}\right)}${\displaystyle \left({\begin{pmatrix}1\\-1\0円\1円\end{pmatrix}}\right)} ist eine Basis von ${\displaystyle U\cap W}${\displaystyle U\cap W}.

• 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 . 

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

1. ↑ 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]). 
2. ↑ Fischer, S. 210.
3. ↑ GAP – Matrices. Abgerufen am 15. September 2012. 
4. ↑ MeatAxe – Other Kernel Functions. Ehemals im Original (nicht mehr online verfügbar); abgerufen am 15. September 2012.@1 @2 Vorlage:Toter Link/www.math.rwth-aachen.de (Seite nicht mehr abrufbar. Suche in Webarchiven) 

• Algorithmus
• Lineare Algebra

• Wikipedia:Weblink offline