Zassenhaus-Algorithmus

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.

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

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

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

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.