Forma normal de Hermite

Una matriz${\displaystyle A\in \mathbb {Z} ^{m\times n}}$tiene una (fila) forma normal de Hermite${\displaystyle H}$si existe una matriz unimodular cuadrada${\displaystyle U}$de tal manera que${\displaystyle H=UA}$y: ^{[ 4 ] [ 5 ] [ 6 ]}

1. ${\displaystyle H}$es triangular superior (es decir,${\displaystyle h_{ij}=0}$para${\displaystyle i>j}$), y cualquier fila de ceros se encuentra debajo de cualquier otra fila.
2. El coeficiente principal (el primer elemento distinto 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 que se encuentran debajo de los pivotes son cero y los elementos que se encuentran encima de los pivotes son no negativos y estrictamente menores que el pivote.

La tercera condición no es estándar entre los autores; por ejemplo, algunas fuentes obligan a que los no pivotes sean no positivos ^{[ 7 ] [ 8 ]} o no imponen ninguna restricción de signo sobre ellos. ^{[ 9 ]} Sin embargo, estas definiciones son equivalentes utilizando una matriz unimodular diferente.${\displaystyle U}$Una matriz unimodular es una matriz cuadrada de números enteros cuyo determinante es 1 o -1 (y, por lo tanto, invertible ). De hecho, una matriz unimodular es invertible sobre los números enteros, como se puede observar, por ejemplo, en la regla de Cramer .

Una matriz${\displaystyle A\in \mathbb {Z} ^{m\times n}}$tiene una (columna) forma normal de Hermite${\displaystyle H}$si existe una matriz unimodular cuadrada${\displaystyle U}$dónde${\displaystyle H=AU}$y${\displaystyle H}$tiene las siguientes restricciones: ^{[ 8 ] [ 10 ]}

1. ${\displaystyle H}$es triangular inferior (${\displaystyle h_{ij}=0}$para${\displaystyle i<j}$) y cualquier columna de ceros se encuentra a la derecha.
2. El coeficiente principal (el primer valor distinto 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 menores que el pivote.

Tenga en cuenta que la definición de estilo de fila tiene una matriz unimodular.${\displaystyle U}$multiplicando${\displaystyle A}$a la izquierda (que significa${\displaystyle U}$está actuando sobre las filas de${\displaystyle A}$), mientras que la definición de estilo columna tiene la acción de matriz unimodular sobre las columnas de${\displaystyle A}$Las dos definiciones de formas normales de Hermite son simplemente transpuestas una de la otra.

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 única fila de A tiene un coeficiente principal positivo o negativo.

Hay muchos algoritmos para calcular la forma normal de Hermite, que datan de 1851. Uno de esos algoritmos se describe en ^{[ 13 ] : 43--45} Pero no fue hasta 1979 que se desarrolló por primera vez un algoritmo para calcular la forma normal de Hermite que se ejecutaba en tiempo fuertemente polinomial ; ^{[ 14 ]} es decir, el número de pasos para calcular la forma normal de Hermite está acotado superiormente por un polinomio en las dimensiones de la matriz de entrada, y el espacio utilizado por el algoritmo (números intermedios) está acotado 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 puede utilizarse para calcular eficientemente la forma normal de Hermite. ^{[ 17 ] [ 18 ]}

Una red típica en R ⁿ tiene la forma${\textstyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}\mathbf {a} _{i}\;\right\vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$donde los a _i están en R ⁿ . Si las columnas de una matriz A son los 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 redes. Para lo que sigue,${\displaystyle L_{A}}$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 consiste en decidir si${\displaystyle L_{A}=L_{A'}.}$Esto se puede hacer comprobando si la forma normal de Hermite de estilo columna de A y A'son iguales salvo la adición de columnas cero. Esta estrategia también es útil para decidir si un retículo es un subconjunto (${\displaystyle L_{A}\subseteq L_{A'}}$si y solo si${\displaystyle L_{[A\mid A']}=L_{A'}}$), decidiendo si un vector v está en una red (${\displaystyle v\in L_{A}}$si y solo si${\displaystyle L_{[v\mid A]}=L_{A}}$), y para otros cálculos. ^{[ 19 ]}

El sistema lineal Ax = b tiene una solución entera x si y solo si el sistema Hy = b tiene una solución entera y, donde y = U ⁻¹ x y H es la forma normal de Hermite en columnas 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}