Copositive matrix

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

x^{\top }Ax\geq 0

for every nonnegative vector $x\geq 0$ (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

Every real positive-semidefinite matrix is copositive by definition.
Every symmetric nonnegative matrix is copositive. This includes the zero matrix.
The exchange matrix ${\bigl (}{\begin{smallmatrix}0&1\\1&0\end{smallmatrix}}{\bigr )}$ is copositive but not positive-semidefinite.

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 principal submatrix of $A$ is copositive as well. In particular, the entries on the main diagonal must be nonnegative.
the spectral radius $ρ(A)$ is an eigenvalue of $A$ .^[3]

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] ${\begin{pmatrix}1&-1&1&1&-1\\-1&1&-1&1&1\\1&-1&1&-1&1\\1&1&-1&1&-1\\-1&1&1&-1&1\end{pmatrix}}$

Characterization

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

A real symmetric matrix $A$ is copositive if and only if every principal submatrix $B$ of $A$ has no eigenvector $v > 0$ with associated eigenvalue $λ < 0$ .

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

Assume that all the off-diagonal entries of a real symmetric matrix A are nonpositive. Then A is copositive if and only if it is positive semidefinite.

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

References

Berman, Abraham; Robert J. Plemmons (1979). Nonnegative Matrices in the Mathematical Sciences. Academic Press. ISBN 0-12-092250-9.

^ Changqing Xu. "Copositive matrix". MathWorld. Retrieved 23 September 2024.
^ Copositive matrix at PlanetMath.
^ ^a ^b 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.
^ 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.
^ 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.
^ 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.
^ Schweighofer, Markus; Vargas, Luis Felipe (19 October 2023). "Sum-of-squares certificates for copositivity via test states". arXiv:2310.12853 [math.AG].

[1] Changqing Xu. "Copositive matrix". MathWorld. Retrieved 23 September 2024.

[2] Copositive matrix at PlanetMath.

[Ikramov2000-3] 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].

[1]