Ir al contenido

Forma normal de Hermite

De Wikipedia, la enciclopedia libre

En álgebra lineal, la Forma Normal de Hermite es un término análogo de la matriz escalonada para matrices de enteros. Del mismo modo que la matriz escalonada, puede ser empleada en la resolución de problemas que involucren sistemas lineales Ax=b, donde x está en Rn, la Forma Normal de Hermite puede resolver problemas en los que los valores de x se limiten a coordenadas enteras. Otras aplicaciones de la forma normal de Hermite incluyen programación en enteros[1]criptografía,[2]​ y álgebra abstracta.[3]

Definición

[editar]

Diversos autores podrían preferir diferenciar entre forma normal de Hermite por filas o por columnas. Ambas formas son esencialmente iguales incluso en su trasposición.

Forma normal de Hermite por filas

[editar]

Sea A una matriz mxn con miembros enteros. A poseerá matriz normal de Hermite H si existe un cuadrado matriz unimodular U tal que H=U*A, teniendo H las siguientes restricciones:[4][5][6]

  1. H es una matriz triangular superior (es decir, hij = 0 para i > j), y ninguna fila de ceros se sitúa por debajo de cualquier otra fila.
  2. El coeficiente dominante (el primer elemento distinto de cero comenzando desde la izquierda, también llamado elemento pivote) de una fila distinta de cero debe estar estrictamente a la derecha del coeficiente dominante de la fila por encima suya y ser, además, positivo.
  3. Los elementos bajo los pivotes son cero y los elementos por encima de los pivotes son positivos y estrictamente más pequeños que el pivote.

Esta tercera condición no está estandarizada entre autores. Por ejemplo, algunas fuentes fuerzan la negatividad de los valores que no sean pivotes.[7][8]​ o no limitan su signo.[9]​ De todas formas, estas definiciones son equivalente mediante el uso de una matriz unimodular U diferente. Una matriz unimodular es una matriz cuadrada e invertible de enteros cuyo determinante es ±1.

Forma normal de Hermite por columnas

[editar]

Sea A una matriz mxn con miembros enteros. A poseerá matriz normal de Hermite H si existe un cuadrado matriz unimodular U tal que H=A*U, teniendo H las siguientes restricciones:[8][10]

  1. H es triangular inferior, es decir, hij = 0 para i < j y ninguna columna de ceros está situada a la derecha.
  2. El coeficiente dominante (el primer elemento distinto de cero comenzando desde arriba, también llamado elemento pivote) de una columna distinta de cero debe estar estrictamente por debajo del coeficiente dominante de la fila anterior y ser, además, positivo.
  3. Los elementos a la derecha de los pivotes son cero y los elementos a la izquierda de los pivotes son positivos y estrictamente más pequeños que el pivote.

Advierta que la definición por filas tiene una matriz unimodular U multiplicando a A por la izquierda (singificando que U actúa sobre las filas de A ) mientras que en la definición por columnas la matriz unimodular actúa sobre las columnas de A. Las dos definiciones de la forma normal de Hermite son simples trasposiciones recíprocas.

Existencia y unicidad de la forma normal de Hermite

[editar]

Cada matriz mxn A de miembros enteros tiene una única matriz H tal que H=UA para alguna matriz unimodular U.[5][11][12]

Ejemplos

[editar]

En los ejemplos a continuación mostrados, H es la matriz de la forma normal de Hermite de la matriz A y U es una matriz unimodular tal que UA=H.

Si A tiene solo una fila, entonces o bien H = A o bien H = A, dependiendo del signo del coeficiente dominante de la única fila de A.

Algoritmos

[editar]

Existen multitud de algoritmos para procesar la forma normal de Hermite desde 1851. No fue hasta 1979 que se creó un algoritmo para procesar la forma normal de Hermite que se ejecutaba en un tiempo fuertemente polinómico,[13]​ es decir, que el número de pasos para procesar la forma normal de Hermite estaba acotado superiormente por un polinomio cuyo tamaño de codificación binaria es el de los números de la matriz. Un tipo de algoritmo está basado en aplicar el método de Gauss a las matrices elementales que son continuamente usadas.[11][14][15]​ The LLL algorithm can also be used to efficiently compute the Hermite normal form.[16][17]

Aplicaciones

[editar]

Cálculo de redes

[editar]

Una red en Rn toma la forma donde ai se encuentra en Rn. Si las columnas de una matriz A son ai, entonces la red puede ser asociada con las columnas de una matriz, y A es considerada base de L. Dado que la forma normal de Hermite es única, puede ser usada para la resolución de multitud de cuestiones que involucren dos descripciones de redes. Con lo siguiente se denota la red generada por las columnas de A. Dado que la base está en las columnas de la matriz A, la formas normal de la matriz de Hermite por columnas debe ser empleada. Dadas dos bases de una red, A y A', el problema equivalente es decidir si . Esto puede hacerse comprobando si la forma normal de Hermite por columnas de A y A' son las mismas. Esta estrategia es también útil para decidir si una red es un subconjunto ( if and only if ), si un vector v se encuentra en una red ( if and only if ) y otros cálculos.[18]

Soluciones enteras a sistemas lineales

[editar]

El sistema lineal Ax = B tiene por solución integral x si y solo si el sistema Hy = b tiene solución entera y donde Uy = x y H es la forma normal de Hermite por columnas de H.[11]: 55  Comprobar que Hy = b tiene solución entera es más sencillo que hacerlo en Ax = b, pues la matriz H es triangular.

Implementaciones

[editar]

Existen diversos paquetes de software matemática capaces de procesar la forma normal de Hermite:

Referencias

[editar]
  1. Hung, Ming S.; Rom, Walter O. (15 de octubre de 1990). «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 (1 de enero de 2013). Hermite normal forms and its cryptographic applications. University of Wollongong. 
  3. Adkins, William; Weintraub, Steven (6 de diciembre de 2012). Algebra: An Approach via Module Theory (en inglés). Springer Science & Business Media. p. 306. ISBN 9781461209232. 
  4. «Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices». doc.sagemath.org. Consultado el 22 de junio de 2016. 
  5. a b Mader, A. (9 de marzo de 2000). Almost Completely Decomposable Groups (en inglés). CRC Press. ISBN 9789056992255. 
  6. Micciancio, Daniele; Goldwasser, Shafi (6 de diciembre de 2012). Complexity of Lattice Problems: A Cryptographic Perspective (en inglés). Springer Science & Business Media. ISBN 9781461508977. 
  7. W., Weisstein, Eric. «Hermite Normal Form». mathworld.wolfram.com (en inglés). Consultado el 22 de junio de 2016. 
  8. a b Bouajjani, Ahmed; Maler, Oded (19 de junio de 2009). Computer Aided Verification: 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings (en inglés). Springer Science & Business Media. ISBN 9783642026577. 
  9. «Hermite normal form of a matrix - MuPAD». www.mathworks.com. Archivado desde el original el 17 de febrero de 2019. Consultado el 22 de junio de 2016. 
  10. Martin, Richard Kipp (6 de diciembre de 2012). Large Scale Linear and Integer Optimization: A Unified Approach (en inglés). Springer Science & Business Media. ISBN 9781461549758. 
  11. a b c Schrijver, Alexander (7 de julio de 1998). Theory of Linear and Integer Programming (en inglés). John Wiley & Sons. ISBN 9780471982326. 
  12. Cohen, Henri (17 de abril de 2013). A Course in Computational Algebraic Number Theory (en inglés). Springer Science & Business Media. ISBN 9783662029459. 
  13. Kannan, R.; Bachem, A. (1 de noviembre de 1979). «Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix». SIAM Journal on Computing 8 (4): 499-507. ISSN 0097-5397. doi:10.1137/0208040. 
  14. «Euclidean Algorithm and Hermite Normal Form». 2 de marzo de 2010. Archivado desde el original el 7 de agosto de 2016. Consultado el 17 de febrero de 2019. 
  15. Martin, Richard Kipp (6 de diciembre de 2012). «Chapter 4.2.4 Hermite Normal Form». Large Scale Linear and Integer Optimization: A Unified Approach (en inglés). Springer Science & Business Media. ISBN 9781461549758. 
  16. Bremner, Murray R. (12 de agosto de 2011). «Chapter 14: The Hermite Normal Form». Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications (en inglés). CRC Press. ISBN 9781439807040. 
  17. Havas, George; Majewski, Bohdan S.; Matthews, Keith R. (1998). «Extended GCD and Hermite normal form algorithms via lattice basis reduction». Experimental Mathematics 7 (2): 130-131. ISSN 1058-6458. 
  18. Micciancio, Daniele. «Basic Algorithms». Consultado el 25 de junio de 2016.