Zassenhaus algorithm

The Zassenhaus algorithm is an algorithm for the determination of intersection and sum bases of two subspaces in linear algebra . The algorithm is named after the mathematician Hans Zassenhaus , but Zassenhaus is not aware of any scientific publication of the algorithm. It is used in computer algebra systems .

algorithm

requirements

Let a vector space and two finite-dimensional sub-vector spaces of , each of which have a known generating system: ${\displaystyle V}$ ${\displaystyle U,W}$ ${\displaystyle V}$

${\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }$

and

${\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle }$.

Finally, one still needs linearly independent vectors in which the representation ${\displaystyle B_{1},\ldots ,B_{m}}$

${\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}$

and

${\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}}$

is known.

Goal of the algorithm

We are looking for bases of the sum and the intersection . ${\displaystyle U+W}$ ${\displaystyle U\cap W}$

algorithm

Put the following matrix as a block matrix ${\displaystyle ((n+k)\times (2m))}$

${\displaystyle {\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}}}$

on. With the help of the line transformations, this matrix is ​​transformed into a matrix in the form of steps of the following form:

${\displaystyle {\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}}}$

Let the vectors for and for not be the zero vectors. ${\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})}$ ${\displaystyle p\in \{1,\ldots ,q\}}$ ${\displaystyle (d_{p,1},\ldots ,d_{p,m})}$ ${\displaystyle p\in \{1,\ldots ,l\}}$

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

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

a basis of and with ${\displaystyle U+W}$ ${\displaystyle (z_{1},\ldots ,z_{l})}$

${\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}$

a base of . ${\displaystyle U\cap W}$

correctness

The correctness of the algorithm is based on the following knowledge: The subspace satisfies and , where the projection is on the first component. At the same time, the core is limited to projection. In particular is . ${\displaystyle H:=\{(u,u)|u\in U\}+\{(w,0)|w\in W\}\leq V\times V}$ ${\displaystyle \pi _{1}(H)=U+W}$ ${\displaystyle H\cap (0\times V)=0\times (U\cap W)}$ ${\displaystyle \pi _{1}:V\times V\to V}$ ${\displaystyle H\cap (0\times V)}$ ${\displaystyle H}$ ${\displaystyle \dim(H)=\dim(U+W)+\dim(U\cap W)}$

The Zassenhaus algorithm calculates a basis of . A base of is calculated in the first columns of the matrix . The lines are obviously contained in and are linearly independent because of the line step form. All nonzero rows together so and have but one based on form, ie the number of true with consistent, d. H. a basis of . ${\displaystyle H}$ ${\displaystyle m}$ ${\displaystyle y_{i}}$ ${\displaystyle U+W}$ ${\displaystyle (0,z_{i})}$ ${\displaystyle H\cap (0\times V)}$ ${\displaystyle (y_{i},\ast )}$ ${\displaystyle (0,z_{i})}$ ${\displaystyle H}$ ${\displaystyle z_{i}}$ ${\displaystyle \dim(U\cap W)}$ ${\displaystyle U\cap W}$

example

The two subspaces and des are given . ${\displaystyle U=\left\langle {\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}},{\begin{pmatrix}0\\0\\1\\-1\end{pmatrix}}\right\rangle }$ ${\displaystyle W=\left\langle {\begin{pmatrix}5\\0\\-3\\3\end{pmatrix}},{\begin{pmatrix}0\\5\\-3\\-2\end{pmatrix}}\right\rangle }$ ${\displaystyle \mathbb {R} ^{4}}$

By using as the unit basis of the use, you have the following matrix ${\displaystyle (B_{1},B_{2},B_{3},B_{4})}$ ${\displaystyle \mathbb {R} ^{4}}$

${\displaystyle {\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}}}$

bring them to a stepped form using elementary line transformations. This ultimately delivers

${\displaystyle {\begin{pmatrix}1&0&0&0&&*&*&*&*\\0&1&0&-1&&*&*&*&*\\0&0&1&-1&&*&*&*&*\\\\0&0&0&0&&1&-1&0&1\end{pmatrix}}}$.

Hence is a basis of , and is a basis of . ${\displaystyle \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)}$ ${\displaystyle U+W}$ ${\displaystyle \left({\begin{pmatrix}1\\-1\\0\\1\end{pmatrix}}\right)}$ ${\displaystyle U\cap W}$

literature

• Gerd Fischer : textbook linear algebra and analytical geometry . Vieweg + Teubner , Wiesbaden 2012, ISBN 978-3-8348-2378-6 , pp. 207-210 , doi : 10.1007 / 978-3-8348-2379-3 .

Web links

• Mathematics online lexicon: Zassenhaus algorithm. Retrieved September 15, 2012 . 

Individual evidence

1. ^ Eugene M. Luks, Ferenc Rákóczi, Charles RB Wright: Some Algorithms for Nilpotent Permutation Groups . 1996, p. 15 ( online [accessed September 15, 2012]).
2. ↑ Fischer, p. 210
3. ^ GAP matrices. Retrieved September 15, 2012 . 
4. ↑ MeatAxe - Other Kernel Functions. (No longer available online.) Formerly in the original ; Retrieved September 15, 2012 .  ( Page no longer available , search in web archives )