- Completely positive semidefinite rank Anupam Prakash(aprakashntu.edu.sg) Jamie Sikora(cqtjwjsnus.edu.sg) Antonios Varvitsiotis(avarvitsgmail.com) Zhaohui Wei(weizhaohuigmail.com.) 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 cpsd-rank 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 cpsd-rank which we motivate twofold. First, the cpsd-rank is a natural non-commutative analogue of the completely positive rank of a completely positive matrix. Second, we show that the cpsd-rank 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 cpsd-rank. Unlike the completely positive rank which is at most quadratic in the size of the matrix, no general upper bound is known on the cpsd-rank of a cpsd matrix. In fact, we show that the cpsd-rank can be exponential in terms of the size. Specifically, for any $n\ge1,$ we construct a cpsd matrix of size $2n$ whose cpsd-rank 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 cpsd-rank 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 high-rank extreme points of the $n$-dimensional elliptope. Lastly, we study cpsd-graphs, 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 cp-graphs. Keywords: completely positive semidefinite cone, cpsd-rank, Lorentz cone, elliptope, Bell scenario, quantum behaviors, quantum correlations, cpsd-graphs Category 1: Linear, Cone and Semidefinite Programming (Other ) Citation: Download: [PDF]Entry Submitted: 04/25/2016Entry Accepted: 04/25/2016Entry Last Modified: 04/25/2016Modify/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 Optimization Online is supported by the Mathematical Optmization Society.