Matriz unimodular

En matemáticas , una matriz unimodular M es una matriz de enteros cuadrados que tiene un determinante +1 o −1. De manera equivalente, es una matriz de enteros que es invertible sobre los enteros : hay una matriz de enteros N que es su inversa (estos son equivalentes bajo la regla de Cramer ). Por lo tanto, cada ecuación Mx = b , donde M y b tienen componentes enteros y M es unimodular, tiene una solución entera. Las matrices unimodulares n × n forman ungrupo llamado el grupo lineal general n × n sobre , que se denota . ${\ estilo de visualización \ mathbb {Z}}$ ${\ estilo de visualización \ nombre del operador {GL} _ {n} (\ mathbb {Z})}$

Las matrices unimodulares forman un subgrupo del grupo lineal general bajo la multiplicación de matrices , es decir, las siguientes matrices son unimodulares:

Una matriz totalmente unimodular ^[1] (matriz TU) es una matriz para la cual toda submatriz cuadrada no singular es unimodular. De manera equivalente, cada submatriz cuadrada tiene un determinante 0, +1 o −1. No es necesario que una matriz totalmente unimodular sea cuadrada. De la definición se sigue que cualquier submatriz de una matriz totalmente unimodular es ella misma totalmente unimodular (TU). Además, se deduce que cualquier matriz TU tiene solo 0, +1 o −1 entradas. Lo contrario no es cierto, es decir, una matriz con solo 0, +1 o −1 entradas no es necesariamente unimodular. Una matriz es TU si y solo si su traspuesta es TU.

Las matrices totalmente unimodulares son extremadamente importantes en la combinatoria poliédrica y la optimización combinatoria , ya que brindan una forma rápida de verificar que un programa lineal es integral (tiene un óptimo integral, cuando existe algún óptimo). Específicamente, si A es TU y b es integral, entonces los programas lineales de formas como o tienen óptimos integrales, para cualquier c . Por lo tanto, si A es totalmente unimodular yb es integral, cada punto extremo de la región factible (por ejemplo, ) es integral y, por lo tanto, la región factible es un poliedro integral . $\{\min cx\mid Ax\geq b,x\geq 0\}$ $\{\max cx\mid Ax\leq b\}$ $\{x\mid Ax\geq b\}$

1. La matriz de incidencia no orientada de un gráfico bipartito , que es la matriz de coeficientes para el emparejamiento bipartito , es totalmente unimodular (TU). (La matriz de incidencia no orientada de un gráfico no bipartito no es TU.) Más generalmente, en el apéndice de un artículo de Heller y Tompkins, ^[2] AJ Hoffman y D. Gale prueban lo siguiente. Sea una matriz de m por n cuyas filas se pueden dividir en dos conjuntos disjuntos y . Entonces las siguientes cuatro condiciones juntas son suficientes para que A sea totalmente unimodular: ${\ estilo de visualización A}$ ${\ estilo de visualización B}$ ${\ estilo de visualización C}$

Más tarde se comprendió que estas condiciones definen una matriz de incidencia de un grafo balanceado con signo ; así, este ejemplo dice que la matriz de incidencia de un grafo con signo es totalmente unimodular si el grafo con signo está balanceado. Lo contrario es válido para gráficos con signo sin medios bordes (esto generaliza la propiedad de la matriz de incidencia no orientada de un gráfico). ^[3]