Forma normal de Hermita

En álgebra lineal , la forma normal de Hermite es análoga a la forma escalonada reducida para matrices sobre números enteros Z. Así como la forma escalonada reducida se puede utilizar para resolver problemas sobre la solución del sistema lineal Ax = b donde x está en R ⁿ , la forma normal de Hermite puede resolver problemas sobre la solución del sistema lineal Ax = b donde esta vez x es restringido a tener coordenadas enteras únicamente. Otras aplicaciones de la forma normal de Hermite incluyen programación entera , ^[1] criptografía , ^[2] y álgebra abstracta . ^[3]

Definición

Es posible que varios autores prefieran hablar de la forma normal de Hermite en estilo de fila o de columna. Son esencialmente los mismos hasta la transposición.

Forma normal de Hermite estilo fila

Una matriz A de m por n con entradas enteras tiene una forma normal de Hermite (fila) H si hay una matriz unimodular cuadrada U donde H = UA y H tiene las siguientes restricciones: ^{[4] [5] [6]}

1. H es triangular superior (es decir, h _ij = 0 para i > j ), y cualquier fila de ceros se ubica debajo de cualquier otra fila.
2. El coeficiente principal (la primera entrada distinta de cero desde la izquierda, también llamada pivote ) de una fila distinta de cero siempre está estrictamente a la derecha del coeficiente principal de la fila superior; además, es positivo.
3. Los elementos debajo de los pivotes son cero y los elementos encima de los pivotes no son negativos y estrictamente más pequeños que el pivote.

La tercera condición no es estándar entre los autores; por ejemplo, algunas fuentes obligan a los no pivotes a no ser positivos ^{[7] [8]} o no les imponen restricciones de signo. ^[9] Sin embargo, estas definiciones son equivalentes al utilizar una matriz unimodular diferente U. Una matriz unimodular es una matriz entera cuadrada invertible cuyo determinante es 1 o −1.

Forma normal de Hermite estilo columna

Una matriz A de m por n con entradas enteras tiene una forma normal de Hermite (columna) H si hay una matriz unimodular cuadrada U donde H = AU y H tiene las siguientes restricciones: ^{[8] [10]}

1. H es triangular inferior, h _ij = 0 para i < j y todas las columnas de ceros se encuentran a la derecha.
2. El coeficiente principal (la primera entrada distinta de cero desde arriba, también llamada pivote ) de una columna distinta de cero siempre está estrictamente por debajo del coeficiente principal de la columna anterior; además, es positivo.
3. Los elementos a la derecha de los pivotes son cero y los elementos a la izquierda de los pivotes no son negativos y son estrictamente más pequeños que el pivote.

Tenga en cuenta que la definición de estilo de fila tiene una matriz unimodular U que multiplica A a la izquierda (lo que significa que U actúa sobre las filas de A ), mientras que la definición de estilo de columna tiene la acción de matriz unimodular sobre las columnas de A. Las dos definiciones de formas normales de Hermite son simplemente transposiciones entre sí.

Existencia y unicidad de la forma normal de Hermite.

Cada matriz A de rango completo de m por n con entradas enteras tiene una matriz H única de m por n en forma normal de Hermite, tal que H = UA para alguna matriz unimodular cuadrada U. ^{[5] [11] [12]}

Ejemplos

En los ejemplos siguientes, H es la forma normal de Hermite de la matriz A y U es una matriz unimodular tal que UA = H. $${\displaystyle 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&19&1\\0&0&0&3\end{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)}$$

$${\displaystyle A={\begin{pmatrix}2&3&6&2\\5&6&1&6\\8&3&1&1\end{pmatrix}}\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)}$$

Si A tiene solo una fila, entonces H = A o H = − A , dependiendo de si la única fila de A tiene un coeficiente principal positivo o negativo.

Algoritmos

Hay muchos algoritmos para calcular la forma normal de Hermite, que se remontan a 1851. Uno de esos algoritmos se describe en ^{[13] : 43--45} Pero sólo en 1979 se desarrolló un algoritmo para calcular la forma normal de Hermite que se ejecutaba en tiempo fuertemente polinomial . desarrollado por primera vez; ^[14] es decir, el número de pasos para calcular la forma normal de Hermite está limitado por un polinomio en las dimensiones de la matriz de entrada, y el espacio utilizado por el algoritmo (números intermedios) está limitado por un polinomio en la codificación binaria. tamaño de los números en la matriz de entrada.

Una clase de algoritmos se basa en la eliminación gaussiana en el sentido de que se utilizan repetidamente matrices elementales especiales. ^{[11] [15] [16]} El algoritmo LLL también se puede utilizar para calcular eficientemente la forma normal de Hermite. ^{[17] [18]}

Aplicaciones

Cálculos de celosía

Una red típica en R ⁿ tiene la forma donde los a _i están en R ⁿ . Si las columnas de una matriz A son ai _, la red se puede asociar con las columnas de una matriz, y se dice que A es una base de L. Debido a que la forma normal de Hermite es única, se puede utilizar para responder muchas preguntas sobre dos descripciones de celosías. Para lo que sigue, denota la red generada por las columnas de A. Debido a que la base está en las columnas de la matriz A , se debe usar la forma normal de Hermite estilo columna. Dadas dos bases para una red, A y A' , el problema de equivalencia es decidir si Esto se puede hacer comprobando si la forma normal de Hermite estilo columna de A y A' son iguales hasta la suma de cero columnas. Esta estrategia también es útil para decidir si una red es un subconjunto ( si y solo si ), decidir si un vector v está en una red ( si y solo si ) y para otros cálculos. ^[19] ${\textstyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}\mathbf {a} _{i}\;\right\vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$ ${\displaystyle L_{A}}$ ${\displaystyle L_{A}=L_{A'}.}$ ${\displaystyle L_{A}\subseteq L_{A'}}$ ${\displaystyle L_{[A\mid A']}=L_{A'}}$ ${\displaystyle v\in L_{A}}$ ${\displaystyle L_{[v\mid A]}=L_{A}}$

Soluciones enteras a sistemas lineales.

El sistema lineal Ax = b tiene una solución entera x si y solo si el sistema Hy = b tiene una solución entera y donde y = U ⁻¹ x y H es la forma normal de Hermite estilo columna de A. Comprobar que Hy = b tiene una solución entera es más fácil que Ax = b porque la matriz H es triangular. ^{[11] : 55}

Implementaciones

Muchos paquetes de software matemático pueden calcular la forma normal de Hermite:

• Arce con HermiteForm
• Mathematica con HermiteDescomposición
• MATLAB con hermiteForm
• NTL con HNF
• PARI/GP con mathnf
• SageMath con hermite_form

Sobre un dominio arbitrario de Dedekind

La forma normal de Hermite se puede definir cuando reemplazamos Z por un dominio arbitrario de Dedekind . ^[20] (por ejemplo, cualquier dominio ideal principal ). Por ejemplo, en teoría de control puede resultar útil considerar la forma normal de Hermite para los polinomios F [ x ] sobre un campo dado F .

Ver también

• Anillo de ermita
• Forma normal de Smith
• forma normal de howell
• Ecuación diofántica

Referencias

1. Colgado, Ming S.; Rom, Walter O. (15 de octubre de 1990). "Una aplicación de la forma normal de Hermite en programación entera". Álgebra lineal y sus aplicaciones . 140 : 163-179. doi : 10.1016/0024-3795(90)90228-5 .
2. Evangelos, Tourloupis, Vasilios (1 de enero de 2013). "Formas normales de Hermite y sus aplicaciones criptográficas". Colección de tesis de la Universidad de Wollongong 1954-2016 . Universidad de Wollongong.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
3. Adkins, William; Weintraub, Steven (6 de diciembre de 2012). Álgebra: un enfoque a través de la teoría de módulos. Medios de ciencia y negocios de Springer. pag. 306.ISBN​ 9781461209232.
4. "Matrices densas sobre el anillo de enteros - Manual de referencia de Sage v7.2: matrices y espacios de matrices". doc.sagemath.org . Consultado el 22 de junio de 2016 .
5. Mader, A. (9 de marzo de 2000). Grupos casi completamente descomponibles. Prensa CRC. ISBN 9789056992255.
6. Micciancio, Daniele; Goldwasser, Shafi (6 de diciembre de 2012). Complejidad de los problemas de celosía: una perspectiva criptográfica. Medios de ciencia y negocios de Springer. ISBN 9781461508977.
7. Weisstein, Eric W. "Forma normal de Hermite". mathworld.wolfram.com . Consultado el 22 de junio de 2016 .
8. Bouajjani, Ahmed; Maler, Oded (19 de junio de 2009). Verificación asistida por computadora: XXI Conferencia Internacional, CAV 2009, Grenoble, Francia, 26 de junio - 2 de julio de 2009, Actas. Medios de ciencia y negocios de Springer. ISBN 9783642026577.
9. "Forma normal de Hermite de una matriz - MuPAD". www.mathworks.com . Archivado desde el original el 17 de febrero de 2019 . Consultado el 22 de junio de 2016 .
10. Martín, Richard Kipp (6 de diciembre de 2012). Optimización lineal y entera a gran escala: un enfoque unificado. Medios de ciencia y negocios de Springer. ISBN 9781461549758.
11. Schrijver, Alejandro (7 de julio de 1998). Teoría de la Programación Lineal y Entera. John Wiley e hijos. ISBN 9780471982326.
12. Cohen, Henri (17 de abril de 2013). Un curso de teoría de números algebraica computacional. Medios de ciencia y negocios de Springer. ISBN 9783662029459.
13. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, señor  1261419
14. Kannan, R.; Bachem, A. (1 de noviembre de 1979). "Algoritmos polinómicos para calcular las formas normales de Smith y Hermite de una matriz entera" (PDF) . Revista SIAM de Computación . 8 (4): 499–507. doi :10.1137/0208040. ISSN  0097-5397.
15. "Algoritmo euclidiano y forma normal de Hermite". 2 de marzo de 2010. Archivado desde el original el 7 de agosto de 2016 . Consultado el 25 de junio de 2015 .
16. Martín, Richard Kipp (6 de diciembre de 2012). "Capítulo 4.2.4 Forma normal de Hermite". Optimización lineal y entera a gran escala: un enfoque unificado . Medios de ciencia y negocios de Springer. ISBN 9781461549758.
17. Bremner, Murray R. (12 de agosto de 2011). "Capítulo 14: La forma normal de Hermite". Reducción de la base de celosía: una introducción al algoritmo LLL y ​​sus aplicaciones . Prensa CRC. ISBN 9781439807040.
18. Havas, George; Majewski, Bohdan S.; Matthews, Keith R. (1998). "Algoritmos de forma normal GCD extendido y Hermite mediante reducción de base reticular". Matemáticas Experimentales . 7 (2): 130–131. doi :10.1080/10586458.1998.10504362. ISSN  1058-6458. S2CID  263873475.
19. Micciancio, Daniele. "Algoritmos básicos" (PDF) . Consultado el 25 de junio de 2016 .
20. Cohen, Henri (1999). Temas avanzados en teoría computacional de números . Saltador. §1.4.2. ISBN 0-387-98727-4.