TY - JOUR
T1 - A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices
AU - Kakimura, Naonori
PY - 2010/10/1
Y1 - 2010/10/1
N2 - Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al.
AB - Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al.
KW - Chordal graphs
KW - Matrix completion problem
KW - Positive semidefinite matrices
UR - http://www.scopus.com/inward/record.url?scp=77953133068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953133068&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2010.04.012
DO - 10.1016/j.laa.2010.04.012
M3 - Article
AN - SCOPUS:77953133068
SN - 0024-3795
VL - 433
SP - 819
EP - 823
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
IS - 4
ER -