# 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 given 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 is the smallest number of nonnegative rank-one matrices into which the matrix can be decomposed additively:

${\displaystyle {\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}\geq 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 ${\displaystyle m\times n}$ matrix A the nonnegative rank ${\displaystyle rank_{+}(A)}$ of A satisfies

${\displaystyle {\mbox{rank}}\,(A)\leq {\mbox{rank}}_{+}(A)\leq \min(m,n),}$ where ${\displaystyle 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

${\displaystyle \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 ${\displaystyle {{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