Zassenhaus algorithm

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.^[2] It is used in computer algebra systems.^[3]

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$ .

References

↑ Luks, Eugene M.; Rákóczi, Ferenc; Wright, Charles R. B. (April 1997), "Some algorithms for nilpotent permutation groups", Journal of Symbolic Computation, 23 (4): 335–354, doi:10.1006/jsco.1996.0092 .
↑ Fischer, Gerd (2012), Lernbuch Lineare Algebra und Analytische Geometrie (in German), Vieweg+Teubner, pp. 207–210, doi:10.1007/978-3-8348-2379-3, ISBN 978-3-8348-2378-6
↑ The GAP Group (February 13, 2015), "24 Matrices", GAP Reference Manual, Release 4.7, retrieved 2015-06-11

External links

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

This article is issued from Wikipedia - version of the 10/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Zassenhaus algorithm

Algorithm

Input

Output

Algorithm

Proof of correctness

Example

See also

References

External links