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

doi:10.1080/03081080903542791

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 journal › Article › peer-review

25 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 language	English
Pages (from-to)	483-506
Number of pages	24
Journal	Linear and Multilinear Algebra
Volume	59
Issue number	5
DOIs	https://doi.org/10.1080/03081080903542791
Publication status	Published - 2011
Externally published	Yes

Keywords

rank
positive semidefinite
graph of a matrix
vector representation

Access to Document

10.1080/03081080903542791

Cite this

@article{6fc961e2e5344fdb929a67b48ad7834d,

title = "On the minimum semidefinite rank of a simple graph",

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.",

keywords = "rank, positive semidefinite, graph of a matrix, vector representation",

author = "Matthew Booth and Philip Hackney and Benjamin Harris and Johnson, {Charles R.} and Margaret Lay and Lenker, {Terry D.} and Mitchell, {Lon H.} and Narayan, {Sivaram K.} and Amanda Pascoe and Sutton, {Brian D.}",

year = "2011",

doi = "10.1080/03081080903542791",

language = "English",

volume = "59",

pages = "483--506",

journal = "Linear and Multilinear Algebra",

issn = "0308-1087",

publisher = "Taylor & Francis",

number = "5",

}

TY - JOUR

T1 - On the minimum semidefinite rank of a simple graph

AU - Booth, Matthew

AU - Hackney, Philip

AU - Harris, Benjamin

AU - Johnson, Charles R.

AU - Lay, Margaret

AU - Lenker, Terry D.

AU - Mitchell, Lon H.

AU - Narayan, Sivaram K.

AU - Pascoe, Amanda

AU - Sutton, Brian D.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - rank

KW - positive semidefinite

KW - graph of a matrix

KW - vector representation

U2 - 10.1080/03081080903542791

DO - 10.1080/03081080903542791

M3 - Article

SN - 0308-1087

VL - 59

SP - 483

EP - 506

JO - Linear and Multilinear Algebra

JF - Linear and Multilinear Algebra

IS - 5

ER -

On the minimum semidefinite rank of a simple graph

Abstract

Keywords

Access to Document

Fingerprint

Cite this