자센하우스 알고리즘

수학에서 자센하우스 알고리즘은^[1] 벡터 공간의 두 서브스페이스의 교차로와 합을 계산하는 방법이다.한스 자센하우스(Hans Zassenhaus)의 이름을 따서 명명되었지만, 그에 의해 이 알고리즘의 간행물은 알려져 있지 않다.^[2]그것은 컴퓨터 대수 체계에서 사용된다.^[3]

알고리즘.

입력

V는 벡터 공간이 되고 U, W는 다음과 같은 스패닝 세트가 있는 V의 두 개의 유한한 차원 서브스페이스가 된다.

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

그리고

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

마지막으로 B ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle B_{}}$ ${\displaystyle {}_{}}$ ${\$은(는$)$ ${\displaystyle u_{}}$ i {\$displaystyle$u_{$i}$ 및 ${\displaystyle w_{}}$ i ${\$라고 쓸 수 있도록$$ 선형 독립 벡터가 되도록$$ 한다.

${\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}}}}}$

그리고

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

출력

알고리즘은 $U{\displaystyle }$+ ${\displaystyle W}$의$$합계 베이스와$$ U$u{\displaystyle }$$$W의 ${\displaystyle \mathrm{교차점}}$ $베이스$ U comput W {\$displaystyle$ U$\cap$ W$}$를 계산한다$.$

알고리즘.

알고리즘은 다음과 같은 크기의 블록 매트릭스${\displaystyle }$( ${\displaystyle (\mathrm{n}}$+ k${\displaystyle }$)${\displaystyle \times }$ ( 2 ${\displaystyle m}$)${\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&amp을 말한다.0&, \cdots, 0\\\vdots, \vdots &, 및 &, \vdots &, \vdots &, \vdots & &,&\vdots \\b_{k,1}&, b_{k,2}&, \cdots &, b_{k,m}&, 0&, 0&, \cdo.ts &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_{120.}&\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&\cdots &0&\vdots &\vdots &\0&#0&#cdots &0&#0&#cdots &0&#0>cdt;{pmatrix}}}}$

Here, ${\displaystyle \bullet }$ stands for arbitrary numbers, and the vectors ${\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})}$ for every ${\displaystyle p\in \{1,\ldots ,q\}}$ and ${\displaystyle (d_{p,1},\ldots ,d_{p,m}$$p{\displaystyle \in \{1,}$… ,${\displaystyle \ell \}}$ ${\displaystyle p\in \{1,\ldots,\ell \}}$은(는) 0이 아니다$$.

그런$$ 다음$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle {}_{}}$ ${\displaystyle q_{}}$) ${\displaystyle(y_{1},\ldots ,y_{q}},$

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

$U{\displaystyle }$$$${\displaystyle }$+ ${\displaystyle W}$ ${\displaystyle U+W}$ 및$$ $({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, z ${\displaystyle {\ell }_{}}$) ${\displaystyle (z_{1},\ldots ,z_{\ell }}}$의 기본 구성 요소:

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

$U{\displaystyle }$ ${\displaystyle \cap }$ ${\displaystyle W}$ ${\displaystyle U\cap W}$의 기본이다$.$

정확성 증명

${\displaystyle \mathrm{먼저}}$ $\pi {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$: ${\displaystyle V}$ ${\displaystyle \times }$ V${\displaystyle }$→ ${\displaystyle V}$,${\displaystyle }$( ${\displaystyle a}$, ${\displaystyle b}$) ${\displaystyle \mapsto }$ a ${\displaystyle \pi _{1}:$$V\time V\to$V$,$ $(a,b)\mapsto a}$이(가) 첫 번째 구성 요소에 대한 투영이어야 함

Let ${\displaystyle H:=\{(u,u)\mid u\in U\}+\{(w,0)\mid w\in W\}\subseteq V\times V.}$ Then ${\displaystyle \pi _{1}(H)=U+W}$ and ${\displaystyle H\cap (0\times V)=0\times (U\cap W)}$.

또한 $H{\displaystyle }$ ${\displaystyle \cap }$(${\displaystyle 0}$ ${\displaystyle \times }$ V${\displaystyle }$) ${\displaystyle H\cap (0\time$ V$)}$은 $\pi {\displaystyle {{}_{}}_{}}$ ${\displaystyle {{1\mathrm{}}_{}}_{}}$ ${\displaystyle {H{}_{}}_{}}$ ${\$의 커널이며$,$ 투영법은 H로 제한된다.따라서 ${\displaystyle 딤)}$ (${\displaystyle }$H )${\displaystyle }$=${\displaystyle 딤w}$(${\displaystyle }$U +${\displaystyle W}$ ) + 딤 ${\displaystyle )}$ ${\displaystyle \cap }$ ${\displaystyle W}$ ) ${\displaystyle \dim(H)=\dim(U+W)+\dim$(U$\backslash$$cap$ W$)}}.$

자센하우스 알고리즘은 H의 기초를 계산한다.이 행렬의 첫 번째 m 열에는 $U{\displaystyle }$+ ${\displaystyle W}$ ${\displaystyle U+W}$의 기본 ${\displaystyle y_{}}$ ${\$가 있다$.$

$({\displaystyle }$$0{\displaystyle {}_{}}$${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle (0,z_{i}}})$ 형식의 행은 $분명히{\displaystyle }$ H$$$$($0$ ${\displaystyle V)}$ ${\displaystyle z_$${i}\$$neq 0$$\}$에 있다$.$ 행렬이 echelon 형식에 있기 때문에 이들 행도 선형적으로 독립적이다$.$All rows which are different from zero (${\displaystyle (y_{i},\bullet )}$ and ${\displaystyle (0,z_{i})}$) are a basis of H, so there are ${\displaystyle \dim(U\cap W)}$ such ${\displaystyle z_{i}}$s.따라서 $z{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 $U{\displaystyle }$ ${\displaystyle \cap }$ ${\displaystyle W}$ ${\displaystyle U\cap W}$의 기초를 형성한다$.$

예

Consider the two subspaces ${\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 ${\displaystyle W=⟨\left(\begin{array}{r}5\\ 0\\ -3\\ 3\end{array}\right),(\begin{array}{r}0\\ 5\\ -3\end{array}}$${\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 ${\displaystyle \mathbb {R} ^{4}}$.

표준 기준을 사용하여 다음과 ${\displaystyle \mathrm{같은}}$ 치수 행렬$({\displaystyle 2}$+ 2${\displaystyle }$) ${\displaystyle \times }$( ${\displaystyle 2}$ ${\displaystyle \cdot }$ 4$){\displaystyle(2+2)\time(2\cdot$ 4$)}$을 $생성$한다$.$

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

기본 행 연산을 사용하여 이 행렬을 다음과 같은 행렬로 변환한다.

(1000∙∙ ∙ ∙ 010− 1∙∙ ∙ ∙ 001− 1∙∙ ∙ ∙ 00001− 101){\displaystyle \left({\begin{배열}{rrrrrrrrr}1&, 0&, 0&, 0&,&\bullet&\bullet&\bullet&\bullet \\0&, 1&, 0&, -1&,&\bullet&\bullet&\bullet &a.Mp, \bullet \\0&, 0&, 1&, -1&,&\bullet&\bullet&\bullet&\bullet\.$\\\0&0&0&0&#1&1$&1$&1$&#$1\end${array$}\right)}($일부 항목은 결과와 무관하기 때문에 ${\displaystyle }$ ${\displaystyle \bullet$ $\}"$로 대체되었다.)

Therefore ${\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 ${\displaystyle U+W}$${\displaystyle U+W$ 및${\displaystyle }$(${\displaystyle 1\begin{array}{r}\mathrm{}\\ \end{array}}$- ${\displaystyle \begin{array}{}1\\ \mathrm{}\end{array}}$ 0 ${\displaystyle \begin{array}{}1\\ \mathrm{}\end{array}}$)${\$\1\nd{$array}\오른쪽)}$는 U${\displaystyle }${ ${\displaystyle W}$ ${\displaystystystyle$ U$\cap$ W$}$의 기본이다$.$

참고 항목

• 그뢰브너 기준

참조

외부 링크

• "Mathematik-Online-Lexikon: Zassenhaus-Algorithmus" (in German). Retrieved 2012-09-15.