Article ID Journal Published Year Pages File Type
418949 Discrete Applied Mathematics 2008 15 Pages PDF
Abstract

For any zero–nonzero pattern of a matrix, the minimum possible rank is at least the size of a sub-pattern that is permutation equivalent to a triangular pattern with nonzero diagonal. For certain numbers of rows and columns, the minimum rank of a pattern is k only when there is a k-by-k such triangle. Here, we complete the determination of such sizes by showing that an m-by-n pattern of minimum rank k must contain a k  -triangle for m=5m=5, k=4k=4; m=6m=6, k=5k=5; and m=6m=6, k=4k=4. A table is given showing whether or not this happens for all m, n, k. In the process, a Schur complement approach to minimum rank is described and used, and simple ways to recognize the presence of triangles of sizes less than 7 are given.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,