Matrices with high completely positive semidefinite rank

DOI10.1016/J.LAA.2016.10.015zbMATH Open1349.15091arXiv1605.00988OpenAlexW2345805953MaRDI QIDQ344893FDOQ344893

Authors: Sander Gribling, David de Laat, Monique Laurent 

Publication date: 25 November 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: A real symmetric matrix $M$ is completely positive semidefinite if it admits a Gram representation by (Hermitian) positive semidefinite matrices of any size $d$. The smallest such $d$ is called the (complex) completely positive semidefinite rank of $M$, and it is an open question whether there exists an upper bound on this number as a function of the matrix size. We construct completely positive semidefinite matrices of size $4k^2+2k+2$ with complex completely positive semidefinite rank $2^k$ for any positive integer $k$. This shows that if such an upper bound exists, it has to be at least exponential in the matrix size. For this we exploit connections to quantum information theory and we construct extremal bipartite correlation matrices of large rank. We also exhibit a class of completely positive matrices with quadratic (in terms of the matrix size) completely positive rank, but with linear completely positive semidefinite rank, and we make a connection to the existence of Hadamard matrices.

Full work available at URL: https://arxiv.org/abs/1605.00988

Recommendations

• Completely positive semidefinite rank
• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Lower bounds for maximal cp-ranks of completely positive matrices and tensors
• Completely positive matrices.
• On the cp-rank and minimal cp factorizations of a completely positive matrix

zbMATH Keywords

matrix factorizationquantum correlationsClifford algebrasHadamard matricescompletely positive semidefinite cone

Mathematics Subject Classification ID

Factorization of matrices (15A23) Semidefinite programming (90C22) Positive matrices and their generalizations; cones of matrices (15B48)

Cites Work

• Lie groups. An approach through invariants and representations
• Conic formulations of graph homomorphisms
• Title not available (Why is that?)
• Expressing combinatorial optimization problems by linear programs
• Quantum analogues of the Bell inequalities. The case of two spatially separated domains
• Approximation of the stability number of a graph via copositive programming
• Bell inequalities and entanglement
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lifts of Convex Sets and Cone Factorizations
• Completely positive matrices associated withM-matrices
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• A Note on Extreme Correlation Matrices
• Positive semidefinite rank
• Extremal bipartite matrices
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• Lower bounds on the entanglement needed to play XOR non-local games
• New results on the cp-rank and related properties of co(mpletely) positive matrices
• New lower bounds and asymptotics for the cp-rank
• From seven to eleven: completely positive matrices with high cp-rank
• On vector configurations that can be realized in the cone of positive matrices
• Title not available (Why is that?)

Cited In (16)

• Pairwise completely positive matrices and conjugate local diagonal unitary invariant quantum states
• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Separability of Hermitian tensors and PSD decompositions
• Lifting for simplicity: concise descriptions of convex sets
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Algorithms for positive semidefinite factorization
• Title not available (Why is that?)
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Self-Dual Polyhedral Cones and Their Slack Matrices
• Completely positive semidefinite rank
• On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings
• Range decompositions and generalized square roots of positive semidefinite matrices
• Approximate completely positive semidefinite factorizations and their ranks
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Universal rigidity of complete bipartite graphs

This page was built for publication: Matrices with high completely positive semidefinite rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344893)