Alexander Oertel: Rational Certificates for Complete Positivity of Symmetric Matrices

Rational Certificates for Complete Positivity of Symmetric Matrices

Alexander Oertel, University of Rostock

Abstract: Voronoi's classical theory of perfect matrices allows solving the sphere packing problem in lattices. This theory can be extended to the dual pair of completely positive and copositive matrices, that is to symmetric matrices of the form BB^T for a nonnegative matrix B and to symmetric matrices Q satisfying x^T Q x >= 0 for all nonnegative vectors x. This leads to a theory of perfect copositive matrices along with both outer and inner polyhedral approximations to the cone of completely positive matrices. They allow finding rational CP-certificates: For a rational completely positive matrix Q we find a rational nonnegative matrix B with Q=BB^T. If Q is not completely positive we also find a certificate for that. In this talk we summarize this theory and briefly generalize it to copositivity over a cone K, where the condition is x^T Q x >= 0 for all x in K.