Non-chordal patterns associated with the positive definite completion problem

Abstract

A partial matrix, is a matrix for which some entries are specified and some unspecified. In general completion problems ask whether a given partial matrix, may be completed to a matrix where all the entries are specified, such that this completion admits a specific structure. The positive definite completion problem asks whether a partial Hermitian matrix admits a completion such that the completed matrix is positive semidefinite. The minimum solution criterion, is that every fully specified principal submatrix is nonnegative. Then the set of partial Hermitian matrices, which admit a positive semidefinite completion, forms a convex cone, and its dual cone can be identified as the set of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G: Furthermore, the set of partial Hermitian matrices, with non-negative fully specified principal minors, also forms a convex cone, and its dual cone can be identified as the set of positive semidefinite Hermitian matrices which can be written as the sum of rank one matrices, with underlying graph G. Consequently, the problem reduces to determining when these cones are equal. Indeed, we find that this happens if and only if the underlying graph is chordal. It then follows that the extreme rays of the cone of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G is generated by rank one matrices. The question that arises, is what happens if the underlying graph is not chordal. In particular, what can be said about the extreme rays of the cone of positive semidefinite matrices with some non-chordal pattern. This gives rise to the notion of the sparsity order of a graph G; that is, the maximum rank of matrices lying on extreme rays of the cone of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non- edges in the graph G: We will see that those graphs having sparsity order less than or equal to 2 can be fully characterized. Moreover, one can determine in polynomial time whether a graph has sparsity order less than or equal to 2, using a clique-sum decomposition. We also show that one can determine whether a graph has sparsity order less than or equal to 2, by considering the characteristic polynomial of the adjacency matrix of certain forbidden induced subgraphs and comparing it with the characteristic polynomial of principal submatrices of appropriate size.