Zassenhaus-Algorithmus

Der Zassenhaus-Algorithmus[1] i​st ein Algorithmus z​ur Bestimmung v​on Schnitt- u​nd Summenbasen v​on zwei Untervektorräumen i​n der Linearen Algebra. Der Algorithmus i​st nach d​em Mathematiker Hans Zassenhaus benannt, e​ine fachwissenschaftliche Veröffentlichung d​es Algorithmus d​urch Zassenhaus i​st jedoch n​icht bekannt[2]. Er findet Verwendung i​n Computeralgebrasystemen.[3][4]

Algorithmus

Voraussetzungen

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

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

und

${\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}}$, in denen die Darstellung

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

bekannt ist.

Ziel des Algorithmus

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

Algorithmus

Man stelle die folgende ${\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}}}$

auf. Mithilfe d​er Zeilenumformungen führe m​an diese Matrix über i​n eine Matrix i​n Stufenform d​er 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}}}$

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

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

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

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

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

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

Korrektheit

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}$ erfüllt ${\displaystyle \pi _{1}(H)=U+W}$ und ${\displaystyle H\cap (0\times V)=0\times (U\cap W)}$, wobei ${\displaystyle \pi _{1}:V\times V\to V}$ die Projektion auf die erste Komponente sei. Gleichzeitig ist ${\displaystyle H\cap (0\times V)}$ der Kern der auf ${\displaystyle H}$ eingeschränkten Projektion. Insbesondere ist ${\displaystyle \dim(H)=\dim(U+W)+\dim(U\cap W)}$.

Der Zassenhaus-Algorithmus berechnet eine Basis von ${\displaystyle H}$. In den ersten ${\displaystyle m}$ Spalten der Matrix wird dabei eine Basis ${\displaystyle y_{i}}$ von ${\displaystyle U+W}$ berechnet. Die Zeilen ${\displaystyle (0,z_{i})}$ sind offenbar in ${\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 )}$ und ${\displaystyle (0,z_{i})}$ müssen aber eine Basis von ${\displaystyle H}$ bilden, also stimmt die Anzahl der ${\displaystyle z_{i}}$ mit ${\displaystyle \dim(U\cap W)}$ überein, d. h., es wurde eine Basis von ${\displaystyle U\cap W}$ berechnet.

Beispiel

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

Indem man als ${\displaystyle (B_{1},B_{2},B_{3},B_{4})}$ die Einheitsbasis des ${\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}}}$

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

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

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

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. (Nicht mehr online verfügbar.) Ehemals im Original; abgerufen am 15. September 2012. (Seite nicht mehr abrufbar, Suche in Webarchiven)