Алгоритм Зассенхауза

В математике алгоритм Цассенхауза это метод вычисления основы пересечения — и суммы двух подпространств векторного пространства .Он назван в честь Ганса Зассенхауса , но о публикации им этого алгоритма неизвестно. Он используется в системах компьютерной алгебры .

Алгоритм

Вход

Пусть V — векторное пространство и U , W — два конечномерных подпространства V со следующими остовными множествами :

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

и

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

Наконец, позвольте $B_{1},\ldots ,B_{m}$ быть линейно независимыми векторами так, что $u_{i}$ и $w_{i}$ можно записать как

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

и

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

Выход

Алгоритм вычисляет основание суммы $U+W$ и основание пересечения $U\cap W$.

Алгоритм

Алгоритм создает следующую блочную матрицу размера $((n+k)\times (2m))$:

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

Используя элементарные операции над строками , эта матрица преобразуется в форму звена строк . Тогда он имеет следующую форму:

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

Здесь, $\bullet$ обозначает произвольные числа, а векторы $(c_{p,1},c_{p,2},\ldots ,c_{p,m})$ для каждого $p\in \{1,\ldots ,q\}$ и $(d_{p,1},\ldots ,d_{p,m})$ для каждого $p\in \{1,\ldots ,\ell \}$ ненулевые.

Затем $(y_{1},\ldots ,y_{q})$ с

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

является основой $U+W$и $(z_{1},\ldots ,z_{\ell })$ с

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

является основой $U\cap W$.

Доказательство правильности

Сначала мы определяем $\pi _{1}:V\times V\to V,(a,b)\mapsto a$ быть проекцией на первый компонент.

Позволять $H:=\{(u,u)\mid u\in U\}+\{(w,0)\mid w\in W\}\subseteq V\times V.$Затем $\pi _{1}(H)=U+W$ и $H\cap (0\times V)=0\times (U\cap W)$.

Также, $H\cap (0\times V)$ является ядром ​ ${\pi _{1}|}_{H}$ проекция ограничена H , .Поэтому, $\dim(H)=\dim(U+W)+\dim(U\cap W)$.

Алгоритм Зассенхауза вычисляет базис H . В первых m столбцах этой матрицы находится базис $y_{i}$ из $U+W$.

Строки формы $(0,z_{i})$ (с $z_{i}\neq 0$), очевидно, находятся в $H\cap (0\times V)$. Поскольку матрица имеет форму эшелона строк , они также линейно независимы.Все строки, отличные от нуля ( $(y_{i},\bullet )$ и $(0,z_{i})$) являются базисом H , поэтому существуют $\dim(U\cap W)$ такой $z_{i}$с. Таким образом, $z_{i}$составляют основу $U\cap W$.

Пример

Рассмотрим два подпространства $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$ и $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$ векторного пространства $\mathbb {R} ^{4}$.

Используя стандартный базис , создадим следующую матрицу размерности $(2+2)\times (2\cdot 4)$:

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

Используя элементарные операции над строками , преобразуем эту матрицу в следующую матрицу:

$\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)$ (Некоторые записи заменены на " $\bullet$«потому что они не имеют отношения к результату.)

Поэтому $\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)$ является основой $U+W$, и $\left(\left({\begin{array}{r}1\\-1\\0\\1\end{array}}\right)\right)$ является основой $U\cap W$.

См. также

• База Грёбнер

Внешние ссылки

• «Математический онлайн-лексикон: алгоритм Цассенхауза» (на немецком языке) . Проверено 15 сентября 2012 г.