En matemáticas , una matriz balanceada es una matriz 0-1 (una matriz donde cada entrada es cero o uno) que no contiene ninguna submatriz cuadrada de orden impar que tenga todas las sumas de filas y todas las sumas de columnas iguales a 2.
Las matrices balanceadas se estudian en programación lineal . La importancia de las matrices balanceadas proviene del hecho de que la solución a un problema de programación lineal es integral si su matriz de coeficientes está balanceada y su lado derecho o su vector objetivo es un vector todo-uno. [1] [2] En particular, si uno busca una solución integral a un programa lineal de este tipo, no es necesario resolver explícitamente un programa lineal entero , sino que basta con encontrar una solución de vértice óptima del propio programa lineal .
A modo de ejemplo, la siguiente matriz es una matriz equilibrada:
Equivalente a la definición, una matriz 0-1 está equilibrada si y sólo si no contiene una submatriz que sea la matriz de incidencia de cualquier ciclo impar (un gráfico de ciclo de orden impar). [2]
Por lo tanto, la única matriz 0-1 de tres por tres que no está equilibrada es (hasta permutación de filas y columnas) la siguiente matriz de incidencia de un gráfico de ciclo de orden 3:
La siguiente matriz es la matriz de incidencia de un gráfico de ciclo de orden 5:
La caracterización anterior implica que cualquier matriz que contenga o (o la matriz de incidencia de cualquier otro ciclo impar) como submatriz, no está equilibrada.
Toda matriz equilibrada es una matriz perfecta .
Más restrictiva que la noción de matrices balanceadas es la noción de matrices totalmente balanceadas . Una matriz 0-1 se llama totalmente balanceada si no contiene una submatriz cuadrada que no tenga columnas repetidas y todas las sumas de filas y columnas sean iguales a 2. De manera equivalente, una matriz está totalmente balanceada si y solo si no contiene una submatriz que sea la matriz de incidencia de cualquier ciclo (no importa si es de orden par o impar). Esta caracterización implica inmediatamente que cualquier matriz totalmente balanceada está balanceada. [3]
Además, cualquier matriz 0-1 que sea totalmente unimodular también está equilibrada. La siguiente matriz es una matriz equilibrada, ya que no contiene ninguna submatriz que sea la matriz de incidencia de un ciclo impar:
Dado que esta matriz no es totalmente unimodular (su determinante es -2), las matrices totalmente unimodulares 0-1 son un subconjunto propio de matrices balanceadas. [2]
Por ejemplo, las matrices balanceadas surgen como la matriz de coeficientes en casos especiales del problema de partición de conjuntos. [4]
Un método alternativo para identificar algunas matrices balanceadas es a través del recuento de subsecuencias, donde el recuento de subsecuencias SC de cualquier fila s de la matriz A es
Si una matriz 0-1 A tiene SC( s ) ≤ 1 para todas las filas s = 1, ..., m , entonces A tiene una subsucesión única, es totalmente unimodular [4] y, por lo tanto, también está balanceada. Nótese que esta condición es suficiente pero no necesaria para que A esté balanceada. En otras palabras, las matrices 0-1 con SC( s ) ≤ 1 para todas las filas s = 1, ..., m son un subconjunto propio del conjunto de matrices balanceadas.
Como noción más general, una matriz donde cada entrada es 0, 1 o -1 se llama equilibrada si en cada submatriz con dos entradas distintas de cero por fila y columna, la suma de las entradas es un múltiplo de 4. [5]
