In mathematics, the Zassenhaus algorithm
is a method to calculate a
basis
Basis may refer to:
Finance and accounting
* Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting ...
for the
intersection and
sum of two
subspaces of a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
.
It is named after
Hans Zassenhaus, but no publication of this algorithm by him is known.
It is used in
computer algebra system
A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The d ...
s.
Algorithm
Input
Let be a vector space and , two finite-dimensional subspaces of with the following
spanning set
In mathematics, the linear span (also called the linear hull or just span) of a set of vectors (from a vector space), denoted , pp. 29-30, §§ 2.5, 2.8 is defined as the set of all linear combinations of the vectors in . It can be characterized ...
s:
:
and
:
Finally, let
be
linearly independent
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts are ...
vectors so that
and
can be written as
:
and
:
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
:
:
Using
elementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multi ...
, this matrix is transformed to the
row echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian ...
. Then, it has the following shape:
:
Here,
stands for arbitrary numbers, and the vectors
for every
and
for every
are nonzero.
Then
with
:
is a basis of
and
with
:
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
Kernel may refer to:
Computing
* Kernel (operating system), the central component of most operating systems
* Kernel (image processing), a matrix used for image convolution
* Compute kernel, in GPGPU programming
* Kernel method, in machine learn ...
of
, the projection
restricted to .
Therefore,
.
The Zassenhaus algorithm calculates a basis of . In the first 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
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian ...
, they are also linearly independent.
All rows which are different from zero (
and
) are a basis of , 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
:
:
Using
elementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multi ...
, 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
*
Gröbner basis
In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field . A Gröbn ...
References
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
Algorithms
Linear algebra