Matriz unimodular
# 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

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

Um matriz totalmente unimodular ( 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.