Consider a doubly non-negative 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 non-negative. $B$ is $n\times k$. The smallest possible value of $k$ is the cp-rank 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 non-negative 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 non-negative orthant of $R^r$ though they are within $90^{\circ}$ of each other. So can we say that a doubly non-negative matrix is completely positive if and only if the $n$ vectors making up the gram matrix lie in the non-negative orthant of some space of dimension $\geq r$, even $>n$?
-
$\begingroup$ What's a "doubly non-negative matrix"? $\endgroup$– Gerry MyersonCommented Jun 13, 2011 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'RourkeCommented Jun 13, 2011 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 SteinCommented Jun 13, 2011 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 non-negative orthant of $R^{r}$ but that alone does not rule out the possibility of $A$ being completely positive. $\endgroup$– Pawan AuroraCommented Jun 13, 2011 at 15:36
1 Answer
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 cp-rank.
The existence of an $n\times n$ matrix $A$ whose cp-rank 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 higher-dimensional space.
Caratheodory's theorem gives an easy quadratic upper bound on the cp-rank in terms of $n$. There is a tight quadratic bound on the cp-rank in terms of the rank in a paper of Barioli and Berman, but I am not familiar with the details.
