Zassenhaus-Algorithmus

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion!

Der Zassenhaus-Algorithmus ist ein Algorithmus zur Bestimmung von Schnitt- und Summenbasen von 2 Teilräumen in der Linearen Algebra. Er wurde 1948 von dem Mathematiker Hans Zassenhaus vorgeschlagen.

Dazu müssen die beiden Teilräume Unterräume eines gemeinsamen Vektorraums sein, und die Basen dieser beiden Teilräume müssen gegeben sein. Die Anwendung des Algorithmus ist dem des gaußschen Eliminationsverfahrens sehr ähnlich.

Algorithmus

Voraussetzungen

Es sei $\mathfrak{V}$ ein Vektorraum und $\mathfrak{U}, \mathfrak{W}$ zwei endlichdimensionale Teilräume von $\mathfrak{V}$, von denen jeweils ein Erzeugendensystem bekannt ist:

$\mathfrak{U} = \langle u_1, \ldots, u_n\rangle$

und

$\mathfrak{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 von $\mathfrak{U} + \mathfrak{W}$ und $\mathfrak{U} \cap \mathfrak{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 $\mathfrak{U}+\mathfrak{W}$ und $(z_1, \ldots, z_l)$ mit

$z_i := \sum_{j=1}^m d_{i,j}B_j$

eine Basis von $\mathfrak{U} \cap \mathfrak{W}$.

Beispiel

Gegeben seien die beiden Untervektorräume $\mathfrak{U} = \left\langle \begin{pmatrix} 1\\ -1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \\ -1 \end{pmatrix} \right\rangle$ und $\mathfrak{V} = \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₁,B₂,B₃,B₄) 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 $\mathfrak{U}+\mathfrak{V}$, und $\left(\begin{pmatrix} 1\\-1\\0\\1\end{pmatrix}\right)$ ist eine Basis von $\mathfrak{U} \cap \mathfrak{V}$.

Weblinks

interaktive Berechnung des Zassenhausalgorithmus