In mathematics, the Zassenhaus algorithm is a method to calculate a basis for the intersection and sum of two subspaces of a vector space. It is named after Hans Zassenhaus, but no publication of this algorithm by him is known. It is used in computer algebra systems.
Let be a vector space and , two finite-dimensional subspaces of with the following spanning sets:
and
Finally, let be linearly independent vectors so that and can be written as
and
The algorithm computes the base of the sum and a base of the intersection .
The algorithm creates the following block matrix of size :
Using elementary row operations, this matrix is transformed to the row echelon form. Then, it has the following shape:
Here, stands for arbitrary numbers, and the vectors for every and for every are nonzero.
Then with
is a basis of and with
is a basis of .
First, we define to be the projection to the first component.
Let
Then and .
Also, is the kernel of , the projection restricted to . Therefore, .
The Zassenhaus algorithm calculates a basis of . In the first columns of this matrix, there is a basis of .
The rows of the form (with ) are obviously in . Because the matrix is in row echelon form, they are also linearly independent. All rows which are different from zero ( and ) are a basis of , so there are such s. Therefore, the s form a basis of .
Consider the two subspaces and of the vector space .
Using the standard basis, we create the following matrix of dimension :
Using elementary row operations, we transform this matrix into the following matrix:
Therefore is a basis of , and is a basis of .