Page 53 - Textos de Matemática Vol. 39

TRIANGLE SIZE AND RANK FOR ZERO-NONZERO PATTERNS 43
many more cells by Lemmas 1.1 and 1.2. We next describe these examples. The first is verified in [2, Section 5].
Example 1.8. For the 7-by-7 pattern
⎡⎢ ∗ ∗ ∗ 0 ∗ 0 0 ⎤⎥ ⎢ 0 ∗ 0 ∗ ∗ ∗ 0 ⎥ ⎢ 0 0 ∗ 0 ∗ ∗ ∗ ⎥
P=⎢∗ 0 ∗ ∗ 0 ∗ 0⎥ ⎢0∗∗∗00∗⎥ ⎣∗00∗∗0∗⎦
∗∗000∗∗
we have mr(P) = 4 but MT(P) = 3. Thus t(7,7,4) ≤ 3.
We verify the next necessary example here: Example 1.9. Let P be the following 7-by-7 pattern
⎡⎢ ∗ 0 ∗ ∗ 0 0 0 ⎤⎥ ⎢ 0 ∗ 0 ∗ ∗ 0 0 ⎥ ⎢ 0 0 ∗ 0 ∗ ∗ 0 ⎥
P=⎢0 0 0 ∗ 0 ∗ ∗⎥. ⎢⎣ 0 ∗ ∗ 0 0 0 ∗ ⎥⎦
∗∗000∗0 ∗000∗0∗
An inspection of P shows that it includes 4-triangles, but no 5-triangles because neitherthepatternR= ∗ 0 0 0 0 norRT existsasasubpatternofP,
•∗000
in which ∗ is a nonzero entry and • may be either nonzero or zero. Therefore,
MT(P ) = 4.
By [2, Corollary 3.3] we have 4 ≤ mr(P ) ≤ 5, and now we prove by using
Gaussian Elimination that mr(P ) = 5. Then t(7, 7, 5) ≤ 4.
Since rank is unchanged by diagonal equivalence, we may suppose that the
matrix A specifying P has the form
⎡⎢ 1 0 a 1 3 a 1 4 0 0 0 ⎤⎥ ⎢ 0 1 0 a24 1 0 0 ⎥ ⎢ 0 0 1 0 a35 1 0 ⎥
A=⎢0 0 0 1 0 a46 1 ⎥ ⎢⎣ 0 1 a 5 3 0 0 0 a 5 7 ⎥⎦
1 a62 0 0 0 a66 0
1 0 0 0 a75 0 a77
in which aij ̸= 0. (Such a simplification may be accomplished by first multiplying by a diagonal matrix to make the diagonal element equal to 1 and then using