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:
:$U = \langle u_1, \ldots, u_n\rangle$
and
:$W = \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 as
:$u_i = \sum_^m a_B_j$
and
:$w_i = \sum_^m b_B_j.$

Output

The algorithm computes the base of the sum $U + W$ and a base of the intersection $U \cap W$.

Algorithm

The algorithm creates the following block matrix of size $((n+k) \times (2m))$:
:$\begin a_&a_&\cdots&a_&a_&a_&\cdots&a_\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ a_&a_&\cdots&a_&a_&a_&\cdots&a_\\ b_&b_&\cdots&b_&0&0&\cdots&0\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ b_&b_&\cdots&b_&0&0&\cdots&0 \end$

Using elementary row operations, this matrix is transformed to the row echelon form. Then, it has the following shape:
:$\begin c_&c_&\cdots&c_&\bullet&\bullet&\cdots&\bullet\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ c_&c_&\cdots&c_&\bullet&\bullet&\cdots&\bullet\\ 0&0&\cdots&0&d_&d_&\cdots&d_\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 0&0&\cdots&0&d_&d_&\cdots&d_\\ 0&0&\cdots&0&0&0&\cdots&0\\ \vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\ 0&0&\cdots&0&0&0&\cdots&0 \end$
Here, $\bullet$ stands for arbitrary numbers, and the vectors
$(c_, c_, \ldots, c_)$ for every $p \in \$ and $(d_, \ldots, d_)$ for every $p\in \$ are nonzero.

Then $(y_1, \ldots, y_q)$ with
:$y_i := \sum_^m c_B_j$
is a basis of $U+W$
and $(z_1, \ldots, z_\ell)$ with
:$z_i := \sum_^m d_B_j$
is a basis of $U \cap W$.

Proof of correctness

First, we define $\pi_1 : V \times V \to V, (a, b) \mapsto a$ to be the projection to the first component.

Let
$H:=\+\ \subseteq V\times V.$
Then $\pi_1(H) = U+W$ and
$H\cap(0\times V)=0\times(U\cap W)$.

Also, $H \cap (0 \times V)$ is the kernel of $_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 \neq 0$) are obviously in $H \cap (0 \times 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 1\\ -1 \\ 0 \\ 1 \end \right), \left( \begin 0 \\ 0 \\ 1 \\ -1 \end \right) \right\rangle$ and $W = \left\langle \left( \begin 5 \\ 0 \\ -3 \\ 3 \end \right), \left( \begin 0 \\ 5 \\ -3 \\ -2 \end \right) \right\rangle$ of the vector space $\mathbb^4$.

Using the standard basis, we create the following matrix of dimension $(2 + 2) \times (2 \cdot 4)$:
:$\left( \begin 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 \right).$

Using elementary row operations, we transform this matrix into the following matrix:
:$\left( \begin 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 \right)$ (Some entries have been replaced by "$\bullet$" because they are irrelevant to the result.)

Therefore
$\left( \left(\begin 1\\0\\0\\0\end \right), \left( \begin 0\\1\\0\\-1\end \right), \left( \begin 0\\0\\1\\-1\end\right) \right)$ is a basis of $U+W$, and
$\left( \left(\begin 1\\-1\\0\\1\end\right) \right)$ is a basis of $U \cap W$.

See also

* Gröbner basis

References

External links

* {{cite web, url=http://mo.mathematik.uni-stuttgart.de/inhalt/beispiel/beispiel1105/, title=Mathematik-Online-Lexikon: Zassenhaus-Algorithmus, access-date=2012-09-15, language=de

Algorithms
Linear algebra
Eponymous algorithms