Matriz unimodular

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática, uma matriz unimodular M é uma matriz inteira quadrada com determinante +1 ou −1. De forma equivalente, é uma matriz inteira inversível sobre os inteiros, ou seja, existe uma matriz inteira N que é o seu inverso (elas são equivalentes sob a regra de Cramer). Assim, toda equação Mx = b, na qual M e b são ambos inteiros, e M é unimodular, tem uma solução inteira.

Exemplos de matrizes unimodulares[editar | editar código-fonte]

Matrizes unimodulares formam um subgrupo do grupo linear geral sob a multiplicação de matrizes. Portanto, as seguintes matrizes são unimodulares:

Total unimodularidade[editar | editar código-fonte]

Um matriz totalmente unimodular [1] ( matriz TU) é uma matriz na qual toda submatriz quadrada  não-singular (isto é, admite inversa) é unimodular. Uma matriz totalmente unimodular não precisa de ser quadrada. Pela definição temos que qualquer submatriz de uma matriz totalmente unimodular e ela própria também totalmente unimodular.

Devido a essas definições toda matriz TU tem apenas 0, +1 ou −1 entradas (basta lembrar que toda submatriz de tamanho 1x1 tem determinante igual ao próprio elemento). O oposto não é verdadeiro; uma matriz com apenas 0, +1 ou −1 entradas não é, necessariamente, unimodular.

Matrizes totalmente unimodulares são extremamente importantes na otimização combinatória, pois fornecem uma forma rápida de verificar se um programa linear é inteiro (ou seja, se existir, a solução ótima é inteira). Especificamente, se A é TU e b é inteiro, programas lineares da forma ou têm solução ótima inteira, para qualquer c. Assim, se A é totalmente unimodular e b é inteiro, todo ponto extremo da região viável (por exemplo, ) é inteiro e, portanto, a região viável é um poliedro inteiro.

Notas[editar | editar código-fonte]

  1. O termo foi cunhado por Claude Berge, consulte Hoffman, A.J.; Kruskal, J. (2010), «Introduction to Integral Boundary Points of Convex Polyhedra», in: M. Jünger et al. (eds.), 50 Years of Integer Programming, 1958-2008, Springer-Verlag, pp. 49–50 

Referências[editar | editar código-fonte]