Nonnegative rank (linear algebra)

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. For the nonnegative rank, it is required that the vectors must have nonnegative entries, and also that the coefficients in the linear combinations are nonnegative.

Formal Definition

There are several equivalent definitions, all modifying the definition of the linear rank slightly. Apart from the definition give above, there is the following: The nonnegative rank of a nonnegative m×n-matrix A is equal to the smallest number q such there exists a nonnegative m×q-matrix B and a nonnegative q×n-matrix C such that A = BC (the usual matrix product). To obtain the linear rank, drop the condition that B and C must be nonnegative.

Further, the nonnegative rank it the smallest number of nonnegative rank-one matrices into which the matrix can be decomposed additively:

$\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 \ge 0\},$ where R_j ≥ 0 stands for "R_j is nonnegative".^[1] (To obtain the usual linear rank, drop the condition that the R_j have to be nonnegative.) Given a nonnegative $m \times n$ matrix A the nonnegative rank rank ₊ (A) of A satisfies

$\mbox{rank}\,(A) \leq \mbox{rank}_+(A) \leq \min(m,n),$ where rank(A) denotes the usual linear rank of A.

A Fallacy

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 strictly greater than the largest number of columns such that no selected column can be written as a nonnegative linear combination of the other selected columns.

Connection with the linear rank

It is always true that rank(A) ≤ rank₊(A). In fact rank₊(A) = rank(A) holds whenever rank(A) ≤ 2 [2].

In the case rank(A) ≥ 3, however, rank(A) < rank₊(A) is possible. For example, the matrix

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

satisfies rank(A) = 3 < 4 = rank₊(A) [2].

Computing the nonnegative rank

The nonnegative rank of a matrix can be determined algorithmically.^[2]

It has been proved that determining whether rank ₊ (A) = rank(A) is NP-hard.^[3]

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.

Ancillary Facts

Nonnegative rank has important applications in Combinatorial optimization:^[4] The minimum number of facets of an extension of a polyhedron P is equal to the nonnegative rank of its so-called slack matrix.^[5]

References

1. ^ Abraham Berman and Robert J. Plemmons. Nonnegative Matrices in the Mathematical Sciences, SIAM
2. ^ J. Cohen and U. Rothblum. "Nonnegative ranks, decompositions and factorizations of nonnegative matrices". Linear Algebra and its Applications, 190:149–168, 1993.
3. ^ Stephen Vavasis, On the complexity of nonnegative matrix factorization, SIAM Journal on Optimization 20 (3) 1364-1377, 2009.
4. ^ Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci., 43(3):441–466, 1991.
5. ^ See this blog post