实成对完全正矩阵

doi:10.15960/j.cnki.issn.1007-6093.2025.03.008

摘要/Abstract

摘要：

本文引入实成对完全正(RPCP)矩阵, 其中一个矩阵必为半正定的, 另一个矩阵必非负, 且该矩阵对具有实成对完全正(RPCP)分解。研究了RPCP矩阵的性质, 给出了矩阵对为RPCP的一些充分和必要条件。首先, 我们给出RPCP矩阵的另一个等价分解。证明了矩阵对(X, X)是RPCP当且仅当X为完全正矩阵。此外, 还证明了RPCP矩阵判定问题等价于可分补全问题。同时, 对于RPCP矩阵判定和分解问题, 提出了一种半定松弛算法。讨论了算法的渐进收敛性和有限收敛性。若矩阵对是RPCP, 算法可进一步给出其一个RPCP分解; 若不是, 算法也能够给出一个判定依据。

关键词: 实成对完全正矩阵, 截断矩问题, 半定松弛

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

中图分类号:

O221.2

周安娃, 何佳怡. 实成对完全正矩阵[J]. 运筹学学报（中英文）, 2025, 29(3): 160-178.

Anwa ZHOU, Jiayi HE. Real pairwise completely positive matrices[J]. Operations Research Transactions, 2025, 29(3): 160-178.

图/表 6

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

参考文献 36

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. doi: 10.13001/1081-3810.3842
2	SinghS.Entanglement detection in triangle-free quantum states[J].Physical Review A,2021,103(3):032436. doi: 10.1103/PhysRevA.103.032436
3	SinghS,NechitaI.Diagonal unitary and orthogonal symmetries in quantum theory[J].Journal of Physics. A. Mathematical and Theoretical,2022,55(25):255302. doi: 10.1088/1751-8121/ac7017
4	NechitaI,SinghS.A graphical calculus for integration over random diagonal unitary matrices[J].Linear Algebra and its Applications,2021,613,46-86. doi: 10.1016/j.laa.2020.12.014
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. doi: 10.1007/s10589-013-9594-z
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. doi: 10.1137/120890636
8	BurerS.On the copositive representation of binary and continuous nonconvex quadratic programs[J].Mathematical Programming,2009,120(2):479-495. doi: 10.1007/s10107-008-0223-z
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. doi: 10.1137/S1052623401383248
10	DukanovicI,RendlF.Copositive programming motivated bounds on the stability and the chromatic numbers[J].Mathematical Programming,2010,121(2):249-268. doi: 10.1007/s10107-008-0233-x
11	GühneO,TothG.Entanglement detection[J].Physics Reports,2009,474(1-6):1-75. doi: 10.1016/j.physrep.2009.02.004
12	GvozdenovićN,LaurentM.The operator Ψ for the chromatic number of a graph[J].SIAM Journal on Optimization,2008,19(2):572-591. doi: 10.1137/050648237
13	ZhouA,FanJ.The CP-matrix completion problem[J].SIAM Journal on Matrix Analysis and Applications,2014,35(1):127-142. doi: 10.1137/130919490
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. doi: 10.1016/j.laa.2006.08.026
15	WernerR F.Quantum states with Einstein-Podolsky-Rosen correlations admitting a hiddenvariable model[J].Physical Review A,1989,40(8):4277-4281. doi: 10.1103/PhysRevA.40.4277
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. doi: 10.1007/s11464-009-0016-6
19	DohertyA C,ParriloP A,SpedalieriF M.Complete family of separability criteria[J].Physical Review A,2004,69(2):022308. doi: 10.1103/PhysRevA.69.022308
20	GurvitsL,BarnumH.Largest separable balls around the maximally mixed bipartite quantum state[J].Physical Review A,2002,66(6):062311. doi: 10.1103/PhysRevA.66.062311
21	HorodeckiR,HorodeckiP,HorodeckiM,et al.Quantum entanglement[J].Reviews of Modern Physics,2009,81(2):865-942. doi: 10.1103/RevModPhys.81.865
22	NieJ,ZhangX.Positive maps and separable matrices[J].SIAM Journal on Optimization,2016,26(2):1236-1256. doi: 10.1137/15M1018514
23	PutinarM.Positive polynomials on compact semi-algebraic sets[J].Indiana University Mathematics Journal,1993,42(3):969-984. doi: 10.1512/iumj.1993.42.42045
24	NieJ.Optimality conditions and finite convergence of Lasserre's hierarchy[J].Mathematical Programming,2014,146(1-2):97-121. doi: 10.1007/s10107-013-0680-x
25	LasserreJ B.Completely positive matrices associated with M-matrices[J].Linear and Multilinear Algebra,1994,37(4):303-310. doi: 10.1080/03081089408818334
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. doi: 10.1007/s10208-014-9225-9
30	NieJ.Certifying convergence of Lasserre's hierarchy via flat truncation[J].Mathematical Programming,2013,142(1-2):485-510. doi: 10.1007/s10107-012-0589-9
31	NieJ.Linear optimization with cones of moments and nonnegative polynomials[J].Mathematical Programming,2015,153(1):247-274. doi: 10.1007/s10107-014-0797-6
32	HenrionD,LasserreJ B,LoefbergJ.GloptiPoly 3: Moments, optimization and semidefinite programming[J].Optimization Methods and Software,2009,24(4-5):761-779. doi: 10.1080/10556780802699201
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.

k	λ_k	v_k	w_k
1	1.238 1	(0.089 3, 0.996 0)$ ^{\top} $	(0.795 9, −0.605 4)$ ^{\top} $
2	10.011 9	(0.723 5, 0.690 4)$ ^{\top} $	(0.215 7, 0.976 5)$ ^{\top} $

k	λ_k	v_k	w_k
1	0.627 9	(0.067 1, -0.757 0, -0.649 9)$ ^{\top} $	(-0.447 0, -0.299 6, -0.842 8)$ ^{\top} $
2	4.344 4	(-0.636 1, 0.377 6, 0.672 9)$ ^{\top} $	(0.289 8, -0.599 7, -0.745 9)$ ^{\top} $
3	1.410 9	(0.058 9, -0.980 0, -0.190 2)$ ^{\top} $	(0.062 6, 0.845 4, -0.530 4)$ ^{\top} $
4	2.740 0	(0.630 9, -0:583 3, -0.511 5)$ ^{\top} $	(-0:848 2, 0.519 7, 0.101 9)$ ^{\top} $
5	0.227 1	(-0.154 9, 0.197 0, -0.968 1)$ ^{\top} $	(0.228 1, -0.187 8, 0.955 4)$ ^{\top} $
6	1.149 8	(0.745 0, 0.442 1, -0.499 5)$ ^{\top} $	(-0:942 3, 0.329 5, 0.059 4)$ ^{\top} $

k	λ_k	v_k	w_k
1	12.068 1	(-0.264 9, -0.896 3, -0.355 6)$ ^{\top} $	(-0.427 4, -0.900 4, -0.081 5)$ ^{\top} $
2	0.408 4	(-0.400 5, 0.727 9, -0.556 5)$ ^{\top} $	(-0.442 4, 0.048 8, 0.895 5)$ ^{\top} $
3	5.814 8	(0.826 2, -0.260 4, 0.499 6)$ ^{\top} $	(-0:677 9, -0.163 0, 0.716 8)$ ^{\top} $
4	5.708 7	(0.442 7, 0.348 6, -0.826 1)$ ^{\top} $	(-0:086 9, -0.431 2, 0.898 1)$ ^{\top} $

k	λ_k	v_k	w_k
1	2.126 9	(0.726 0, -0.039 4, -0.686 6)$ ^{\top} $	(-0.523 3, -0.242 1, 0.817 1)$ ^{\top} $
2	2.383 2	(0.841 0, -0.035 2, -0.539 9)$ ^{\top} $	(-0.432 2, -0.200 0, 0.879 3)$ ^{\top} $
3	11.959 4	(-0.299 9, 0.807 6, -0.507 7)$ ^{\top} $	(0.403 6, -0.816 5, 0.412 8)$ ^{\top} $
4	0.630 0	(0.197 0, -0.784 7, 0.587 7)$ ^{\top} $	(-0.076 6, 0.997 0, -0.009 8)$ ^{\top} $
5	4.745 5	(0.008 2, 0.911 5, 0.411 1)$ ^{\top} $	(0.418 5, -0.816 4, 0.397 9)$ ^{\top} $
6	9.103 1	(-0.747 9, 0.090 3, 0.657 6)$ ^{\top} $	(0.657 6, -0.156 7, 0.736 8)$ ^{\top} $
7	0.254 0	(-0.035 4, -0.028 7, 0.999 0)$ ^{\top} $	(0.991 5, 0.042 9, 0.123 2)$ ^{\top} $
8	0.797 9	(0.008 0, 0.993 3, 0.115 0)$ ^{\top} $	(0.054 1, 0.997 7, 0.041 6)$ ^{\top} $

k	λ_k	v_k(= w_k)
1	14.421 6	(0.568 3, 0.059 3, 0.322 5, -0.718 1, -0.231 9)$ ^{\top} $
2	48.262 8	(-0.529 0, 0.645 6, -0.457 6, 0.304 3, 0.036 7)$ ^{\top} $
3	27.476 1	(0.325 1, 0.287 1, 0.722 2, -0.523 0, 0.129 5)$ ^{\top} $
4	51.271 5	(-0.499 6, 0.160 0, 0.565 6, -0.114 4, 0.626 0)$ ^{\top} $
5	84.568 1	(-0.346 2, 0.524 4, -0.088 4, 0.485 2, 0.601 6)$ ^{\top} $