A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

DOI10.1016/J.LAA.2010.04.012MaRDI QIDQ979016zbMATH OpenOpenAlexFDO

Authors Naonori Kakimura

Publication date 25 June 2010

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

Full work available at URL https://doi.org/10.1016/j.laa.2010.04.012

zbMATH Keywords

chordal graphsmatrix completion problempositive semidefinite matricesrank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03) Factorization of matrices (15A23) Matrix completion problems (15A83) Positive matrices and their generalizations; cones of matrices (15B48)

Review text

The paper deals with the matrix decomposition of chordal-structured positive semidefinite matrices. An undirected graph \(G\) is chordal if every cycle of length at least four has a chord. \textit{J. Agler, W. Helton, S. McCullough} and \textit{L. Rodman} [Linear Algebra Appl. 107, 101--149 (1988; Zbl 0655.15016)] proved that a graph \(G\) is chordal if and only if any positive semidefinite symmetric matrix, whose nonzero entries are specified by \(G\), can be decomposed as a sum of positive semidefinite matrices corresponding to the maximal cliques of \(G\). In this paper, the author shows an alternative proof of this result using simple linear algebra, which allows to impose an additional rank condition on positive semidefinite matrices obtained by the decomposition. In addition, the author presents a new proof, via duality theory, of the well-known characterization for positive semidefinite matrix completion of a chordal-structured matrix due to \textit{R. Grone, C. R. Johnson, E. M. Sá} and \textit{H. Wolkowicz} [Linear Algebra Appl. 58, 109--124 (1984; Zbl 0547.15011)].

Recommendations

• Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming
• The positive definite completion problem revisited
• The positive definite completion problem relative to a subspace
• Matrices attaining the minimum semidefinite rank of a chordal graph
• Matrix completions and chordal graphs

Cites work

• Cuts, matrix completions and graph rigidity
• Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
• scientific article; zbMATH DE number 4158856 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 3365044 (Why is no real title available?)
• On the sparsity order of a graph and its deficiency in chordality
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrices with a given sparsity pattern

Cited in

(11)

• Decomposed structured subsets for semidefinite and sum-of-squares optimization
• Decomposition of arrow type positive semidefinite matrices with application to topology optimization
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Matrices attaining the minimum semidefinite rank of a chordal graph
• Sparse matrix decompositions and graph characterizations
• Sparse polynomial optimisation for neural network verification
• Cholesky decomposition of a positive semidefinite matrix with known kernel
• Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
• The positive definite completion problem revisited
• Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

This page was built for publication: A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

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