Algoritmo de Zassenhaus

Sea V un espacio vectorial y U , W dos subespacios de dimensión finita de V con los siguientes conjuntos generadores :

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

y

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

Finalmente, dejemos${\displaystyle B_{1},\ldots ,B_{m}}$sean vectores linealmente independientes de modo que${\displaystyle u_{i}}$y${\displaystyle w_{i}}$se puede escribir como

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

y

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

El algoritmo calcula la base de la suma${\displaystyle U+W}$y una base de la intersección${\displaystyle U\cap W}$.

El algoritmo crea la siguiente matriz de bloques de tamaño${\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}}}$

Utilizando operaciones elementales de fila , esta matriz se transforma a la forma escalonada de fila . Entonces, tiene la siguiente forma:

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

Aquí,${\displaystyle \bullet }$representa números arbitrarios y los vectores ${\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})}$por cada${\displaystyle p\in \{1,\ldots ,q\}}$y${\displaystyle (d_{p,1},\ldots ,d_{p,m})}$por cada${\displaystyle p\in \{1,\ldots ,\ell \}}$son distintos de cero.

Entonces${\displaystyle (y_{1},\ldots ,y_{q})}$con

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

es una base de${\displaystyle U+W}$ y${\displaystyle (z_{1},\ldots ,z_{\ell })}$con

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

es una base de${\displaystyle U\cap W}$.

Primero, definimos${\displaystyle \pi _{1}:V\times V\to V,(a,b)\mapsto a}$ser la proyección al primer componente.

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

También,${\displaystyle H\cap (0\times V)}$es el núcleo de${\displaystyle {\pi _{1}|}_{H}}$, la proyección restringida a H. Por lo tanto,${\displaystyle \dim(H)=\dim(U+W)+\dim(U\cap W)}$.

El algoritmo de Zassenhaus calcula una base de H. En las primeras m columnas de esta matriz, hay una base.${\displaystyle y_{i}}$de${\displaystyle U+W}$.

Las filas del formulario${\displaystyle (0,z_{i})}$(con${\displaystyle z_{i}\neq 0}$) están obviamente en${\displaystyle H\cap (0\times V)}$. Debido a que la matriz está en forma escalonada por filas , también son linealmente independientes. Todas las filas que son diferentes de cero (${\displaystyle (y_{i},\bullet )}$y${\displaystyle (0,z_{i})}$) son una base de H , por lo que hay${\displaystyle \dim(U\cap W)}$semejante${\displaystyle z_{i}}$s. Por lo tanto, el${\displaystyle z_{i}}$s forman una base de${\displaystyle U\cap W}$.