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 V be a vector space and U, W two finite-dimensional subspaces of V 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 _{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))$:

${\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots &a_{1,m}&a_{1,1}&a_{1,2}&\cdots &a_{1,m}\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\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\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\b_{k,1}&b_{k,2}&\cdots &b_{k,m}&0&0&\cdots &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}&\cdots &c_{1,m}&*&*&\cdots &*\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\c_{q,1}&c_{q,2}&\cdots &c_{q,m}&*&*&\cdots &*\\0&0&\cdots &0&d_{1,1}&d_{1,2}&\cdots &d_{1,m}\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\0&0&\cdots &0&d_{l,1}&d_{l,2}&\cdots &d_{l,m}\\0&0&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\0&0&\cdots &0&0&0&\cdots &0\end{pmatrix}}$

Here, $*$ 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 ,l\}$ are nonzero.

Then $(y_{1},\ldots ,y_{q})$ with

$y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}$

is a basis of $U+W$ and $(z_{1},\ldots ,z_{l})$ 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}\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},*)$ 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\langle {\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}},{\begin{pmatrix}0\\0\\1\\-1\end{pmatrix}}\right\rangle$ and $W=\left\langle {\begin{pmatrix}5\\0\\-3\\3\end{pmatrix}},{\begin{pmatrix}0\\5\\-3\\-2\end{pmatrix}}\right\rangle$ of the vector space $\mathbb {R} ^{4}$.

Using the standard basis, we create the following matrix of dimension $(2+2)\times (2\cdot 4)$:

${\begin{pmatrix}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{pmatrix}}.$

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

${\begin{pmatrix}1&0&0&0&&*&*&*&*\\0&1&0&-1&&*&*&*&*\\0&0&1&-1&&*&*&*&*\\\\0&0&0&0&&1&-1&0&1\end{pmatrix}}$ (some entries have been replaced by "$*$" because they are irrelevant to the result).

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

See also

• Gröbner basis

External links

• "Mathematik-Online-Lexikon: Zassenhaus-Algorithmus" (in German). Retrieved 2012-09-15.