Copositive matrix

Last updated

In mathematics, specifically linear algebra, a real symmetric matrix A is copositive if

Contents

for every nonnegative vector (where the inequalities should be understood coordinate-wise). Some authors do not require A to be symmetric. [1] The collection of all copositive matrices is a proper cone; [2] it includes as a subset the collection of real positive-definite matrices.

Copositive matrices find applications in economics, operations research, and statistics.

Examples

Properties

It is easy to see that the sum of two copositive matrices is a copositive matrix. More generally, any conical combination of copositive matrices is copositive.

Let A be a copositive matrix. Then we have that

Every copositive matrix of order less than 5 can be expressed as the sum of a positive semidefinite matrix and a nonnegative matrix. [4] A counterexample for order 5 is given by a copositive matrix known as Horn-matrix: [5]

Characterization

The class of copositive matrices can be characterized using principal submatrices. One such characterization is due to Wilfred Kaplan: [6]

Several other characterizations are presented in a survey by Ikramov, [3] including:

The problem of deciding whether a matrix is copositive is co-NP-complete. [7]

References

  1. Changqing Xu. "Copositive matrix". MathWorld . Retrieved 23 September 2024.
  2. Copositive matrix at PlanetMath .
  3. 1 2 Ikramov, Kh. D.; Savel'eva, N. V. (1 January 2000). "Conditionally definite matrices" . Journal of Mathematical Sciences. 98 (1): 1–50. doi:10.1007/BF02355379. ISSN   1573-8795.
  4. Diananda, P. H. (January 1962). "On non-negative forms in real variables some or all of which are non-negative" . Mathematical Proceedings of the Cambridge Philosophical Society . 58 (1): 17–25. doi:10.1017/S0305004100036185. ISSN   1469-8064.
  5. Dür, Mirjam (2010). "Copositive Programming – a Survey" (PDF). In Diehl, Moritz; Glineur, Francois; Jarlebring, Elias; Michiels, Wim (eds.). Recent Advances in Optimization and its Applications in Engineering. Berlin, Heidelberg: Springer. pp. 3–20. doi:10.1007/978-3-642-12598-0_1. ISBN   978-3-642-12598-0.
  6. Kaplan, Wilfred (1 July 2000). "A test for copositive matrices". Linear Algebra and Its Applications. 313 (1): 203–206. doi:10.1016/S0024-3795(00)00138-5. ISSN   0024-3795.
  7. Schweighofer, Markus; Vargas, Luis Felipe (19 October 2023). "Sum-of-squares certificates for copositivity via test states". arXiv: 2310.12853 [math.AG].