Minimum Rank of Matrices Described by a Graph or Pattern over the Rational, Real and Complex Numbers

Date
2008-01-01
Authors
Berman, Avi
Friedland, Shmuel
Hogben, Leslie
Hogben, Leslie
Rothblum, Uriel
Shader, Bryan
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

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.

Description
<p>This is an article from the <em>Electronic Journal of Combinatorics </em>15 (2008).</p>
Keywords
minimum rank, graph, pattern, zero-nonzero pattern, field, matroid, symmetric matrix, matrix, real, rational, complex
Citation
Collections