Lower Bounds in Minimum Rank Problems

Lon H. Mitchell; Sivaram K. Narayan; Andrew M. Zimmer

doi:10.1016/j.laa.2009.08.023

Lower Bounds in Minimum Rank Problems

Lon H. Mitchell, Sivaram K. Narayan, Andrew M. Zimmer

Mathematics

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.

Original language	English
Pages (from-to)	430-440
Number of pages	11
Journal	Linear Algebra and Its Applications
Volume	432
Issue number	1
DOIs	https://doi.org/10.1016/j.laa.2009.08.023
State	Published - Jan 1 2010

Keywords

Minimum rank
Minimum semidefinite rank
Zero forcing set

Access to Document

10.1016/j.laa.2009.08.023

Cite this

@article{da45623e0fac42d1b2648ddaa94524e5,

title = "Lower Bounds in Minimum Rank Problems",

abstract = "The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.",

keywords = "Minimum rank, Minimum semidefinite rank, Zero forcing set",

author = "Mitchell, {Lon H.} and Narayan, {Sivaram K.} and Zimmer, {Andrew M.}",

note = "Funding Information: Research supported by NSF Grant 05-52594.",

year = "2010",

month = jan,

day = "1",

doi = "10.1016/j.laa.2009.08.023",

language = "English",

volume = "432",

pages = "430--440",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Linear Algebra and its Applications",

number = "1",

}

TY - JOUR

T1 - Lower Bounds in Minimum Rank Problems

AU - Mitchell, Lon H.

AU - Narayan, Sivaram K.

AU - Zimmer, Andrew M.

N1 - Funding Information: Research supported by NSF Grant 05-52594.

PY - 2010/1/1

Y1 - 2010/1/1

N2 - The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.

AB - The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.

KW - Minimum rank

KW - Minimum semidefinite rank

KW - Zero forcing set

UR - http://www.scopus.com/inward/record.url?scp=70449525222&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2009.08.023

DO - 10.1016/j.laa.2009.08.023

M3 - Article

AN - SCOPUS:70449525222

SN - 0024-3795

VL - 432

SP - 430

EP - 440

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 1

ER -

Lower Bounds in Minimum Rank Problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this