CRITICAL GRAPHS FOR THE POSITIVE-DEFINITE COMPLETION PROBLEM

Among various matrix completion problems that have been considered in recent years, the positive definite completion problem seems to have r eceived the most attention. Indeed, in addition to being a problem of great interest, it is related to various applications as well as other completion problems. It may also be viewed as a fundamental problem i n Euclidean geometry. A partial positive definite matrix A is ''critic al'' if A has no positive definite completion, though every proper pri ncipal submatrix does. The graph G is called critical for the positive definite completion problem if there is a critical partial positive d efinite matrix A, the graph of whose specified entries is G. Complete analytical understanding of the general positive definite completion p roblem reduces to understanding the problem for critical graphs. Thus, it is important to try to characterize such graphs. The first, crucia l step toward that understanding is taken here. A novel and restrictiv e topological graph theoretic condition necessary for criticality is i dentified. The condition, which may also be of interest on pure graph theoretic grounds, is also shown to be sufficient for criticality of g raphs on fewer than 7 vertices, and the authors suspect it to be suffi cient in general. In any event, the condition, which may be efficientl y verified, dramatically narrows the class of graphs for which complet ability conditions on the specified data are needed. The concept of cr iticality and the graph theoretic condition extend to other completion problems, such as that for Euclidean distance matrices.