Extreme elements of 𝒞⁶

This website is dedicated to the problem of classifying the extremal matrices of the copositive cone 𝒞⁶. This is the copositive cone of smallest dimension for which such a classification is not yet available.

Copositive matrices are real symmetric matrices which, if considered as quadratic forms, are nonnegative on the positive orthant. For a fixed matrix size n, these matrices form a convex cone, the copositive cone 𝒞. This cone contains both the cone of positive semi-definite matrices and the cone of element-wise nonnegative matrices. An exceptional copositive matrix is a matrix which cannot be represented as a sum of a positive semi-definite matrix and a nonnegative matrix. An extremal copositive matrix is a matrix which cannot be represented as a sum of two linearly independent copositive matrices. A reduced copositive matrix is a matrix which ceases to be copositive if a non-zero non-exceptional copositive matrix is subtracted. Any exceptional extremal copositive matrix is necessarily reduced.

One possibility to classify copositive matrices is via their minimal zero support sets. This support set is a collection of index sets, each index set corresponding to the support of a minimal zero of the matrix. There is only a finite number of minimal zero support sets which an extremal copositive matrix can have. For 6x6 matrices these have been narrowed down to the reasonable number of 44 candidates listed in the table below.

The classification of extreme rays will be complete if for every one of these 44 candidate minimal zero support sets, it is shown that either

• there are no exceptional extremal copositive matrices with this minimal zero support set
• there are exceptional extremal copositive matrices with this minimal zero support set

and a description of the extremal matrices is provided. Solved cases are marked with the corresponding color and are linked to the description of the solution.

A detailed description of the problem can be found here, further material and helpful technical lemmas can be found here.

Solutions of individual cases can be sent to me by e-mail and should include

• a description of all exceptional extremal copositive matrices with the corresponding minimal zero support set
• a proof that no further such matrices exist

Submitted solutions will be verified and posted on the site. Should the list of open cases shrink to the empty set, a publication of the full classification is envisaged with all people having submitted correct solutions participating as authors.

Update: on May 24, 2019 the last open case has been solved and the classification is now complete. Many thanks to Andrei Afonin (Moscow Institute of Physics and Technology) who performed the majority of the computations, and to Peter J.C. Dickinson (RaboBank) whose recent work on copositive cones greatly simplified the proofs.

List of candidate minimal zero support sets
 1 {1,2},{1,3},{1,4},{2,5},{3,6},{5,6} 2 {1,2},{1,3},{1,4},{2,5},{3,6},{4,5,6} 3 {1,2},{1,3},{1,4},{2,5},{3,5,6},{4,5,6} 4 {1,2},{1,3},{1,4},{2,5,6},{3,5,6},{4,5,6} 5 {1,2},{1,3},{2,4},{3,4,5},{1,5,6},{4,5,6} 6 {1,2},{1,3},{1,4,5},{2,4,6},{3,4,6},{4,5,6} 7 {1,2},{1,3},{2,4,5},{3,4,5},{2,4,6},{3,4,6} 8 {1,2},{1,3},{2,4,5},{3,4,5},{2,4,6},{3,5,6} 9 {1,2},{3,4},{1,3,5},{2,4,6},{1,5,6},{4,5,6} 10 {1,2},{1,3,4},{1,3,5},{2,3,6},{3,4,6},{3,5,6} 11 {1,2},{1,3,4},{1,3,5},{1,4,6},{2,5,6},{3,5,6} 12 {1,2},{1,3,4},{1,3,5},{1,4,6},{3,5,6},{4,5,6} 13 {1,2},{1,3,4},{1,3,5},{2,4,6},{3,4,6},{2,5,6} 14 {1,2},{1,3,4},{1,3,5},{2,4,6},{3,4,6},{3,5,6} 15 {1,2},{1,3,4},{1,3,5},{2,4,6},{3,4,6},{4,5,6} 16 {1,2},{1,3,4},{1,3,5},{2,4,6},{3,5,6},{4,5,6} 17 {1,2},{1,3,4},{2,3,5},{3,4,5},{2,4,6},{3,4,6} 18 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{1,4,6},{1,5,6} 19 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{1,4,6},{2,5,6} 20 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{1,4,6},{3,5,6} 21 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{2,4,6},{3,4,6} 22 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{2,4,6},{3,5,6} 23 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{2,4,6},{3,4,5,6} 24 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{3,4,6},{3,5,6} 25 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{3,4,6},{4,5,6} 26 {1,2,3},{1,2,4},{1,3,5},{1,4,5},{2,3,6},{2,4,6} 27 {1,2,3},{1,2,4},{1,3,5},{1,4,5},{2,3,6},{3,4,6} 28 {1,2,3},{1,2,4},{1,3,5},{2,4,5},{3,4,5},{2,3,6} 29 {1,2,3},{1,2,4},{1,3,5},{2,4,5},{2,3,6},{2,5,6} 30 {1,2,3},{1,2,4},{1,3,5},{2,4,5},{3,4,6},{3,5,6} 31 {1,2,3},{1,2,4},{1,3,5},{2,4,5},{1,5,6},{2,5,6} 32 {1,2,3},{1,2,4},{1,3,5},{2,4,5},{1,5,6},{4,5,6} 33 {1,2,3},{1,2,4},{1,3,5},{2,4,5},{3,5,6},{4,5,6} 34 {1,2,3},{1,2,4},{1,3,5},{2,4,6},{3,5,6},{4,5,6} 35 {1,2,3,4},{1,2,3,5},{1,2,4,6},{1,3,5,6},{2,4,5,6},{3,4,5,6} 36 {1,2},{1,3},{1,4},{2,5},{4,5},{3,6},{5,6} 37 {1,2},{1,3,4},{1,3,5},{1,4,6},{2,5,6},{3,5,6},{4,5,6} 38 {1,2},{1,3,4},{1,3,5},{2,4,6},{3,4,6},{2,5,6},{3,5,6} 39 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{1,4,6},{2,5,6},{3,5,6} 40 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{1,4,6},{3,5,6},{4,5,6} 41 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{2,4,6},{3,4,6},{3,5,6} 42 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{2,4,6},{3,5,6},{4,5,6} 43 {1,2,3},{1,2,4},{1,2,5},{1,3,6},{1,4,6},{2,5,6},{3,5,6},{4,5,6} 44 {1,2,3},{1,2,4},{1,3,5},{1,4,5},{2,3,6},{2,4,6},{3,5,6},{4,5,6}