# 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 Rj ≥ 0 stands for "Rj is nonnegative".[1] (To obtain the usual linear rank, drop the condition that the Rj 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