Consider a matrix $A\in{\bf M}\_{n\times m}({\mathbb R})$, whose entries are non-negative. Let $r$ be the rank of $A$.


It is well-known that $A$ decomposes as $x\_1y\_1^T+\cdots+x\_ry\_r^T$ with $x\_j\in{\mathbb R}^n$ and $y\_i\in{\mathbb R}^m$. But is this still true if we require in addition that $x\_1,\ldots,y\_r$ be non-negative ?


If not, what is the minimal number $s$ of terms in such a non-negative decomposition $x\_1y\_1^T+\cdots+x\_sy\_s^T$ ? By *minimal*, I mean that for every non-negative $n\times m$ matrix $A$ of rank $r$, a non-negative decomposition exists with $s$ terms.


Of course $s\le\min(n,m)$ works because either a row or a column is of the form $xy^T$. If $r=1$, then $s=1$ works (obvious); that is, the answer to the first question is positive.



Non-negative decomposition of a non-negative matrix
This seems to be the well-known (and difficult) task of computing [the nonnegative rank of a matrix.](http://en.wikipedia.org/wiki/Nonnegative_rank_%28linear_algebra%29)


It seems that the true complexity of computing the nn-rank is unknown, while verifying whether nn-rank equals actual rank is NP-Hard (the Wikipedia page comments on this).


