In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, the nonnegative rank of a
nonnegative matrix
In mathematics, a nonnegative matrix, written
: \mathbf \geq 0,
is a matrix in which all the elements are equal to or greater than zero, that is,
: x_ \geq 0\qquad \forall .
A positive matrix is a matrix in which all the elements are strictly gre ...
is a concept similar to the usual linear
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
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
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
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
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
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:
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
matrix ''A'' the nonnegative rank
of ''A'' satisfies
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
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
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
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
: The minimum number of
facet
Facets () are flat faces on geometric shapes. The organization of naturally occurring facets was key to early developments in crystallography, since they reflect the underlying symmetry of the crystal structure. Gemstones commonly have facets cut ...
s of an
extension of a polyhedron In convex geometry and polyhedral combinatorics, the extension complexity is a convex polytope P is the smallest number of facets among convex polytopes Q that have P as a projection. In this context, Q is called an extended formulation of P; it m ...
''P'' is equal to the nonnegative rank of its so-called ''slack matrix''.
[See thi]
blog post
References
{{DEFAULTSORT:Nonnegative Rank (Linear Algebra)
Linear algebra