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.
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:
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
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.
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
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]
El rango no negativo de una matriz se puede determinar algorítmicamente. [4]
Se ha demostrado que determinar si es NP-difícil. [5]
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 .
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]