I have asked this question in math.se without any success.

Let $\mathbf{A}$ be a symmetric $n\times n$ positive semi-definite matrix and also such that each of its entries is positive. Does $\mathbf{A}$ have a decomposition of the form \begin{align} \mathbf{A} \,=\,\sum_{i=1}^{k}\mathbf{y}_i\mathbf{y}_i^T \end{align} where each vector $\mathbf{y}$ is also entry-wise positive and $k\leq n$.


2 Answers 2


No, there exist doubly nonnegative matrices which are not completely positive, see for example The difference between 5 x 5 doubly nonnegative and completely positive matrices (2009).

A graph-based characterization of doubly nonnegative matrices which are completely positive is: Every doubly nonnegative matrix realization of a graph $G$ is completely positive if and only if $G$ does not contain an odd cycle of length at least 5, see Open problems in the theory of completely positive and copositive matrices (2015).

An alternative characterization is give in a 2011 MO question: A doubly nonnegative $n\times n$ 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 $>n$.


Not necessarily.

If this would hold, all components of the $y_i$ would be bounded in terms of $A$; so, by compactness argument, the same would hold for matrices and columns with non-negative entries. We will show that this is not the case.

Let $I$ and $J$ be the identty and the all-ones matrices of order $3\times3$. Set $$ A=\left[\matrix{ 100I&J\\J&100I}\right]. $$ Then each $y_i$ may contain at most one non-zero among the first three entries, the same for the last three. On the other hand, for each $a=1,2,3$ and $b=4,5,6$ there should be a $y_i$ with non-zero $a$th and $b$th entries. Thus $k\geq9$.

Remark. This argument shows that, in general, $k\geq [n^2/4]$. It cannot show more, since the edges of an arbitrary graph on $n$ vertices may be split into at most $n^2/4$ cliques. It may happen that this estimate is sharp.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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