Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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}. \]

share|improve this answer
    
actually, some literature search reveals that the claim for $M \le 4$ is due to Maxfield and Minc in a 1962 paper; correct me if i'm wrong. –  Suvrit Jun 8 '11 at 21:55
    
@Suvrit: Interesting. I don't think I had seen that paper before, though I don't consider myself terribly familiar with the history of this area. Diananda's result is essentially the dual of the result requested here. It looks like Maxfield and Minc may have been first to put it in this form. –  Noah Stein Jun 8 '11 at 22:42
    
Good. The example is accurate in the sense that it is not positive definite. –  Denis Serre Jun 9 '11 at 6:58
    
Now I have a doubt about the 'counter-example': This matrix writes as $$\begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\\\ 0 & 1 & 0 & 0 & 1 \\\\ 0 & 0 & 8/9 & 0 & 8 \\\\ 0 & 0 & 0 & 0 & 0 \\\\ 1 & 1 & 8 & 0 & 74 \end{pmatrix}+\begin{pmatrix} 1 & 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 &1 & 0 \\\\ 0 & 0 & 1/9 & 1 & 0 \\\\ 1 & 1 & 1 & 11 & 0 \\\\ 0 & 0 & 0 & 0 & 0 \end{pmatrix},$$ where both matrices are non-negative. Since the answer to the question is positive for $n=4$, and these matrices are block-diagonal, $A$ can be written in the requested form. –  Denis Serre Jun 9 '11 at 9:33
    
@Denis Serre: Thanks for the counter-counterexample! I had been a bit suspicious of the method used to construct it, as it seemed to assume that the CP-rank of a matrix is equal to the rank, or something like that. Hopefully the original example due to Hall quoted by Suvrit is correct. –  Noah Stein Jun 9 '11 at 12:59

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.

share|improve this answer
    
@Suvrit. That $A$ is not $X^TX$ for an $X$ with non-negative entries does not make a counter-example. –  Denis Serre Jun 9 '11 at 15:30
    
Nevertheless, I made calculations which convince me that this matrix is a counter-example. –  Denis Serre Jun 9 '11 at 16:18
    
Does this example in some way generalize to $M>5$? –  Pawan Aurora Jun 9 '11 at 16:59
    
@Denis: thanks for your comments; I will think about this a bit more when I get a chance. @Pawan: I guess so; perhaps merely embedding this 5 x 5 matrix as a principal submatrix of a larger matrix should do the trick---not sure. –  Suvrit Jun 9 '11 at 17:44
    
The fact that the above matrix is not Completely Positive tells us that for any $M>5$, we cannot find five vectors in the non-negative orthant of $R^{M}$ that have their mutual dot products given by the Gram matrix $A$ above. So for $M>5$ there obviously exist counter examples. –  Pawan Aurora Jun 15 '11 at 6:24

Your Answer

 
discard

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.