tailieunhanh - Báo cáo toán học: "Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers. | Minimum rank of matrices described by a graph or pattern over the rational real and complex numbers Avi Berman Faculty of Mathematics Technion Haifa 32000 Israel berman@ Leslie Hogben Department of Mathematics Iowa State University Ames IA 50011 USA lhogben@ Shmuel Friedland Department of Mathematics Statistics and Computer Science University of Illinois at Chicago Chicago IL 60607-7045 USA friedlan@ Uriel G. Rothblum Faculty of Industrial Engineering and Management Technion Haifa 32000 Israel rothblum@ Bryan Shader Department of Mathematics University of Wyoming Laramie Wy 82071 USA bshader@ Submitted Apr 18 2007 Accepted Dec 22 2007 Published Feb 4 2008 Mathematics Subject Classification 05C50 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 G-1 and G2 with the analogous minimum rank properties. We also discuss issues of computational complexity related to minimum rank. Keywords minimum rank graph pattern zero-nonzero pattern field matroid symmetric matrix matrix real rational complex. This research began at the American Institute of Mathematics workshop Spectra of Families of Matrices described by Graphs Digraphs and Sign Patterns and the authors thank AIM and NSF for their support. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R25 1 1 Introduction The real symmetric minimum rank problem for a graph is to determine the minimum rank among real symmetric matrices whose zero-nonzero pattern of off-diagonal entries is described by a given .