Zassenhaus algorithm

Input

Let V be a vector space and U, W two finite-dimensional subspaces of V with the following spanning sets:

U = ⟨ u 1 , … , u n ⟩

and

W = ⟨ w 1 , … , w k ⟩ .

Finally, let B 1 , … , B m be linearly independent vectors so that u i and w i can be written as

u i = ∑ j = 1 m a i , j B j

and

w i = ∑ j = 1 m b i , j B j .

Output

The algorithm computes the base of the sum U + W and a base of the intersection U ∩ W .

Algorithm

The algorithm creates the following block matrix of size ( ( n + k ) × ( 2 m ) ) :

( a 1 , 1 a 1 , 2 ⋯ a 1 , m a 1 , 1 a 1 , 2 ⋯ a 1 , m ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ a n , 1 a n , 2 ⋯ a n , m a n , 1 a n , 2 ⋯ a n , m b 1 , 1 b 1 , 2 ⋯ b 1 , m 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ b k , 1 b k , 2 ⋯ b k , m 0 0 ⋯ 0 )

Using elementary row operations, this matrix is transformed to the row echelon form. Then, it has the following shape:

( c 1 , 1 c 1 , 2 ⋯ c 1 , m ∗ ∗ ⋯ ∗ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ c q , 1 c q , 2 ⋯ c q , m ∗ ∗ ⋯ ∗ 0 0 ⋯ 0 d 1 , 1 d 1 , 2 ⋯ d 1 , m ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 0 d l , 1 d l , 2 ⋯ d l , m 0 0 ⋯ 0 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 0 0 0 ⋯ 0 )

Here, ∗ stands for arbitrary numbers, and the vectors ( c p , 1 , c p , 2 , … , c p , m ) for every p ∈ { 1 , … , q } and ( d p , 1 , … , d p , m ) for every p ∈ { 1 , … , l } are nonzero.

Then ( y 1 , … , y q ) with

y i := ∑ j = 1 m c i , j B j

is a basis of U + W and ( z 1 , … , z l ) with

z i := ∑ j = 1 m d i , j B j

is a basis of U ∩ W .

Proof of correctness

First, we define π 1 : V × V → V , ( a , b ) ↦ a to be the projection to the first component.

Let H := { ( u , u ) ∣ u ∈ U } + { ( w , 0 ) ∣ w ∈ W } ⊆ V × V . Then π 1 ( H ) = U + W and H ∩ ( 0 × V ) = 0 × ( U ∩ W ) .

Also, H ∩ ( 0 × V ) is the kernel of π 1 | H , the projection restricted to H. Therefore, dim ⁡ ( H ) = dim ⁡ ( U + W ) + dim ⁡ ( U ∩ W ) .

The Zassenhaus Algorithm calculates a basis of H. In the first m columns of this matrix, there is a basis y i of U + W .

The rows of the form ( 0 , z i ) (with z i ≠ 0 ) are obviously in H ∩ ( 0 × V ) . Because the matrix is in row echelon form, they are also linearly independent. All rows which are different from zero ( ( y i , ∗ ) and ( 0 , z i ) ) are a basis of H, so there are dim ⁡ ( U ∩ W ) such z i s. Therefore, the z i s form a basis of U ∩ W .

Example

Consider the two subspaces U = ⟨ ( 1 − 1 0 1 ) , ( 0 0 1 − 1 ) ⟩ and W = ⟨ ( 5 0 − 3 3 ) , ( 0 5 − 3 − 2 ) ⟩ of the vector space R 4 .

Using the standard basis, we create the following matrix of dimension ( 2 + 2 ) × ( 2 ⋅ 4 ) :

( 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 ) .

Using elementary row operations, we transform this matrix into the following matrix:

( 1 0 0 0 ∗ ∗ ∗ ∗ 0 1 0 − 1 ∗ ∗ ∗ ∗ 0 0 1 − 1 ∗ ∗ ∗ ∗ 0 0 0 0 1 − 1 0 1 ) (some entries have been replaced by " ∗ " because they are irrelevant to the result).

Therefore, ( ( 1 0 0 0 ) , ( 0 1 0 − 1 ) , ( 0 0 1 − 1 ) ) is a basis of U + W , and ( ( 1 − 1 0 1 ) ) is a basis of U ∩ W .