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
ein Vektorraum und
zwei endlichdimensionale Untervektorräume von
, von denen jeweils ein Erzeugendensystem bekannt ist:
![{\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbb0a4d146bd541bf2fe42e74d789212cd5546a8)
und
.
Schließlich benötigt man noch linear unabhängige Vektoren
, in denen die Darstellung
![{\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce71eaa8f86e7d1574adb4ef364d84ef00b8332)
und
![{\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c987fed521c43dc50c0724319a2c28f2400adb0)
bekannt ist.
Gesucht sind Basen der Summe
und der Schnittmenge
.
Man stelle die folgende
-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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4be0f4cd69f1d5d750da11ba0c6711af3cd64b57)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ece3818f499e5beb291e2bd1b2e1183aa8d9cb0)
Dabei seien die Vektoren
für
und
für
nicht die Nullvektoren.
Dann ist
mit
![{\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/849be68856fa1e5dcab0cf6303da0e62dc4e4217)
eine Basis von
und
mit
![{\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3de8a60b95a49a1b17faaa134139c493e64c450f)
eine Basis von
.
Die Korrektheit des Algorithmus basiert auf folgender Erkenntnis: Der Unterraum
erfüllt
und
, wobei
die Projektion auf die erste Komponente sei. Gleichzeitig ist
der Kern der auf
eingeschränkten Projektion. Insbesondere ist
.
Der Zassenhaus-Algorithmus berechnet eine Basis von
. In den ersten
Spalten der Matrix wird dabei eine Basis
von
berechnet. Die Zeilen
sind offenbar in
enthalten und wegen der Zeilenstufenform linear unabhängig. Alle von Null verschiedenen Zeilen zusammen, also
und
müssen aber eine Basis von
bilden, also stimmt die Anzahl der
mit
überein, d. h., es wurde eine Basis von
berechnet.
Gegeben seien die beiden Untervektorräume
und
des
.
Indem man als
die Einheitsbasis des
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/718a3dcaa4126f0bebc20c2fa2a8c63d2a288dd9)
mittels elementarer Zeilenumformungen auf Stufenform bringen.
Dies liefert schließlich
.
Demnach ist
eine Basis von
, und
ist eine Basis von
.
- ↑ 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]).
- ↑ Fischer, S. 210.
- ↑ GAP – Matrices. Abgerufen am 15. September 2012.
- ↑ MeatAxe – Other Kernel Functions. Ehemals im Original (nicht mehr online verfügbar); abgerufen am 15. September 2012.@1@2Vorlage:Toter Link/www.math.rwth-aachen.de (Seite nicht mehr abrufbar. Suche in Webarchiven)