Completion of partial matrices to contractions (Q580679)

The main result of this paper solves completely the following problem: Which patterns for the specified entries of a partial contraction guarantee completability of a contraction? More precisely, an \(n\times m\) complex matrix in which some entries are not yet specified is called a partial contraction if each submatrix consisting entirely of specified entries is a contraction. The problem asks for patterns for the specified entries so that for each partial contraction with this pattern there is a specification of the unspecified entries resulting in a conventional matrix which is a contraction. The problem arises in different contexts including engineering control problems and the study of nest algebras, and some partial results have been obtained before. In the ``generic'' situation, a necessary and sufficient condition for this to occur for an \(n\times m\) pattern P is that P be, up to permutations of rows and/or columns, of the form \[ \left[\begin{matrix} B_{11} &?&?&...&? \\ B_{21} & B_{22} &?&...&? \\ \vdots & \vdots & \ddots & \ddots& \vdots \\ B_{p1} & B_{p2} & ... &&B_{pp} \end{matrix}\right] \] where the (possibly rectangular) blocks \(B_{ij}\) (i\(\geq j)\) consist entirely of specified entries. In graph- theoretic terminology, this says that certain (undirected) bipartite graph associated with P is chordal when some edges are added to it. This problem is closely related to that of the completion of partitional positive (semi)-definite Hermitian matrices which was solved earlier by C. R. Johnson et al.