Representation of Zeros of a Copositive Matrix via Maximal Cliques of a Graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914969497370624 |
|---|---|
| author | Kostyukova, O. I. Tchemisova, T. V. |
| author_facet | Kostyukova, O. I. Tchemisova, T. V. |
| contents | There is a profound connection between copositive matrices and graph theory. Copositive matrices provide a powerful tool for formulating and solving various challenging graph-related problems. Conversely, graph theory provides a rich set of concepts and techniques that can be applied to analyze key properties of copositive matrices, including their eigenvalues and spectra. In this paper, we present new aspects of the relationship between copositive matrices and graph theory. Focusing on the set of normalized zeros of a copositive matrix, we investigate its properties and demonstrate that this set can be expressed as a union of convex hulls of subsets of minimal zeros. We show that these subsets are connected with the set of maximal cliques of a special graph constructed on the basis of the set of minimal zeros of this matrix. We develop an algorithm for constructing both the set of normalized minimal zeros and the set of all normalized zeros of a copositive matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Representation of Zeros of a Copositive Matrix via Maximal Cliques of a Graph Kostyukova, O. I. Tchemisova, T. V. Optimization and Control 90C25, 15B48, 05C50, 05C69 There is a profound connection between copositive matrices and graph theory. Copositive matrices provide a powerful tool for formulating and solving various challenging graph-related problems. Conversely, graph theory provides a rich set of concepts and techniques that can be applied to analyze key properties of copositive matrices, including their eigenvalues and spectra. In this paper, we present new aspects of the relationship between copositive matrices and graph theory. Focusing on the set of normalized zeros of a copositive matrix, we investigate its properties and demonstrate that this set can be expressed as a union of convex hulls of subsets of minimal zeros. We show that these subsets are connected with the set of maximal cliques of a special graph constructed on the basis of the set of minimal zeros of this matrix. We develop an algorithm for constructing both the set of normalized minimal zeros and the set of all normalized zeros of a copositive matrix. |
| title | Representation of Zeros of a Copositive Matrix via Maximal Cliques of a Graph |
| topic | Optimization and Control 90C25, 15B48, 05C50, 05C69 |
| url | https://arxiv.org/abs/2410.08066 |