# Rank-one positive decomposition for a entry-wise positive positive definite matrix

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

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.