The elliptic matrix completion problem

Completions of partial elliptic matrices are studied. Given an undirected graph G, it is shown that every partial elliptic matrix with graph G can be completed to an elliptic matrix if and only if the maximal cliques of G are pairwise disjoint. Further, given a partial elliptic matrix A with undirected graph G, it is proved that if G is chordal and each specified principal submatrix defined by a pair of intersecting maximal cliques is nonsingular, then A can be completed to an elliptic matrix. Conversely, if G is nonchordal or if the regularity condition is relaxed, it is shown that there exist partial elliptic matrices which are not completable to an elliptic matrix. In the process we obtain several results concerning chordal graphs that may be of independent interest.