Completions of P-Matrix Patterns

Abstract:  A list of positions in an n n real matrix (a pattern) is said to have P-completion if every partial P-matrix that specifies exactly these positions can be completed to a P-matrix. We extend work of Johnson and Kroschel [JK] by proving a larger class of patterns has P- completion, including any 4 4 pattern with eight or fewer off-diagonal positions. We also show that any pattern whose digraph contains a minimally chordal symmetric-Hamiltonia n induced subdigraph does not have P-completion. AMS Subject Classification: 15A48 Keywords: matrix completion, P-matrix, pattern, digraph, Hamiltonian 1. Introduction A partial matrix is a matrix in which some entries are specified and others are not. A completion of a partial matrix is a specific choice of values for the unspecified entries. A pattern for n n matrices is a list of positions of an n n matrix. A partial matrix specifies the pattern if its specified entries are exactly those listed in the pattern. A matrix completion problem fo...