Hermitovská normální forma

Hermitova normální forma je analogií stupňovité formy matice pro matice přes kruh celých čísel . Zatímco stupňovitá forma matice se používá k řešení soustav lineárních rovnic tvaru pro , hermitovská normální forma může být použita k řešení lineárních soustav diofantických rovnic , u kterých se předpokládá, že . Hermitova normální forma se používá při řešení problémů celočíselného programování [1] , kryptografie [2] a obecné algebry [3] . $\mathbb {Z}$ $sekera=b$ $x\in \mathbb{R} ^{n}$ $x\in \mathbb {Z} ^{n}$

Definice

Matice je hermitovská normální forma celočíselné matice , pokud existuje unimodulární matice taková, že a splňuje následující omezení [4] [5] [6] : $H$ $A$ $U$ $H=UA$ $H$

$H$ je horní-trojúhelníkový, to znamená, pokud je jakýkoli řetězec sestávající výhradně z nul pod všemi ostatními. $h_{ij}=0$ $i>j$
Vedoucí prvek libovolného nenulového řádku je vždy kladný a leží vpravo od vodícího koeficientu řádku nad ním.
Prvky pod úvodními jsou rovny nule a prvky nad úvodními jsou nezáporné a přísně menší než úvodní.

Někteří autoři ve třetí podmínce požadují, aby prvky byly nepozitivní [7] [8] nebo na ně nekladli žádná omezení znaménka [9] .

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

Hermitova normální forma existuje a je jedinečná pro jakoukoli celočíselnou matici [5] [10] [11] . $H$ $A$

Příklady

V příkladech níže je matice hermitovská normální forma matice a odpovídající unimodulární matice je matice taková, že . $H$ $A$ $U$ $H=UA$

A={\begin{pmatrix}3&3&1&4\\0&1&0&0\\0&0&19&16\\0&0&0&3\end{pmatrix}}\qquad H={\begin{pmatrix}3&0&1&1\\0&1&0&0\9\0&0&0&0&1\end&1\0 pmatrix}}\qquad U=\left({\begin{array}{rrrr}1&-3&0&-1\\0&1&0&0\\0&0&1&-5\\0&0&0&1\end{array}}\right)

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

Algoritmy

První algoritmy pro výpočet hermitovské normální formy pocházejí z roku 1851. Přitom první algoritmus, který pracuje v přísně polynomiálním čase, byl vyvinut až v roce 1979 [12] . Jedna z široce používaných tříd algoritmů pro redukci matice na hermitovskou normální formu je založena na modifikované Gaussově metodě [10] [13] [14] . Další běžnou metodou pro výpočet Hermitovy normální formy je algoritmus LLL [15] [16] .

Aplikace

Výpočty mřížek

Obvykle mají mřížky tvar , kde . Pokud vezmeme v úvahu matici, jejíž řádky jsou složeny z vektorů , pak její hermitovská normální forma bude definovat nějakou jednoznačně definovanou mřížkovou bázi. Toto pozorování umožňuje rychle zkontrolovat, zda se mřížky generované řadami matic a , u kterých stačí ověřit, že matice mají stejné hermitovské normální formy, shodují. Podobně lze zkontrolovat, zda je mříž podmřížkou mřížky , pro kterou stačí uvažovat matici získanou sjednocením řádků a . V tomto nastavení je podmřížka právě tehdy, když se hermitovské normální formy a [17] shodují . $\mathbb {R} ^{n}$ ${\textstyle L=\left\{\left.\alpha _{1}a_{1}+\alpha _{2}a_{2}+\tečky +\alpha _{n}a_{n}\;\ vpravo\vert \;\alpha _{i}\in \mathbb {Z} \right\}}$ $a_{i}\in \mathbb {R} ^{n}$ $A$ $a_{i}$ $A$ $A'$ ${\displaystyle L_{A'))$ $L_{A}$ $A''$ $A$ $A'$ ${\displaystyle L_{A'))$ $L_{A}$ $A$ $A''$

Diofantní lineární rovnice

Systém lineárních rovnic má celočíselné řešení právě tehdy, když má systém celočíselné řešení, kde je hermitovský normální tvar matice [10] :55 . $sekera=b$ $X$ $Hx=Ub$ $H=UA$ $A$

Implementace

Výpočet hermitovské normální formy je implementován v mnoha systémech počítačové algebry:

Viz také

Poznámky

↑ Hung, Ming S.; Rom, Walter O. Aplikace Hermitovy normální formy v celočíselném programování // Lineární algebra a její aplikace : časopis . - 1990. - 15. října ( sv. 140 ). - S. 163-179 . - doi : 10.1016/0024-3795(90)90228-5 .
↑ Evangelos, Tourloupis, Vasilios. Normální formy Hermite a její kryptografické aplikace (anglicky) : journal. - University of Wollongong, 2013. - 1. ledna.
↑ Adkins, William; Weintraub, Stevene. Algebra: Přístup prostřednictvím teorie modulu . - Springer Science & Business Media , 2012. - S. 306. - ISBN 9781461209232 .
↑ Husté matice přes celý kruh - Sage Reference Manual v7.2: Matrices and Spaces of Matrices . doc.sagemath.org . Staženo: 22. června 2016. (neurčitý)
↑ 1 2 Mader, A. Téměř kompletně rozložitelné skupiny . - CRC Press , 2000. - ISBN 9789056992255 .
↑ Micciancio, Daniele; Goldwasser, Shafi. Složitost problémů s mřížkou: Kryptografická perspektiva . - Springer Science & Business Media , 2012. - ISBN 9781461508977 .
↑ W., Weisstein, Eric Hermite Normal Form . mathworld.wolfram.com . Staženo: 22. června 2016.
↑ Bouajjani, Ahmed; Maler, Oded. Computer Aided Verification: 21. mezinárodní konference, CAV 2009, Grenoble, Francie, 26. června - 2. července 2009, sborník příspěvků . - Springer Science & Business Media , 2009. - ISBN 9783642026577 .
↑ Hermitova normální forma matice - MuPAD . www.mathworks.com . Staženo: 22. června 2016. (neurčitý)
↑ 1 2 3 Schrijver, Alexander. Teorie lineárního a celočíselného programování . - John Wiley & Sons , 1998. - ISBN 9780471982326 .
↑ Cohen, Henry. Kurz výpočetní algebraické teorie čísel . - Springer Science & Business Media , 2013. - ISBN 9783662029459 .
↑ Kannan, R.; Bachem, A. Polynomial Algorithms for Computing Smith and Hermite Normal Forms of a Integer Matrix // SIAM Journal on Computing : deník. - 1979. - 1. listopadu ( roč. 8 , č. 4 ). - str. 499-507 . — ISSN 0097-5397 . - doi : 10.1137/0208040 .
↑ Euclidean Algorithm and Hermite Normal Form (odkaz není k dispozici) (2. března 2010). Získáno 25. června 2015. Archivováno z originálu 7. srpna 2016. (neurčitý)
↑ Martin, Richard Kipp. Kapitola 4.2.4 Hermite Normal Form // Lineární a celočíselná optimalizace ve velkém měřítku: Jednotný přístup . - Springer Science & Business Media , 2012. - ISBN 9781461549758 .
↑ Bremner, Murray R. Kapitola 14: The Hermite Normal Form // Redukce mřížkové báze: Úvod do algoritmu LLL a jeho aplikací . - CRC Press , 2011. - ISBN 9781439807040 .
↑ Havas, Jiří; Majewski, Bohdan S.; Matthews, Keith R. Rozšířené GCD a Hermite algoritmy normální formy prostřednictvím redukce mřížkové báze // Experimental Mathematics: journal. - 1998. - Sv. 7 , č. 2 . - S. 130-131 . — ISSN 1058-6458 .
↑ Micciancio, Daniele Základní algoritmy . Staženo: 25. června 2016. (neurčitý)