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

I want to check under what conditions a matrix of the form $\alpha J -Q$ is copositive, where $J$ is the all-ones matrix and $Q$ is doubly nonegative (i.e. entrywise nonnegative and positive semidefinite). Talking about theory here, not an algorithm. I scanned the literature but didn't find anything to build on. Do you have suggestions?

share|improve this question
3  
I believe the answer is that this is true if and only if $\alpha$ is at least the largest diagonal entry of $Q$, and this holds just under the assumption that $Q$ is nonnegative definite. This follows from the following two facts: (i) a matrix $A$ is copositive if and only if $x^T A x \geq 0$ for all $x$ in the simplex $S_n$. (ii) if $Q$ is nonnegative definite, then $x^T Q X$ is convex and $\max_{x \in S_n} x^T Q x$ is achieved at the extreme points $e_i$ of the simplex. –  alex o. May 4 '12 at 5:55
    
Alex, thanks for the answer! Can you give a reference for fact (ii) - it seems true to me but I can't nail it? Thanks again! –  Felix Goldberg May 4 '12 at 9:14
    
I've now proved Alex's statement to myself, deriving it from the general Motzkin-Straus theorem. But would still love to get a textbook reference. Thanks once again, Alex. –  Felix Goldberg May 4 '12 at 10:15
1  
Felix, if $Q$ is nonnegative definite, then it has a symmetric square root $L$ and $x^T Q x = ||Lx||_2^2$, so $x^T Q x$ is the composition of a linear function ($x \rightarrow Lx$) and a convex function ($x \rightarrow ||x||_2^2$). Consequently, it is convex. Next, for every convex function $f$, we have that by definition of convexity, $f(\sum_i \alpha_i x_i) \leq \sum_i \alpha_i f(x_i) \leq \max_i f(x_i)$, where $\alpha_i$ are nonnegative and add up to $1$. Finally, every point in the simplex is a convex combination of the vectors $e_i$. –  alex o. May 4 '12 at 18:56
    
Thanks, this is a nice argument. –  Felix Goldberg May 6 '12 at 23:29

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.