SPN graphs: When copositive = SPN

详细信息    查看全文

• 作者：Naomi Shaked-Monderer ^{nomi@tx.technion.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：15B48 ; 15B35
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 November 2016
• 年：2016
• 卷：509
• 期：Complete
• 页码：82-113
• 全文大小：541 K

文摘

A real symmetric matrix A   is copositive if x^TAx≥0${\mathbf{x}}^{T}A\mathbf{x}\ge 0$ for every nonnegative vector x. A matrix is SPN if it is a sum of a real positive semidefinite matrix and a nonnegative one. Every SPN matrix is copositive, but the converse does not hold for matrices of order greater than 4. A graph G is an SPN graph if every copositive matrix whose graph is G is SPN. In this paper we present sufficient conditions for a graph to be SPN (in terms of its possible blocks) and necessary conditions for a graph to be SPN (in terms of forbidden subgraphs). We also discuss the remaining gap between these two sets of conditions, and make a conjecture regarding the complete characterization of SPN graphs.