Generating extreme copositive matrices near matrices obtained from COP-irreducible graphs

Maxim Manainen (1) , Mikhail Seliugin (1) , Roman Tarasov (1) , Roland Hildebrand (2)

1 MIPT - Moscow Institute of Physics and Technology [Moscow]
2 DAO - Données, Apprentissage et Optimisation

In this paper we construct new families of extremal copositive matrices in arbitrary dimension by an algorithmic procedure. Extremal copositive matrices are organized in relatively open subsets of real-algebraic varieties, and knowing a particular such matrix A allows in principle to obtain the variety in which A is embedded by solving the corresponding system of algebraic equations. We show that if A is a matrix associated to a so-called COP-irreducible graph with stability number equal 3, then by a trigonometric transformation these algebraic equations become linear and can be solved by linear algebra methods. We develop an algorithm to construct and solve the corresponding linear systems and give examples where the variety contains singularities at the initial matrix A. For the cycle graph we completely characterize the part of the variety which consists of copositive matrices.

Mots clés: Copositive cone; Stability number

Domaines: Mathématiques [math]

Maxim Manainen, Mikhail Seliugin, Roman Tarasov, Roland Hildebrand. Generating extreme copositive matrices near matrices obtained from COP-irreducible graphs. Linear Algebra and its Applications, In press, ⟨10.1016/j.laa.2023.09.026⟩. ⟨hal-04249070⟩