Forma normal de Hermite

En álgebra lineal , la forma normal de Hermite es análoga a la forma escalonada reducida para matrices sobre los 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 está restringido a tener solo coordenadas enteras. 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 filas o de columnas. En esencia, son las mismas, salvo la transposición.

Forma normal de Hermite en estilo fila

Una matriz A de m por n con entradas enteras tiene una forma normal de Hermite (por filas) H si existe 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 llamado 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 fuerzan a que los no pivotes sean no positivos ^{[7] [8]} o no les imponen ninguna restricción 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 en estilo columna

Una matriz A de m por n con entradas enteras tiene una forma normal de Hermite (columna) H si existe 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 cualquier columna de ceros se ubica a la derecha.
2. El coeficiente principal (la primera entrada distinta de cero desde arriba, también llamado 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 son no negativos y estrictamente más pequeños que el pivote.

Tenga en cuenta que la definición de estilo fila tiene una matriz unimodular U multiplicando a A a la izquierda (lo que significa que U actúa sobre las filas de A ), mientras que la definición de estilo columna tiene la acción de la 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 de fila completo de m por n con entradas enteras tiene una matriz H de m por n única 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 fila única de A tiene un coeficiente principal positivo o negativo.

Algoritmos

Existen muchos algoritmos para calcular la forma normal de Hermite, que datan de 1851. Uno de estos algoritmos se describe en ^{[13] : 43--45} Pero recién en 1979 se desarrolló por primera vez un algoritmo para calcular la forma normal de Hermite que se ejecutaba en un tiempo fuertemente polinomial ; ^[14] es decir, el número de pasos para calcular la forma normal de Hermite está limitado arriba 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 el tamaño de codificación binaria de los números en la matriz de entrada.

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

Aplicaciones

Cálculos en red

Una red típica en R ⁿ tiene la forma donde las a _i están en R ⁿ . Si las columnas de una matriz A son las a _i , 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 red. 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 utilizar la forma normal de Hermite de 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 de estilo columna de A y A' son las mismas hasta la adición 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 de sistemas lineales

El sistema lineal Ax = b tiene una solución entera x si y sólo si el sistema Hy = b tiene una solución entera y donde y = U ⁻¹ x y H es la forma normal de Hermite en columna de A. Comprobar que Hy = b tiene una solución entera es más fácil que comprobar 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
• Descomposición de Mathematica con Hermite
• MATLAB con hermiteForm
• NTL con HNF
• PARI/GP con mathnf
• SageMath con hermite_form

Sobre un dominio Dedekind arbitrario

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

Véase también

• Anillo de hermita
• Forma normal de Smith
• Forma normal de Howell
• Ecuación diofántica

Referencias

1. Hung, 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}}: CS1 maint: 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. Springer Science & Business Media. pág. 306. ISBN 9781461209232.
4. "Matrices densas sobre el anillo entero — 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. CRC Press. ISBN 9789056992255.
6. Micciancio, Daniele; Goldwasser, Shafi (6 de diciembre de 2012). Complejidad de los problemas de red: una perspectiva criptográfica. Springer Science & Business Media. 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: 21.ª conferencia internacional, CAV 2009, Grenoble, Francia, 26 de junio - 2 de julio de 2009, Actas. Springer Science & Business Media. 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. Martin, Richard Kipp (6 de diciembre de 2012). Optimización lineal y entera a gran escala: un enfoque unificado. Springer Science & Business Media. ISBN 9781461549758.
11. Schrijver, Alexander (7 de julio de 1998). Teoría de la programación lineal y entera. John Wiley & Sons. ISBN 9780471982326.
12. Cohen, Henri (17 de abril de 2013). Un curso de teoría de números algebraicos computacionales. Springer Science & Business Media. 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, Sr.  1261419
14. Kannan, R.; Bachem, A. (1979-11-01). "Algoritmos polinomiales 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. Martin, 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 . Springer Science & Business Media. ISBN 9781461549758.
17. Bremner, Murray R. (12 de agosto de 2011). "Capítulo 14: La forma normal de Hermite". Reducción de base reticular: una introducción al algoritmo LLL y ​​sus aplicaciones . CRC Press. ISBN 9781439807040.
18. Havas, George; Majewski, Bohdan S.; Matthews, Keith R. (1998). "Algoritmos extendidos de MCD y de forma normal de Hermite mediante reducción de base reticular". Experimental Mathematics . 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 de números computacionales . Springer. §1.4.2. ISBN 0-387-98727-4.