The minimum rank problem: A counterexample

DOI10.1016/J.LAA.2007.10.016MaRDI QIDQ2477550zbMATH OpenOpenAlexWikidataFDO

Authors Swastik Kopparty, K. P. S. Bhaskara Rao

Publication date 14 March 2008

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.1707

zbMATH Keywords

minimum rankminimum rank of a graphsign pattern matrixzero nonzero pattern

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03) Matrices of integers (15B36) Projective analytic geometry (51N15)

Abstract: We provide a counterexample to a recent conjecture that the minimum rank of every sign pattern matrix can be realized by a rational matrix. We use one of the equivalences of the conjecture and some results from projective geometry. As a consequence of the counterexample, we show that there is a graph for which the minimum rank over the reals is strictly smaller than the minimum rank over the rationals. We also make some comments on the minimum rank of sign pattern matrices over different subfields of $mathbbR$.

Review text

A matrix with entries from the set \(\{0,+1,-1\}\) is called a sign pattern matrix. Given such a matrix \(A\) and a subfield \(\mathbb F\) of the field of real numbers the minimum rank of \(A\) over \(\mathbb F\) is defined as the minimum over the ranks of all matrices \(B\) over \(\mathbb F\) with \(\text{ sgn\,} B=A\); here the sign of \(B\) is understood elementwise. The authors give an example of a sign pattern matrix whose minimum rank over the reals is different from its minimum rank over the rational numbers. Their short and elegant proof is based on recent work of \textit{M. Arav, F. J. Hall, S. Koyuncu, Z. Li}, and \textit{B. Rao} about sign pattern matrices [Linear Algebra Appl. 409, 111--125 (2005; Zbl 1079.15001)] and a paper of \textit{S. MacLane} about the realisation of matroids in terms of configurations of points and lines [Am. J. Math. 58, 236--240 (1936; Zbl 0013.19503)].

Recommendations

• Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers
• Rational realizations of the minimum rank of a sign pattern matrix
• Sign patterns with minimum rank 2 and upper bounds on minimum ranks
• Minimum ranks of sign patterns via sign vectors and duality
• Sign patterns of rational matrices with large rank. II

Cites work

• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• Rational realizations of the minimum rank of a sign pattern matrix
• Some Interpretations of Abstract Linear Dependence in Terms of Projective Geometry

Cited in

(17)

• Sign-central matrices
• Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations
• A sign pattern with all diagonal entries nonzero whose minimal rank realizations are not diagonalizable over \(\mathbb{C}\)
• Interval matrices: realization of ranks by rational matrices
• A remark on ranks of sign patterns
• Fooling-sets and rank
• Rational realizations of the minimum rank of a sign pattern matrix
• Rational realization of the minimum ranks of nonnegative sign pattern matrices.
• Sign patterns with minimum rank 2 and upper bounds on minimum ranks
• Essential sign change numbers of full sign pattern matrices
• The minimum rank problem over finite fields
• Sign patterns of rational matrices with large rank
• Matroids and the minimum rank problem for matrix patterns
• Generalization of real interval matrices to other fields
• Sign patterns that require almost unique rank
• Rational solutions of certain matrix equations
• The minimum rank problem over the finite field of order 2: Minimum rank 3

This page was built for publication: The minimum rank problem: A counterexample

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2477550)