WEDGE LEMMA

JIM MORROW

(1) Let

[\begin{matrix}x & y \\ a & b \\ c & d \end{matrix}]

be a TNN matrix. Suppose that

x > 0, |\begin{matrix}a & b \\ c & d \end{matrix}| > 0

Then

|\begin{matrix}x & y \\ c & d \end{matrix}| > 0

Proof. (This is the first step in the proof of the wedge lemma.) By the principal minor theorem, a > 0, b > 0. Also c ≥ 0. The following string of inequalities constitutes the proof.

d > \frac{cb}{a} ≥ \frac{cy}{x}

The following statements are proved in a similar fashion.

(a) Let

[\begin{matrix}x & a & b \\ y & c & d \end{matrix}]

be TNN and suppose that

x > 0, |\begin{matrix}a & b \\ c & d \end{matrix}| > 0

Then

|\begin{matrix}x & b \\ y & d \end{matrix}| > 0

2 JIM MORROW

(b) Let

[\begin{matrix}x & a & b \\ y & c & d \end{matrix}]

be TNN and suppose that

d > 0, |\begin{matrix}x & a \\ y & c \end{matrix}| > 0

Then

|\begin{matrix}x & b \\ y & d \end{matrix}| > 0

(c) Let

[\begin{matrix}x & a & b & u \\ y & c & d & v \end{matrix}]

be TNN and suppose that

x > 0, v > 0, |\begin{matrix}a & b \\ c & d \end{matrix}| > 0

Then

|\begin{matrix}x & u \\ y & v \end{matrix}| > 0

(2) Let

[\begin{matrix}x & y & z \\ u & a & b \\ v & c & d \end{matrix}]

be TNN and suppose that

x > 0, |\begin{matrix}a & b \\ c & d \end{matrix}| > 0

Then

|\begin{matrix}x & z \\ v & d \end{matrix}| > 0

Proof. If vz = 0, then the result is a consequence of the principal minor theorem. So suppose that vz ≠ 0. From uc − av ≥ 0 it follows that uc ≠ 0. Similarly yb ≠ 0 and all of the entries of the matrix are hence positive. We have

d > \frac{bc}{a} ≥ \frac{zc}{y}

Now we can apply (a) above to the matrix

[\begin{matrix}x & y & z \\ v & c & d \end{matrix}]

(3) Let

[\begin{matrix}x & y & z & w \\ u & a & b & r \\ v & c & d & s \\ e & f & g & h \end{matrix}]

be TNN and suppose that

x > 0, h > 0, |\begin{matrix}a & b \\ c & d \end{matrix}| > 0

Then

|\begin{matrix}x & w \\ e & h \end{matrix}| > 0

Proof. From (2) it follows that ah − rf > 0. Then apply (2) to the matrix

[\begin{matrix}x & y & w \\ u & a & r \\ e & f & h \end{matrix}]

to get xh − ew > 0.

(4) Let

[\begin{matrix}x & Y & z \\ d & E & f \\ U & C & V \\ r & S & t \end{matrix} ]

be TNN and suppose that

x > 0, |\begin{matrix}d & E & f \\ U & C & V \\ r & S & t \end{matrix} | > 0

Then

|\begin{matrix}x & Y & z \\ U & C & V \\ r & S & t \end{matrix} | > 0

Proof. By the principal minor theorem

|C| > 0, |\begin{matrix}C & V \\ S & t \end{matrix} | > 0, |\begin{matrix}d & E \\ U & C \end{matrix}| > 0

By induction,

|\begin{matrix}x & Y \\ U & C \end{matrix}| > 0

By the six-term identity, we want to show that

|\begin{matrix}x & Y \\ U & C \end{matrix}| |\begin{matrix}C & V \\ S & t \end{matrix} | − |\begin{matrix}Y & z \\ C & V \end{matrix} | |\begin{matrix}U & C \\ r & S \end{matrix}| > 0

If

|\begin{matrix}Y & z \\ C & V \end{matrix} | |\begin{matrix}U & C \\ r & S \end{matrix}| = 0

we are done. So assume that

|\begin{matrix}Y & z \\ C & V \end{matrix} | |\begin{matrix}U & C \\ r & S \end{matrix}| > 0

The assumption, the six-term identity and the above statements imply that

\begin{matrix}| & \begin{matrix}C & V \\ S & t \end{matrix} & | \\ | & \begin{matrix}U & C \\ r & S \end{matrix} & | \end{matrix} > \begin{matrix}| & \begin{matrix}E & f \\ C & V \end{matrix} & | \\ | & \begin{matrix}d & E \\ U & C \end{matrix} & | \end{matrix}

Since the matrix is TNN,

\begin{matrix}| & \begin{matrix}E & f \\ C & V \end{matrix} & | \\ | & \begin{matrix}d & E \\ U & C \end{matrix} & | \end{matrix} ≥ \begin{matrix}| & \begin{matrix}Y & z \\ C & V \end{matrix} & | \\ | & \begin{matrix}x & Y \\ U & C \end{matrix} & | \end{matrix}

(5) Let

A = [\begin{matrix}x & l & Y & z \\ d & m & E & f \\ U & N & C & V \\ r & o & S & t \end{matrix} ]

be TNN and suppose that

x > 0, |\begin{matrix}m & E & f \\ N & C & V \\ o & S & t \end{matrix} | > 0

Then

|\begin{matrix}x & Y & z \\ U & C & V \\ r & S & t \end{matrix} | > 0

Proof. By the principal minor theorem

|C| > 0, |\begin{matrix}C & V \\ S & t \end{matrix} | > 0, |\begin{matrix}m & E \\ N & C \end{matrix}| > 0

By induction,

|\begin{matrix}x & Y \\ U & C \end{matrix}| > 0

By the six-term identity, we want to show that

|\begin{matrix}x & Y \\ U & C \end{matrix}| |\begin{matrix}C & V \\ S & t \end{matrix} | − |\begin{matrix}Y & z \\ C & V \end{matrix} | |\begin{matrix}U & C \\ r & S \end{matrix}| > 0

If

|\begin{matrix}Y & z \\ C & V \end{matrix} | |\begin{matrix}U & C \\ r & S \end{matrix}| = 0

6 JIM MORROW

we are done. So assume that

|\begin{matrix}Y & z \\ C & V \end{matrix} | |\begin{matrix}U & C \\ r & S \end{matrix}| > 0

Since the given matrix is TNN,

|\begin{matrix}d & E \\ U & C \end{matrix}| |\begin{matrix}N & C \\ o & S \end{matrix}| − |\begin{matrix}m & E \\ N & C \end{matrix}| |\begin{matrix}U & C \\ r & S \end{matrix}| ≥ 0

Since

|\begin{matrix}m & E \\ N & C \end{matrix}| |\begin{matrix}U & C \\ r & S \end{matrix}| > 0

it follows that

|\begin{matrix}d & E \\ U & C \end{matrix}| |\begin{matrix}N & C \\ o & S \end{matrix}| > 0

By assumption and by the above

|\begin{matrix}C & V \\ S & t \end{matrix} | > \begin{matrix}|\begin{matrix}E & f \\ C & V \end{matrix} | & |\begin{matrix}N & C \\ 0 & S \end{matrix}| \\ | & \begin{matrix}m & E \\ N & C \end{matrix} & | \end{matrix} ≥ \begin{matrix}|\begin{matrix}E & f \\ C & V \end{matrix} | & |\begin{matrix}U & C \\ r & S \end{matrix}| \\ | & \begin{matrix}d & E \\ U & C \end{matrix} & | \end{matrix}

Alternate proof of (5) by induction and Schur complement: Proof. By the principal minor theorem and by induction

t > 0, |\begin{matrix}x & z \\ r & t \end{matrix}| > 0

Take the Schur complement of A with respect to t to get a TNN matrix

Â = [\begin{matrix}x̂ & l̂ & Ŷ \\ d̂ & m̂ & Ê \\ Û & N̂ & Ĉ \end{matrix}]

with

x̂ > 0, |\begin{matrix}m̂ & Ê \\ N̂ & Ĉ \end{matrix}| > 0

By induction,

|\begin{matrix}x̂ & Ŷ \\ Û & Ĉ \end{matrix}| > 0

WEDGE LEMMA 7

and hence

|\begin{matrix}x & Y & z \\ U & C & V \\ r & S & t \end{matrix} | > 0

(6) Let

A = [\begin{matrix}x & y & z \\ u & a & b \\ v & c & d \\ e & f & g \end{matrix}]

be TNN and suppose that

|\begin{matrix}x & y \\ u & a \end{matrix}| > 0, |\begin{matrix}u & a & b \\ v & c & d \\ e & f & g \end{matrix}| > 0

Then

|\begin{matrix}x & y & z \\ u & a & b \\ e & f & g \end{matrix}| > 0

Proof. Let

[\begin{matrix}x̂ & ẑ \\ v̂ & d̂ \\ ê & ĝ \end{matrix}]

be the Schur complement of A with respect to a. Then

x̂ > 0, |\begin{matrix}v̂ & d̂ \\ ê & ĝ \end{matrix}| > 0

By (1),

|\begin{matrix}x̂ & ẑ \\ ê & ĝ \end{matrix}| > 0

Hence

|\begin{matrix}x & y & z \\ u & a & b \\ e & f & g \end{matrix}| > 0

(7) Let

A = [\begin{matrix}a & b & c & d & e \\ f & g & h & i & j \\ k & l & m & n & o \\ p & q & r & s & t \\ u & v & w & x & y \end{matrix}]

be TNN. Suppose that

|\begin{matrix}a & b \\ f & g \end{matrix}| > 0, |\begin{matrix}m & n & o \\ r & s & t \\ w & x & y \end{matrix}| > 0

Then

|\begin{matrix}a & b & e \\ f & g & j \\ u & v & y \end{matrix}| > 0

Proof. Let

Â = [\begin{matrix}ĝ & ĥ & î & ĵ \\ l̂ & m̂ & n̂ & ô \\ q̂ & r̂ & ŝ & t̂ \\ v̂ & ŵ & x̂ & ŷ \end{matrix}]

be the Schur complement of A with respect to a. Then Â is a TNN matrix. From

|\begin{matrix}a & b \\ f & g \end{matrix}| > 0, |\begin{matrix}a & d & e \\ p & s & t \\ u & x & y \end{matrix}| > 0

it follows that

ĝ > 0, |\begin{matrix}ŝ & t̂ \\ x̂ & ŷ \end{matrix}| > 0

Hence

|\begin{matrix}ĝ & ĵ \\ v̂ & ŷ \end{matrix}| > 0

and thus

|\begin{matrix}a & b & e \\ f & g & j \\ u & v & y \end{matrix}| > 0

WEDGE LEMMA 9

(8) Let

A = [\begin{matrix}a & B & c & D & E \\ F & G & H & I & J \\ k & L & m & N & O \\ P & Q & R & S & T \\ U & V & W & X & Y \end{matrix}]

be TNN, where the capital letters represent matrices. Suppose that

|\begin{matrix}a & B \\ F & G \end{matrix}| > 0, |\begin{matrix}m & N & O \\ R & S & T \\ W & X & Y \end{matrix}| > 0

Then

|\begin{matrix}a & B & E \\ F & G & J \\ U & V & Y \end{matrix}| > 0

Proof. Let

Â = [\begin{matrix}Ĝ & Ĥ & Î & Ĵ \\ L̂ & m̂ & N̂ & Ô \\ Q̂ & R̂ & Ŝ & T̂ \\ V̂ & Ŵ & X̂ & Ŷ \end{matrix}]

be the Schur complement of A with respect to a. Then Â is a TNN matrix. From

|\begin{matrix}a & B \\ F & G \end{matrix}| > 0, |\begin{matrix}a & D & E \\ P & S & T \\ U & X & Y \end{matrix}| > 0

it follows that

Ĝ > 0, |\begin{matrix}Ŝ & T̂ \\ X̂ & Ŷ \end{matrix}| > 0

Hence

|\begin{matrix}Ĝ & Ĵ \\ V̂ & Ŷ \end{matrix}| > 0

and thus

|\begin{matrix}a & B & E \\ F & G & J \\ U & V & Y \end{matrix}| > 0

(9) Let

[\begin{matrix}x & y & z & w \\ u & a & b & r \\ v & c & d & s \\ e & f & g & h \end{matrix}]

be TNN, where now all letters represent matrices, and suppose that

|x| > 0, |h| > 0, |\begin{matrix}a & b \\ c & d \end{matrix}| > 0

Then

|\begin{matrix}x & w \\ e & h \end{matrix}| > 0

Proof. From (8) it follows that

|\begin{matrix}a & r \\ f & h \end{matrix}| > 0

Next apply (8) to the TNN matrix

[\begin{matrix}x & y & w \\ u & a & r \\ e & f & h \end{matrix}]

to get

|\begin{matrix}x & w \\ e & h \end{matrix}| > 0

(10) Notation. If X and Y are k-tuples of positive integers, X ≤ Y will mean x_{j} ≤ y_{j}, j = 1, ⋯, k. X_{k} will denote the first k elements of X and X^{k} will denote the last k elements of X. Let N be an matrix. (A, B) will denote the submatrix N(A, B) and (A, B) > 0 will mean |N(A, B)| > 0. (A, B) ≤ (C, D) will mean A ≤ C, B ≤ D.

Theorem 0.1. (Ingerman’s wedge lemma) Suppose N is a TNN matrix and (A, B) is an n×n submatrix with (A, B) > 0. Let (P, Q), (R, S) be submatrices of size k × k and m × m respectively, where k + m ≤ n. Suppose that (P, Q) > 0, (R, S) > 0, (P, Q) ≤ (A_{k}, B_{k}), (A^{m}, B^{m}) ≤ (R, S). Then (P +R, Q+S) > 0.

Proof. Without loss of generality we may assume that n = k + m. As in (9), By working with the blocks E = (P, Q) and F = (R, S) separately we may assume that (R, S) = (A^{m}, B^{m}). The proof will now be a minor modification of the proof of (8). Let a = (p_{1}, q_{1}) be the upper left entry of (P, Q). Then p_{1} ≤ a_{1}, q_{1} ≤ b_{1}. (If both of these are equalities there is nothing to prove, so assume that a is not an entry of (A, B).) Now take the Schur complement of N with respect to a to get a TNN matrix N̂. The matrix Ê will be (k−1)×(k−1) and Ê > 0. The matrix F̂ will be m × m and F̂ > 0. (This notation is a little bit off but I think it is clear.) Finally let G = (A^{n−1}, B^{n−1}). Then Ĝ > 0 by (5). We have reduced the size of the matrix (P, Q) and preserved the hypothesis. By induction the result is true for the smaller system and we pull back to get it for the larger system.