Consider a doubly nonnegative matrix $A$ of order $n$. $A$ is completely positive if and only if $A$ can be factorized into $BB^{T}$ where all entries in $B$ are nonnegative. $B$ is $n\times k$. The smallest possible value of $k$ is the cprank of $A$. If $r$ is the rank of $A$ then $k\geq r$. Consider such a factorization of $A$ where $k>r$. Now viewing $A$ as a gram matrix, each row of $B$ is a $k$dimensional vector and so we have a set of $n$ vectors in the nonnegative orthant of $R^k$ where $k>n$ (assuming $A$ is full rank). An alternative way of looking at gram matrix $A$ is in terms of the $n$ vectors in $R^r$. These vectors need not lie in the nonnegative orthant of $R^r$ though they are within $90^{\circ}$ of each other. So can we say that a doubly nonnegative matrix is completely positive if and only if the $n$ vectors making up the gram matrix lie in the nonnegative orthant of some space of dimension $\geq r$, even $>n$?

$\begingroup$ What's a "doubly nonnegative matrix"? $\endgroup$ – Gerry Myerson Jun 13 '11 at 12:08

$\begingroup$ "A doubly nonnegative matrix is a real positive semidefinite $n \times n$ square matrix with nonnegative entries," and "A positive semidefinite matrix is a Hermitian matrix all of whose eigenvalues are nonnegative." mathworld.wolfram.com/DoublyNonnegativeMatrix.html $\endgroup$ – Joseph O'Rourke Jun 13 '11 at 12:20

$\begingroup$ Could you explain the sentence "Since the rank of $A$ is less than $k$, the gram matrix $A$ is made up of all possible inner products among $n$ vectors in $R^r$"? I thought those vectors were in $R^k$, $k>r$? $\endgroup$ – Noah Stein Jun 13 '11 at 13:20

$\begingroup$ @Noah Stein, I meant to say that there is an alternative way of looking at the gram matrix $A$. If the rank of $A$ is $r$, then the vectors lie in a $r$dimensional space. So I guess my main question is that these vectors may not lie in the nonnegative orthant of $R^{r}$ but that alone does not rule out the possibility of $A$ being completely positive. $\endgroup$ – Pawan Aurora Jun 13 '11 at 15:36
If I understand correctly, the anser is yes. A completely positive $n\times n$ matrix can always be viewed as the gram matrix of some vectors in the nonnegative orthant of some $R^k$ and vice versa. The smallest such $k$ is another way of defining the cprank.
The existence of an $n\times n$ matrix $A$ whose cprank strictly exceeds $n$ means that in general to view $A$ as the gram matrix of nonnegative vectors we may need to consider these vectors in a space of dimension $>n$. Of course, we may always view $A$ as a gram matrix of vectors in $R^n$. However, there may be no way to simultaneously rotate these all into the nonnegative orthant, even though there would be a way if we looked at $A$ as a gram matrix of vectors in a higherdimensional space.
Caratheodory's theorem gives an easy quadratic upper bound on the cprank in terms of $n$. There is a tight quadratic bound on the cprank in terms of the rank in a paper of Barioli and Berman, but I am not familiar with the details.