Zassenhaus-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

Voraussetzungen

[Bearbeiten | Quelltext bearbeiten]

Es sei ein Vektorraum und zwei endlichdimensionale Untervektorräume von , von denen jeweils ein Erzeugendensystem bekannt ist:

und

.

Schließlich benötigt man noch linear unabhängige Vektoren , in denen die Darstellung

und

bekannt ist.

Ziel des Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Gesucht sind Basen der Summe und der Schnittmenge .

Man stelle die folgende -Matrix als Blockmatrix

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

Dabei seien die Vektoren für und für nicht die Nullvektoren.

Dann ist mit

eine Basis von und mit

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

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

.

Demnach ist eine Basis von , und ist eine Basis von .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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@2Vorlage:Toter Link/www.math.rwth-aachen.de (Seite nicht mehr abrufbar. Suche in Webarchiven)