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 del rango lineal . Además 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 existe una matriz B no negativa m × q 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 deben ser no negativos.
Además, el rango no negativo es el número más pequeño de matrices de rango uno no negativo en las que la matriz se puede descomponer de forma aditiva:
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).
Dado un no negativo matriz A el rango no negativode A satisface
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 puede escribirse como una combinación lineal de las otras columnas seleccionadas. No es cierto que agregar no negatividad a esta caracterización da 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 mantiene siempre que rango (A) ≤ 2 [2].
Sin embargo, en el caso de rango (A) ≥ 3 , es posible rango (A)
satisface rango (A) = 3 <4 = rango + (A) [2].
Calcular el rango no negativo
El rango no negativo de una matriz se puede determinar algorítmicamente. [2]
Se ha demostrado que determinar si es NP-duro. [3]
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 : [4] 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 de holgura . [5]
Referencias
- ^ Abraham Berman y Robert J. Plemmons . Matrices no negativas en las ciencias matemáticas , SIAM
- ^ J. Cohen y U. Rothblum. "Rangos no negativos, descomposiciones y factorizaciones de matrices no negativas". Álgebra lineal y sus aplicaciones , 190: 149-168, 1993.
- ^ Stephen Vavasis, Sobre la complejidad de la factorización matricial no negativa, SIAM Journal on Optimization 20 (3) 1364-1377, 2009.
- ^ Mihalis Yannakakis. Expresar problemas de optimización combinatoria mediante programas lineales. J. Comput. Syst. Sci., 43 (3): 441–466, 1991.
- ^ Vea esta publicación de blog Archivado el 7 de octubre de 2014 en la Wayback Machine.