Hermiittinen normaalimuoto

Hermiittinen normaalimuoto on analogi matriisin askelmuodolle kokonaislukurenkaan ylittäville matriiseille . Matriisin vaiheittaista muotoa käytetään muodon lineaaristen yhtälöjärjestelmien ratkaisemiseen , kun taas Hermitian normaalimuotoa voidaan käyttää lineaaristen diofantiiniyhtälöjärjestelmien ratkaisemiseen , joissa oletetaan, että . Hermitian normaalimuotoa käytetään kokonaislukuohjelmoinnin [1] , kryptografian [2] ja yleisalgebran [3] ongelmien ratkaisemisessa . $\mathbb {Z}$ $ax=b$ $x\in \mathbb{R} ^{n}$ $x\in \mathbb {Z} ^{n}$

Määritelmä

Matriisi on kokonaislukumatriisin hermiittinen normaalimuoto, jos on olemassa unimodulaarinen matriisi , joka täyttää seuraavat rajoitukset [4] [5] [6] : $H$ $A$ $U$ $H=UA$ $H$

$H$ on ylemmän kolmion muotoinen, eli jos jokin kokonaan noloista koostuva merkkijono on kaikkien muiden alapuolella. $h_{ij}=0$ $i>j$
Minkä tahansa nollasta poikkeavan rivin johtava elementti on aina positiivinen ja sijaitsee sen yläpuolella olevan rivin johtavan kertoimen oikealla puolella.
Alkuelementtien alapuolella olevat elementit ovat yhtä suuria kuin nolla, ja alkujen yläpuolella olevat elementit ovat ei-negatiivisia ja tiukasti pienempiä kuin johtava.

Jotkut kolmannen ehdon kirjoittajat vaativat, että elementit eivät ole positiivisia [7] [8] tai eivät aseta niille mitään merkkirajoituksia [9] .

Eremiittisen normaalimuodon olemassaolo ja ainutlaatuisuus

Hermiittinen normaalimuoto on olemassa ja on ainutlaatuinen mille tahansa kokonaislukumatriisille [5] [10] [11] . $H$ $A$

Esimerkkejä

Alla olevissa esimerkeissä matriisi on matriisin hermiittinen normaalimuoto ja vastaava unimodulaarinen matriisi on sellainen matriisi , että . $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\&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{array}}\right)$

Algoritmit

Ensimmäiset algoritmit Hermitian normaalimuodon laskemiseksi ovat peräisin vuodelta 1851. Samanaikaisesti ensimmäinen tiukasti polynomisessa ajassa toimiva algoritmi kehitettiin vasta vuonna 1979 [12] . Yksi laajalti käytetyistä algoritmiluokista matriisin pelkistämiseksi hermiittiseen normaalimuotoon perustuu modifioituun Gaussin menetelmään [10] [13] [14] . Toinen yleinen tapa laskea hermiittinen normaalimuoto on LLL-algoritmi [15] [16] .

Sovellukset

Hilalaskelmat

Yleensä hilat ovat muodossa , jossa . Jos tarkastelemme matriisia, jonka rivit koostuvat vektoreista , niin sen hermiittinen normaalimuoto määrittelee jonkin yksilöllisesti määritellyn hilakannan. Tämän havainnon avulla voit nopeasti tarkistaa, täsmäävätkö matriisirivien ja matriisirivien muodostamat hilat , jolle riittää, että matriiseilla on samat hermiittiset normaalimuodot. Vastaavasti voidaan tarkistaa, onko hila hilan alihila , jolle riittää, kun tarkastellaan rivien ja :n liitosta saatua matriisia . Tässä asetuksessa on alihila , jos ja vain jos hermiittien normaalimuodot ja [17] osuvat yhteen . $\mathbb {R} ^{n}$ ${\textstyle L=\left\{\left.\alpha _{1}a_{1}+\alpha _{2}a_{2}+\dots +\alpha _{n}a_{n}\;\ oikea\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''$

Diofantiini lineaariyhtälöt

Lineaariyhtälöjärjestelmällä on kokonaislukuratkaisu silloin ja vain, jos järjestelmällä on kokonaislukuratkaisu, missä on matriisin hermiittinen normaalimuoto [10] :55 . $ax=b$ $x$ $Hx=Ub$ $H=UA$ $A$

Toteutus

Hermitian normaalimuodon laskenta on toteutettu monissa tietokonealgebrajärjestelmissä:

Katso myös

Muistiinpanot

↑ Hung, Ming S.; Rom, Walter O. Hermite-normaalimuodon sovellus kokonaislukuohjelmoinnissa // Lineaarinen algebra ja sen sovellukset : journal . - 1990. - 15. lokakuuta ( nide 140 ). - s. 163-179 . - doi : 10.1016/0024-3795(90)90228-5 .
↑ Evangelos, Tourloupis, Vasilios. Hermite-normaalimuodot ja sen kryptografiset sovellukset (englanniksi) : Journal. - Wollongongin yliopisto, 2013. - 1. tammikuuta.
↑ Adkins, William; Weintraub, Steven. Algebra: Lähestymistapa kautta moduuliteoria . - Springer Science & Business Media , 2012. - S. 306. - ISBN 9781461209232 .
↑ Tiheät matriisit kokonaislukurenkaan päällä - Sage Reference Manual v7.2: Matriisit ja matriisiavaruudet . doc.sagemath.org . Haettu: 22.6.2016. (määrätön)
↑ 1 2 Mader, A. Melkein täysin hajoavat ryhmät . - CRC Press , 2000. - ISBN 9789056992255 .
↑ Micciancio, Daniele; Goldwasser, Shafi. Hilaongelmien monimutkaisuus : kryptografinen näkökulma . - Springer Science & Business Media , 2012. - ISBN 9781461508977 .
↑ W., Weisstein, Eric Hermite Normaali muoto . mathworld.wolfram.com . Haettu: 22.6.2016.
↑ Bouajjani, Ahmed; Maler, Oded. Tietokoneavusteinen todentaminen: 21. kansainvälinen konferenssi, CAV 2009, Grenoble, Ranska, 26. kesäkuuta - 2. heinäkuuta 2009, Proceedings . - Springer Science & Business Media , 2009. - ISBN 9783642026577 .
↑ Eremiitti matriisin normaalimuoto - MuPAD . www.mathworks.com . Haettu: 22.6.2016. (määrätön)
↑ 1 2 3 Schrijver, Alexander. Lineaari- ja kokonaislukuohjelmoinnin teoria . - John Wiley & Sons , 1998. - ISBN 9780471982326 .
↑ Cohen, Henry. Laskennallisen algebrallisen lukuteorian kurssi . - Springer Science & Business Media , 2013. - ISBN 9783662029459 .
↑ Kannan, R.; Bachem, A. Polynomialgoritmit Smithin ja Hermiten kokonaislukumatriisin normaalimuotojen laskemiseen // SIAM Journal on Computing : päiväkirja. - 1979. - 1. marraskuuta ( nide 8 , nro 4 ). - s. 499-507 . — ISSN 0097-5397 . - doi : 10.1137/0208040 .
↑ Euklidinen algoritmi ja Eremitin normaalimuoto (linkki ei saatavilla) (2. maaliskuuta 2010). Haettu 25. kesäkuuta 2015. Arkistoitu alkuperäisestä 7. elokuuta 2016. (määrätön)
↑ Martin, Richard Kipp. Luku 4.2.4 Eremitin normaalimuoto // Suuren mittakaavan lineaarinen ja kokonaislukuoptimointi: yhtenäinen lähestymistapa . - Springer Science & Business Media , 2012. - ISBN 9781461549758 .
↑ Bremner, Murray R. Luku 14: Eremitin normaalimuoto // Hilapohjainen pelkistys: Johdatus LLL-algoritmiin ja sen sovelluksiin . - CRC Press , 2011. - ISBN 9781439807040 .
↑ Havas, George; Majewski, Bohdan S.; Matthews, Keith R. Laajennetut GCD- ja Hermite-normaalimuoto-algoritmit hilapohjan vähentämisen kautta // Experimental Mathematics : Journal. - 1998. - Voi. 7 , ei. 2 . - s. 130-131 . — ISSN 1058-6458 .
↑ Micciancio, Daniele Perusalgoritmit . Haettu: 25.6.2016. (määrätön)