Zassenhaus algorithm explained

In mathematics, the Zassenhaus algorithm^[1] 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:

U = \langle u _{1,} \ldots, u _{n\rangle} andW = \langle w _{1,} \ldots, w _{k\rangle.} Finally, let B _{1,} \ldots, B _{m} be linearly independent vectors so that u _{i} and w _{i} can be written asu _{i} = \sum ^{m} _{j =1} a _{i,j} B _{j} andw _{i} = \sum ^{m} _{j =1} b _{i,j} B _{j.}

Output

U + W and a base of the intersection U \cap W .

Algorithm

The algorithm creates the following block matrix of size

((n + k) x ( 2 m)) :\begin{pmatrix} a _{1,1} &a _{1,2} & … &a _{1,m} &a _{1,1} &a _{1,2} & … &a _{1,m} \\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 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 \\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ b _{k,1} &b _{k,2} & … &b _{k,m} & 0 & 0 & … & 0 \end{pmatrix}

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

\begin{pmatrix} c _{1,1} &c _{1,2} & … &c _{1,m} &\bullet&\bullet& … &\bullet\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ c _{q,1} &c _{q,2} & … &c _{q,m} &\bullet&\bullet& … &\bullet\\ 0 & 0 & … & 0 &d _{1,1} &d _{1,2} & … &d _{1,m} \\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 0 & 0 & … & 0 &d _{\ell,1} &d _{\ell,2} & … &d _{\ell,m} \\ 0 & 0 & … & 0 & 0 & 0 & … & 0 \\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 0 & 0 & … & 0 & 0 & 0 & … & 0 \end{pmatrix} Here, \bullet stands for arbitrary numbers, and the vectors (c _{p,1} , c _{p,2} , \ldots, c _{p,m} ) for every p \in \{ 1 , \ldots, q\} and (d _{p,1} , \ldots, d _{p,m} ) for every p\in \{ 1 , \ldots, \ell\} are nonzero.

Then

(y _{1,} \ldots, y _{q)} withy _{i} : = \sum ^{m} _{j =1} c _{i,j} B _{j} is a basis of U + W and (z _{1,} \ldots, z _{\ell)} withz _{i} : = \sum ^{m} _{j =1} d _{i,j} B _{j} is a basis of U \cap W .

Proof of correctness

First, we define

\pi _{1} : V x V \to V, (a, b) \mapsto a to be the projection to the first component.

Let

H: = \{(u,u) \mid u\in U\} + \{(w, 0 ) \mid w\in W\} \subseteq V x V. Then \pi _{1(H)} = U + W andH\cap( 0 x V) =0 x (U\cap W) .

Also,

H \cap ( 0 x V) is the kernel of {\pi _{1|}} _{H} , the projection restricted to .Therefore, \dim(H) = \dim(U + W) + \dim(U\cap W) .

The Zassenhaus algorithm calculates a basis of . In the first 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 \cap ( 0 x V) . Because the matrix is in row echelon form, they are also linearly independent.All rows which are different from zero ((y _{i,} \bullet) and ( 0 , z _{i)} ) are a basis of, so there are \dim(U \cap W) such z _{i} s. Therefore, the z _{i} s form a basis of U \cap W .

Example

Consider the two subspaces

U = \left\langle \left( \begin{array}{r} 1 \ -1 \ 0 \ 1 \end{array} \right), \left( \begin{array}{r} 0 \ 0 \ 1 \ -1 \end{array} \right) \right\rangle and W = \left\langle \left( \begin{array}{r} 5 \ 0 \ -3 \ 3 \end{array} \right), \left( \begin{array}{r} 0 \ 5 \ -3 \ -2 \end{array} \right) \right\rangle of the vector space R ^{4} .

Using the standard basis, we create the following matrix of dimension

( 2 + 2 ) x ( 2 ⋅ 4 ) :\left( \begin{array}{rrrrrrrr} 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 \end{array} \right).

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

\left( \begin{array}{rrrrrrrrr} 1 & 0 & 0 & 0 & & \bullet & \bullet & \bullet & \bullet \\ 0 & 1 & 0 & -1 & &\bullet&\bullet&\bullet&\bullet\\ 0 & 0 & 1 & -1 & &\bullet&\bullet&\bullet&\bullet\ \\ 0 & 0 & 0 & 0 & & 1 & -1 & 0 & 1 \end{array} \right) (Some entries have been replaced by "\bullet " because they are irrelevant to the result.)

Therefore

\left( \left(\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \end{array} \right), \left( \begin{array}{r} 0 \\ 1 \\ 0 \\ -1 \end{array} \right), \left( \begin{array}{r} 0 \\ 0 \\ 1 \\ -1 \end{array}\right) \right) is a basis of U + W , and\left( \left(\begin{array}{r} 1 \\ -1 \\ 0 \\ 1 \end{array}\right) \right) is a basis of U \cap W .

See also

• Gröbner basis

External links

• Web site: Mathematik-Online-Lexikon: Zassenhaus-Algorithmus. 2012-09-15. de.

Notes and References

1. .