Algoritmus Zassenhaus - Zassenhaus algorithm

V matematice je Algoritmus Zassenhaus^[1]je metoda pro výpočet a základ pro průsečík a součet ze dvou podprostory a vektorový prostor.Jmenuje se podle Hans Zassenhaus, ale není známa žádná jeho publikace tohoto algoritmu.^[2] Používá se v systémy počítačové algebry.^[3]

Algoritmus

Vstup

Nechat PROTI být vektorovým prostorem a U, Ž dva konečně-dimenzionální podprostory PROTI s následujícími překlenovací sady:

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

a

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

Nakonec nechte ${ displaystyle B_ {1}, ldots, B_ {m}}$ být lineárně nezávislé vektory tak ${ displaystyle u_ {i}}$ a ${ displaystyle w_ {i}}$ lze psát jako

${ displaystyle u_ {i} = součet _ {j = 1} ^ {m} a_ {i, j} B_ {j}}$

a

${ displaystyle w_ {i} = součet _ {j = 1} ^ {m} b_ {i, j} B_ {j}.}$

Výstup

Algoritmus počítá základnu součet ${ displaystyle U + W}$ a základna průsečík ${ displaystyle U cap W}$.

Algoritmus

Algoritmus vytváří následující bloková matice velikosti ${ displaystyle ((n + k) krát (2 m))}$:

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

Použitím základní řádkové operace, je tato matice transformována na řádkový sled. Poté má následující tvar:

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

Tady, ${ displaystyle *}$ znamená libovolná čísla a vektory ${ displaystyle (c_ {p, 1}, c_ {p, 2}, ldots, c_ {p, m})}$ pro každého ${ displaystyle p in {1, ldots, q }}$ a ${ displaystyle (d_ {p, 1}, ldots, d_ {p, m})}$ pro každého ${ displaystyle p in {1, ldots, l }}$ jsou nenulové.

Pak ${ displaystyle (y_ {1}, ldots, y_ {q})}$ s

${ displaystyle y_ {i}: = součet _ {j = 1} ^ {m} c_ {i, j} B_ {j}}$

je základem ${ displaystyle U + W}$a ${ displaystyle (z_ {1}, ldots, z_ {l})}$ s

${ displaystyle z_ {i}: = součet _ {j = 1} ^ {m} d_ {i, j} B_ {j}}$

je základem ${ displaystyle U cap W}$.

Důkaz správnosti

Nejprve definujeme ${ displaystyle pi _ {1}: V krát V až V, (a, b) mapsto a}$ být projekcí na první komponentu.

Nechat${ displaystyle H: = {(u, u) mid u v U } + {(w, 0) mid w v W } subseteq V krát V.}$Pak ${ displaystyle pi _ {1} (H) = U + W}$ a${ displaystyle H cap (0 krát V) = 0 krát (U cap W)}$.

Taky, ${ displaystyle H cap (0 krát V)}$ je jádro z ${ displaystyle { pi _ {1} |} _ {H}}$, projekce omezený na H.Proto, ${ displaystyle dim (H) = dim (U + W) + dim (U cap W)}$.

Algoritmus Zassenhaus vypočítá základ H. Zaprvé m sloupce této matice existuje základ ${ displaystyle y_ {i}}$ z ${ displaystyle U + W}$.

Řádky formuláře ${ displaystyle (0, z_ {i})}$ (s ${ displaystyle z_ {i} neq 0}$) jsou zjevně v ${ displaystyle H cap (0 krát V)}$. Protože matice je uvnitř řádkový sled, jsou také lineárně nezávislé. všechny řádky, které se liší od nuly (${ displaystyle (y_ {i}, *)}$ a ${ displaystyle (0, z_ {i})}$) jsou základem H, takže existují ${ displaystyle dim (U cap W)}$ takový ${ displaystyle z_ {i}}$s. Proto ${ displaystyle z_ {i}}$tvoří základ ${ displaystyle U cap W}$.

Příklad

Zvažte dva podprostory ${ displaystyle U = left langle { begin {pmatrix} 1 - 1 0 1 end {pmatrix}}, { begin {pmatrix} 0 0 1 - 1 end {pmatrix}} right rangle}$ a ${ displaystyle W = left langle { begin {pmatrix} 5 0 - 3 3 end {pmatrix}}, { begin {pmatrix} 0 5 - 3 - 2 end {pmatrix}} right rangle}$ vektorového prostoru ${ displaystyle mathbb {R} ^ {4}}$.

Za použití standardní základ, vytvoříme následující matici dimenze ${ displaystyle (2 + 2) krát (2 cdot 4)}$:

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

Použitím základní řádkové operace, transformujeme tuto matici na následující matici:

${ displaystyle { begin {pmatrix} 1 & 0 & 0 & 0 && * & * & * & * 0 & 1 & 0 & -1 && * & * & * & * 0 & 0 & 1 & -1 && * & * & * & * 0 & 0 & 0 & 0 && 1 & -1 & 0 & 1 {pmatrix}}}$ (některé položky byly nahrazeny „${ displaystyle *}$„protože jsou pro výsledek irelevantní).

Proto,${ 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)}$ je základem ${ displaystyle U + W}$, a${ displaystyle left ({ begin {pmatrix} 1 - 1 0 1 end {pmatrix}} right)}$ je základem ${ displaystyle U cap W}$.

Viz také

• Gröbnerův základ

Reference

externí odkazy

• "Mathematik-Online-Lexikon: Zassenhaus-Algorithmus" (v němčině). Citováno 2012-09-15.