Zassenhaus algorithm

Short description: Mathematic algorithm for basis

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 V be a vector space and U, W two finite-dimensional subspaces of V with the following spanning sets:

$U=⟨u_1,\dots ,u_n⟩$

and

$W=⟨w_1,\dots ,w_k⟩.$

Finally, let $B_1,\dots ,B_m$ be linearly independent vectors so that $u_i$ and $w_i$ can be written as

$u_i=\sum _{j=1}^m{a}_{i,j}{B}_j$

and

$w_i=\sum _{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\cap W$.

Algorithm

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

$\left(\begin{array}{cccccccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,m}& a_{1,1}& a_{1,2}& \cdots & a_{1,m}\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ a_{n,1}& a_{n,2}& \cdots & a_{n,m}& a_{n,1}& a_{n,2}& \cdots & a_{n,m}\\ b_{1,1}& b_{1,2}& \cdots & b_{1,m}& 0& 0& \cdots & 0\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ b_{k,1}& b_{k,2}& \cdots & b_{k,m}& 0& 0& \cdots & 0\end{array}\right)$

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

$\left(\begin{array}{cccccccc}{c}_{1,1}& c_{1,2}& \cdots & c_{1,m}& \bullet & \bullet & \cdots & \bullet \\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ c_{q,1}& c_{q,2}& \cdots & c_{q,m}& \bullet & \bullet & \cdots & \bullet \\ 0& 0& \cdots & 0& d_{1,1}& d_{1,2}& \cdots & d_{1,m}\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0& d_{\ell ,1}& d_{\ell ,2}& \cdots & d_{\ell ,m}\\ 0& 0& \cdots & 0& 0& 0& \cdots & 0\\ ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0& 0& 0& \cdots & 0\end{array}\right)$

Here, $\bullet$ stands for arbitrary numbers, and the vectors $(c_{p,1},c_{p,2},\dots ,c_{p,m})$ for every $p\in \{1,\dots ,q\}$ and $(d_{p,1},\dots ,d_{p,m})$ for every $p\in \{1,\dots ,\ell \}$ are nonzero.

Then $(y_1,\dots ,y_q)$ with

$y_i:=\sum _{j=1}^m{c}_{i,j}{B}_j$

is a basis of $U+W$ and $(z_1,\dots ,z_{\ell })$ with

$z_i:=\sum _{j=1}^m{d}_{i,j}{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:=\{(u,u)\mid u\in U\}+\{(w,0)\mid w\in W\}\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 ${{\pi }_1|}_H$, the projection restricted to H. Therefore, $\dim (H)=\dim (U+W)+\dim (U\cap 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\ne 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 H, 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(\begin{array}{r}1\\ -1\\ 0\\ 1\end{array}\right),\left(\begin{array}{r}0\\ 0\\ 1\\ -1\end{array}\right)⟩$ and $W=⟨\left(\begin{array}{r}5\\ 0\\ -3\\ 3\end{array}\right),\left(\begin{array}{r}0\\ 5\\ -3\\ -2\end{array}\right)⟩$ 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{array}{rrrrrrrrr}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(\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))$ 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

• "Mathematik-Online-Lexikon: Zassenhaus-Algorithmus" (in de). http://mo.mathematik.uni-stuttgart.de/inhalt/beispiel/beispiel1105/.