Forma normal de Hermite

En àlgebra llineal, la Forma Normal de Hermite és un terme anàlec de la matriu escalonada para matrius de sancers. De la mateixa manera que la matriu escalonada, pot ser amprada en la resolució de problemes que involucren sistemes llineals Ax=b, a on x està en Rⁿ, la Forma Normal de Hermite pot resoldre problemes en els que els valors de x es llimiten a coordenades sanceres. Atres aplicacions de la forma normal de Hermite inclouen programació en sancers^[1] criptografia,^[2] i àlgebra abstracta.^[3]

Definició

Diversos autors podrien preferir diferenciar entre forma normal de Hermite per files o per columnes. Abdós formes són essencialment iguals inclús en la seua trasposición.

Forma normal de Hermite per files

Siga A una matriu mxn en membres sancers. A posseirà matriu normal de Hermite H si existix un quadrat matriu unimodular O tal que H=OA, tenint H les següents restriccions:^[4]^[5]^[6]

H és una matriu triangular superior (és dir, h_ij = 0 per a i > j), i cap fila de zeros se situa per baix de qualsevol atra fila.
El coeficient dominant (el primer element distint de zero començant des de l'esquerra, també cridat element pivot) d'una fila distinta de zero deu estar estrictament a la dreta del coeficient dominant de la fila per damunt seua i ser, ademés, positiu.
Els elements baix els pivots són zero i els elements per damunt dels pivots són positius i estrictament més menuts que el pivot.

Esta tercera condició no està estandardisada entre autors. Per eixemple, algunes fonts forcen la negatividad dels valors que no siguen pivots.^[7]^[8] o no llimiten el seu signe.^[9] De totes formes, estes definicions són equivalent per mig de l'us d'una matriu unimodular O diferent. Una matriu unimodular és una matriu quadrada i invertible de sancers que el seu determinant és ±1.

Forma normal de Hermite per columnes

Siga A una matriu mxn en membres sancers. A posseirà matriu normal de Hermite H si existix un quadrat matriu unimodular O tal que H=AO, tenint H les següents restriccions:^[8]^[10]

H és triangular inferior, és dir, h_ij = 0 per a i < j i cap columna de zeros està situada a la dreta.
El coeficient dominant (el primer element distint de zero començant des de dalt, també cridat element pivot) d'una columna distinta de zero deu estar estrictament per baix del coeficient dominant de la fila anterior i ser, ademés, positiu.
Els elements a la dreta dels pivots són zero i els elements a l'esquerra dels pivots són positius i estrictament més menuts que el pivot.

Advertixca que la definició per files té una matriu unimodular O multiplicant a A per l'esquerra (singificando que O actua sobre les files de A ) mentres que en la definició per columnes la matriu unimodular actua sobre les columnes de A. Les dos definicions de la forma normal de Hermite són simples trasposiciones recíproques.

Existència i unicitat de la forma normal de Hermite

Cada matriu mxn A de membres sancers té una única matriu H tal que H=UA per a alguna matriu unimodular O.^[5]^[11]^[12]

Eixemples

En els eixemples a continuació mostrats, H és la matriu de la forma normal de Hermite de la matriu A i O és una matriu unimodular tal que UA=H.

A = (\begin{matrix} 3 & 3 & 1 & 4 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 19 & 16 \\ 0 & 0 & 0 & 3 \end{matrix}) H = (\begin{matrix} 3 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 19 & 1 \\ 0 & 0 & 0 & 3 \end{matrix}) U = (\begin{matrix} 1 & - 3 & 0 & - 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & - 5 \\ 0 & 0 & 0 & 1 \end{matrix})

$A = (\begin{matrix} 0 & 0 & 5 & 0 & 1 & 4 \\ 0 & 0 & 0 & - 1 & - 4 & 99 \\ 0 & 0 & 0 & 20 & 19 & 16 \\ 0 & 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) H = (\begin{matrix} 0 & 0 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) U = (\begin{matrix} 1 & 100 & 5 & 152 & - 3462 & 0 \\ 0 & 79 & 4 & 120 & - 2735 & 0 \\ 0 & 100 & 5 & 153 & - 3461 & 0 \\ 0 & 40 & 2 & 61 & - 1384 & 0 \end{matrix})$

$A = (\begin{matrix} 2 & 3 & 6 & 2 \\ 5 & 6 & 1 & 6 \\ 8 & 3 & 1 & 1 \end{matrix}) H = (\begin{matrix} 1 & 0 & 50 & - 11 \\ 0 & 3 & 28 & - 2 \\ 0 & 0 & 61 & - 13 \end{matrix}) U = (\begin{matrix} 9 & - 5 & 1 \\ 5 & - 2 & 0 \\ 11 & - 6 & 1 \end{matrix})$

Si A té solament una fila, llavors o be H = A o be H = A, depenent del signe del coeficient dominant de l'única fila de A.

Algoritmes

Existixen multitut d'algoritmes per a processar la forma normal de Hermite des de 1851. No va ser fins a 1979 que es va crear un algoritme per a processar la forma normal de Hermite que s'eixecutava en un temps fortament polinòmic,^[13] és dir, que el número de passos per a processar la forma normal de Hermite estava acotat superiorment per un polinomi el tamany del qual de codificació binaria és el dels números de la matriu. Un tipo d'algoritme està basat en aplicar el método de Gauss a les matrius elementals que són contínuament usades.^[11]^[14]^[15] The LLL algorithm ca also be used to efficiently compute the Hermite normal form.^[16]^[17]

Referències

↑ Hung, Ming S.. “An application of the Hermite normal form in integer programming”. Linear Algebra and its Applications 140: 163–179. doi:10.1016/0024-3795(90)90228-5.
↑ Evangelos, Tourloupis, Vasilios. “Hermite normal forms and its cryptographic applications”. University of Wollongong.
↑ Adkins, William (6 de decembre de 2012). Algebra: An Approach via Module Theory (en en), Springer Science & Business Mija, p. 306. ISBN 9781461209232.
↑ «Donen-se matrius over the integer ring — Sage Reference Manual v7.2: Matrius and Spaces of Matrius».
↑ ^5,0 ^5,1 Mader, A.. Almost Completely Decomposable Groups (en en), CRC Press. ISBN 9789056992255.
↑ Micciancio, Daniele. Complexity of Lattice Problems: A Cryptographic Perspective (en en), Springer Science & Business Mija. ISBN 9781461508977.
↑ W., Weisstein, Eric. «Hermite Normal Form» (en en).
↑ ^8,0 ^8,1 Bouajjani, Ahmed. Computer Aided Verification: 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings (en en), Springer Science & Business Mija. ISBN 9783642026577.
↑ «Hermite normal form of a matrix - MuPAD». Archivat des d'el original, el 17 de febrer de 2019.
↑ Martin, Richard Kipp. Large Scale Linear and Integer Optimization: A Unified Approach (en en), Springer Science & Business Mija. ISBN 9781461549758.
↑ ^11,0 ^11,1 Schrijver, Alexander (7 de juliol de 1998). Theory of Linear and Integer Programming (en en), John Wiley & Sons. ISBN 9780471982326.
↑ Cohen, Henri. A Course in Computational Algebraic Number Theory (en en), Springer Science & Business Mija. ISBN 9783662029459.
↑ Kannan, R.. “Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix”. SIAM Journal on Computing 8 (4): 499–507. doi:10.1137/0208040. ISSN 0097-5397.
↑ «Euclidean Algorithm and Hermite Normal Form». Archivat des d'el original, el 7 d'agost de 2016. Consultat el 17 de febrer de 2019.
↑ Martin, Richard Kipp. «Chapter 4.2.4 Hermite Normal Form», Large Scale Linear and Integer Optimization: A Unified Approach (en en), Springer Science & Business Mija. ISBN 9781461549758.
↑ Bremner, Murray R.. «Chapter 14: The Hermite Normal Form», Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications (en en), CRC Press. ISBN 9781439807040.
↑ Havas, George. “Estendre GCD and Hermite normal form algorithms via lattice basis reduction”. Experimental Mathematics 7 (2): 130-131. ISSN 1058-6458.

Referències

Este artícul conté una traducció derivada de «Forma normal de Hermite» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Hung, Ming S.. “An application of the Hermite normal form in integer programming”. Linear Algebra and its Applications 140: 163–179. doi:10.1016/0024-3795(90)90228-5.

[2] Evangelos, Tourloupis, Vasilios. “Hermite normal forms and its cryptographic applications”. University of Wollongong.

[3] Adkins, William (6 de decembre de 2012). Algebra: An Approach via Module Theory (en en), Springer Science & Business Mija, p. 306. ISBN 9781461209232.

[4] «Donen-se matrius over the integer ring — Sage Reference Manual v7.2: Matrius and Spaces of Matrius».

[:1-5] 5,0 ^5,1 Mader, A.. Almost Completely Decomposable Groups (en en), CRC Press. ISBN 9789056992255.

[6] Micciancio, Daniele. Complexity of Lattice Problems: A Cryptographic Perspective (en en), Springer Science & Business Mija. ISBN 9781461508977.

[7] W., Weisstein, Eric. «Hermite Normal Form» (en en).

[:0-8] 8,0 ^8,1 Bouajjani, Ahmed. Computer Aided Verification: 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings (en en), Springer Science & Business Mija. ISBN 9783642026577.

[9] «Hermite normal form of a matrix - MuPAD». Archivat des d'el original, el 17 de febrer de 2019.

[10] Martin, Richard Kipp. Large Scale Linear and Integer Optimization: A Unified Approach (en en), Springer Science & Business Mija. ISBN 9781461549758.

[:3-11] 11,0 ^11,1 Schrijver, Alexander (7 de juliol de 1998). Theory of Linear and Integer Programming (en en), John Wiley & Sons. ISBN 9780471982326.

[:2-12] Cohen, Henri. A Course in Computational Algebraic Number Theory (en en), Springer Science & Business Mija. ISBN 9783662029459.

[13] Kannan, R.. “Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix”. SIAM Journal on Computing 8 (4): 499–507. doi:10.1137/0208040. ISSN 0097-5397.

[14] «Euclidean Algorithm and Hermite Normal Form». Archivat des d'el original, el 7 d'agost de 2016. Consultat el 17 de febrer de 2019.

[15] Martin, Richard Kipp. «Chapter 4.2.4 Hermite Normal Form», Large Scale Linear and Integer Optimization: A Unified Approach (en en), Springer Science & Business Mija. ISBN 9781461549758.

[16] Bremner, Murray R.. «Chapter 14: The Hermite Normal Form», Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications (en en), CRC Press. ISBN 9781439807040.

[17] Havas, George. “Estendre GCD and Hermite normal form algorithms via lattice basis reduction”. Experimental Mathematics 7 (2): 130-131. ISSN 1058-6458.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]