On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph

Authors:
  • MBMatthew Booth
    Matthew Booth
  • BHBenjamin Harris
    Benjamin Harris
  • CJCharles R. Johnson
    Charles R. Johnson
  • MLMargaret Lay
    Margaret Lay
  • SNSivaram K. Narayan
    Sivaram K. Narayan
  • APAmanda Pascoe
    Amanda Pascoe
  • KSKelly Steinmetz
    Kelly Steinmetz
  • BSBrian D. Sutton
    Brian D. Sutton
  • WWWendy Wang
    Wendy Wang

Abstract
Let $\mathcal{P}(G)$ be the set of all positive semidefinite matrices whose graph is G, and $\operatorname{msr}(G)$ be the minimum rank of all matrices in $\mathcal{P}(G)$. Upper and lower bounds for $\operatorname{msr}(G)$ are given and used to determine $\operatorname{msr}(G)$ for some well-known graphs, including chordal graphs, and for all simple graphs on less than seven vertices.

This publication has 15 references indexed in Scilit: