- Source: Zassenhaus algorithm
In mathematics, the Zassenhaus algorithm
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. It is used in computer algebra systems.
Algorithm
= Input
=Let V be a vector space and U, W two finite-dimensional subspaces of V with the following spanning sets:
U
=
⟨
u
1
,
…
,
u
n
⟩
{\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }
and
W
=
⟨
w
1
,
…
,
w
k
⟩
.
{\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle .}
Finally, let
B
1
,
…
,
B
m
{\displaystyle B_{1},\ldots ,B_{m}}
be linearly independent vectors so that
u
i
{\displaystyle u_{i}}
and
w
i
{\displaystyle w_{i}}
can be written as
u
i
=
∑
j
=
1
m
a
i
,
j
B
j
{\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}
and
w
i
=
∑
j
=
1
m
b
i
,
j
B
j
.
{\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}.}
= Output
=The algorithm computes the base of the sum
U
+
W
{\displaystyle U+W}
and a base of the intersection
U
∩
W
{\displaystyle U\cap W}
.
= Algorithm
=The algorithm creates the following block matrix of size
(
(
n
+
k
)
×
(
2
m
)
)
{\displaystyle ((n+k)\times (2m))}
:
(
a
1
,
1
a
1
,
2
⋯
a
1
,
m
a
1
,
1
a
1
,
2
⋯
a
1
,
m
⋮
⋮
⋮
⋮
⋮
⋮
a
n
,
1
a
n
,
2
⋯
a
n
,
m
a
n
,
1
a
n
,
2
⋯
a
n
,
m
b
1
,
1
b
1
,
2
⋯
b
1
,
m
0
0
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
b
k
,
1
b
k
,
2
⋯
b
k
,
m
0
0
⋯
0
)
{\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}}}
Using elementary row operations, this matrix is transformed to the row echelon form. Then, it has the following shape:
(
c
1
,
1
c
1
,
2
⋯
c
1
,
m
∙
∙
⋯
∙
⋮
⋮
⋮
⋮
⋮
⋮
c
q
,
1
c
q
,
2
⋯
c
q
,
m
∙
∙
⋯
∙
0
0
⋯
0
d
1
,
1
d
1
,
2
⋯
d
1
,
m
⋮
⋮
⋮
⋮
⋮
⋮
0
0
⋯
0
d
ℓ
,
1
d
ℓ
,
2
⋯
d
ℓ
,
m
0
0
⋯
0
0
0
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
0
0
⋯
0
0
0
⋯
0
)
{\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}}}
Here,
∙
{\displaystyle \bullet }
stands for arbitrary numbers, and the vectors
(
c
p
,
1
,
c
p
,
2
,
…
,
c
p
,
m
)
{\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})}
for every
p
∈
{
1
,
…
,
q
}
{\displaystyle p\in \{1,\ldots ,q\}}
and
(
d
p
,
1
,
…
,
d
p
,
m
)
{\displaystyle (d_{p,1},\ldots ,d_{p,m})}
for every
p
∈
{
1
,
…
,
ℓ
}
{\displaystyle p\in \{1,\ldots ,\ell \}}
are nonzero.
Then
(
y
1
,
…
,
y
q
)
{\displaystyle (y_{1},\ldots ,y_{q})}
with
y
i
:=
∑
j
=
1
m
c
i
,
j
B
j
{\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}}
is a basis of
U
+
W
{\displaystyle U+W}
and
(
z
1
,
…
,
z
ℓ
)
{\displaystyle (z_{1},\ldots ,z_{\ell })}
with
z
i
:=
∑
j
=
1
m
d
i
,
j
B
j
{\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}
is a basis of
U
∩
W
{\displaystyle U\cap W}
.
= Proof of correctness
=First, we define
π
1
:
V
×
V
→
V
,
(
a
,
b
)
↦
a
{\displaystyle \pi _{1}:V\times V\to V,(a,b)\mapsto a}
to be the projection to the first component.
Let
H
:=
{
(
u
,
u
)
∣
u
∈
U
}
+
{
(
w
,
0
)
∣
w
∈
W
}
⊆
V
×
V
.
{\displaystyle H:=\{(u,u)\mid u\in U\}+\{(w,0)\mid w\in W\}\subseteq V\times V.}
Then
π
1
(
H
)
=
U
+
W
{\displaystyle \pi _{1}(H)=U+W}
and
H
∩
(
0
×
V
)
=
0
×
(
U
∩
W
)
{\displaystyle H\cap (0\times V)=0\times (U\cap W)}
.
Also,
H
∩
(
0
×
V
)
{\displaystyle H\cap (0\times V)}
is the kernel of
π
1
|
H
{\displaystyle {\pi _{1}|}_{H}}
, the projection restricted to H.
Therefore,
dim
(
H
)
=
dim
(
U
+
W
)
+
dim
(
U
∩
W
)
{\displaystyle \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
{\displaystyle y_{i}}
of
U
+
W
{\displaystyle U+W}
.
The rows of the form
(
0
,
z
i
)
{\displaystyle (0,z_{i})}
(with
z
i
≠
0
{\displaystyle z_{i}\neq 0}
) are obviously in
H
∩
(
0
×
V
)
{\displaystyle H\cap (0\times V)}
. Because the matrix is in row echelon form, they are also linearly independent.
All rows which are different from zero (
(
y
i
,
∙
)
{\displaystyle (y_{i},\bullet )}
and
(
0
,
z
i
)
{\displaystyle (0,z_{i})}
) are a basis of H, so there are
dim
(
U
∩
W
)
{\displaystyle \dim(U\cap W)}
such
z
i
{\displaystyle z_{i}}
s. Therefore, the
z
i
{\displaystyle z_{i}}
s form a basis of
U
∩
W
{\displaystyle U\cap W}
.
Example
Consider the two subspaces
U
=
⟨
(
1
−
1
0
1
)
,
(
0
0
1
−
1
)
⟩
{\displaystyle 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 }
and
W
=
⟨
(
5
0
−
3
3
)
,
(
0
5
−
3
−
2
)
⟩
{\displaystyle 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
R
4
{\displaystyle \mathbb {R} ^{4}}
.
Using the standard basis, we create the following matrix of dimension
(
2
+
2
)
×
(
2
⋅
4
)
{\displaystyle (2+2)\times (2\cdot 4)}
:
(
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
)
.
{\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).}
Using elementary row operations, we transform this matrix into the following matrix:
(
1
0
0
0
∙
∙
∙
∙
0
1
0
−
1
∙
∙
∙
∙
0
0
1
−
1
∙
∙
∙
∙
0
0
0
0
1
−
1
0
1
)
{\displaystyle \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 "
∙
{\displaystyle \bullet }
" because they are irrelevant to the result.)
Therefore
(
(
1
0
0
0
)
,
(
0
1
0
−
1
)
,
(
0
0
1
−
1
)
)
{\displaystyle \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)}
is a basis of
U
+
W
{\displaystyle U+W}
, and
(
(
1
−
1
0
1
)
)
{\displaystyle \left(\left({\begin{array}{r}1\\-1\\0\\1\end{array}}\right)\right)}
is a basis of
U
∩
W
{\displaystyle U\cap W}
.
See also
Gröbner basis
References
External links
"Mathematik-Online-Lexikon: Zassenhaus-Algorithmus" (in German). Retrieved 2012-09-15.
Kata Kunci Pencarian:
- Grup ruang
- Zassenhaus algorithm
- Cantor–Zassenhaus algorithm
- Berlekamp–Zassenhaus algorithm
- Hans Zassenhaus
- Zassenhaus
- Factorization of polynomials over finite fields
- List of algorithms
- Berlekamp's algorithm
- Elwyn Berlekamp
- Computer algebra
