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

Abstract

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