New results on the cp-rank and related properties of co(mpletely )positive matrices

Abstract

Copositive and completely positive matrices play an increasingly important role in Applied Mathematics, namely as a key concept for approximating NP-hard optimization problems. The cone of copositive matrices of a given order and the cone of completely positive matrices of the same order are dual to each other with respect to the standard scalar product on the space of symmetric matrices. This paper establishes some new relations between orthogonal pairs of such matrices lying on the boundary of either cone. As a consequence, we can establish an improvement on the upper bound of the cp-rank of completely positive matrices of general order and a further improvement for such matrices of order six.

Keywords:

• copositive optimization
• completely positive matrices
• cp-rank
• nonnegative factorization

AMS Subject Classifications:

• 15B48
• 90C25
• 15A23

Notes

The work of Abraham Berman and Naomi Shaked-Monderer was supported by the German-Israeli Foundation for Scientific Research and Development (GIF) [grant number G-18-304.2/2011].