Page 51 - Textos de Matemática Vol. 39

TRIANGLE SIZE AND RANK FOR ZERO-NONZERO PATTERNS 41
columns or zero rows or columns. By permutation equivalence we may assume that the first row of Q has the fewest nonzeros of any row and the pattern of this first row is
∗∗···∗00···0. We consider two cases:
(1) thenumberof0’sintherow1is1,or
(2) the number of 0’s in the row 1 is greater than 1.
Note that if row 1 has no 0’s, then Q is full, and mr(Q) = 1, contrary to the hypothesis. In case 2, consider the columns headed by zeros; there are at least 2. Either all subsequent rows in these columns are either totally nonzero or totally zero, or some subsequent rows have both zeros and nonzeros. Since there are at least 2 such columns the former eventuality contradicts the fact that there are no repeated columns, (which flows from minimality). In the latter eventuality, Q must contain a 3-triangle, formed by row 1, a row with mixed zeros and nonzeros in our columns, and another row with a nonzero in a column in which the second has a zero (such a row exists, as there are no zero columns); the columns of the 3-triangle are one in which the first row has a nonzero (which must exist as there are no zero rows), and two columns indicated by the rows identified above, so that the last two rows and columns appear as
∗0, •∗
where • may be nonzero or zero. Thus, case 1 is the only possibility. However, in case 1 there are two sub-possibilities. Either 1.a some rows are full or 1.b each row has exactly 1 entry equal to 0. Possibility 1.a leads to a contradiction to minimality as follows. There is at most one full row (since there are no repeated rows), and if there is only one, either it can be arranged be a linear combination of the others (a contradiction to minimality) or the pattern appears as
⎡⎢ ∗ ∗ · · · ∗ 0 ⎤⎥ ⎢∗∗···∗0⎥
⎢ . . . . ⎥ , ⎢⎣ ∗ ∗ · · · ∗ 0 ⎥⎦
∗∗···∗∗
which contradicts minimality by repeated lines, unless Q is 2-by-2, which con- tradicts mr(Q) = 3.