  


Completely positive semidefinite rank
Anupam Prakash(aprakashntu.edu.sg) Abstract: An $n\times n$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $d\times d$ Hermitian positive semidefinite {matrices} $\{P_i\}_{i=1}^n$ (for some $d\ge 1$) such that $X_{ij}= {\rm Tr}(P_iP_j),$ for all $i,j \in \{ 1, \ldots, n \}$. The cpsdrank of a cpsd matrix is the smallest $d\ge 1$ for which such a representation is possible. In this work we initiate the study of the cpsdrank which we motivate twofold. First, the cpsdrank is a natural noncommutative analogue of the completely positive rank of a completely positive matrix. Second, we show that the cpsdrank is physically motivated as it can be used to upper and lower bound the size of a quantum system needed to generate a quantum behavior. In this work we present several properties of the cpsdrank. Unlike the completely positive rank which is at most quadratic in the size of the matrix, no general upper bound is known on the cpsdrank of a cpsd matrix. In fact, we show that the cpsdrank can be exponential in terms of the size. Specifically, for any $n\ge1,$ we construct a cpsd matrix of size $2n$ whose cpsdrank is $2^{\Omega(\sqrt{n})}$. Our construction is based on Gram matrices of Lorentz cone vectors, which we show are cpsd. The proof relies crucially on the connection between the cpsdrank and quantum behaviors. In particular, we use a known lower bound on the size of matrix representations of extremal quantum correlations which we apply to highrank extreme points of the $n$dimensional elliptope. Lastly, we study cpsdgraphs, i.e., graphs $G$ with the property that every doubly nonnegative matrix whose support is given by $G$ is cpsd. We show that a graph is cpsd if and only if it has no odd cycle of length at least $5$ as a subgraph. This coincides with the characterization of cpgraphs. Keywords: completely positive semidefinite cone, cpsdrank, Lorentz cone, elliptope, Bell scenario, quantum behaviors, quantum correlations, cpsdgraphs Category 1: Linear, Cone and Semidefinite Programming (Other ) Citation: Download: [PDF] Entry Submitted: 04/25/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  