PSD matrix with non-negative entries

Question

We have convex sets $C_1=Conv(yy^{T}|y^{T}y=a,y\in R^{M})$ and $C_2=Conv(yy^{T}|y^{T}y=a,y\in R_{\geq 0}^{M})$. Clearly $C_2\subset C_1$. Does there exist a PSD matrix $A$ having $tr(A)=a,A(i,j)\geq 0$ $\forall i,j$ and $A\in C_1\setminus C_2$?

Answer 1

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Hall showed that they do exist for $M\geq 5$ (referenced in Diananda's paper).

EDIT: As Denis Serre shows in the comments, the $M=5$ "counterexample" quoted below from Gray and Wilson is in fact not a counterexample at all!

A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". The idea is to view the matrix $A$ as a Gram matrix. The question is then whether a set of vectors all having nonnegative inner products with each other can be simultaneously rotated into the nonnegative orthant. They give an example family of vectors which cannot, leading to the $M=5$ counterexample \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]

Answer 2

Maxfield and Minc (1962) in their paper entitled On the matrix equation $X'X=A$, quote an example due to Hall (1958), A survey of combinatorial analysis, which shows that for $M\ge 5$ we can find counterexamples of the desired kind. Here is their example:

The matrix $$A = \begin{bmatrix} 1 & 0 & 0 &1/2 & 1/2\\\\ 0 & 1 & 3/4 & 0 & 1/2\\\ 0 & 3/4 & 1 & 1/2 & 0\\\\ 1/2 & 0 & 1/2 & 1 & 0\\\\ 1/2 & 1/2 & 0 & 0 & 1 \end{bmatrix}$$ is positive semidefinite, yet there is no matrix $X$ with nonnegative entries such that $X^TX=A$.

The eigenvalues of the above matrix are approximately (2.12,1.42,1.25,.20,0), where the $0$ is exact as this matrix has rank-4.