Matriz unimodular

En matemáticas, una matriz unimodular es una matriz cuadrada de enteros con determinante +1 ó -1.

Una matriz es totalmente unimodular, TUM , si cada submatriz cuadrada no singular (inversible) B es también unimodular. Como consecuencia, una matriz totalmente unimodular está formada sólo por los elementos -1, 0 y +1.

Ejemplo

La siguiente matriz es totalmente unimodular (TUM):

Esta matriz surge como la matriz restrictiva de la formulación del problema lineal (sin la restricción ) del problema del flujo máximo en la siguiente red:


Esta matriz tiene las siguientes propiedades:

  • todos sus elementos ;
  • cualquier columna tiene como máximo dos elementos distintos de cero;
  • las columnas con dos elementos distintos de cero tienen elementos de distinto signo.

Estas propiedades son suficientes para que la matriz sea totalmente unimodular (TUM) (pero no son necesarias). Cualquier problema de red de flujo produciría una matriz restrictiva con la susodicha estructura (por esto es que cualquier problema de redes de flujo con capacidades acotadas enteras tiene un valor óptimo entero).

Other Languages