Poustevník normální forma - Hermite normal form

v lineární algebra, Poustevník normální forma je obdobou snížená echelonová forma pro matice přes celá čísla Z. Stejně jako snížená echelonová forma lze použít k řešení problémů týkajících se řešení lineárního systému Sekera = b kde X je v Rⁿ, Hermitova normální forma může vyřešit problémy týkající se řešení lineárního systému Sekera = b kde tentokrát X je omezeno pouze na celočíselné souřadnice. Mezi další aplikace Hermitovy normální formy patří celočíselné programování,^[1] kryptografie,^[2] a abstraktní algebra.^[3]

Definice

Různí autoři možná upřednostňují mluvit o Hermitově normální formě ve stylu řádků nebo sloupců. Jsou až do transpozice v podstatě stejné.

Normální forma poustevníka

An m podle n matice A s celočíselnými položkami má (řádek) Hermitův normální tvar H pokud existuje čtverec unimodulární matice U kde H = UA a H má následující omezení:^[4][5][6]

1. H je horní trojúhelníkový (tj. h_ij = 0 pro i> j) a všechny řádky nul jsou umístěny pod jakýmkoli jiným řádkem.
2. The vedoucí koeficient (první nenulová položka zleva, nazývaná také pivot ) nenulové řady je vždy striktně napravo od počátečního koeficientu řady nad ní; navíc je to pozitivní.
3. Prvky pod čepy jsou nulové a prvky nad čepy jsou nezáporné a přísně menší než čep.

Třetí podmínka není mezi autory standardní, například některé zdroje přinutí non-čepy být nonpositive^[7][8] nebo na ně neukládejte žádná omezení.^[9] Tyto definice jsou však ekvivalentní použitím jiné unimodulární matice U. Unimodulární matice je čtverec invertibilní celočíselná matice jehož určující je 1 nebo -1.

Sloupová poustevnická normální forma

Matice m x n A s celočíselnými položkami má (sloupec) Hermitův normální tvar H pokud existuje čtverec unimodulární matice U kde H = AU a H má následující omezení:^[8][10]

1. H je nižší trojúhelníkový, h_ij = 0 pro i a všechny sloupce s nulami jsou umístěny vpravo.
2. The vedoucí koeficient (první nenulová položka shora, nazývaná také pivot ) nenulového sloupce je vždy přísně pod vedoucím koeficientem sloupce před ním; navíc je to pozitivní.
3. Prvky napravo od čepů jsou nulové a prvky nalevo od čepů jsou nezáporné a přísně menší než čep.

Všimněte si, že definice stylu řádků má unimodulární matici U množení A vlevo (význam U jedná na řádcích A), zatímco definice stylu sloupce má akci unimodulární matice na sloupcích A. Dvě definice hermitských normálních forem jsou jednoduše transpozice navzájem.

Existence a jedinečnost poustevnické normální formy

Každý m podle n matice A s celočíselnými položkami má jedinečný m podle n matice H, takový, že H = UA pro nějakou čtvercovou unimodulární matici U.^[5][11][12]

Příklady

V níže uvedených příkladech H je Hermitova normální forma matice A, a U je taková unimodulární matice UA = H.

${displaystyle A = {egin {pmatrix} 3 & 3 & 1 & 4 0 & 1 & 0 & 0 0 & 0 & 19 & 16 0 & 0 & 0 & 3end {pmatrix}} qquad H = {egin {pmatrix} 3 & 0 & 1 & 1 0 & 1 & 0 & 0 0 & 0 & 19 & 1 0 & 0 & 0 & 3end {p {matice} rrrr} 1 & -3 & 0 & -1 0 & 1 & 0 & 0 0 & 0 & 1 & -5 0 & 0 & 0 & 1end {pole}} v pořádku)}$

${displaystyle A = left ({egin {array} {rrrr} 2 & 3 & 6 & 2 5 & 6 & 1 & 6 8 & 3 & 1 & 1end {array}} ight) qquad H = left ({egin {array} {rrrr} 1 & 0 & 50 & -11 0 & 3 & 28 & -2 0 & 0 & 61 & -13end { array}} ight) qquad U = left ({egin {array} {rrr} 9 & -5 & 1 5 & -2 & 0 11 & -6 & 1end {array}} ight)}$

Li A má pouze jeden řádek H = A nebo H = -A, v závislosti na tom, zda jediný řádek A má kladný nebo záporný počáteční koeficient.

Algoritmy

Existuje mnoho algoritmů pro výpočet Hermitovy normální formy, které sahají až do roku 1851. Teprve v roce 1979 byl spuštěn algoritmus pro výpočet Hermitovy normální formy silně polynomiální čas byl poprvé vyvinut;^[13] to znamená, že počet kroků k výpočtu Hermitovy normální formy je omezen výše polynomem v rozměrech vstupní matice a prostor použitý algoritmem (mezilehlá čísla) je omezen polynomem v binární velikosti kódování čísla ve vstupní matici. Jedna třída algoritmů je založena na Gaussova eliminace v tom jsou opakovaně použity speciální elementární matice.^[11][14][15] The JÁ BUDU Algoritmus lze také použít k efektivnímu výpočtu Hermitovy normální formy.^[16][17]

Aplikace

Příhradové výpočty

Typický mříž v Rⁿ má formu ${displaystyle L = left {left.sum _ {i = 1} ^ {n} alpha _ {i} a_ {i}; ightvert; alpha _ {i} v mathbb {Z} ight}}$ Kde A_i jsou v Rⁿ. Pokud sloupce matice A jsou A_i, mřížka může být spojena se sloupci matice a A se říká, že je základem L. Protože Hermitova normální forma je jedinečná, lze ji použít k zodpovězení mnoha otázek o dvou popisech mřížky. Z toho, co následuje, ${displaystyle L_ {A}}$ označuje mřížku generovanou sloupy A. Protože základ je ve sloupcích matice A, musí být použit sloupcový styl Hermitovy normální formy. Vzhledem k tomu, dvě základny pro mříž, A a A', problémem ekvivalence je rozhodnout, zda ${displaystyle L_ {A} = L_ {A '}.}$ Toho lze dosáhnout kontrolou, zda je Hermitova normální forma sloupcového stylu A a A' jsou stejné až do přidání nulových sloupců. Tato strategie je také užitečná při rozhodování, zda je mřížka podmnožinou (${displaystyle L_ {A} subseteq L_ {A '}}$ kdyby a jen kdyby ${displaystyle L _ {[Amid A ']} = L_ {A'}}$), rozhodování, zda je vektor v v mřížce (${displaystyle vin L_ {A}}$ kdyby a jen kdyby ${displaystyle L _ {[vmid A]} = L_ {A}}$) a pro další výpočty.^[18]

Celé řešení lineárních systémů

Lineární systém Sekera = b má celočíselné řešení X jen a jen v případě, že systém Hy = b má celočíselné řešení y kde Uy = x a H je Hermitova normální forma sloupcového stylu A.^[11]:55 Zkontroluji to Hy = b má celočíselné řešení je jednodušší než Sekera = b protože matice H je trojúhelníkový.

Implementace

Mnoho matematických softwarových balíků může vypočítat Hermitovu normální formu:

• Javor s HermiteForm
• Mathematica s Poustevník
• MATLAB s hermiteForm
• NTL s HNF
• PARI / GP s mathnf
• SageMath s hermite_form

Viz také

• Hermitský prsten
• Smith normální forma
• Diophantine rovnice

Reference