The completely positive and doubly nonnegative completion problems

DOI10.1080/03081089808818550MaRDI QIDQ4208353zbMATH OpenOpenAlexFDO

Authors John H. Drew, Charles R. Johnson

Publication date 28 April 1999

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/03081089808818550

zbMATH Keywords

chordal graphcompletely positive matrixcompletion problemsdoubly-nonnegative matrixsymmetric matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48)

Review text

A real symmetric matrix is called doubly-nonnegative (DN) if it is both positive semidefinite and has nonnegative entries; it is called completely positive (CP) if it can be written in the form \(BB^{T}\) where \(B\) is a rectangular matrix with nonnegative entries. Let \(A\) be an \(n\times n\) partial symmetric matrix where some of the entries are unspecified, and let \(G(A)\) be the graph with vertex set \(\{ 1,2,\dots,n\} \) and edges \((i,j)\) for those pairs where the \((i,j)\)th entry of \(A\) is specified. Suppose that every fully specified principal submatrix of \(A\) is (DN) (respectively, (CP)). Then the authors show that \(A\) can be completed to a (DN) (respectively, (CP)) matrix if and only if \(G(A)\) is a block clique graph (that is, a chordal graph in which every pair of maximal cliques intersect in at most one vertex).

Recommendations

• The cycle completable graphs for the completely positive and doubly nonnegative completion problems
• The doubly negative matrix completion problem
• The CP-matrix completion problem

Cites work

• Bipartite completely positive matrices
• Completely positive matrices associated withM-matrices
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Nonnegative factorization of completely positive matrices
• Nonnegative factorization of positive semidefinite nonnegative matrices
• Positive definite completions of partial Hermitian matrices

Cited in

(21)

• Sub-direct sums and positivity classes of matrices
• \(P\)-matrix completions under weak symmetry assumptions
• The cycle completable graphs for the completely positive and doubly nonnegative completion problems
• Note on subdirect sums of \(\{i_0\}\)-Nekrasov matrices
• Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems
• Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures
• Linearly constrained positive definite completions
• The integer cp-rank of \(2 \times 2\) matrices
• SPN completable graphs
• The CP-matrix completion problem
• Adjacent edge conditions for the totally nonnegative completion problem
• Critical Graphs for the Positive Definite Completion Problem
• Completely positive matrices associated withM-matrices
• scientific article; zbMATH DE number 1182570 (Why is no real title available?)
• The real positive definite completion problem: cycle completability
• Note on subdirect sums of SDD(p) matrices
• Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization
• Conic optimization techniques yield sufficient conditions for set-completely positive matrix completion under arrowhead specification pattern
• The symmetric M-matrix and symmetric inverse M-matrix completion problems
• A survey of totally positive matrix completion problems
• The totally positive completion problem: the 3-by-n case

This page was built for publication: The completely positive and doubly nonnegative completion problems

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