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=⟨u_1,\dots ,u_n⟩$

und

$W=⟨w_1,\dots ,w_k⟩$.

Schließlich benötigt man noch linear unabhängige Vektoren $B_1,\dots ,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

$\left(\begin{array}{cccccccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,m}& a_{1,1}& a_{1,2}& \cdots & a_{1,m}\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ 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\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ b_{k,1}& b_{k,2}& \cdots & b_{k,m}& 0& 0& \cdots & 0\end{array}\right)$

auf. Mithilfe der Zeilenumformungen führe man diese Matrix über in eine Matrix in Stufenform der folgenden Gestalt:

$\left(\begin{array}{cccccccc}{c}_{1,1}& c_{1,2}& \cdots & c_{1,m}& *& *& \cdots & *\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ 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}\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0& d_{l,1}& d_{l,2}& \cdots & d_{l,m}\\ 0& 0& \cdots & 0& 0& 0& \cdots & 0\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0& 0& 0& \cdots & 0\end{array}\right)$

Dabei seien die Vektoren $(c_{p,1},c_{p,2},\dots ,c_{p,m})$ für $p\in \{1,\dots ,q\}$ und $(d_{p,1},\dots ,d_{p,m})$ für $p\in \{1,\dots ,l\}$ nicht die Nullvektoren.

Dann ist $(y_1,\dots ,y_q)$ mit

$y_i:=\sum _{j=1}^m{c}_{i,j}{B}_j$

eine Basis von $U+W$ und $(z_1,\dots ,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\}\le 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(\begin{array}{c}1\\ -1\\ 0\\ 1\end{array}\right),\left(\begin{array}{c}0\\ 0\\ 1\\ -1\end{array}\right)⟩$ und $W=⟨\left(\begin{array}{c}5\\ 0\\ -3\\ 3\end{array}\right),\left(\begin{array}{c}0\\ 5\\ -3\\ -2\end{array}\right)⟩$ des ${ℝ}^4$.

Indem man als $(B_1,B_2,B_3,B_4)$ die Einheitsbasis des ${ℝ}^4$ verwendet, muss man die folgende Matrix

$\left(\begin{array}{ccccccccc}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{array}\right)$

mittels elementarer Zeilenumformungen auf Stufenform bringen. Dies liefert schließlich

$\left(\begin{array}{ccccccccc}1& 0& 0& 0& & *& *& *& *\\ 0& 1& 0& -1& & *& *& *& *\\ 0& 0& 1& -1& & *& *& *& *\\ \\ 0& 0& 0& 0& & 1& -1& 0& 1\end{array}\right)$.

Demnach ist $(\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 0\\ -1\end{array}\right),\left(\begin{array}{c}0\\ 0\\ 1\\ -1\end{array}\right))$ eine Basis von $U+W$, und $\left(\left(\begin{array}{c}1\\ -1\\ 0\\ 1\end{array}\right)\right)$ ist eine Basis von $U\cap W$.

Literatur

• Vorlage:Literatur

Weblinks

• Vorlage:Internetquelle