Representation of zeros of a copositive matrix via maximal cliques of a graph

There is a strong connection between copositive matrices and graph theory. Copositive matrices provide a powerful tool for formulating and approximating various challenging graph-related problems. In return, graph theory offers a rich set of concepts and techniques that can be used to explore important properties of copositive matrices, such as their eigenvalues and spectra. This paper presents new insights into this interplay. Specifically, we focus on the set of all zeros of a copositive matrix, examining its properties and demonstrating that it can be expressed as a union of convex hulls of certain subsets of minimal zeros. We further show that these subsets are closely linked to the maximal cliques of a special graph, constructed based on the minimal zeros of the matrix. An algorithm is explicitly described for constructing the complete set of normalized zeros and minimal zeros of a copositive matrix. • Given a copositive matrix, its minimal zeros graph is introduced, and new properties of the sets of zeros and minimal zeros are established. • The set of all maximal cliques of the minimal zeros graph uniquely determines the subsets of the minimal zeros set of a copositive matrix. • The union of convex hulls of the subsets of the minimal zeros set forms the entire set of all zeros of a copositive matrix. • A detailed algorithm for constructing the set of minimal zeros of a copositive matrix is presented.