The Zassenhaus algorithm is an algorithm for the determination of intersection and sum bases of two subspaces in linear algebra . The algorithm is named after the mathematician Hans Zassenhaus , but Zassenhaus is not aware of any scientific publication of the algorithm. It is used in computer algebra systems .
algorithm
requirements
Let a vector space and two finite-dimensional sub-vector spaces of , each of which have a known generating system:
and
-
.
Finally, one still needs linearly independent vectors in which the representation
and
is known.
Goal of the algorithm
We are looking for bases of the sum and the intersection .
algorithm
Put the following matrix as a block matrix
on. With the help of the line transformations, this matrix is transformed into a matrix in the form of steps of the following form:
Let the vectors
for and for not be the zero vectors.
Then is with
a basis of
and with
a base of .
correctness
The correctness of the algorithm is based on the following knowledge: The subspace satisfies and , where the projection is on the first component. At the same time, the core is limited to projection. In particular is .
The Zassenhaus algorithm calculates a basis of . A base of is calculated in the first columns of the matrix . The lines are obviously contained in and are linearly independent because of the line step form. All nonzero rows together so and have but one based on form, ie the number of true with consistent, d. H. a basis of .
example
The two subspaces and des are given .
By using as the unit basis of the use, you have the following matrix
bring them to a stepped form using elementary line transformations. This ultimately delivers
-
.
Hence is
a basis of , and
is a basis of .
literature
Web links
Individual evidence
-
^ Eugene M. Luks, Ferenc Rákóczi, Charles RB Wright: Some Algorithms for Nilpotent Permutation Groups . 1996, p. 15 ( online [accessed September 15, 2012]).
-
↑ Fischer, p. 210
-
^ GAP matrices. Retrieved September 15, 2012 .
-
↑ MeatAxe - Other Kernel Functions. (No longer available online.) Formerly in the original ; Retrieved September 15, 2012 . ( Page no longer available , search in web archives )@1@ 2Template: Toter Link / www.math.rwth-aachen.de