MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What's a "doubly non-negative matrix"? – Gerry Myerson Jun 13 '11 at 12:08
"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." – Joseph O'Rourke Jun 13 '11 at 12:20
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$? – Noah Stein Jun 13 '11 at 13:20
@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. – Pawan Aurora Jun 13 '11 at 15:36
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.