Em álgebra linear, a forma normal de Hermite é um análogo da forma escalonada reduzida para matrizes sobre os números inteiros . Assim como a forma escalonada reduzida pode ser usada para resolver problemas sobre a solução do sistema linear onde , a forma normal de Hermite pode resolver problemas sobre a solução do sistema linear onde desta vez está restrito a ter apenas coordenadas inteiras. Outras aplicações da forma normal de Hermite incluem programação inteira, criptografia, e álgebra abstrata.

Definição Vários autores podem preferir falar sobre a forma normal de Hermite no estilo de linhas ou no estilo de colunas. Elas são essencialmente as mesmas a menos de transposição.

Forma normal de Hermite no estilo de linhas Uma matriz tem uma forma normal de Hermite (de linhas) se existe uma matriz unimodular quadrada tal que e: é triangular superior (isto é, para ), e quaisquer linhas de zeros estão localizadas abaixo de qualquer outra linha. 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. 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 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 tem uma forma normal de Hermite (de colunas) se existe uma matriz unimodular quadrada onde e tem as seguintes restrições: é triangular inferior ( para ) e quaisquer colunas de zeros estão localizadas à direita. 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. 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 multiplicando à esquerda (o que significa que está agindo sobre as linhas de ), enquanto a definição no estilo de colunas tem a ação da matriz unimodular sobre as colunas de . As duas definições de formas normais de Hermite são simplesmente transpostas uma da outra.

Existência e unicidade da forma normal de Hermite Toda matriz m-por-n de posto de linha completo A com entradas inteiras tem uma única matriz m-por-n H na forma normal de Hermite, tal que H=UA para alguma matriz unimodular quadrada U.

Exemplos Nos exemplos abaixo, é a forma normal de Hermite da matriz , e é uma matriz unimodular tal que .

Se tem apenas uma linha, então ou ou , dependendo se a única linha de 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. 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.

Aplicações

Cálculos de reticulados Um reticulado típico em Rn tem a forma onde os ai estão em Rn. Se as colunas de uma matriz A são os ai, 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, 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 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 ( se e somente se ), decidir se um vetor v está em um reticulado ( se e somente se ), e para outros cálculos.

Soluções inteiras para sistemas lineares O sistema linear tem uma solução inteira se e somente se o sistema tem uma solução inteira onde e é a forma normal de Hermite no estilo de colunas de . Verificar que tem uma solução inteira é mais fácil que porque a matriz é triangular.

Implementações Muitos pacotes de software matemático podem calcular a forma normal de Hermite: Maple com HermiteForm MATLAB com hermiteForm NTL com HNF PARI/GP com mathnf SageMath com hermite_form

Sobre um domínio de Dedekind arbitrário A forma normal de Hermite pode ser definida quando substituímos Z por um domínio de Dedekind arbitrário. (por exemplo, qualquer domínio de ideais principais). Por exemplo, em teoria de controle pode ser útil considerar a forma normal de Hermite para os polinômios sobre um dado corpo .

Ver também Anel de Hermite Forma normal de Smith Forma normal de Howell Equação diofantina

Referências

Categoria:Álgebra linear Categoria:Formas normais de matrizes