Charles Johnson
College of William & Mary

Matrix Completion Problems

Abstract: A "partial matrix" is a rectangular array in which some entries are specified and the rest are free to be chosen from an agreed upon set (usually a field). A completion of a partial matrix is a choice of values for the unspecified entries, resulting in a conventional matrix. A matrix completion problem asks which partial matrices have a completion with a desired property (eg positive definite, a certain rank, total nonnegativity, etc). Often the focus is upon a given pattern for the specified entries and what are the conditions on the specified data that guarantee the existence of a completion of desired type. We survey early and recent work on matrix completion problems, some general results and some of the combinatorial results that have arisen.