Nonnegative rank (linear algebra)
# 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:

${\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 $R_j$ ≥ 0 stands for $"R_j$ is nonnegative". (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),$

${\mbox{rank}}\,(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 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.

## 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.

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).

These two results (including the 4×4 matrix example above) were first provided by Thomas in a response to a question posed in 1973 by Berman and Plemmons.

## Computing the nonnegative rank

The nonnegative rank of a matrix can be determined algorithmically.

It has been proved that determining whether ${{\text{rank}}_{+}}(A)={\text{rank}}(A)$ is NP-hard.

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: The minimum number of facets of an extension of a polyhedron P is equal to the nonnegative rank of its so-called slack matrix.

