View source for Zassenhaus algorithm

{{Short description|Mathematic algorithm for basis}}
In mathematics, the '''Zassenhaus algorithm'''<ref>{{citation
 | last2 = Rákóczi | first2 = Ferenc
 | last3 = Wright | first3 = Charles R. B.
 | date = April 1997
 | doi = 10.1006/jsco.1996.0092
 | issue = 4
 | journal = Journal of Symbolic Computation
 | pages = 335–354
 | title = Some algorithms for nilpotent permutation groups
 | volume = 23| doi-access = free
 }}.</ref>
is a method to calculate a [[Basis (linear algebra)|basis]] for the [[Linear subspace#Intersection|intersection]] and [[Linear subspace#Sum|sum]] of two [[Linear subspace|subspaces]] of a [[Vector space|vector space]].
It is named after Hans Zassenhaus, but no publication of this algorithm by him is known.<ref name="fischer">{{citation
 | last = Fischer | first = Gerd
 | doi = 10.1007/978-3-8348-2379-3
 | isbn = 978-3-8348-2378-6
 | language = de
 | pages = 207–210
 | publisher = Vieweg+Teubner
 | title = Lernbuch Lineare Algebra und Analytische Geometrie
 | year = 2012}}</ref> It is used in [[Software:Computer algebra system|computer algebra system]]s.<ref>{{citation
 | access-date = 2015-06-11
 | author = The GAP Group
 | contribution = 24 Matrices
 | contribution-url = http://www.gap-system.org/Manuals/doc/ref/chap24.html
 | date = February 13, 2015
 | title = GAP Reference Manual, Release 4.7}}</ref>

== Algorithm ==

=== Input ===

Let {{mvar|V}} be a vector space and {{mvar|U}}, {{mvar|W}} two finite-dimensional subspaces of {{mvar|V}} with the following spanning sets:
:<math>U = \langle u_1, \ldots, u_n\rangle</math>
and
:<math>W = \langle w_1, \ldots, w_k\rangle.</math>
Finally, let <math>B_1, \ldots, B_m</math> be [[Linear independence|linearly independent]] vectors so that <math>u_i</math> and <math>w_i</math> can be written as
:<math>u_i = \sum_{j=1}^m a_{i,j}B_j</math>
and
:<math>w_i = \sum_{j=1}^m b_{i,j}B_j.</math>

=== Output ===

The algorithm computes the base of the [[Linear subspace#Sum|sum]] <math>U + W</math> and a base of the [[Linear subspace#Intersection|intersection]] <math>U \cap W</math>.

=== Algorithm ===

The algorithm creates the following [[Block matrix|block matrix]] of size <math>((n+k) \times (2m))</math>:
:<math>\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}</math>

Using elementary row operations, this matrix is transformed to the [[Row echelon form|row echelon form]]. Then, it has the following shape:
:<math>\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}</math>
Here, <math>\bullet</math> stands for arbitrary numbers, and the vectors 
<math>(c_{p,1}, c_{p,2}, \ldots, c_{p,m})</math> for every <math>p \in \{1, \ldots, q\}</math> and <math>(d_{p,1}, \ldots, d_{p,m})</math> for every <math>p\in \{1, \ldots, \ell\}</math> are nonzero.

Then <math>(y_1, \ldots, y_q)</math> with
:<math>y_i := \sum_{j=1}^m c_{i,j}B_j</math> 
is a basis of <math>U+W</math>
and <math>(z_1, \ldots, z_\ell)</math> with
:<math>z_i := \sum_{j=1}^m d_{i,j}B_j</math> 
is a basis of <math>U \cap W</math>.

=== Proof of correctness ===

First, we define <math>\pi_1 : V \times V \to V, (a, b) \mapsto a</math> to be the projection to the first component.

Let
<math>H:=\{(u,u) \mid u\in U\}+\{(w,0) \mid w\in W\} \subseteq V\times V.</math>
Then <math>\pi_1(H) = U+W</math> and
<math>H\cap(0\times V)=0\times(U\cap W)</math>.

Also, <math>H \cap (0 \times V)</math> is the [[Kernel (linear algebra)|kernel]] of <math>{\pi_1|}_H</math>, the projection [[Restriction (mathematics)|restricted]] to {{mvar|H}}.
Therefore, <math>\dim(H) = \dim(U+W)+\dim(U\cap W)</math>.

The Zassenhaus algorithm calculates a basis of {{mvar|H}}. In the first {{mvar|m}} columns of this matrix, there is a basis <math>y_i</math> of <math>U+W</math>.

The rows of the form <math>(0, z_i)</math> (with <math>z_i \neq 0</math>) are obviously in <math>H \cap (0 \times V)</math>. Because the matrix is in [[Row echelon form|row echelon form]], they are also linearly independent.
All rows which are different from zero (<math>(y_i, \bullet)</math> and <math>(0, z_i)</math>) are a basis of {{mvar|H}}, so there are <math>\dim(U \cap W)</math> such <math>z_i</math>s. Therefore, the <math>z_i</math>s form a basis of <math>U \cap W</math>.

== Example ==
Consider the two subspaces <math>U = \left\langle \left( \begin{array}{r} 1\\ -1 \\ 0 \\ 1 \end{array} \right), \left( \begin{array}{r} 0 \\ 0 \\ 1 \\ -1 \end{array} \right) \right\rangle </math> and <math>
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
</math> of the vector space <math>\mathbb{R}^4</math>.

Using the [[Standard basis|standard basis]], we create the following matrix of dimension <math>(2 + 2) \times (2 \cdot 4)</math>:
:<math>
\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).</math>

Using elementary row operations, we transform this matrix into the following matrix:
:<math>
\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)
</math> (Some entries have been replaced by "<math>\bullet</math>" because they are irrelevant to the result.)

Therefore
<math> \left( \left(\begin{array}{r} 1\\0\\0\\0\end{array} \right), \left( \begin{array}{r} 0\\1\\0\\-1\end{array} \right), \left( \begin{array}{r} 0\\0\\1\\-1\end{array}\right) \right) </math> is a basis of <math>U+W</math>, and
<math> \left( \left(\begin{array}{r} 1\\-1\\0\\1\end{array}\right) \right) </math> is a basis of <math>U \cap W</math>.

== See also ==
* [[Gröbner basis]]

== References ==
{{reflist}}

== External links ==
* {{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]]

{{Sourceattribution|Zassenhaus algorithm}}