This page is in support of an article I wrote showing that the triangle graph T_6 is not SPN.
A real symmetric matrix A is said to be copositive (COP) if x'Ax \geq 0 for every nonnegative vector x. It is said to be SPN if it can be expressed as a sum of a real positive semidefinite matrix and a nonnegative matrix. It is immediate that every SPN matrix is COP. Diananda [2] showed that every COP matrix of order less than or equal to 4 is SPN. A more comprehensive discussion of this situation is given in [7].
For matrices of order 5 and more, not every COP matrix is SPN. The question then becomes to understand which non-zero patterns allow one to deduce SPN from COP. This is done in terms of a graph G, the matrix under consideration only being allowed to have non-zero entries on the diagonal and where the adjacency matrix of G is non-zero. A graph G is said to be SPN if this additional restriction forces a COP matrix to be SPN.
In [8] Shaked-Monderer gives a comprehensive and fascinating discussion of this topic. Unfortunately the article contains an unfortunate error see [9]. In a further paper [6] further progress is made and a number of conjectures are made. In particular, it is conjectured that the triangle graph T_n is SPN for all n \geq 5. The graph T_n has vertices 1 and 2 joined by an edge and further vertices 3,4,\ldots,n each joined only to the vertices 1 and 2.
The object of the article was to show that T_6 is not an SPN graph and one may conclude that T_n is also not an SPN graph for n \geq 6. It is known that T_5 is an SPN graph [9].
For a real symmetric n \times n matrix A, one may define
{\rm copv}(A) = \inf \{x'Ax, x\in {\rm R}_+^{n}, \|x||\leq 1\}
where \|x\| denotes the euclidean norm of the vector x. One may also define
| \displaystyle{{\rm spnv}(A) = \sup \{\lambda_{\rm min} (A-N), N {\rm\ a\ nonnegative\ matrix}\}. } | (1) |
Here, we have denoted \lambda_{\rm min}(X) the smallest eigenvalue of a real symmetric matrix X. Clearly {\rm spnv}(A) \leq {\rm copv}(A), A is COP if and only if {\rm copv}(A) \geq 0 and A is SPN if and only if {\rm spnv}(A) \geq 0.
The quantity {\rm spnv}(A) can be computed for real symmetric matrices A with constant diagonal (i.e. all diagonal entries equal) using semidefinite programming. To see this first observe that the definition of {\rm spnv}(A) is unchanged if we restrict N to be a nonnegative matrix with zero diagonal in (1). Then we will have
| \displaystyle{{\rm spnv}(A) = \sup\{t; A - N - X -tI=0, N {\rm\ nonnegative\ with\ zero\ diagonal}, X {\rm psd.}\} } | (2) |
But in (2) X is forced to have a constant diagonal. Therefore
{\rm spnv}(A) = \sup\{-x_{1,1}; X {\rm\ psd.\ with\ constant\ diagonal}, X \leq A {\rm\ off\ diagonal}\}
Thus the computation of {\rm spnv}(A) becomes a semidefinite programming problem over n \times n real psd. matrices X with objective function X \mapsto -x_{1,1}, linear constraints x_{1,1}-x_{j,j} = 0 for j=2,\ldots,n and linear inequalities x_{j,k} \leq a_{j,k} for 1 \leq j < k \leq n. There are well established software packages CSDP [1] and SDPA [10] for such computations.
The computation of {\rm copv}(A) is more difficult. We suggest two methods.
- The first is the method of surface subcubes used in the Matsaev Conjecture counterexample [3]. It is based on an idea of J.J. Green [4]. The method can be adapted to determine {\rm copv}(A) to any required degree of accuracy. There are some difficulties to be overcome since the feasible set for the problem has a nonempty boundary. Since we didn't use this method in simulations, we won't go into details.
- The second way of estimating {\rm copv}(A) depends on the following well known lemma [2, Lemma 7].
Lemma
Suppose that the matrix A with {\rm copv}(A)=0and x\geq 0 a vector such that x'Ax=0. Then Ax vanishes on {\rm supp}(x).
Let x be a nonnegative unit vector such that x'(A - {\rm copv}(A) I)x=0. Let S be the support of x. Then by the lemma (A - {\rm copv}(A) I)_{[S]} x_{[S]} = 0. Thus ({\rm copv},x_{[S]}) is an eigenvalue eigenvector pair for A_{[S]}. We investigate all possible eigenvalue eigenvector pairs as S runs over all nonempty subsets of \{1,\ldots,n\}. If the eigenvector has entries of both signs then it cannot be \pm x_{[S]}. It therefore suffices to take the minimum value of the remaining eigenvalues. Again, there is a catch. There could be eigenvalues with multiplicity greater than one. In that case some linear program would be needed to determine if the eigenvalue can be eliminated. One can argue that if the matrix A is random (as it would be in a computer search), then all the eigenvalues will be single. This is also not quite satisfactory, since if eigenvalues are close together then their eigenvectors are subject to possible roundoff error and determining the signs of their entries can be affected by small errors.
1. The example
Let
A=\pmatrix{
1 & \alpha & 2\alpha^2-1 & \alpha & -\sqrt{1-\alpha^2} & 1\cr
\alpha & 1 & \alpha & 2\alpha^2-1 & 1 & -\sqrt{1-\alpha^2}\cr
2\alpha^2-1 & \alpha & 1 & 0 & 0 & 0\cr
\alpha & 2\alpha^2-1 & 0 & 1 & 0 & 0\cr
-\sqrt{1-\alpha^2} & 1 & 0 & 0 & 1 & 0\cr
1 & -\sqrt{1-\alpha^2} & 0 & 0 & 0 & 1\cr
}
where \alpha = -0.933755. Then A is carried on the graph T_6. Our objective is to show that A is COP but not SPN.
To show that A is not SPN we used the well established software packages CSDP [1, Lemma 7] and SDPA [10, Lemma 7] to show that {\rm spnv}(A) \approx -0.0028725 with an error certainly smaller than 10^{-6}.
To show that A is COP, we used the method of eigenvalue eigenvector pairs.
We list the minimum distance between pairs of eigenvalues of A[S] at least one of which is negative for all nonempty subsets S. The table shows that all negative eigenvalues are single.
We also list the eigenvectors of A[S] corresponding to negative eigenvalues for all nonempty subsets S. Some of the eigenvalues are identically zero and these have been omitted. The point to note is that all the eigenvectors have entries with both signs.
2. General comments on computer searches
There are various types of computer searches. The simplest method is to generate random members of the feasible set and test them by evaluating the objective function. But the counterexamples may occupy a very small part of the feasible set and will be difficult to find. More powerful is a directed search. In this type of search, when one finds an instance that gives the best value of the objective function seen so far, one remembers it and then subsequently looks only at small perturbations of this instance. This requires being able to generate random perturbations of a given instance within the feasible set --- not always easy. Usually there is some rule for determining how much to perturb based on how difficult it is to generate better instances. Then there are other types of search (for example the conjugate gradient method) where instances are perturbed in a nonrandom way based on some additional information.
3. Computer searches for non-SPN graphs
We used a random directed search to find the example above. The obvious way to do this is to work with real symmetric matrices A with zero diagonal and carried on the graph and attempt to maximize the objective function {\rm spnv}(A)/{\rm copv}(A). This works well once one has found an example where {\rm spnv}(A)/{\rm copv}(A)>1. Finding such an example is not so easy. It would appear that there are large portions of the feasible set where {\rm spnv}(A)={\rm copv}(A). In trying to maximize the ratio, one is actually maximizing the roundoff error involved in the calculations often leading to spurious results.
So, the first step is to search over real symmetric matrices A with zero diagonal for which the ratio exceeds some value slightly larger than unity. The objective function is the sum of squares of the graph elements and we try to minimize it. If one is lucky, this leads to a matrix that can be adjusted as the starting point of the more obvious search suggested above. The example presented was found in searching for the graph T_8. On careful examination we discovered that the example could be fitted onto T_6. There is some sense to this. One has more scope to find matrices with {\rm spnv}(A)/{\rm copv}(A)>1 the larger the order of the matrix.
4. An example with integer entries
The referee suggested that we include an example with integer entries. Here it is, obtained from \alpha=-\frac{24}{25}.
X=\pmatrix{625&-600&527&-600&-175&625\cr
-600&625&-600&527&625&-175\cr
527&-600&625&0&0&0\cr
-600&527&0&625&0&0\cr
-175&625&0&0&625&0\cr
625&-175&0&0&0&625\cr
}
We have that X is a COP matrix and {\rm spnv}(X) \approx -1.517659, that is that the diagonal elements would have to be replaced with 626.517659 to render the resulting matrix SPN.
Bibliography
[1] B. Borchers, CSDP, a C library for semidefinite programming, Optimization Methods and Software, Volume 11, 1999 - Issue 1-4: Interior Point Methods.
[2] P.H. Diananda, On non-negative forms in real variables some or all of which are non-negative, Proc. Cambridge Philos. Soc. 58 (1962) 17-25.
[3] S. W. Drury, A counterexample to a conjecture of Matsaev, Linear Algebra Appl. 435 (2011) 323--329.
[4] J.J. Green, Calculating the maximum modulus of a polynomial using Stečkin's lemma, SIAM J. Numer. Anal. 36 (4) (1999) 1022--1029.
[5] A.J. Hoffman and Francisco Pereira. On copositive matrices with -1,0,1 entries. Journal of Combinatorial Theory. Series A, 14:302-309, 1973.
[6] L. Hogben and N. Shaked-Monderer, (2019), "SPN Graphs", Electronic Journal of Linear Algebra, Volume 35, pp. 376-386.
[7] P. Li, Y.-Y. Feng, Criteria for copositive matrices of order four, Linear Algebra Appl. 194 (1993) 109-124.
[8] N. Shaked-Monderer, SPN graphs: when copositive = SPN, Linear Algebra Appl. 509 (2016) 82-113.
[9] N. Shaked-Monderer. Corrigendum to ``SPN graphs: When copositive = SPN". Linear Algebra Appl., 541:285-286, 2018.
[10] M. Yamashita, K. Fujisawa, K. Nakata, M. Nakata, M. Fukuda, K. Kobayashi, and K. Goto, A high-performance software package for semidefinite programs: SDPA 7, Research Report B-460 Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan, September, 2010.