Matriz equilibrada

En matemáticas , una matriz equilibrada es una matriz binaria (una matriz donde cada elemento es cero o uno) que no contiene ninguna submatriz cuadrada de orden impar cuyas sumas de filas y columnas sean todas iguales a 2.

Las matrices balanceadas se estudian en programación lineal . La importancia de las matrices balanceadas radica en que la solución a un problema de programación lineal es entera si su matriz de coeficientes está balanceada y su lado derecho o su vector objetivo es un vector de unos. ^{[ 1 ] [ 2 ]} En particular, si se busca una solución entera 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 óptima de vértice del propio programa lineal .

Como ejemplo, la siguiente matriz es una matriz balanceada:

${\displaystyle {\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}}$

De forma equivalente a la definición, una matriz 0-1 está equilibrada si y solo si no contiene una submatriz que sea la matriz de incidencia de algún ciclo impar (un grafo de ciclo de orden impar). ^{[ 2 ]}

Por lo tanto, la única matriz binaria de tres por tres que no está balanceada es (salvo permutación de filas y columnas) la siguiente matriz de incidencia de un grafo cíclico de orden 3:

${\displaystyle C_{3}={\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\\\end{bmatrix}}}$

La siguiente matriz es la matriz de incidencia de un grafo cíclico de orden 5:

${\displaystyle C_{5}={\begin{bmatrix}1&0&0&0&1\\1&1&0&0&0\\0&1&1&0&0\\0&0&1&1&0\\0&0&0&1&1\\\end{bmatrix}}}$

La caracterización anterior implica que cualquier matriz que contenga${\displaystyle C_{3}}$o${\displaystyle C_{5}}$(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 binaria (0-1) se denomina totalmente balanceada si no contiene una submatriz cuadrada sin columnas repetidas y con sumas de filas y columnas iguales a 2. De forma equivalente, una matriz es totalmente balanceada si y solo si no contiene una submatriz que sea la matriz de incidencia de ningún ciclo (ya sea de orden par o impar). Esta caracterización implica inmediatamente que cualquier matriz totalmente balanceada es balanceada. ^{[ 3 ]}

Además, cualquier matriz binaria (0-1) totalmente unimodular también es equilibrada. La siguiente matriz es una matriz equilibrada, ya que no contiene ninguna submatriz que sea la matriz de incidencia de un ciclo impar:

${\displaystyle {\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}}$

Dado que esta matriz no es totalmente unimodular (su determinante es -2), las matrices totalmente unimodulares 0-1 son un subconjunto propio de las 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 conteo de subsecuencias, donde el conteo de subsecuencias SC de cualquier fila s de la matriz A es

SC = |{ t | [ a _sj  =  1, a _ij  =  0 para s  < i < t , a _tj = 1], j = 1, ..., n }|         

Si una matriz binaria A 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. Cabe señalar que esta condición es suficiente, pero no necesaria, para que A esté balanceada. En otras palabras, las matrices binarias con SC( s ) ≤ 1 para todas las filas s = 1, ..., m constituyen 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 denomina 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 ]}