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