Mathematic algorithm for basis
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:
![{\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbb0a4d146bd541bf2fe42e74d789212cd5546a8)
and
![{\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/529d75b63509e6642e2dfabaa1ac142cdd428a50)
Finally, let
be linearly independent vectors so that
and
can be written as
![{\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce71eaa8f86e7d1574adb4ef364d84ef00b8332)
and
![{\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/191d7738d2d39d5222b8c1fc50717e9baa1f8ad0)
Output
The algorithm computes the base of the sum
and a base of the intersection
.
Algorithm
The algorithm creates the following block matrix of size
:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78dbf22b8c4aeb0719928c47a64571699a5eacc8)
Using elementary row operations, this matrix is transformed to the row echelon form. Then, it has the following shape:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d251d231d67450ac80764545ff2877e06874116b)
Here,
stands for arbitrary numbers, and the vectors
for every
and
for every
are nonzero.
Then
with
![{\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/849be68856fa1e5dcab0cf6303da0e62dc4e4217)
is a basis of
and
with
![{\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3de8a60b95a49a1b17faaa134139c493e64c450f)
is a basis of
.
Proof of correctness
First, we define
to be the projection to the first component.
Let
Then
and
.
Also,
is the kernel of
, the projection restricted to H. Therefore,
.
The Zassenhaus algorithm calculates a basis of H. In the first m columns of this matrix, there is a basis
of
.
The rows of the form
(with
) are obviously in
. Because the matrix is in row echelon form, they are also linearly independent. All rows which are different from zero (
and
) are a basis of H, so there are
such
s. Therefore, the
s form a basis of
.
Example
Consider the two subspaces
and
of the vector space
.
Using the standard basis, we create the following matrix of dimension
:
![{\displaystyle \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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5013679dea948ccdc59c88b8fca8e9d8cdaf529f)
Using elementary row operations, we transform this matrix into the following matrix:
(Some entries have been replaced by "
" because they are irrelevant to the result.)
Therefore
is a basis of
, and
is a basis of
.
See also
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.