In linear algebra, the nonnegative rank of a nonnegative matrix is a concept similar to the usual linear rank of a real matrix, but adding the requirement that certain coefficients and entries of vectors/matrices have to be nonnegative.
For example, the linear rank of a matrix is the smallest number of vectors, such that every column of the matrix can be written as a linear combination of those vectors.
To obtain the linear rank, drop the condition that B and C must be nonnegative.
Further, the nonnegative rank is the smallest number of nonnegative rank-one matrices into which the matrix can be decomposed additively: where Rj ≥ 0 stands for "Rj is nonnegative".
[1] (To obtain the usual linear rank, drop the condition that the Rj have to be nonnegative.)
of A satisfies The rank of the matrix A is the largest number of columns which are linearly independent, i.e., none of the selected columns can be written as a linear combination of the other selected columns.
It is not true that adding nonnegativity to this characterization gives the nonnegative rank: The nonnegative rank is in general less than or equal to the largest number of columns such that no selected column can be written as a nonnegative linear combination of the other selected columns.
These two results (including the 4×4 matrix example above) were first provided by Thomas in a response[2] to a question posed in 1973 by Berman and Plemmons.
[3] The nonnegative rank of a matrix can be determined algorithmically.
[5] Obvious questions concerning the complexity of nonnegative rank computation remain unanswered to date.
For example, the complexity of determining the nonnegative rank of matrices of fixed rank k is unknown for k > 2.
Nonnegative rank has important applications in Combinatorial optimization:[6] The minimum number of facets of an extension of a polyhedron P is equal to the nonnegative rank of its so-called slack matrix.