Universally optimal matrices and field independence of the minimum rank of a graph
Main Article Content
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.
Article Details
Issue
Section
Article