Zassenhaus-Algorithmus

Der Zassenhaus-Algorithmus 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. Er findet Verwendung in Computeralgebrasystemen.

Algorithmus

Voraussetzungen

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

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

und

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

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

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

und

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

bekannt ist.

Ziel des Algorithmus

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

Algorithmus

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

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

${\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 $(c_{p,1},c_{p,2},\ldots ,c_{p,m})$ für $p\in \{1,\ldots ,q\}$ und $(d_{p,1},\ldots ,d_{p,m})$ für $p\in \{1,\ldots ,l\}$ nicht die Nullvektoren.

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

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

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

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

eine Basis von $U\cap W$.

Beispiel

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

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

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

${\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 $\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 $U+W$, und $\left({\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}}\right)$ ist eine Basis von $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. 
• Demonstration des Zassenhaus-Algorithmus mit Zwischenschritten. Abgerufen am 15. September 2012.