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]

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

Korrektheit

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

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

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.

Einzelnachweise

↑ 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@2 (Seite nicht mehr abrufbar. Suche in Webarchiven)

[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 (Seite nicht mehr abrufbar. Suche in Webarchiven)

[1]

[2]

[3]

[4]

Algorithmus

Zassenhaus-Algorithmus

Inhaltsverzeichnis

Algorithmus

Voraussetzungen

Ziel des Algorithmus

Algorithmus

Korrektheit

Beispiel

Literatur

Weblinks

Einzelnachweise

What are your Feelings

Zassenhaus-Algorithmus

Algorithmus

Voraussetzungen

Ziel des Algorithmus

Algorithmus

Korrektheit

Beispiel

Literatur

Weblinks

Einzelnachweise

What are your Feelings

Share This Article :