Graph theoretic methods for matrix completion problems

By Leslie Hogben. 2001

58 citations recorded by the source corpus.

Abstract A pattern is a list of positions in an n×n real matrix. A matrix completion problem for the class of Π -matrices asks whether every partial Π -matrix whose specified entries are exactly the positions of the pattern can be completed to a Π -matrix. We survey the current state of research on Π -matrix completion problems for many subclasses Π of P 0 -matrices, including positive definite matrices, M-matrices, inverse M-matrices, P-matrices, and matrices defined by various sign symmetry and positivity conditions on P 0 - and P-matrices. Graph theoretic techniques used to study completion problems are discussed. Several new results are also presented, including the solution to the M 0 -matrix completion problem and the sign symmetric P 0 -matrix completion problem.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/378dc7eff5c41a3e5f3d86a4f58dbfa96f36e4df