João Gouveia; Positive semidefinite rank and representations of polytopes

Tuesday, January 19, 2016, 4:00 pm
SIG 226

João Gouveia, University of Coimbra .

Let M be a p-by-q matrix with nonnegative entries. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A_i,B_j of size k×k such that M_{ij}=trace(A_i,B_j). The psd rank was recently introduced, and has has many appealing interpretations, capturing some geometrical aspects of the power and limitations of semidefinite programming. In this talk, we will briefly cover basic properties and open questions on this quantity, and proceed to use some of this results to provide a complete characterization of polytopes in R^4 that can be represented as economically as possible by means of a semidefinite program.