# 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).

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.

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:

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

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.

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:

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: