实成对完全正矩阵

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.

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

参考文献

[1] Johnston N, MacLean O. Pairwise completely positive matrices and conjugate local diagonal unitary invariant quantum states [J]. Electronic Journal of Linear Algebra, 2019, 35: 156-180.
[2] Singh S. Entanglement detection in triangle-free quantum states [J]. Physical Review A, 2021, 103(3): 032436.
[3] Singh S, Nechita I. Diagonal unitary and orthogonal symmetries in quantum theory [J]. Journal of Physics. A. Mathematical and Theoretical, 2022, 55(25): 255302.
[4] Nechita I, Singh S. A graphical calculus for integration over random diagonal unitary matrices [J]. Linear Algebra and its Applications, 2021, 613: 46-86.
[5] Berman A, Shaked-Monderer N. Completely Positive Matrices [M]. River Edge: World Scientific, 2003.
[6] Dickinson P J, Gijben L, Han D. 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] Arima N, Kim S, Kojima M. A quadratically constrained quadratic optimization model for completely positive cone programming [J]. SIAM Journal on Optimization, 2013, 23(4): 2320- 2340.
[8] Burer S. On the copositive representation of binary and continuous nonconvex quadratic programs [J]. Mathematical Programming, 2009, 120(2): 479-495.
[9] de Klerk E, Pasechnik D V. Approximation of the stability number of a graph via copositive programming [J]. SIAM Journal on Optimization, 2002, 12(4): 875-892.
[10] Dukanovic I, Rendl F. Copositive programming motivated bounds on the stability and the chromatic numbers [J]. Mathematical Programming, 2010, 121(2): 249-268.
[11] Gühne O, Toth G. Entanglement detection [J]. Physics Reports, 2009, 474(1-6): 1-75.
[12] Gvozdenović N, Laurent M. The operator Ψ for the chromatic number of a graph [J]. SIAM Journal on Optimization, 2008, 19(2): 572-591.
[13] Zhou A, Fan J. The CP-matrix completion problem [J]. SIAM Journal on Matrix Analysis and Applications, 2014, 35(1): 127-142.
[14] Dahl G, Leinaas J M, Myrheim J, et al. A tensor product matrix approximation problem in quantum physics [J]. Linear Algebra and its Applications, 2007, 420(2-3): 711-725.
[15] Werner R F. Quantum states with Einstein-Podolsky-Rosen correlations admitting a hiddenvariable model [J]. Physical Review A, 1989, 40(8): 4277-4281.
[16] Gharibian S. 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] Qi L, Dai H, Han D. Conditions for strong ellipticity and M-eigenvalues [J]. Frontiers of Mathematics in China, 2009, 4(2): 349-364.
[19] Doherty A C, Parrilo P A, Spedalieri F M. Complete family of separability criteria [J]. Physical Review A, 2004, 69(2): 022308.
[20] Gurvits L, Barnum H. Largest separable balls around the maximally mixed bipartite quantum state [J]. Physical Review A, 2002, 66(6): 062311.
[21] Horodecki R, Horodecki P, Horodecki M, et al. Quantum entanglement [J]. Reviews of Modern Physics, 2009, 81(2): 865-942.
[22] Nie J, Zhang X. Positive maps and separable matrices [J]. SIAM Journal on Optimization, 2016, 26(2): 1236-1256.
[23] Putinar M. Positive polynomials on compact semi-algebraic sets [J]. Indiana University Mathematics Journal, 1993, 42(3): 969-984.
[24] Nie J. Optimality conditions and finite convergence of Lasserre’s hierarchy [J]. Mathematical Programming, 2014, 146(1-2): 97-121.
[25] Lasserre J 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] Nie J. Moment and Polynomial Optimization [M]. Philadelphia: Society for Industrial and Applied Mathematics, 2023.
[28] Curto R, Fialkow L. Truncated K-moment problems in several variables [J]. Journal of Operator Theory, 2005, 54(1): 189-226.
[29] Nie J. The A-truncated K-moment problem [J]. Foundations of Computational Mathematics, 2014, 14(6): 1243-1276.
[30] Nie J. Certifying convergence of Lasserre’s hierarchy via flat truncation [J]. Mathematical Programming, 2013, 142(1-2): 485-510.
[31] Nie J. Linear optimization with cones of moments and nonnegative polynomials [J]. Mathematical Programming, 2015, 153(1): 247-274.
[32] Henrion D, Lasserre J B, Loefberg J. GloptiPoly 3: Moments, optimization and semidefinite programming [J]. Optimization Methods and Software, 2009, 24(4-5): 761-779.
[33] Sturm J 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] Demmel J W. Applied Numerical Linear Algebra [M]. Philadelphia: Society for Industrial and Applied Mathematics, 1997.
[35] Golub G H, Van Loan, Charles F. 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.