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]
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.
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]
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.
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]
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.
Cada matriz mxn A de miembros enteros tiene una única matriz H tal que H=UA para alguna matriz unimodular U.[5][11][12]
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.
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]
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]
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.
Existen diversos paquetes de software matemática capaces de procesar la forma normal de Hermite: