Question

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$?

Answer 1

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.