Hypergraph characterizations of copositive tensors

Abstract

A real symmetric tensor \mathcal{A}=(a_{i_{\mathrm{1}}}\cdots i_m)\in {ℝ}^{[mn]} is copositive (resp., strictly copositive) if \mathcal{A}{x}^m\ge \mathrm{0} (resp., \mathcal{A}{x}^m>\mathrm{0}) for any nonzero nonnegative vectorx\in {ℝ}^n: By using the associated hypergraph of \mathcal{A}, we give necessary and sufficient conditions for the copositivity of \mathcal{A}: For a real symmetric tensor \mathcal{A}satisfying the associated negative hypergraph H\_(\mathcal{A}) and associated positive hypergraph H_{+}(\mathcal{A}) are edge disjoint subhypergraphs of a supertree or cored hypergraph, we derive criteria for the copositivity of \mathcal{A}: We also use copositive tensors to study the positivity of tensor systems.

Keywords

Copositive tensor / hypergraph / positive system

References

[1] Bartosiewicz Z. Positive nonlinear systems, response maps and realizations. In: Proc of 54th IEEE Conference on Decision and Control, December 15-18, 2015, Osaka.2015, 6379–6384

[2] Bretto A. Hypergraph Theory: An Introduction. Berlin: Springer, 2013

[3] Bu C J, Li H F, Zhou J. Inverse Perron values and connectivity of a uniform hyper-graph. Electron J Combin, 2018, 25: P4.28

[4] Bu C J, Wei Y M, Sun L Z, Zhou J. Brualdi-type eigenvalue inclusion sets of tensors. Linear Algebra Appl, 2015, 480: 168–175

[5] Chen H B, Huang Z H, Qi L Q. Copositive detection of tensors: theory and algorithm. J Optim Theory Appl, 2017, 174: 746–761

[6] Chen H B, Huang Z H, Qi L Q. Copositive tensor detection and its applications in physics and hypergraphs. Comput Optim Appl, 2018, 69: 133–158

[7] Chen H B, Wang Y J. High-order copositive tensors and its applications. J Appl Anal Comput, 2018, 8(6): 1863–1885

[8] Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl, 2012, 436: 3268–3292

[9] Ding W Y, Qi L Q, Wei Y M.ℳ-tensors and nonsingular ℳ-tensors. Linear Algebra Appl, 2013, 439: 3264–3278

[10] Farina L, Rinaldi S. Positive Linear Systems: Theory and Applications. New York: Wiley Interscience, 2000

[11] Hiriart-Urruty J B, Seeger A. A variational approach to copositive matrices. SIAM Rev, 2010, 52(4): 593–629

[12] Hu S L, Qi L Q, Shao J Y. Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues. Linear Algebra Appl, 2013, 439: 2980–2998

[13] Kannike K. Vacuum stability of a general scalar potential of a few fields. Eur Phys J C, 2016, 76: 324

[14] Li H H, Shao J Y, Qi L Q. The extremal spectral radii of k-uniform supertrees. J Comb Optim, 2016, 32: 741–764

[15] Li L, Zhang X Z, Huang Z H, Qi L Q. Test of copositive tensors. J Ind Manag Optim, 2019, 15(2): 881–891

[16] Lim L H. Singular values and eigenvalues of tensors: a variational approach.In: Proc1st IEEE International Workshop on Computational Advances of Multisensor AdaptiveProcessing, Puerto Vallarta, 2005. 2005, 129–132

[17] Motzkin T S. Copositive quadratic forms. National Bureau Standards Report, 1952, 1818: 11–12

[18] Nie J W, Yang Z, Zhang X Z. A complete semidefinite algorithm for detecting copositive matrices and tensors. SIAM J Optim, 2018, 28: 2902–2921

[19] Pena J, Vera J C, Zuluaga L F. Completely positive reformulations for polynomial optimization. Math Program, 2014, 151: 405. Complet431

[20] Qi L Q. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324

[21] Qi L Q. Symmetric nonnegative tensors and copositive tensors. Linear Algebra Appl, 2013, 439: 228–238

[22] Qi L Q, Luo Z Y. Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia: SIAM, 2017

[23] Shaked-Monderer N. SPN graphs: When copositive= SPN. Linear Algebra Appl, 2016, 509: 82–113

[24] Shao J Y, Qi L Q, Hu S L. Some new trace formulas of tensors with applications in spectral hypergraph theory. Linear Multilinear Algebra, 2015, 63: 971–992

[25] Song Y S, Qi L Q. Necessary and sufficient conditions for copositive tensors. Linear Multilinear Algebra, 2015, 63: 120–131

[26] Wang C Y, Chen H B, Wang Y J, Zhou G L. On copositiveness identification of partially symmetric rectangular tensors. J Comput Appl Math, 2020, 372: 112678

[27] Zhang L P, Qi L Q, Zhou G L. M-tensors and some applications. SIAM J Matrix Anal Appl, 2014, 35: 437–452

RIGHTS & PERMISSIONS

Higher Education Press