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\} \leq 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 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 Thursday, August 27, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.