ザッセンハウスアルゴリズム

Vをベクトル空間とし、U、WをVの2つの有限次元部分空間とし、UとWの持つ生成集合を以下のように定義する。

${\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle }$

そして

${\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle .}$

最後に${\displaystyle B_{1},\ldots ,B_{m}}$線形独立なベクトルであるため、$u_i$そして${\displaystyle w_{i}}$次のように書くことができます

$u_i=\sum_j=1^ma_i,jB_j$

そして

${\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}.}$

このアルゴリズムは和の底を計算します${\displaystyle U+W}$交差点の基点${\displaystyle U\cap W}$。

このアルゴリズムは、次のサイズのブロック行列を作成します。${\displaystyle ((n+k)\times (2m))}$:

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

基本行操作を用いて、この行列を行階段形に変換します。すると、次の形状になります。

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

ここ、${\displaystyle \bullet }$は任意の数値を表し、ベクトルは ${\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})}$すべての${\displaystyle p\in \{1,\ldots ,q\}}$そして${\displaystyle (d_{p,1},\ldots ,d_{p,m})}$すべての${\displaystyle p\in \{1,\ldots ,\ell \}}$ゼロではない。

それから${\displaystyle (y_{1},\ldots ,y_{q})}$と

${\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}}$

は基礎となる${\displaystyle U+W}$ そして${\displaystyle (z_{1},\ldots ,z_{\ell })}$と

${\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}}$

は基礎となる${\displaystyle U\cap W}$。

まず、定義します${\displaystyle \pi _{1}:V\times V\to V,(a,b)\mapsto a}$最初の成分への投影となる。

させて ${\displaystyle H:=\{(u,u)\mid u\in U\}+\{(w,0)\mid w\in W\}\subseteq V\times V.}$ それから${\displaystyle \pi _{1}(H)=U+W}$そして ${\displaystyle H\cap (0\times V)=0\times (U\cap W)}$。

また、${\displaystyle H\cap (0\times V)}$は核心です${\displaystyle {\pi _{1}|}_{H}}$、射影はHに制限される。したがって、${\displaystyle \dim(H)=\dim(U+W)+\dim(U\cap W)}$。

ザッセンハウスアルゴリズムはHの基底を計算します。この行列の最初のm列には基底があります。${\displaystyle y_{i}}$の${\displaystyle U+W}$。

フォームの行${\displaystyle (0,z_{i})}$（と${\displaystyle z_{i}\neq 0}$）は明らかに${\displaystyle H\cap (0\times V)}$行列は行階段形なので、線形独立でもあります。ゼロと異なるすべての行 (${\displaystyle (y_{i},\bullet )}$そして${\displaystyle (0,z_{i})}$) はHの基底なので、${\displaystyle \dim(U\cap W)}$そのような${\displaystyle z_{i}}$s。したがって、${\displaystyle z_{i}}$s は基礎を形成する${\displaystyle U\cap W}$。