imported>Nachtigaller II: /* growthexperiments-addlink-summary-summary:1|0|0 */

2026-03-19T22:41:09Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Der '''Zassenhaus-Algorithmus'''<ref>{{Literatur |Autor=Eugene M. Luks, Ferenc Rákóczi, Charles R. B. Wright |Titel=Some Algorithms for Nilpotent Permutation Groups |Datum=1996 |Seiten=15 |Online=[https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.4437 online] |Abruf=2012-09-15}}</ref> ist ein [[Algorithmus]] zur Bestimmung von Schnitt- und Summenbasen von zwei [[Untervektorraum|Untervektorräumen]] in der [[Lineare Algebra|Linearen Algebra]]. Der Algorithmus ist nach dem [[Mathematiker]] [[Hans Julius Zassenhaus|Hans Zassenhaus]] benannt, eine fachwissenschaftliche Veröffentlichung des Algorithmus durch Zassenhaus ist jedoch nicht bekannt.<ref>Fischer, S. 210.</ref> Er findet Verwendung in [[Computeralgebrasystem]]en.<ref>{{Internetquelle |url=https://www.gap-system.org/Manuals/doc/ref/chap24.html |titel=GAP – Matrices |abruf=2012-09-15}}</ref><ref>{{Internetquelle |url=http://www.math.rwth-aachen.de/~MTX/doc24/group__ff2.html |titel=MeatAxe – Other Kernel Functions |offline=1 |abruf=2012-09-15}}</ref>

== Algorithmus ==

=== Voraussetzungen ===

Es sei <math>V</math> ein [[Vektorraum]] und <math>U, W</math> zwei endlichdimensionale Untervektorräume von <math>V</math>, von denen jeweils ein [[Erzeugendensystem]] bekannt ist:
:<math>U = \langle u_1, \ldots, u_n\rangle</math>
und
:<math>W = \langle w_1, \ldots, w_k\rangle</math>.
Schließlich benötigt man noch linear unabhängige Vektoren <math>B_1, \ldots, B_m</math>, in denen die Darstellung
:<math>u_i = \sum_{j=1}^m a_{i,j}B_j</math>
und
:<math>w_i = \sum_{j=1}^m b_{i,j}B_j</math>
bekannt ist.

=== Ziel des Algorithmus ===

Gesucht sind Basen der [[Untervektorraum#Summe|Summe]] <math>U + W</math> und der [[Schnittmenge]] <math>U \cap W</math>.

=== Algorithmus ===

Man stelle die folgende <math>((n+k) \times (2m))</math>-Matrix als [[Blockmatrix]]
:<math>\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}</math>
auf. Mithilfe der Zeilenumformungen führe man diese Matrix über in eine Matrix in Stufenform der folgenden Gestalt:
:<math>\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}</math>
Dabei seien die Vektoren
<math>(c_{p,1}, c_{p,2}, \ldots, c_{p,m})</math> für <math>p \in \{1, \ldots, q\}</math> und <math>(d_{p,1}, \ldots, d_{p,m})</math> für <math>p\in \{1, \ldots, l\}</math> nicht die Nullvektoren.

Dann ist <math>(y_1, \ldots, y_q)</math> mit
:<math>y_i := \sum_{j=1}^m c_{i,j}B_j</math>
eine Basis von <math>U+W</math>
und <math>(z_1, \ldots, z_l)</math> mit
:<math>z_i := \sum_{j=1}^m d_{i,j}B_j</math>
eine Basis von <math>U \cap W</math>.

=== Korrektheit ===

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

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

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

Indem man als <math>(B_1, B_2, B_3, B_4)</math> die [[Einheitsbasis]] des <math>\mathbb{R}^4</math> verwendet, muss man die folgende Matrix
:<math>
\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}</math>
mittels elementarer Zeilenumformungen auf Stufenform bringen.
Dies liefert schließlich
:<math>
\begin{pmatrix} 1 & 0 &0&0& &*&*&*&* \\
0&1&0&-1& &*&*&*&*\\
0&0&1&-1& &*&*&*&*\\ \\
0&0&0&0& &1&-1&0&1 \end{pmatrix}
</math>.
Demnach ist
<math>\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)</math> eine Basis von <math>U+W</math>, und
<math>
\left(\begin{pmatrix} 1\\-1\\0\\1\end{pmatrix}\right)
</math> ist eine Basis von <math>U \cap W</math>.

== Literatur ==
* {{Literatur |Autor=[[Gerd Fischer (Mathematiker)|Gerd Fischer]] |Titel=Lernbuch Lineare Algebra und Analytische Geometrie |Verlag=[[Vieweg+Teubner]] |Ort=Wiesbaden |Datum=2012 |ISBN=978-3-8348-2378-6 |Seiten=207–210 |DOI=10.1007/978-3-8348-2379-3}}

== Weblinks ==
* {{Internetquelle |url=https://mo.mathematik.uni-stuttgart.de/inhalt/beispiel/beispiel1105/ |titel=Mathematik-Online-Lexikon: Zassenhaus-Algorithmus |abruf=2012-09-15}}

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Lineare Algebra]]

Zassenhaus-Algorithmus - Versionsgeschichte

imported>Nachtigaller II: /* growthexperiments-addlink-summary-summary:1|0|0 */