Hermitisk normalform

Hermitisk normalform är en analog till stegformen av matrisen för matriser över ringen av heltal . Medan den stegvisa formen av matrisen används för att lösa system av linjära ekvationer av formen för , kan den hermitiska normalformen användas för att lösa linjära system av diofantiska ekvationer , där det antas att . Hermitisk normalform används för att lösa problem med heltalsprogrammering [1] , kryptografi [2] och allmän algebra [3] . $\mathbb {Z}$ $ax=b$ $x\in \mathbb{R} ^{n}$ $x\in \mathbb {Z} ^{n}$

Definition

En matris är en hermitisk normalform av en heltalsmatris om det finns en unimodulär matris så att och uppfyller följande begränsningar [4] [5] [6] : $H$ $A$ $U$ $H=UA$ $H$

$H$ är övre triangulär, det vill säga om någon sträng som helt består av nollor är under alla andra. $h_{ij}=0$ $i>j$
Det inledande elementet i en rad som inte är noll är alltid positivt och ligger till höger om den inledande koefficienten för raden ovanför den.
Elementen under de ledande är lika med noll, och elementen ovanför de ledande är icke-negativa och strikt mindre än de ledande.

Vissa författare i det tredje villkoret kräver att elementen är icke-positiva [7] [8] eller lägger inga teckenbegränsningar på dem alls [9] .

Existens och unikhet hos en hermitisk normalform

Den hermitiska normalformen finns och är unik för alla heltalsmatriser [5] [10] [11] . $H$ $A$

Exempel

I exemplen nedan är matrisen den hermitiska normalformen av matrisen , och motsvarande unimodulära matris är matrisen så att . $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&0\\0&0&3&0&0\\0&0&3&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)$

Algoritmer

De första algoritmerna för att beräkna den hermitiska normalformen går tillbaka till 1851. Samtidigt utvecklades den första algoritmen som fungerar i strikt polynomtid först 1979 [12] . En av de mycket använda klasserna av algoritmer för att reducera en matris till hermitisk normalform är baserad på en modifierad Gaussisk metod [10] [13] [14] . En annan vanlig metod för att beräkna den hermitiska normalformen är LLL-algoritmen [15] [16] .

Applikationer

Gitterberäkningar

Vanligtvis har gittren i formen , där . Om vi betraktar en matris vars rader är sammansatta av vektorer , kommer dess Hermitiska normalform att definiera någon unikt definierad gitterbas. Denna observation låter dig snabbt kontrollera om gittren som genereras av raderna av matriser och , för vilka det räcker att kontrollera att matriserna har samma hermitiska normala former, sammanfaller. På samma sätt kan man kontrollera om gittret är ett subgitter av gittret , för vilket det räcker att beakta matrisen som erhålls från föreningen av raderna och . I denna inställning, är ett subgitter om och endast om Hermitian normala former och [17] sammanfaller . $\mathbb {R} ^{n}$ ${\textstyle L=\left\{\left.\alpha _{1}a_{1}+\alpha _{2}a_{2}+\dots +\alpha _{n}a_{n}\;\ höger\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''$

Diofantiska linjära ekvationer

Ett system med linjära ekvationer har en heltalslösning om och endast om systemet har en heltalslösning, där är den hermitiska normalformen av matrisen [10] :55 . $ax=b$ $x$ $Hx=Ub$ $H=UA$ $A$

Implementering

Beräkningen av den hermitiska normalformen är implementerad i många datoralgebrasystem:

Se även

Anteckningar

↑ Hung, Ming S.; Rom, Walter O. En tillämpning av Hermites normala form i heltalsprogrammering // Linjär algebra och dess tillämpningar : journal . - 1990. - 15 oktober ( vol. 140 ). - S. 163-179 . - doi : 10.1016/0024-3795(90)90228-5 .
↑ Evangelos, Tourloupis, Vasilios. Hermites normala former och dess kryptografiska tillämpningar (engelska) : journal. - University of Wollongong, 2013. - 1 januari.
↑ Adkins, William; Weintraub, Steven. Algebra: An Approach via Module Theory . - Springer Science & Business Media , 2012. - P. 306. - ISBN 9781461209232 .
↑ Täta matriser över heltalsringen - Sage Reference Manual v7.2: Matriser och mellanrum för matriser . doc.sagemath.org . Hämtad: 22 juni 2016. (obestämd)
↑ 1 2 Mader, A. Nästan helt nedbrytbara grupper . - CRC Press , 2000. - ISBN 9789056992255 .
↑ Micciancio, Daniele; Goldwasser, Shafi. Gitterproblemens komplexitet: ett kryptografiskt perspektiv . - Springer Science & Business Media , 2012. - ISBN 9781461508977 .
↑ W., Weisstein, Eric Hermite Normal Form . mathworld.wolfram.com . Hämtad: 22 juni 2016.
↑ Bouajjani, Ahmed; Maler, Oded. Datorstödd verifiering: 21:a internationella konferensen, CAV 2009, Grenoble, Frankrike, 26 juni - 2 juli 2009, Proceedings . - Springer Science & Business Media , 2009. - ISBN 9783642026577 .
↑ Hermites normala form av en matris - MuPAD . www.mathworks.com . Hämtad: 22 juni 2016. (obestämd)
↑ 1 2 3 Schrijver, Alexander. Teori för linjär- och heltalsprogrammering . - John Wiley & Sons , 1998. - ISBN 9780471982326 .
↑ Cohen, Henry. En kurs i beräkningsalgebraisk talteori . - Springer Science & Business Media , 2013. - ISBN 9783662029459 .
↑ Kannan, R.; Bachem, A. Polynomalgoritmer för beräkning av Smith och Hermites normala former av en heltalsmatris // SIAM Journal on Computing : journal. - 1979. - 1 november ( vol. 8 , nr 4 ). - S. 499-507 . — ISSN 0097-5397 . - doi : 10.1137/0208040 .
↑ Euklidisk algoritm och Hermites normala form (länk ej tillgänglig) (2 mars 2010). Hämtad 25 juni 2015. Arkiverad från originalet 7 augusti 2016. (obestämd)
↑ Martin, Richard Kipp. Kapitel 4.2.4 Hermites normalform // Storskalig linjär- och heltalsoptimering: En enhetlig metod . - Springer Science & Business Media , 2012. - ISBN 9781461549758 .
↑ Bremner, Murray R. Kapitel 14: Hermitens normala form // Lattice Basis Reduction: En introduktion till LLL-algoritmen och dess tillämpningar . - CRC Press , 2011. - ISBN 9781439807040 .
↑ Havas, George; Majewski, Bohdan S.; Matthews, Keith R. Utökade GCD och Hermite normalformsalgoritmer via gitterbasreduktion // Experimental Mathematics: journal. - 1998. - Vol. 7 , nr. 2 . - S. 130-131 . — ISSN 1058-6458 .
↑ Micciancio, Daniele Grundläggande algoritmer . Hämtad: 25 juni 2016. (obestämd)