Matriz unimodular
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:
- Matriz de identidade
- A inversa de uma matriz unimodular
- O produto de duas matrizes 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 é 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]
- ↑ 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]
- Wolsey, L.A. (1998), Integer Programming. Wiley Series in Discrete Mathematics and Optimization, ISBN 9780471283669
- Weisstein, Eric W. Unimodular Matrix. De mathworld.wolfram.com (em inglês).