On the minimum rank among positive semidefinite matrices with a given graph

Matthew Booth, Philip Hackney, Benjamin Harris, Charles R. Johnson, Margaret Lay, Lon H. Mitchell, Sivaram K. Narayan*, Amanda Pascoe, Kelly Steinmetz, Brian D. Sutton, Wendy Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

47 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)731-740
Number of pages10
JournalSIAM Journal on Matrix Analysis and Applications
Volume30
Issue number2
DOIs
Publication statusPublished - 2008
Externally publishedYes

Keywords

  • rank
  • positive semidefinite
  • graph of a matrix
  • HERMITIAN MATRIX
  • EIGENVALUES
  • MULTIPLICITIES
  • TREE

Cite this