Some exact distance constants (Q1336395)

The general matrix filling problem is this: given a partially completed matrix, fill in the remaining entries so that the norm of the resulting complete matrix is minimized. In general, a pattern for the fixed entries is given. This is related to problems of approximating general matrices by matrices in some algebra. The maximum of the norms of all complete rectangular subarrays of the partial matrix provides an obvious lower bound for the norm of the completed matrix. The problem is to determine the greatest (or worst case) ratio of the minimal completion norm to this lower bound. This ratio is known as the distance constant for the given pattern. The authors compute the distance constants for various patterns of size up to \(4 \times 4\) and show that in most cases these values are the same when each is replaced by a block of arbitrary size.