On the minimum semidefinite rank of a simple graph

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

The minimum semidefinite rank (msr) of a graph is defined to be the minimum rank among all positive semidefinite matrices whose zero/nonzero pattern corresponds to that graph. We recall some known facts and present new results, including results concerning the effects of vertex or edge removal from a graph on msr.

Original languageEnglish
Pages (from-to)483-506
Number of pages24
JournalLinear and Multilinear Algebra
Volume59
Issue number5
DOIs
Publication statusPublished - 2011
Externally publishedYes

Keywords

  • rank
  • positive semidefinite
  • graph of a matrix
  • vector representation

Cite this