The symmetric \(N\)-matrix completion problem (Q2566765)

A real \(n\times n\) matrix is called an \(N\)-matrix if all its principal minors are negative. Consider a partial symmetric matrix \(A\) where some entries are unspecified. The problem under consideration is whether it is possible to determine these unspecified entries in such a way that the resulting fully specified symmetric matrix is an \(N\)-matrix. Clearly a necessary condition is that \(A\) is a partial \(N\)-matrix; that is, every fully specified principal submatrix of \(A\) is an \(N\)-matrix. Now assume that \(A=\left[ a_{ij}\right] \) is a partial symmetric \(N\)-matrix in which all diagonal entries are specified (and are necessarily negative) and that \(a_{ij}\) is specified whenever \(a_{ji}\) is (necessarily \(a_{ij}=a_{ji}\)). Let \(G\) be the incidence graph associated with \(A\): \(G\) has vertex set \(V:=\{ 1,2,\dots ,n\} \) and an edge between \(i\) and \(j\) (with \(i\neq j\)) if and only if \(a_{ij}\) is specified. This graph is called chordal if every cycle of length at least \(4\) has a chord. The main theorem of this paper shows that, if the graph \(G\) is connected and chordal, then this is a sufficient condition for \(A\) to have a completion to a symmetric \(N\)-matrix. The final section of the paper considers particular examples of partial matrices of special forms and gives more precise criteria for these to have completions to symmetric \(N\)-matrices.