Universally optimal matrices and field independence of the minimum rank of a graph

Abstract

The minimum rank of a simple graph G over a field F is the smallest possible rank among all symmetric matrices over F whose (i, j)th entry (for i ≠  j) isnonzero whenever {i, j} is an edge in G and is zero otherwise. A universally optimal matrix is defined to be an integer matrix A such that every off-diagonal entry of A is 0, 1, or −1, and for all fields F, the rank of A is the minimum rank over F of its graph. Universally optimal matrices are used to establish field independence of minimum rank for numerousgraphs. Examplesare also provided verifying lack of field independence for other graphs.