Forma normal de Hermite

Forma normal de Hermite no estilo de linhas

Uma matriz ${\displaystyle A\in \mathbb {Z} ^{m\times n}}$ tem uma forma normal de Hermite (de linhas) ${\displaystyle H}$ se existe uma matriz unimodular quadrada ${\displaystyle U}$ tal que ${\displaystyle H=UA}$ e:

1. ${\displaystyle H}$ é triangular superior (isto é, ${\displaystyle h_{ij}=0}$ para ${\displaystyle i>j}$), e quaisquer linhas de zeros estão localizadas abaixo de qualquer outra linha.
2. O coeficiente líder (a primeira entrada não nula da esquerda, também chamada de pivô) de uma linha não nula está sempre estritamente à direita do coeficiente líder da linha acima dela; além disso, é positivo.
3. Os elementos abaixo dos pivôs são zero e os elementos acima dos pivôs são não negativos e estritamente menores que o pivô.

A terceira condição não é padrão entre os autores; por exemplo, algumas fontes forçam os não pivôs a serem não positivos ou não impõem nenhuma restrição de sinal sobre eles. No entanto, essas definições são equivalentes usando uma matriz unimodular ${\displaystyle U}$ diferente. Uma matriz unimodular é uma matriz de inteiros quadrada cujo determinante é 1 ou −1 (e, portanto, invertível). De fato, uma matriz unimodular é invertível sobre os inteiros, como pode ser visto, por exemplo, pela regra de Cramer.

Forma normal de Hermite no estilo de colunas

Uma matriz ${\displaystyle A\in \mathbb {Z} ^{m\times n}}$ tem uma forma normal de Hermite (de colunas) ${\displaystyle H}$ se existe uma matriz unimodular quadrada ${\displaystyle U}$ onde ${\displaystyle H=AU}$ e ${\displaystyle H}$ tem as seguintes restrições:

1. ${\displaystyle H}$ é triangular inferior (${\displaystyle h_{ij}=0}$ para ${\displaystyle i<j}$) e quaisquer colunas de zeros estão localizadas à direita.
2. O coeficiente líder (a primeira entrada não nula do topo, também chamada de pivô) de uma coluna não nula está sempre estritamente abaixo do coeficiente líder da coluna anterior; além disso, é positivo.
3. Os elementos à direita dos pivôs são zero e os elementos à esquerda dos pivôs são não negativos e estritamente menores que o pivô.

Observe que a definição no estilo de linhas tem uma matriz unimodular ${\displaystyle U}$ multiplicando ${\displaystyle A}$ à esquerda (o que significa que ${\displaystyle U}$ está agindo sobre as linhas de ${\displaystyle A}$), enquanto a definição no estilo de colunas tem a ação da matriz unimodular sobre as colunas de ${\displaystyle A}$. As duas definições de formas normais de Hermite são simplesmente transpostas uma da outra.

Exemplos

Nos exemplos abaixo, H é a forma normal de Hermite da matriz A, e U é uma 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)}$$

Se A tem apenas uma linha, então ou H = A ou H = −A, dependendo se a única linha de A tem um coeficiente líder positivo ou negativo.

Algoritmos

Há muitos algoritmos para calcular a forma normal de Hermite, remontando a 1851. Um desses algoritmos é descrito em.^(43--45) Mas somente em 1979 foi desenvolvido um algoritmo para calcular a forma normal de Hermite que rodava em tempo fortemente polinomial; isto é, o número de passos para calcular a forma normal de Hermite é limitado superiormente por um polinômio nas dimensões da matriz de entrada, e o espaço usado pelo algoritmo (números intermediários) é limitado por um polinômio no tamanho da codificação binária dos números na matriz de entrada.

Uma classe de algoritmos é baseada na eliminação gaussiana, na qual matrizes elementares especiais são usadas repetidamente. O algoritmo LLL também pode ser usado para calcular eficientemente a forma normal de Hermite.

Cálculos de reticulados

Um reticulado típico em Rⁿ tem a forma ${\textstyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}\mathbf {a} _{i}\;\right\vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$ onde os a_i estão em Rⁿ. Se as colunas de uma matriz A são os a_i, o reticulado pode ser associado às colunas de uma matriz, e A é dito ser uma base de L. Como a forma normal de Hermite é única, ela pode ser usada para responder a muitas perguntas sobre duas descrições de reticulados. Para o que segue, ${\displaystyle L_{A}}$ denota o reticulado gerado pelas colunas de A. Como a base está nas colunas da matriz A, a forma normal de Hermite no estilo de colunas deve ser usada. Dadas duas bases para um reticulado, A e A', o problema de equivalência é decidir se ${\displaystyle L_{A}=L_{A'}.}$ Isso pode ser feito verificando se as formas normais de Hermite no estilo de colunas de A e A' são as mesmas a menos da adição de colunas de zeros. Esta estratégia também é útil para decidir se um reticulado é um subconjunto (${\displaystyle L_{A}\subseteq L_{A'}}$ se e somente se ${\displaystyle L_{[A\mid A']}=L_{A'}}$), decidir se um vetor v está em um reticulado (${\displaystyle v\in L_{A}}$ se e somente se ${\displaystyle L_{[v\mid A]}=L_{A}}$), e para outros cálculos.

Soluções inteiras para sistemas lineares

O sistema linear Ax = b tem uma solução inteira x se e somente se o sistema Hy = b tem uma solução inteira y onde y = U⁻¹x e H é a forma normal de Hermite no estilo de colunas de A. Verificar que Hy = b tem uma solução inteira é mais fácil que Ax = b porque a matriz H é triangular.^:55