Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418949 | Discrete Applied Mathematics | 2008 | 15 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Charles R. Johnson, Joshua A. Link,