Forma normal hermítica

La forma normal hermitiana es análoga a la forma escalonada de la matriz para matrices sobre el anillo de enteros . Mientras que la forma escalonada de la matriz se usa para resolver sistemas de ecuaciones lineales de la forma para , la forma normal hermítica se puede usar para resolver sistemas lineales de ecuaciones diofánticas , en los que se supone que . La forma normal hermítica se utiliza para resolver problemas de programación entera [1] , criptografía [2] y álgebra general [3] . $\matemáticas {Z}$ $hacha=b$ $x\en \mathbb{R} ^{n}$ $x\in \mathbb {Z} ^{n}$

Definición

Una matriz es una forma normal hermitiana de una matriz entera si existe una matriz unimodular tal que y satisface las siguientes restricciones [4] [5] [6] : $H$ $A$ $tu$ ${\ estilo de visualización H = UA}$ $H$

$H$ es triangular superior, es decir, si cualquier cadena que consta completamente de ceros está debajo de todas las demás. $h_{ij}=0$ $yo>j$
El elemento principal de cualquier fila distinta de cero siempre es positivo y se encuentra a la derecha del coeficiente principal de la fila superior.
Los elementos debajo de los principales son iguales a cero, y los elementos arriba de los principales no son negativos y son estrictamente menores que el principal.

Algunos autores en la tercera condición requieren que los elementos sean no positivos [7] [8] o que no les impongan ninguna restricción de signo [9] .

Existencia y singularidad de una forma normal hermítica

La forma normal hermitiana existe y es única para cualquier matriz entera [5] [10] [11] . $H$ $A$

Ejemplos

En los ejemplos siguientes, la matriz es la forma normal hermítica de la matriz y la matriz unimodular correspondiente es la matriz tal que . $H$ $A$ $tu$ ${\ estilo de visualización 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&19&1\\0&0&0&3\end{ pmatrix}}\qquad U=\left({\begin{matriz}{rrrr}1&-3&0&-1\\0&1&0&0\\0&0&1&-5\\0&0&0&1\end{matriz}}\right)

$A=\left({\begin{matriz}{rrrr}2&3&6&2\\5&6&1&6\\8&3&1&1\end{matriz}}\right)\qquad H=\left({\begin{matriz}{rrrr}1&0&50& -11\\0&3&28&-2\\0&0&61&-13\end{matriz}}\right)\qquad U=\left({\begin{matriz}{rrr}9&-5&1\\5&-2&0\\11&-6&1 \end{matriz}}\right)$

Algoritmos

Los primeros algoritmos para calcular la forma normal hermítica datan de 1851. Al mismo tiempo, el primer algoritmo que funciona en tiempo estrictamente polinómico se desarrolló recién en 1979 [12] . Una de las clases de algoritmos ampliamente utilizados para reducir una matriz a la forma normal hermítica se basa en un método gaussiano modificado [10] [13] [14] . Otro método común para calcular la forma normal hermítica es el algoritmo LLL [15] [16] .

Aplicaciones

Cálculos de celosía

Por lo general, las celosías tienen la forma , donde . Si consideramos una matriz cuyas filas están compuestas por vectores , entonces su forma normal hermítica definirá alguna base reticular definida de forma única. Esta observación permite comprobar rápidamente si las redes generadas por las filas de las matrices y , para lo que basta comprobar que las matrices tienen las mismas formas normales hermitianas, coinciden. Del mismo modo, se puede comprobar si la red es una subred de la red , para lo cual basta con considerar la matriz obtenida de la unión de las filas y . En este escenario, es una subred si y sólo si las formas normales hermitianas y [17] coinciden . $\mathbb{R} ^{n}$ ${\textstyle L=\left\{\left.\alpha_{1}a_{1}+\alpha_{2}a_{2}+\dots +\alpha_{n}a_{n}\;\ derecha\vert \;\alpha _{i}\in \mathbb {Z} \derecha\}}$ $a_{i}\en \mathbb {R} ^{n}$ $A$ $ai}$ $A$ $A'$ ${\ Displaystyle L_ {A'))$ ${\ estilo de visualización L_ {A}}$ ${\ estilo de visualización A''}$ $A$ $A'$ ${\ Displaystyle L_ {A'))$ ${\ estilo de visualización L_ {A}}$ $A$ ${\ estilo de visualización A''}$

Ecuaciones lineales diofánticas

Un sistema de ecuaciones lineales tiene solución entera si y sólo si el sistema tiene solución entera, donde es la forma normal hermitiana de la matriz [10] :55 . $hacha=b$ $X$ $Hx=Ub$ ${\ estilo de visualización H = UA}$ $A$

Implementación

El cálculo de la forma normal hermítica se implementa en muchos sistemas de álgebra computacional:

HermiteForm en arce
Descomposición de Hermite en Mathematica
HermiteForm en MATLAB
hermite_form en SageMath

Véase también

Notas

↑ Hung, Ming S.; Rom, Walter O. Una aplicación de la forma normal de Hermite en programación entera // Álgebra lineal y sus aplicaciones : revista . - 1990. - 15 de octubre ( vol. 140 ). - pág. 163-179 . - doi : 10.1016/0024-3795(90)90228-5 .
↑ Evangelos, Tourloupis, Vasilios. Formas normales de Hermite y sus aplicaciones criptográficas (inglés) : revista. - Universidad de Wollongong, 2013. - 1 de enero.
↑ Adkins, Guillermo; Weintraub, Steven. Álgebra: un enfoque a través de la teoría de módulos . - Springer Science & Business Media , 2012. - P. 306. - ISBN 9781461209232 .
↑ Matrices densas sobre el anillo de enteros - Manual de referencia de Sage v7.2: Matrices y espacios de matrices . doc.sagemath.org . Recuperado: 22 junio 2016. (indefinido)
↑ 1 2 Mader, A. Grupos casi completamente descomponibles . - CRC Press , 2000. - ISBN 9789056992255 .
↑ Micciancio, Daniele; Goldwasser, Shafi. Complejidad de los problemas de celosía: una perspectiva criptográfica . - Springer Science & Business Media , 2012. - ISBN 9781461508977 .
↑ W., Weisstein, Eric Hermite Forma normal . mundomatemático.wolfram.com . Recuperado: 22 junio 2016.
↑ Bouajjani, Ahmed; Maler, Oded. 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 , 2009. - ISBN 9783642026577 .
↑ Hermite forma normal de una matriz - MuPAD . www.mathworks.com . Recuperado: 22 junio 2016. (indefinido)
↑ 1 2 3 Schrijver, Alexander. Teoría de la Programación Lineal y Entera . - John Wiley & Sons , 1998. - ISBN 9780471982326 .
↑ Cohen, Enrique. Un curso de teoría de números algebraicos computacionales . - Springer Science & Business Media , 2013. - ISBN 9783662029459 .
↑ Kannan, R.; Bachem, A. Algoritmos polinómicos para calcular las formas normales de Smith y Hermite de una matriz entera // SIAM Journal on Computing : diario. - 1979. - 1 de noviembre ( vol. 8 , no. 4 ). - pág. 499-507 . — ISSN 0097-5397 . -doi : 10.1137/ 0208040 .
↑ Algoritmo euclidiano y forma normal de Hermite (enlace no disponible) (2 de marzo de 2010). Consultado el 25 de junio de 2015. Archivado desde el original el 7 de agosto de 2016. (indefinido)
↑ Martín, Richard Kipp. Capítulo 4.2.4 Forma normal de Hermite // Optimización lineal y entera a gran escala: un enfoque unificado . - Springer Science & Business Media , 2012. - ISBN 9781461549758 .
↑ Bremner, Murray R. 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 . - CRC Press , 2011. - ISBN 9781439807040 .
↑ Havas, Jorge; Majewski, Bohdan S.; Matthews, Keith R. Algoritmos de forma normal GCD y Hermite extendidos a través de la reducción de la base de celosía // Matemáticas experimentales: revista. - 1998. - vol. 7 , núm. 2 . - P. 130-131 . — ISSN 1058-6458 .
↑ Micciancio, Daniele Algoritmos básicos . Recuperado: 25 junio 2016. (indefinido)