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

doi:10.1137/050629793

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

52 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 language	English
Pages (from-to)	731-740
Number of pages	10
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	30
Issue number	2
DOIs	https://doi.org/10.1137/050629793
Publication status	Published - 2008
Externally published	Yes

Keywords

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

Access to Document

10.1137/050629793

Cite this

@article{51f84357ad9c40acbf71f130c5be6435,

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

keywords = "rank, positive semidefinite, graph of a matrix, HERMITIAN MATRIX, EIGENVALUES, MULTIPLICITIES, TREE",

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

year = "2008",

doi = "10.1137/050629793",

language = "English",

volume = "30",

pages = "731--740",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "SIAM PUBLICATIONS",

number = "2",

}

TY - JOUR

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

AU - Booth, Matthew

AU - Hackney, Philip

AU - Harris, Benjamin

AU - Johnson, Charles R.

AU - Lay, Margaret

AU - Mitchell, Lon H.

AU - Narayan, Sivaram K.

AU - Pascoe, Amanda

AU - Steinmetz, Kelly

AU - Sutton, Brian D.

AU - Wang, Wendy

PY - 2008

Y1 - 2008

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

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

KW - rank

KW - positive semidefinite

KW - graph of a matrix

KW - HERMITIAN MATRIX

KW - EIGENVALUES

KW - MULTIPLICITIES

KW - TREE

U2 - 10.1137/050629793

DO - 10.1137/050629793

M3 - Article

SN - 0895-4798

VL - 30

SP - 731

EP - 740

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 2

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this