A proof on 3-by-3 border pattern TP completability

Hi! My project in this summer is to prove whether a partial matrix with certain pattern is completable or not. In this blog, I will prove that a 3-by-3 matrix with only center entry unspecified is  TP completable. I will also introduce one principle and one lemma that will help build my proofs in the next blog.

Before I get to proofs, I would like to introduce some terminologies used during the proof [1]:

  • minor in a given matrix A is the determinant of a square submatrix of A.
  • A matrix in which all minors are positive is called a totally positive matrix and a matrix in which all minors are nonnegative is called a totally nonnegative matrix.
  • A matrix is partial if some of its entries are specified, while the remaining, unspecified, entries are free to be chose.
  • A partial matrix is called partial TP (TN) if each of its fully specified submatrices is TP (TN).

In addition, if you want to now more about determinant and how to calculate it, please follow this link:

https://en.wikipedia.org/wiki/Determinant

We start by proving that a 3-by-3 partial matrix with only center entry unspecified is TN or TP completable. Consider the following matrix, where x represents the unspecified entry.

1

In order to have a TP completion, four strict inequalities from 2-by-2 minor and one strict inequality from the determinant have to be satisfied simultaneously. The inequality has the form:

2

Through the inequalities among specified entries, the inequality can be simplified to the following form:3

The inequalities among specified entries will guarantee the interval above exists. Choosing any value from this interval will yield a TP completion.  This will finish the proof. I will include all the steps at the end of this blog in case anyone wants to check.

 

Before this blog ends, I want to introduce a principle and a lemma that I will use for my proofs in the next blog. The principle  I am going to introduce is called Northwest Principle. I will call the lemma Lemma 1 (because I cannot come up with any good names). The principle and lemma will become very useful as I build by proof for 3-by-n TN completability in the next blog.

Northwest Principle:  Suppose we have a 2-by-2 partial TN matrix and its (1,1) entry, represented by x here, is unspecified.

7

The Northwest principle tells us that to fill x with the minimum value between a and b such that x=min{a,b}. I will show in my next blog how this principle can be applied to complete a partial TN matrix with a border pattern.

Lemma 1: (1,1) AND (m,n) entries

Given a m-by-n TN (TP) matrix:

8

We can increase entries at (1,1) and (m,n) such that the matrix will still be TN (TP). This means if a small value at (1,1) or (m,n) finishes a TN or TP completion, then any value greater than t will also yield a TN or TP completion.

I will show in my next blog how these two principles can be applied to complete a partial TN matrix with a border pattern. Thank you for reading my blog! See you!

 

Steps for 3-by-3 TP completability:

9