Copositive Matrices with Ordered Off-Diagonal Entries
Grigoriy Blekherman, Santanu S. Dey, Alex Dunbar, Burak Kocuk · 2026
Read Copositive Matrices with Ordered Off-Diagonal Entries by Grigoriy Blekherman, Santanu S. Dey, Alex Dunbar, Burak Kocuk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15970.txt.
Introduction
Grigoriy Blekherman and three colleagues study copositive matrices that split into a positive semidefinite part plus a matrix with nonnegative entries. They prove such a split always exists when off-diagonal entries rise across rows and down columns. Applied to optimizing quadratic forms over the standard simplex, the result makes a natural relaxation exact for separable objectives, settling an open question of Dey and Kocuk.
Catalog record
| CREATOR | Grigoriy Blekherman, Santanu S. Dey, Alex Dunbar, Burak Kocuk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58723 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15970
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Copositive Matrices with Ordered Off-Diagonal Entries Grigoriy Blekherman, Santanu S. Dey, Alex Dunbar, Burak Kocuk Abstract . We study copositive matrices which admit a decomposition into a sum of a positive semidefinite matrix and a matrix with nonnegative entries. Our main result shows that if the off-diagonal entries of a copositive matrix are nondecreasing in rows and in columns, then it admits such a decomposition. We apply this result to study optimization of quadratic forms over the standard simplex. As a corollary, we obtain that a natural relaxation of this problem is tight when the objective function is separable, resolving an open question from [ 12 ] . 2020 Mathematics Subject Classification 90C20, 90C22, 15B48 1. Introduction A symmetric n\times n matrix A is copositive if the quadratic form x^{\top}Ax takes only nonnegative values for x in the nonnegative orthant. The collection of copositive n\times n matrices forms a closed convex cone \mathcal{C}op_{n} inside the space of all n\times n symmetric matrices. There has been recent interest in the cone of copositive matrices, as many optimization problems with quadratic objectives can be reformulated as conic optimization problems over the completely positive cone of matries, which are dual to conic optimization problems over the copositive cone [ 5 , 8 , 11 ] . A classical example is the problem of minimizing a quadratic form over the unit simplex, also called a standard quadratic program [ 7 , 5 , 2 , 3 , 9 , 19 , 4 ] , which has an equivalent copositive conic reformulation. Checking copositivity of a matrix is co-NP-complete [ 17 ] . A more tractable inner approximation of the cone of copositive matrices is the cone of symmetric matrices which are the sum of a positive semidefinite matrix and a matrix with only nonnegative entries. Denoting this cone by \mathcal{SPN}_{n} , it is a foundational result that \mathcal{SPN}_{n}=\mathcal{C}op_{n} if and only if n\leq 4 [ 13 ] . For n\geq 5 , there has been interest in determining conditions on copositive matrices which guarantees an SPN decomposition [ 20 , 15 ] . We have two main goals in this paper. First, we develop new conditions, depending only on the off-diagonal entries of a copositive matrix, which guarantee the existence of an SPN decomposition. Secondly, we study the implications of such results on standard quadratic programming problems, since a natural approximation for a copositive reformulation is to replace the cone \mathcal{C}op_{n} with the cone \mathcal{SPN}_{n} . Towards our first goal, we present a simple criterion which ensures that a copositive matrix admits an SPN decomposition as follows: Theorem 1.1 (Theorem 3.5 below) . If A=(a_{i,j})\in\mathcal{C}op_{n} and the off-diagonal entries of A are nondecreasing in rows and columns, i.e. a_{i,j}\leq a_{\ell,k} when i\neq j,\ell\neq k,i\leq\ell, and j\leq k , then A\in\mathcal{SPN}_{n} . Our proof relies on an inductive argument which applies to a broader class of matrices, described in Theorem 3.1 . Building on this inductive framework, we obtain further generalizations, including Theorem 3.9 , in which the ordering assumptions on the off-diagonal entries are weakened: positive entries are required to be nondecreasing in rows and columns, while nonpositive entries need only satisfy a row-ordering condition determined by the location of the first positive entry in the matrix. As a consequence, we obtain exactness of the SPN relaxation for block-structured matrices in which one block has nonpositive off-diagonal entries, the off-diagonal block is nonpositive with nondecreasing rows, and the remaining block has ordered off-diagonal entries, as well as for matrices whose blocks overlap in a single row and column (Corollary 3.10 and Proposition 3.11 ). The matrices considered in Theorem 1.1 also generate a larger collection of matrices for which copositivity implies the existence of an SPN decomposition, via orbits of a group action. Since copositivity and the existence of an SPN decomposition are both invariant under simultaneous permutation of rows and columns and under rescaling by diagonal matrices with positive diagonal, one can ask when a given symmetric matrix can be brought into the ordered setting by such operations. We show in Propositions 4.7 and 4.8 that determining the existence of such a diagonal rescaling or permutation, respectively, admits polynomial time algorithms. Towards our second goal, Theorem 1.1 provides a new class of matrices for which the SPN relaxation is tight. In particular, we show in Proposition 5.7 that this relaxation is tight for quadratic programs with separable objective functions, answering [ 12 , Conjecture 1] . Additionally, we provide simple proofs of exactness of the relaxation for matrices with minimum entry on the diagonal and matrices which define convex objectives over the simplex, originally proven in [ 15 ] . Our results also admit a natural interpretation in the context of existing exactness results for SPN relaxations. A well-known connection links standard quadratic programming to the maximum weighted clique problem: for certain objective functions, standard quadratic programming and its SPN relaxation agree, computing the size of the maximum weighted clique of a perfect graph [ 14 , 16 , 15 ] . The conditions on such objective functions, which include relations between diagonal and off-diagonal entries of the objective matrix, imply that the sign graphs of optimal solution matrices are perfect graphs, where a sign graph is a graph on \{1,2,\dots,n\} whose edges correspond to entries taking a specified sign. We show in Proposition 6.1 that matrices with ordered off-diagonal entries have sign graphs which are threshold graphs [ 10 ] . A threshold graph is a perfect graph which can be obtained by starting with a single vertex and successively adding vertices which are either connected to every other vertex or which are connected to no other vertex. From this perspective, Theorem 1.1 extends existing exactness results for SPN relaxations by removing some of the hypotheses on the objective function, provided that the associated sign graph of the optimal solution is threshold. The remainder of the paper is organized as follows. Section 2 fixes notation and provides background results on copositive and SPN matrices. In Section 3 , we develop results about classes of matrices for which copositivity implies the existence of an SPN decomposition. Section 4 discusses matrices which are in the orbit of the set of matrices with ordered off-diagonal entries. In Section 5 , we apply the results about copositive matrices to certify the tightness of SPN relaxations of standard quadratic programming problems. Finally, in Section 6 , we discuss the sign pattern graphs of matrices which are in the orbit of the ordered off-diagonal matrices. 2. Notation and Background In this section, we fix the notation and provide background results on copositive and SPN matrices. 2.1. Notation We denote by \mathcal{S}^{n} the set of n\times n symmetric matrices with real entries. Let \mathcal{C}op_{n}\subseteq\mathcal{S}^{n} denote the cone of n\times n copositive matrices and \mathcal{SPN}_{n}\subseteq\mathcal{S}^{n} denote the cone of n\times n matrices which are the sum of a positive semidefinite matrix and an entrywise nonnegative matrix. If A\in\mathcal{SPN}_{n} for some n , then we say A is SPN or A admits an SPN decomposition. If A\in\mathcal{S}^{n} is an n\times n symmetric matrix, we let A(i) be the (n-1)\times(n-1) submatrix obtained by deleting row i and column i . For a