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 las filas y todas las 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 se busca una solución integral para un programa lineal de este tipo, no es necesario resolver explícitamente un programa lineal entero , pero basta con encontrar una solución de vértice óptima del propio programa lineal. .
Como ejemplo, la siguiente matriz es una matriz balanceada:
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á balanceada es (hasta la permutación de las filas y columnas) la siguiente matriz de incidencia de un gráfico cíclico 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 equilibradas es la noción de matrices totalmente equilibradas . 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 todas las columnas sean iguales a 2. De manera equivalente, una matriz está totalmente balanceada si y solo si no contiene una submatriz. esa es 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 equilibrada está equilibrada. [3]
Además, cualquier matriz 0-1 que sea totalmente unimodular también está equilibrada. La siguiente matriz es una matriz balanceada 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 0-1 totalmente unimodulares son un subconjunto adecuado de matrices equilibradas. [2]
Por ejemplo, las matrices equilibradas surgen como matriz de coeficientes en casos especiales del problema de partición de conjuntos. [4]
Un método alternativo para identificar algunas matrices equilibradas es mediante el recuento de subsecuencias, donde el recuento de subsecuencias SC de cualquier fila s de la matriz A es
Si una matriz A 0-1 tiene SC( s ) ≤ 1 para todas las filas s = 1, ..., m , entonces A tiene una subsecuencia única, es totalmente unimodular [4] y por lo tanto también está balanceada. Tenga en cuenta que esta condición es suficiente pero no necesaria para que A esté equilibrado. 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 múltiplo de 4. [5]
