Copositive matrix

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

${\displaystyle x^{\top }Ax\geq 0}$

for every nonnegative vector ${\displaystyle 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.

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

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] $${\displaystyle {\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}}}$$

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]

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