The symmetric \(N\)-matrix completion problem (Q2566765)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The symmetric \(N\)-matrix completion problem |
scientific article |
Statements
The symmetric \(N\)-matrix completion problem (English)
0 references
28 September 2005
0 references
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.
0 references
partial matrix
0 references
N-matrix
0 references
completion problem
0 references
undirected graph
0 references