Page 49 - Textos de Matemática Vol. 39

THE RELATIONSHIP BETWEEN MAXIMUM TRIANGLE SIZE AND MINIMUM RANK FOR ZERO-NONZERO PATTERNS
RAFAEL CANTO´ AND CHARLES R. JOHNSON
To our good friend Sa´, who does mathematics for the right reasons – may he long continue!
Abstract. We investigate those dimensions m and n and ranks r, for which an m-by-n pattern with minimum rank r necessarily contains an r-by-r “trian- gular” pattern. Related ideas about the question of minimum rank of patterns are also discussed.
By a pattern we mean an m-by-n array P of 0’s and ∗’s indicating the po- sition of the nonzero entries in a conventional (real) matrix associated with the pattern. We say that A ∈ P if A is an m-by-n real matrix whose nonzeros occur in the positions indicated by the ∗’s of P . By mr(P ) we mean minA∈P rank A, the minimum rank of matrices of the pattern P. By a k-triangle we mean a k-by-k pattern that is permutationally equivalent to a triangular one with nonzero diagonal. It is clear that mr(P) = k if P is a k-triangle, and it has often been noted, and is equally obvious, that if a pattern P “contains” a k-triangle (as a subpattern), mr(P) ≥ k. Our concern here is the extent to which the converse is valid, i.e., if mr(P) = k, when does P necessarily con- tain a k-triangle? It is known that the converse is not always valid (see e.g. [2, Section 5]), but nonetheless, it sometimes is. Our purpose is to give those instances of minimum rank and pattern dimensions when it is.
To this end, for a pattern P define MT(P) to be the maximum triangle size in P , that is, the largest k such that P contains a k-triangle. Then, we may define t(m, n, r) = minP ∈P (m,n,r) MT(P ), in which P (m, n, r) denotes the set of m-by-n patterns P for which mr(P ) = r. Our question then is for which pairs m and n is t(m,n,r) = r (note that t(m,n,r) ≤ r, always). We next make a series of observations (in the form of lemmas) that will help in our cataloging. Then, we give some necessary particular examples and special proofs to present what we have found (see table at end).
2000 Mathematics Subject Classification. 15A03, 15A09, 15A24.
Key words and phrases. Minimum rank, zero-nonzero pattern matrix.
Rafael Cant´o supported by the Spanish DGI and FEDER grant AGL2004-03263/AGR,
the Generalitat Valenciana grant GRUPOS 03/062 and the UPV under its research program.
39