Zassenhaus algorithm


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.

Algorithm

Input

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

Output

The algorithm computes the base of the sum and a base of the intersection.

Algorithm

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.

Proof of correctness

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 are obviously in. Because the matrix is in row echelon form, they are also linearly independent.
All rows which are different from zero are a basis of, so there are such s. Therefore, the s form a basis of.

Example

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.