penultimate line insertion

In this post, I will describe the penultimate line insertion method derived from a paper by S.M. Fallat, C.R. Johnson and Ronald L. Smith. This step is important because it will eventually help us show that a partial TP matrix with a border pattern is TP completable.

We first cite a theorem from S.M. Fallat et al. (2000).

Theorem: Let A be an m-by-n partial TP matrix in which 4<=m<=n and in which the only unspecified entry lies in the (s,t) position. Any such A has a TP completion if and only if s+t<=4 or s+t>=m+n-2.

We show that it is possible to insert a line that has two specified entries t the second or the penultimate row (with entries at two ends specified) of a m-by-n TP matrix. We will that 3-by-n case in the later document (with similar idea). Here we prove that such line insertion is also possible for a m-by-n matrix, where m and n are both greater than 3.

We will show an example of inserting at the second row. The two entreis specified here are a_{2,1} and a_{2,n}.

1

We will show later that the second row is TP completable from the 3-by-n case. Starting from the third row, we complete one row each time and complete its entries from left to right. Notice that the number of rows concerned is greater than or equal to four, so we can apply the theorem cited above.

Each time we will complete one unspecified entry. The entries of the second have been specified so we start from the third row.

2

The (3,2) entry is TP completable by the theorem because it is positioned at the (3,2) entry of the submatrix composed of rows 1, 2, 3 and n and columns 1, 2 and n. The (3,3) entry can be completed in the similar way after we completed (3,2) entry because it is positied at the (3,3) entry of the submatrix composed of row 1, 2, 3 and n and columns 1, 2, 3 and n. In general the (s,t) entry, (3<s<m-1, 2<t<n-1), is TP completable becuase it can be seen as the (s,t) entry of the usbmatrix that contains all rows whose indexes are smaller or equal to s and all columns whose indexes are smaller or equal to t. Such submatrix has size (s+1)-by-(t+1) and has the only unspecified entry at (s,t). By the theorem, the submatrix is TP completalbe. This theorem can be applied to all unspecified entries from the third to the (n-1)th row. Thus a partial TP matrix with the border pattern is TP completable.

  • Fallat, Shaun M., Charles R. Johnson, and Ronald L. Smith. “The general totally positive matrix completion problem with few unspecified entries.”Electron. J. Linear Algebra 7 (2000): 1-20.