Rango no negativo (álgebra lineal)

En álgebra lineal , el rango no negativo de una matriz no negativa es un concepto similar al rango lineal habitual de una matriz real, pero agregando el requisito de que ciertos coeficientes y entradas de vectores/matrices deben ser no negativos.

Por ejemplo, el rango lineal de una matriz es el número más pequeño de vectores, de modo que cada columna de la matriz se puede escribir como una combinación lineal de esos vectores. Para el rango no negativo, se requiere que los vectores tengan entradas no negativas y también que los coeficientes en las combinaciones lineales no sean negativos.

Definicion formal

Hay varias definiciones equivalentes, todas modificando ligeramente la definición de rango lineal . Aparte de la definición dada anteriormente, existe lo siguiente: El rango no negativo de una matriz A m×n no negativa es igual al número más pequeño q tal que exista una matriz B m×q no negativa y una matriz q×n no negativa C tal que A = BC (el producto matricial habitual). Para obtener el rango lineal, elimine la condición de que B y C no deben ser negativos.

Además, el rango no negativo es el número más pequeño de matrices de rango uno no negativos en las que la matriz se puede descomponer de forma aditiva:

${\displaystyle {\mbox{rank}}_{+}(A)=\min\{q\mid \sum _{j=1}^{q}R_{j}=A,\;{\mbox{rank}}\,R_{1}=\dots ={\mbox{rank}}\,R_{q}=1,\;R_{1},\dots ,R_{q}\geq 0\},}$

donde R _j ≥ 0 significa " R _j no es negativo". ^[1] (Para obtener el rango lineal habitual, elimine la condición de que R _j debe ser no negativo).

Dada una matriz A no negativa, el rango no negativo de A satisface ${\displaystyle m\times n}$ ${\displaystyle rank_{+}(A)}$

${\displaystyle {\mbox{rank}}\,(A)\leq {\mbox{rank}}_{+}(A)\leq \min(m,n),}$ donde denota el rango lineal habitual de A . ${\displaystyle {\mbox{rank}}\,(A)}$

Una falacia

El rango de la matriz A es el mayor número de columnas que son linealmente independientes, es decir, ninguna de las columnas seleccionadas se puede escribir como una combinación lineal de las otras columnas seleccionadas. No es cierto que agregar no negatividad a esta caracterización dé el rango no negativo: el rango no negativo es en general menor o igual al mayor número de columnas, de modo que ninguna columna seleccionada puede escribirse como una combinación lineal no negativa de las otras columnas seleccionadas.

Conexión con el rango lineal.

Siempre es cierto que rango(A) ≤ rango ₊ (A) . De hecho, rango ₊ (A) = rango(A) se cumple siempre que rango(A) ≤ 2 .

Sin embargo, en el caso de rango(A) ≥ 3 , rango(A) < rango ₊ (A) es posible. Por ejemplo, la matriz

${\displaystyle \mathbf {A} ={\begin{bmatrix}1&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&1\end{bmatrix}},}$

satisface rango(A) = 3 < 4 = rango ₊ (A) .

Estos dos resultados (incluido el ejemplo de matriz 4×4 anterior) fueron proporcionados por primera vez por Thomas en una respuesta ^[2] a una pregunta planteada en 1973 por Berman y Plemmons. ^[3]

Calcular el rango no negativo

El rango no negativo de una matriz se puede determinar algorítmicamente. ^[4]

Se ha demostrado que determinar si es NP-difícil. ^[5] ${\displaystyle {{\text{rank}}_{+}}(A)={\text{rank}}(A)}$

Las preguntas obvias sobre la complejidad del cálculo de rangos no negativos siguen sin respuesta hasta la fecha. Por ejemplo, se desconoce la complejidad de determinar el rango no negativo de matrices de rango fijo k para k > 2 .

Hechos auxiliares

El rango no negativo tiene aplicaciones importantes en la optimización combinatoria : ^[6] El número mínimo de facetas de una extensión de un poliedro P es igual al rango no negativo de su llamada matriz floja . ^[7]

Referencias

1. Abraham Berman y Robert J. Plemmons . Matrices No Negativas en las Ciencias Matemáticas , SIAM
2. LB Thomas. "Solución al problema 73-14, factorización de rangos de matrices no negativas", SIAM Review 16(3), 393-394, 1974
3. Berman, A., Plemmons, RJ: "Factorización de rangos de matrices no negativas", SIAM Review 15(3), 655, 1973
4. J. Cohen y U. Rothblum. "Rangos no negativos, descomposiciones y factorizaciones de matrices no negativas". Álgebra lineal y sus aplicaciones , 190:149–168, 1993.
5. Stephen Vavasis, Sobre la complejidad de la factorización matricial no negativa, SIAM Journal on Optimization 20 (3) 1364-1377, 2009.
6. Mihalis Yannakakis. Expresar problemas de optimización combinatoria mediante programas lineales. J. Computación. Sistema. Ciencia, 43(3):441–466, 1991.
7. Consulte esta publicación de blog Archivada el 7 de octubre de 2014 en Wayback Machine.