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]:

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

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 *t *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:

## Recent Comments