Border pattern TN completion

In this blog, I will show that a m-by-n partial Tn matrix with a border pattern can be completed to a TN matrix. I will use the Northwest principle and Lemma 1 from the previous blog.

The partial TN matrix has the following form:

1

And I will show it is TN completable following three steps:

Step 1: From the lower-right corner, we complete a row or column each time to get a TN completion. In order to achieve, it requires us to specify 1) the value chosen for the unspecified entry and 2) the direction following which we complete a row or column. The choice of unspecified entry will follow the Northwest principle, where we choose the smaller one between two off-diagonal entries. The direction will also decided by the off-diagonal entries: if the lower-left entry is smaller than the upper-right entry, we complete the row; if the lower-left entry is greater than the upper-right entry, we complete the column. Here are two cases:

  1. lower-left entry is smaller than the upper-right entry:2
  2. upper-right entry is smaller than the lower-left entry:3

Step 2: Observe that besides the last entry of the completed row or column, other entries are forced to be the same as those in the adjacent entries through determinant inequalities. Now following Lemma 1, we can reduce the (m,n) entry to let it be the same as the smaller one between the upper-right entry and the lower-left entry. Discarding one copy will shrink the size of the matrix to (m-1)-by-n or m-by-(n-1). By Lemma 1, if there is a TN completion for the smaller matrix, there will be a TN completion for the larger matrix.

Step 3: Repeat step 1 and step 2. The matrix can be shrunk into a 3-by-n partial TN matrix with border patterns. This pattern can also be shown to be TN-completable following the same Northwest principle (I will discuss this proof in my later blog). Thus there exist a TN completion for m-by-n partial TN matrix with the border pattern.

 

These three-step proof shows that a border-pattern partial TN matrix is TN completable. A inductive reasoning is essential in this proof. Later I will show how the same pattern is also TP completable. The proof is vastly different because in TN cases small minors can be forced to zero whereas in TP cases one must keep them all positive.

Thank you for reading!