Zassenhaus algorithm

Let {{mvar|V}} be a vector space and {{mvar|U}}, {{mvar|W}} two finite-dimensional subspaces of {{mvar|V}} with the following spanning sets:

:$U\; =\; \backslash langle\; u\_1,\; \backslash ldots,\; u\_n\backslash rangle$

and

:$W\; =\; \backslash langle\; w\_1,\; \backslash ldots,\; w\_k\backslash rangle.$

Finally, let $B\_1,\; \backslash ldots,\; B\_m$ be linearly independent vectors so that $u\_i$ and $w\_i$ can be written as

:$u\_i\; =\; \backslash sum\_\{j=1\}^m\; a\_\{i,j\}B\_j$

and

:$w\_i\; =\; \backslash sum\_\{j=1\}^m\; b\_\{i,j\}B\_j.$

The algorithm computes the base of the sum $U\; +\; W$ and a base of the intersection $U\; \backslash cap\; W$.

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

:$\backslash 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:

:$\backslash begin\{pmatrix\}$

c_{1,1}&c_{1,2}&\cdots&c_{1,m}&\bullet&\bullet&\cdots&\bullet\\

\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\

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}\\

\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\

0&0&\cdots&0&d_{\ell,1}&d_{\ell,2}&\cdots&d_{\ell,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, $\backslash bullet$ stands for arbitrary numbers, and the vectors

$(c\_\{p,1\},\; c\_\{p,2\},\; \backslash ldots,\; c\_\{p,m\})$ for every $p\; \backslash in\; \backslash \{1,\; \backslash ldots,\; q\backslash \}$ and $(d\_\{p,1\},\; \backslash ldots,\; d\_\{p,m\})$ for every $p\backslash in\; \backslash \{1,\; \backslash ldots,\; \backslash ell\backslash \}$ are nonzero.

Then $(y\_1,\; \backslash ldots,\; y\_q)$ with

:$y\_i\; :=\; \backslash sum\_\{j=1\}^m\; c\_\{i,j\}B\_j$

is a basis of $U+W$

and $(z\_1,\; \backslash ldots,\; z\_\backslash ell)$ with

:$z\_i\; :=\; \backslash sum\_\{j=1\}^m\; d\_\{i,j\}B\_j$

is a basis of $U\; \backslash cap\; W$.

First, we define $\backslash pi\_1\; :\; V\; \backslash times\; V\; \backslash to\; V,\; (a,\; b)\; \backslash mapsto\; a$ to be the projection to the first component.

Let

$H:=\backslash \{(u,u)\; \backslash mid\; u\backslash in\; U\backslash \}+\backslash \{(w,0)\; \backslash mid\; w\backslash in\; W\backslash \}\; \backslash subseteq\; V\backslash times\; V.$

Then $\backslash pi\_1(H)\; =\; U+W$ and

$H\backslash cap(0\backslash times\; V)=0\backslash times(U\backslash cap\; W)$.

Also, $H\; \backslash cap\; (0\; \backslash times\; V)$ is the kernel of $\{\backslash pi\_1|\}\_H$, the projection restricted to {{mvar|H}}.

Therefore, $\backslash dim(H)\; =\; \backslash dim(U+W)+\backslash dim(U\backslash cap\; W)$.

The Zassenhaus algorithm calculates a basis of {{mvar|H}}. In the first {{mvar|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\; \backslash neq\; 0$) are obviously in $H\; \backslash cap\; (0\; \backslash times\; V)$. Because the matrix is in row echelon form, they are also linearly independent.

All rows which are different from zero ($(y\_i,\; \backslash bullet)$ and $(0,\; z\_i)$) are a basis of {{mvar|H}}, so there are $\backslash dim(U\; \backslash cap\; W)$ such $z\_i$s. Therefore, the $z\_i$s form a basis of $U\; \backslash cap\; W$.

Consider the two subspaces $U\; =\; \backslash left\backslash langle\; \backslash left(\; \backslash begin\{array\}\{r\}\; 1\backslash \backslash \; -1\; \backslash \backslash \; 0\; \backslash \backslash \; 1\; \backslash end\{array\}\; \backslash right),\; \backslash left(\; \backslash begin\{array\}\{r\}\; 0\; \backslash \backslash \; 0\; \backslash \backslash \; 1\; \backslash \backslash \; -1\; \backslash end\{array\}\; \backslash right)\; \backslash right\backslash rangle$ and $$

W = \left\langle \left( \begin{array}{r} 5 \\ 0 \\ -3 \\ 3 \end{array} \right), \left( \begin{array}{r} 0 \\ 5 \\ -3 \\ -2 \end{array} \right) \right\rangle

of the vector space $\backslash mathbb\{R\}^4$.

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

:$$

\left( \begin{array}{rrrrrrrr} 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 "$\backslash bullet$" because they are irrelevant to the result.)

Therefore

$\backslash left(\; \backslash left(\backslash begin\{array\}\{r\}\; 1\backslash \backslash 0\backslash \backslash 0\backslash \backslash 0\backslash end\{array\}\; \backslash right),\; \backslash left(\; \backslash begin\{array\}\{r\}\; 0\backslash \backslash 1\backslash \backslash 0\backslash \backslash -1\backslash end\{array\}\; \backslash right),\; \backslash left(\; \backslash begin\{array\}\{r\}\; 0\backslash \backslash 0\backslash \backslash 1\backslash \backslash -1\backslash end\{array\}\backslash right)\; \backslash right)$ is a basis of $U+W$, and

$\backslash left(\; \backslash left(\backslash begin\{array\}\{r\}\; 1\backslash \backslash -1\backslash \backslash 0\backslash \backslash 1\backslash end\{array\}\backslash right)\; \backslash right)$ is a basis of $U\; \backslash cap\; W$.

• Gröbner basis

{{reflist}}

• {{cite web|url=http://mo.mathematik.uni-stuttgart.de/inhalt/beispiel/beispiel1105/|title=Mathematik-Online-Lexikon: Zassenhaus-Algorithmus|access-date=2012-09-15|language=de}}

Category:Algorithms

Category:Linear algebra

Category:Eponymous algorithms