Forma normal de Hermite

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 Rⁿ, 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 criptografía, y álgebra abstracta.

Definición

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.

Forma normal de Hermite por filas

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:

1. H es una matriz triangular superior (es decir, h_ij = 0 para i > j), y ninguna fila de ceros se sitúa por debajo de cualquier otra fila.
2. El coeficiente dominante (el primer elemento distinto de cero comenzando desde la izquierda, también llamado elemento pivote) de una fila distinta de cero debe estar estrictamente a la derecha del coeficiente dominante de la fila por encima suya y ser, además, positivo.
3. Los elementos bajo los pivotes son cero y los elementos por encima de los pivotes son positivos y estrictamente más pequeños que el pivote.

Esta tercera condición no está estandarizada entre autores. Por ejemplo, algunas fuentes fuerzan la negatividad de los valores que no sean pivotes. o no limitan su signo. 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.

Forma normal de Hermite por columnas

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:

1. H es triangular inferior, es decir, h_ij = 0 para i < j y ninguna columna de ceros está situada a la derecha.
2. El coeficiente dominante (el primer elemento distinto de cero comenzando desde arriba, también llamado elemento pivote) de una columna distinta de cero debe estar estrictamente por debajo del coeficiente dominante de la fila anterior y ser, además, positivo.
3. Los elementos a la derecha de los pivotes son cero y los elementos a la izquierda de los pivotes son positivos y estrictamente más pequeños que el pivote.

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.

Existencia y unicidad de la forma normal de Hermite

Cada matriz mxn A de miembros enteros tiene una única matriz H tal que H=UA para alguna matriz unimodular U.

Ejemplos

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.

$A=\left(\begin{array}{cccc}3& 3& 1& 4\\ 0& 1& 0& 0\\ 0& 0& 19& 16\\ 0& 0& 0& 3\end{array}\right)H=\left(\begin{array}{cccc}3& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 19& 1\\ 0& 0& 0& 3\end{array}\right)U=\left(\begin{array}{cccc}1& -3& 0& -1\\ 0& 1& 0& 0\\ 0& 0& 1& -5\\ 0& 0& 0& 1\end{array}\right)$

$A=\left(\begin{array}{cccccc}0& 0& 5& 0& 1& 4\\ 0& 0& 0& -1& -4& 99\\ 0& 0& 0& 20& 19& 16\\ 0& 0& 0& 0& 2& 1\\ 0& 0& 0& 0& 0& 3\\ 0& 0& 0& 0& 0& 0\end{array}\right)H=\left(\begin{array}{cccccc}0& 0& 5& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right)U=\left(\begin{array}{cccccc}1& 100& 5& 152& -3462& 0\\ 0& 79& 4& 120& -2735& 0\\ 0& 100& 5& 153& -3461& 0\\ 0& 40& 2& 61& -1384& 0\end{array}\right)$

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

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.

Algoritmos

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, 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. The LLL algorithm can also be used to efficiently compute the Hermite normal form.

Aplicaciones

Cálculo de redes

Una red en Rⁿ toma la forma $L=\{\sum _{i=1}^n{\alpha }_i{a}_i|{\alpha }_i\in \mathbb{Z}\}$ donde a_i se encuentra en Rⁿ. Si las columnas de una matriz A son a_i, 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 $L_A$ 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 $L_A=L_{A^{\prime }}.$. 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 ($L_A\subseteq L_{A^{\prime }}$ if and only if $L_{[A\mid A^{\prime }]}=L_{A^{\prime }}$), si un vector v se encuentra en una red ($v\in L_A$ if and only if $L_{[v\mid A]}=L_A$) y otros cálculos.

Soluciones enteras a sistemas lineales

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.Plantilla:Rp Comprobar que Hy = b tiene solución entera es más sencillo que hacerlo en Ax = b, pues la matriz H es triangular.

Implementaciones

Existen diversos paquetes de software matemática capaces de procesar la forma normal de Hermite:

• Maple con HermiteForm
• Mathematica con HermiteDecomposition
• MATLAB conhermiteForm
• NTL con HNF
• SageMath con hermite_form