中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 3: 160 - 178

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.03.008

Research Article

Real pairwise completely positive matrices

  • Anwa ZHOU ,
  • Jiayi HE
Expand
  • 1. College of Sciences, Shanghai University, Shanghai 200444, China
周安娃  E-mail: zhouanwa@shu.edu.cn

Received date: 2025-03-07

  Online published: 2025-09-09

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

Abstract

In this paper, we introduce the real pairwise completely positive (RPCP) matrices with one of them is necessarily positive semidefinite while the other one is necessarily entrywise nonnegative, which has a real pairwise completely positive (RPCP) decomposition. We study the properties of RPCP matrices and give some necessary and sufficient conditions for a matrix pair to be RPCP. First, we give an equivalent decomposition for the RPCP matrices, which is different from the RPCP-decomposition and show that the matrix pair (X, X) is RPCP if and only if X is completely positive. Besides, we also prove that the RPCP matrices checking problem is equivalent to the separable completion problem. A semidefinite algorithm is also proposed for detecting whether or not a matrix pair is RPCP. The asymptotic and finite convergence of the algorithm are also discussed. If it is RPCP, we can further give a RPCP-decomposition for it; if it is not, we can obtain a certificate for this.

Key words： real pairwise completely positive matrices; truncated moment problem; semidefinite relaxation

Cite this article

Anwa ZHOU , Jiayi HE . Real pairwise completely positive matrices[J]. Operations Research Transactions, 2025 , 29(3) : 160 -178 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.03.008

References

1 JohnstonN,MacLeanO.Pairwise completely positive matrices and conjugate local diagonal unitary invariant quantum states[J].Electronic Journal of Linear Algebra,2019,35,156-180.
2 SinghS.Entanglement detection in triangle-free quantum states[J].Physical Review A,2021,103(3):032436.
3 SinghS,NechitaI.Diagonal unitary and orthogonal symmetries in quantum theory[J].Journal of Physics. A. Mathematical and Theoretical,2022,55(25):255302.
4 NechitaI,SinghS.A graphical calculus for integration over random diagonal unitary matrices[J].Linear Algebra and its Applications,2021,613,46-86.
5 BermanA,Shaked-MondererN.Completely Positive Matrices[M].River Edge:World Scientific,2003.
6 DickinsonP J,GijbenL,HanD.On the computational complexity of membership problems for the completely positive cone and its dual[J].Computational Optimization and Applications,2014,57(2):403-415.
7 ArimaN,KimS,KojimaM.A quadratically constrained quadratic optimization model for completely positive cone programming[J].SIAM Journal on Optimization,2013,23(4):2320-2340.
8 BurerS.On the copositive representation of binary and continuous nonconvex quadratic programs[J].Mathematical Programming,2009,120(2):479-495.
9 de KlerkE,PasechnikD V.Approximation of the stability number of a graph via copositive programming[J].SIAM Journal on Optimization,2002,12(4):875-892.
10 DukanovicI,RendlF.Copositive programming motivated bounds on the stability and the chromatic numbers[J].Mathematical Programming,2010,121(2):249-268.
11 GühneO,TothG.Entanglement detection[J].Physics Reports,2009,474(1-6):1-75.
12 Gvozdenovi?N,LaurentM.The operator Ψ for the chromatic number of a graph[J].SIAM Journal on Optimization,2008,19(2):572-591.
13 ZhouA,FanJ.The CP-matrix completion problem[J].SIAM Journal on Matrix Analysis and Applications,2014,35(1):127-142.
14 DahlG,LeinaasJ M,MyrheimJ,et al.A tensor product matrix approximation problem in quantum physics[J].Linear Algebra and its Applications,2007,420(2-3):711-725.
15 WernerR F.Quantum states with Einstein-Podolsky-Rosen correlations admitting a hiddenvariable model[J].Physical Review A,1989,40(8):4277-4281.
16 GharibianS.Strong NP-hardness of the quantum separability problem[J].Quantum Information and Computation,2010,10(3-4):343-360.
17 Gurvits L. Classical deterministic complexity of Edmonds' problem and quantum entanglement[C]//Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, 2003: 10-19.
18 QiL,DaiH,HanD.Conditions for strong ellipticity and M-eigenvalues[J].Frontiers of Mathematics in China,2009,4(2):349-364.
19 DohertyA C,ParriloP A,SpedalieriF M.Complete family of separability criteria[J].Physical Review A,2004,69(2):022308.
20 GurvitsL,BarnumH.Largest separable balls around the maximally mixed bipartite quantum state[J].Physical Review A,2002,66(6):062311.
21 HorodeckiR,HorodeckiP,HorodeckiM,et al.Quantum entanglement[J].Reviews of Modern Physics,2009,81(2):865-942.
22 NieJ,ZhangX.Positive maps and separable matrices[J].SIAM Journal on Optimization,2016,26(2):1236-1256.
23 PutinarM.Positive polynomials on compact semi-algebraic sets[J].Indiana University Mathematics Journal,1993,42(3):969-984.
24 NieJ.Optimality conditions and finite convergence of Lasserre's hierarchy[J].Mathematical Programming,2014,146(1-2):97-121.
25 LasserreJ B.Completely positive matrices associated with M-matrices[J].Linear and Multilinear Algebra,1994,37(4):303-310.
26 Laurent M. Sums of squares, moment matrices and optimization over polynomials[M]//Putinar M, Sullivant S (eds.). Emerging Applications of Algebraic Geometry, New York: Springer, 2009: 157-270.
27 NieJ.Moment and Polynomial Optimization[M].Philadelphia:Society for Industrial and Applied Mathematics,2023.
28 CurtoR,FialkowL.Truncated K-moment problems in several variables[J].Journal of Operator Theory,2005,54(1):189-226.
29 NieJ.The $\mathcal{A}$-truncated K-moment problem[J].Foundations of Computational Mathematics,2014,14(6):1243-1276.
30 NieJ.Certifying convergence of Lasserre's hierarchy via flat truncation[J].Mathematical Programming,2013,142(1-2):485-510.
31 NieJ.Linear optimization with cones of moments and nonnegative polynomials[J].Mathematical Programming,2015,153(1):247-274.
32 HenrionD,LasserreJ B,LoefbergJ.GloptiPoly 3: Moments, optimization and semidefinite programming[J].Optimization Methods and Software,2009,24(4-5):761-779.
33 SturmJ F.Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[J].Optimization Methods and Software,1999,11/12(1-4):625-653.
34 DemmelJ W.Applied Numerical Linear Algebra[M].Philadelphia:Society for Industrial and Applied Mathematics,1997.
35 GolubG H,Van Loan,CharlesF.Matrix Computations[M].Baltimore:Johns Hopkins University Press,1996.
36 Henrion D, Lasserre J B. Detecting global optimality and extracting solutions in GloptiPoly[M]//Henrion D, Garulli A (eds.) Positive Polynomials in Control, Berlin: Saunders, 2005: 293-310.
Options
Outlines

/

〈 〉