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

редактировать

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

Содержание

1 Алгоритм
- 1.1 Вход
- 1.2 Выход
- 1.3 Алгоритм
- 1.4 Доказательство правильности
2 Пример
3 См. Также
4 Ссылки
5 Внешние ссылки

Алгоритм

Входные данные

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

U = ⟨u 1,…, un⟩ {\ displaystyle U = \ langle u_ {1}, \ ldots, u_ {n} \ rangle}

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

W = ⟨ w 1,…, wk⟩. {\ displaystyle W = \ langle w_ {1}, \ ldots, w_ {k} \ rangle.}

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

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

ui = ∑ j = 1 mai, j B j {\ displaystyle u_ {i} = \ sum _ {j = 1} ^ {m} a_ { i, j} B_ {j}}

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

wi = ∑ j = 1 mbi, j B j. {\ displaystyle w_ {i} = \ sum _ {j = 1} ^ {m} b_ {i, j} B_ {j}.}

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

Выходные данные

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

Алгоритм

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

(u 1, 1 u 1, 2 ⋯ u 1, mu 1, 1 u 1, 2 ⋯ u 1, m ⋮ ⋮ ⋮ ⋮ un, 1 un, 2 ⋯ un, mun, 1 un, 2 ⋯ un, mw 1, 1 w 1, 2 ⋯ w 1, m 0 0 ⋯ 0 ⋮ ⋮ ⋮ wk, 1 wk, 2 ⋯ wk, m 0 0 ⋯ 0) {\ displaystyle {\ begin {pmatrix} u_ {1,1} u_ {1,2} \ cdots u_ {1, m} u_ {1,1} u_ {1,2} \ cdots u_ {1, m} \ \\ vdots \ vdots \ vdots \ vdots \ vdots \ vdots \\ u_ {n, 1} u_ {n, 2} \ cdots u_ {n, m} u_ {n, 1} u_ {n, 2} \ cdots u_ {n, m} \\ w_ {1,1} w_ {1,2} \ cdots w_ {1, m} 0 0 \ cdots 0 \\\ vdots \ vdots \ vdots \ vdots \ vdots \ vdots \\ w_ {k, 1} w_ {k, 2} \ cdots w_ {k, m} 0 0 \ cdots 0 \ end {pmatrix}}}

{\ displaystyle { \ begin {pmatrix} u_ {1,1} u_ {1,2} \ cdots u_ {1, m} u_ {1,1} u_ {1,2} \ cdots u_ {1, m} \\\ vdots \ vdots \ vdots \ vdots \ vdots \ vdots \\ u_ {n, 1} u_ {n, 2} \ cdots u_ {n, m} u_ {n, 1} u_ {n, 2 } \ cdots u_ {n, m} \\ w_ {1,1} w_ {1,2} \ cdots w_ {1, m} 0 0 \ cdots 0 \\\ vdots \ vdots \ vdots \ vdots \ vdots \ vdots \\ w_ {k, 1} w_ {k, 2} \ cdots w_ {k, m} 0 0 \ cdots 0 \ end {pmatrix}}}

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

(c 1, 1 c 1, 2 ⋯ c 1, m ∗ ∗ ⋯ ∗ ⋮ ⋮ ⋮ ⋮ cq, 1 cq, 2 ⋯ cq, m ∗ ∗ ⋯ ∗ 0 0 ⋯ 0 d 1, 1 d 1, 2 ⋯ d 1, m ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 0 dl, 1 dl, 2 ⋯ dl, 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} * * \ cdots * \\ \ vdots \ vdots \ vdots \ vdots \ vdots \ vdots \\ c_ {q, 1} c_ {q, 2} \ cdots c_ {q, m} * * \ cdots * \ \ 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_ {l, 1} d_ {l, 2} \ cdots d_ {l, 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}}}

{\ begin {pmatrix} c _ {{1, 1}} c _ {{1,2}} \ cdots c _ {1, m}} * * \ cdots * \\\ vdots \ vdots \ vdots \ vdots \ vdots \ vdots \\ c _ {{q, 1}} c _ {{q, 2}} \ cdots c _ {{q, m}} * * \ cdots * \\ 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 _ {l, 1}} d _ {{l, 2}} \ cdots d _ {{l, 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 *}$ $*$ обозначает произвольные числа, а векторы $(cp, 1, cp, 2,…, cp, m) {\ displaystyle (c_ {p, 1}, c_ {p, 2}, \ ldots, c_ {p, m})}$ $(c _ {{p, 1}}, c _ {{p, 2}}, \ ldots, c _ {{p, m}})$ для каждого $p ∈ {1,…, q} {\ displaystyle p \ in \ {1, \ ldots, q \}}$ $p \ in \ {1, \ ldots, q \}$ и $(dp, 1,…, dp, m) { \ displaystyle (d_ {p, 1}, \ ldots, d_ {p, m})}$ $(d _ {{p, 1}}, \ ldots, d_ {{p, m}})$ для каждого $p ∈ {1,…, l} {\ displaystyle p \ in \ {1, \ ldots, l \}}$ $p \ in \ {1, \ ldots, l \}$ отличны от нуля.

Тогда $(y 1,…, yq) {\ displaystyle (y_ {1}, \ ldots, y_ {q})}$ $(y_ {1}, \ ldots, y_ {q})$ с

yi: = ∑ j = 1 mci, j B j {\ displaystyle y_ {i}: = \ sum _ {j = 1} ^ {m} c_ {i, j} B_ {j}}

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

является основой $U + W {\ displaystyle U + W}$ $U + W$ и $(z 1,…, zl) {\ displaystyle (z_ {1}, \ ldots, z_ {l})}$ $(z_ {1}, \ ldots, z_ { l})$ с

zi: = ∑ j = 1 mdi, j B j {\ displaystyle z_ {i}: = \ sum _ {j = 1} ^ {m} d_ {i, j} B_ {j}}.

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

является основой $U ∩ W {\ displaystyle U \ cap W}$ $U \ cap W$ .

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

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

Пусть $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 \} \ substeq V \ times V.}$ ${\ displaystyle H: = \ {(u, u) \ mid u \ in U \} + \ {(w, 0) \ mid w \ in W \} \ substeq V \ times V.}$ Тогда $π 1 (H) = U + W {\ displaystyle \ pi _ {1} (H) = U + W}$ $\ pi _ { 1} (H) = U + W$ и $H ∩ (0 × V) = 0 × (U ∩ W) {\ Displaystyle H \ cap (0 \ times V) = 0 \ times (U \ cap W)}$ $H \ cap (0 \ times V) = 0 \ times (U \ cap W)$ .

Кроме того, $H ∩ (0 × V) {\ displaystyle H \ cap (0 \ times V)}$ $H \ cap (0 \ times V)$ - это ядро из $π 1 | H {\ displaystyle {\ pi _ {1} |} _ {H}}$ ${ \ pi _ {1} |} _ {H}$ , проекция ограничила до H. Следовательно, $dim ⁡ (H) = dim ⁡ (U + W) + dim ⁡ (U ∩ W) {\ displaystyle \ dim (H) = \ dim (U + W) + \ dim (U \ cap W)}$ $\ dim (H) = \ dim (U + W) + \ dim (U \ cap W)$ .

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

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

Пример

Рассмотрим два подпространства $U = ⟨(1-1 0 1), (0 0 1-1)⟩ {\ displaystyle U = \ left \ langle {\ begin {pmatrix} 1 \\ - 1 \\ 0 \ \ 1 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 0 \\ 1 \\ - 1 \ end {pmatrix}} \ right \ rangle}$ $U = \ left \ langle {\ begin {pmatrix} 1 \\ - 1 \\ 0 \\ 1 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 0 \\ 1 \\ - 1 \ end {pmatrix}} \ right \ rangle$ и $W = ⟨ (5 0 - 3 3), (0 5 - 3 - 2)⟩ {\ Displaystyle W = \ left \ langle {\ begin {pmatrix} 5 \\ 0 \\ - 3 \\ 3 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 5 \\ - 3 \\ - 2 \ end {pmatrix}} \ right \ rangle}$ $W = \ left \ langle {\ begin {pmatrix} 5 \\ 0 \\ - 3 \\ 3 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 5 \\ - 3 \\ - 2 \ end {pmatrix}} \ right \ rangle$ векторного пространства $R 4 {\ displaystyle \ mathbb { R} ^ {4}}$ $\ mathbb {R} ^ {4}$ .

Используя стандартный базис , мы создаем следующую матрицу размерности $(2 + 2) × (2 ⋅ 4) {\ displaystyle (2 + 2) \ times (2 \ cdot 4)}$ $(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 {\ begin {pmatrix} 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}}. Использование}. элементарных операций со строками, преобразуем эту матрицу в следующую матрицу:

(1 0 0 0 ∗ ∗ ∗ ∗ 0 1 0 - 1 ∗ ∗ ∗ ∗ 0 0 1 - 1 ∗ ∗ ∗ ∗ 0 0 0 0 1 - 1 0 1) {\ displaystyle {\ begin {pmatrix} 1 0 0 0 * * * * \\ 0 1 0 -1 * * * * \\ 0 0 1 -1 * * * * \\\ \ 0 0 0 0 1 -1 0 1 \ end {pmatrix}}}

{\ begin {pmatrix} 1 0 0 0 * * * * \\ 0 1 0 -1 * * * * \\ 0 0 1 -1 * * * * \\\\ 0 0 0 0 1 -1 0 1 \ end {pmatrix}}

(некоторые записи были заменены на «

∗ {\ displaystyle *}

*

», потому что они не имеют отношения к результату).

Следовательно, $((1 0 0 0), (0 1 0 - 1), (0 0 1 - 1)) {\ displaystyle \ left ({\ begin {pmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 1 \\ 0 \\ - 1 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 0 \\ 1 \\ -1 \ end {pmatrix}} \ right)}$ $\ left ({\ begin {pmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {pmatrix}}, { \ begin {pmatrix} 0 \\ 1 \\ 0 \\ - 1 \ end {pmatrix}}, {\ begin {pmatrix} 0 \\ 0 \\ 1 \\ - 1 \ end {pmatrix}} \ right)$ является основой для $U + W {\ displaystyle U + W}$ $U + W$ и $((1 - 1 0 1)) {\ displaystyle \ left ({\ begin {pmatrix} 1 \\ - 1 \\ 0 \\ 1 \ end {pmatrix}} \ right)}$ $\ left ({\ begin {pmatrix} 1 \\ - 1 \\ 0 \\ 1 \ end {pmatrix}} \ right)$ является основой $U ∩ W {\ Displaystyle U \ cap W}$ $U \ cap W$ .

См. Также

Базис Грёбнера

Ссылки

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

«Mathematik-Online-Lexikon: Zassenhaus-Algorithmus» (на немецком языке). Проверено 15 сентября 2012 г.