Hermitikus normál forma

A hermitikus normálforma az egész számok gyűrűje feletti mátrixok lépésformájának analógja . Míg a mátrix lépcsőzetes formáját a alakú lineáris egyenletrendszerek megoldására használják , addig a Hermiti normálforma használható diofantusi egyenletrendszerek lineáris megoldására , amelyekben azt feltételezzük, hogy . A Hermitiánus normálformát egészszámú programozás [1] , kriptográfia [2] és általános algebra [3] problémáinak megoldására használják . $\mathbb {Z}$ $ax=b$ $x\in \mathbb{R} ^{n}$ $x\in \mathbb {Z} ^{n}$

Definíció

A mátrix egy egész mátrix hermitikus normál alakja, ha van olyan unimoduláris mátrix , amely teljesíti a következő megszorításokat [4] [5] [6] : $H$ $A$ $U$ $H=UA$ $H$

$H$ felső-háromszög alakú, vagyis ha bármely teljes egészében nullákból álló karakterlánc az összes többi alatt van. $h_{ij}=0$ $i>j$
Bármely nem nulla sor vezető eleme mindig pozitív, és a felette lévő sor vezető együtthatójától jobbra helyezkedik el.
A bevezetők alatti elemek nullával egyenlőek, a bevezetők feletti elemek pedig nem negatívak, és szigorúan kisebbek a bevezetőnél.

Egyes szerzők a harmadik feltételben megkövetelik, hogy az elemek ne legyenek pozitívak [7] [8] , vagy egyáltalán ne írjanak elő jelkorlátozást rájuk [9] .

Egy hermitikus normálforma létezése és egyedisége

A hermitikus normálforma létezik, és minden egész mátrixra egyedi [5] [10] [11] . $H$ $A$

Példák

Az alábbi példákban a mátrix a mátrix hermitikus normál alakja, a megfelelő unimoduláris mátrix pedig az a mátrix , amelyre . $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\&1&0&3\&1&0\&0&0&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{tömb}}\jobbra)$

Algoritmusok

Az első algoritmusok a hermitikus normálforma kiszámítására 1851-ből származnak. Ugyanakkor az első szigorúan polinomiális időben működő algoritmust csak 1979-ben dolgozták ki [12] . A mátrixok hermitikus normálformára való redukálására szolgáló algoritmusok egyik széles körben használt osztálya egy módosított Gauss-módszeren alapul [10] [13] [14] . A hermitikus normálalak másik számítási módja az LLL algoritmus [15] [16] .

Alkalmazások

Rácsszámítások

Általában a rácsok alakja , ahol . Ha egy olyan mátrixot tekintünk, amelynek sorai vektorokból állnak , akkor a hermitikus normálalakja valamilyen egyedileg meghatározott rácsalapot fog meghatározni. Ezzel a megfigyeléssel gyorsan ellenőrizhető, hogy a és a mátrixsorok által generált rácsok , amelyekhez elegendő ellenőrizni, hogy a mátrixok hermitikus normálformái megegyeznek-e, egybeesnek-e. Hasonlóképpen ellenőrizhető, hogy a rács a rács részrácsa -e , amelyhez elegendő a és a sorok uniójából kapott mátrixot figyelembe venni . Ebben a beállításban akkor és csak akkor van részrács , ha a Hermitiánus normálformák és [17] egybeesnek . $\mathbb {R} ^{n}$ ${\textstyle L=\left\{\left.\alpha _{1}a_{1}+\alpha _{2}a_{2}+\dots +\alpha _{n}a_{n}\;\ right\vert \;\alpha _{i}\in \mathbb {Z} \right\}}$ $a_{i}\in \mathbb {R} ^{n}$ $A$ $a_{i}$ $A$ $A'$ $L_{A'}$ $L_{A}$ $A''$ $A$ $A'$ $L_{A'}$ $L_{A}$ $A$ $A''$

Diofantin lineáris egyenletek

Egy lineáris egyenletrendszernek akkor és csak akkor van egész megoldása , ha a rendszernek van egész megoldása, ahol a mátrix hermitikus normálalakja [10] :55 . $ax=b$ $x$ $Hx=Ub$ $H=UA$ $A$

Megvalósítás

A Hermitiánus normálalak számítását számos számítógépes algebrai rendszerben megvalósítják:

Lásd még

Jegyzetek

↑ Hung, Ming S.; Rom, Walter O. A Hermite normálforma alkalmazása egészszámú programozásban // Lineáris algebra és alkalmazásai : folyóirat . - 1990. - október 15. ( 140. köt. ). - 163-179 . o . - doi : 10.1016/0024-3795(90)90228-5 .
↑ Evangelos, Tourloupis, Vasilios. Hermite normálformák és kriptográfiai alkalmazásai (angolul) : folyóirat. - Wollongong Egyetem, 2013. - január 1.
↑ Adkins, William; Weintraub, Steven. Algebra: Megközelítés a modulelméleten keresztül . - Springer Science & Business Media , 2012. - P. 306. - ISBN 9781461209232 .
↑ Sűrű mátrixok az egész gyűrű felett - Sage Reference Manual v7.2: Mátrixok és mátrixterek . doc.sagemath.org . Letöltve: 2016. június 22. (határozatlan)
↑ 1 2 Mader, A. Majdnem teljesen lebontható csoportok . - CRC Press , 2000. - ISBN 9789056992255 .
↑ Micciancio, Daniele; Goldwasser, Shafi. A rácsproblémák összetettsége: kriptográfiai perspektíva . - Springer Science & Business Media , 2012. - ISBN 9781461508977 .
↑ W., Weisstein, Eric Hermite normál forma . mathworld.wolfram.com . Letöltve: 2016. június 22.
↑ Bouajjani, Ahmed; Maler, Oded. Számítógéppel támogatott ellenőrzés: 21. Nemzetközi Konferencia, CAV 2009, Grenoble, Franciaország, 2009. június 26-július 2., Proceedings . - Springer Science & Business Media , 2009. - ISBN 9783642026577 .
↑ A mátrix remete normál formája - MuPAD . www.mathworks.com . Letöltve: 2016. június 22. (határozatlan)
↑ 1 2 3 Schrijver, Alexander. Lineáris és egészszámú programozás elmélete . - John Wiley & Sons , 1998. - ISBN 9780471982326 .
↑ Cohen, Henry. Számítási algebrai számelmélet tanfolyam . - Springer Science & Business Media , 2013. - ISBN 9783662029459 .
↑ Kannan, R.; Bachem, A. Polinomiális algoritmusok egy egész mátrix Smith és Hermite normálformáinak kiszámításához // SIAM Journal on Computing : folyóirat. - 1979. - november 1. ( 8. köt . 4. sz .). - P. 499-507 . — ISSN 0097-5397 . - doi : 10.1137/0208040 .
↑ Euklideszi algoritmus és Hermite normálforma (hivatkozás nem érhető el) (2010. március 2.). Letöltve: 2015. június 25. Az eredetiből archiválva : 2016. augusztus 7.. (határozatlan)
↑ Martin, Richard Kipp. Fejezet 4.2.4 Hermite normál forma // Nagy léptékű lineáris és egész számok optimalizálás: egységes megközelítés . - Springer Science & Business Media , 2012. - ISBN 9781461549758 .
↑ Bremner, Murray R. 14. fejezet: A Hermite normálforma // Rács alapú redukció: Bevezetés az LLL algoritmusba és alkalmazásaiba . - CRC Press , 2011. - ISBN 9781439807040 .
↑ Havas György; Majewski, Bohdan S.; Matthews, Keith R. Kiterjesztett GCD és Hermite normálformájú algoritmusok rácsalapú redukción keresztül // Experimental Mathematics : Journal. - 1998. - Vol. 7 , sz. 2 . - 130-131 . o . — ISSN 1058-6458 .
↑ Micciancio, Daniele Alapvető algoritmusok . Letöltve: 2016. június 25. (határozatlan)