Berman, Avi; Friedland, Shmuel; Hogben, Leslie; Rothblum, Uriel G.; Shader, Bryan

Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers

Electron. J. Comb. 15(1), Research Paper R25, 19 p. (2008)

Summary

Summary: We use a technique based on matroids to construct two nonzero patterns Z1 and Z2 such that the minimum rank of matrices described by Z1 is less over the complex numbers than over the real numbers, and the minimum rank of matrices described by Z2 is less over the real numbers than over the rational numbers. The latter example provides a counterexample to a conjecture in [AHKLR] about rational realization of minimum rank of sign patterns. Using Z1 and Z2, we construct symmetric patterns, equivalent to graphs G1 and G2, with the analogous minimum rank properties. We also discuss issues of computational complexity related to minimum rank.

Mathematics Subject Classification

05C50

Keywords/Phrases

minimum rank, graph, pattern, zero-nonzero pattern, field, matroid, symmetric matrix, matrix, real, rational, complex

Downloads