En álgebra lineal , la forma normal Hermite es un análogo de forma escalonada reducida para matrices más de la enteros Z . Así como la forma escalonada reducida se puede usar para resolver problemas sobre la solución del sistema lineal Ax = b donde x está en R n , la forma normal de Hermite puede resolver problemas sobre la solución del sistema lineal Ax = b donde este tiempo x es restringido para tener coordenadas enteras solamente. Otras aplicaciones de la forma normal de Hermite incluyen programación de enteros , [1] criptografía, [2] y álgebra abstracta . [3]
Definición
Varios autores pueden preferir hablar sobre la forma normal de Hermite en estilo de fila o en estilo de columna. Son esencialmente los mismos hasta la transposición.
Forma normal de Hermite estilo hilera
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]
- H es triangular superior (es decir, h ij = 0 para i> j ), y cualquier fila de ceros se ubica debajo de cualquier otra fila.
- 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.
- Los elementos debajo de los pivotes son cero y los elementos encima de los pivotes no son negativos y son 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 ninguna restricción de signo. [9] Sin embargo, estas definiciones son equivalentes al usar una matriz unimodular U diferente . Una matriz unimodular es una matriz entera cuadrada invertible cuyo determinante es 1 o -1.
Forma normal de Hermite estilo columna
A m por n matriz A con las entradas de números enteros tiene un (columna) forma Hermite normal de H si hay un cuadrado matriz unimodular U donde H = AU y H tiene las siguientes restricciones: [8] [10]
- H es triangular inferior, h ij = 0 para i
, y las columnas de ceros se encuentran a la derecha. - El coeficiente principal (la primera entrada distinta de cero desde la parte superior, 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.
- 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 fila tiene una matriz unimodular T multiplicando A la izquierda (es decir, T tiene en cuenta las filas de A ), mientras que la definición de estilo columna tiene la acción de matriz unimodular en las columnas de A . Las dos definiciones de las formas normales de Hermite son simplemente transposiciones entre sí.
Existencia y singularidad de la forma normal de Hermite.
Cada matriz A de m por n con entradas enteras tiene una matriz H única de m por n , tal que H = UA para alguna matriz U cuadrada unimodular . [5] [11] [12]
Ejemplos de
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 .
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
Hay muchos algoritmos para calcular la forma normal de Hermite, que se remontan a 1851. No fue hasta 1979 cuando se desarrolló por primera vez un algoritmo para calcular la forma normal de Hermite que corría en tiempo fuertemente polinomial ; [13] es decir, el número de pasos para calcular la forma normal de Hermite está acotado arriba por un polinomio en las dimensiones de la matriz de entrada, y el espacio usado por el algoritmo (números intermedios) está acotado 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] [14] [15] El algoritmo LLL también se puede utilizar para calcular de manera eficiente la forma normal de Hermite. [16] [17]
Aplicaciones
Cálculos de celosía
Una celosía típica en R n tiene la formadonde los a i están en R n . Si las columnas de una matriz A son la una i , la red puede estar asociado con las columnas de una matriz, y A se dice que 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ía. Por lo que sigue,denota la celosía 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 celosía, A y A ' , el problema de equivalencia es decidir siEsto se puede hacer comprobando si la forma normal de Hermite de estilo de columna de A y A ' son iguales hasta la adición de cero columnas. Esta estrategia también es útil para decidir si una celosía es un subconjunto ( si y solo si ), decidiendo si un vector v está en una red ( si y solo si ) y para otros cálculos. [18]
Soluciones enteras para sistemas lineales
El sistema lineal Ax = b tiene una solución entera x si y sólo si el sistema de Hy = b tiene una solución entera y donde y = Ux y H es la columna de estilo Hermite forma normal de A . [11] : 55 Verificar que Hy = b tiene una solución entera es más fácil que Ax = b porque la matriz H es triangular.
Implementaciones
Muchos paquetes de software matemático pueden calcular la forma normal de Hermite:
- Arce con HermiteForm
- Mathematica con Hermite Descomposición
- MATLAB con hermiteForm
- NTL con HNF
- PARI / GP con mathnf
- SageMath con hermite_form
Ver también
- Anillo de hermite
- Smith forma normal
- Ecuación diofántica
Referencias
- ^ Hung, Ming S .; Rom, Walter O. (15 de octubre de 1990). "Una aplicación de la forma normal de Hermite en la programación de enteros" . Álgebra lineal y sus aplicaciones . 140 : 163-179. doi : 10.1016 / 0024-3795 (90) 90228-5 .
- ^ Evangelos, Tourloupis, Vasilios (1 de enero de 2013). "Formas normales de Hermite y sus aplicaciones criptográficas" . Universidad de Wollongong. Cite journal requiere
|journal=
( ayuda ) - ^ 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. pag. 306. ISBN 9781461209232.
- ^ "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 .
- ^ a b Mader, A. (9 de marzo de 2000). Grupos casi completamente descomponibles . Prensa CRC. ISBN 9789056992255.
- ^ Micciancio, Daniele; Goldwasser, Shafi (6 de diciembre de 2012). Complejidad de los problemas de celosía: una perspectiva criptográfica . Springer Science & Business Media. ISBN 9781461508977.
- ^ W., Weisstein, Eric. "Forma normal de Hermite" . mathworld.wolfram.com . Consultado el 22 de junio de 2016 .
- ^ a b 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.
- ^ "Forma normal de Hermite de una matriz - MuPAD" . www.mathworks.com . Consultado el 22 de junio de 2016 .
- ^ Martin, Richard Kipp (6 de diciembre de 2012). Optimización lineal y de enteros a gran escala: un enfoque unificado . Springer Science & Business Media. ISBN 9781461549758.
- ^ a b c Schrijver, Alexander (7 de julio de 1998). Teoría de la programación lineal y entera . John Wiley e hijos. ISBN 9780471982326.
- ^ Cohen, Henri (17 de abril de 2013). Un curso de teoría de números algebraicos computacionales . Springer Science & Business Media. ISBN 9783662029459.
- ^ Kannan, R .; Bachem, A. (1 de noviembre de 1979). "Algoritmos polinomiales para calcular las formas normales de Smith y Hermite de una matriz de enteros" (PDF) . Revista SIAM de Computación . 8 (4): 499–507. doi : 10.1137 / 0208040 . ISSN 0097-5397 .
- ^ "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 .
- ^ Martin, Richard Kipp (6 de diciembre de 2012). "Capítulo 4.2.4 Forma normal de Hermite" . Optimización lineal y de enteros a gran escala: un enfoque unificado . Springer Science & Business Media. ISBN 9781461549758.
- ^ 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.
- ^ Havas, George; Majewski, Bohdan S .; Matthews, Keith R. (1998). "Algoritmos extendidos de forma normal de GCD y Hermite a través de la reducción de la base de celosía" . Matemáticas experimentales . 7 (2): 130-131. doi : 10.1080 / 10586458.1998.10504362 . ISSN 1058-6458 .
- ^ Micciancio, Daniele. "Algoritmos básicos" (PDF) . Consultado el 25 de junio de 2016 .