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

Main Article Content

Luz M. DeAlba
Jason Grout
Leslie Hogben
Rana Mikkelson
Kaela Rasmussen

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

Section
Article