ON THE MINIMUM RANK AMONG POSITIVE SEMIDEFINITE MATRICES WITH A GIVEN GRAPH

被引：48

作者：

Booth, Matthew ^{[7
]}

Hackney, Philip ^{[2
]}

Harris, Benjamin ^{[3
]}

Johnson, Charles R. ^{[4
]}

Lay, Margaret ^{[5
]}

Mitchell, Lon H. ^{[6
]}

Narayan, Sivaram K. ^{[1
]}

Pascoe, Amanda ^{[8
]}

Steinmetz, Kelly ^{[9
]}

Sutton, Brian D. ^{[10
]}

Wang, Wendy ^{[11
]}

机构：

[1] Cent Michigan Univ, Dept Math, Mt Pleasant, MI 48859 USA

[2] Purdue Univ, Dept Math, W Lafayette, IN 47907 USA

[3] Brown Univ, Dept Math, Providence, RI 02912 USA

[4] Coll William & Mary, Dept Math, Williamsburg, VA 23187 USA

[5] Grinnell Coll, Dept Math & Comp Sci, Grinnell, IA 50112 USA

[6] Virginia Commonwealth Univ, Dept Math, Richmond, VA 23284 USA

[7] Oberlin Coll, Dept Math, Oberlin, OH 44074 USA

[8] Furman Univ, Dept Math, Greenville, SC 29613 USA

[9] Indiana Univ, Dept Math, Bloomington, IN 47405 USA

[10] Randolph Macon Coll, Dept Math, Ashland, VA 23005 USA

[11] Duke Univ, Dept Math, Durham, NC 27708 USA

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 2008年 / 30卷 / 02期

基金：

美国国家科学基金会;

关键词：

rank; positive semidefinite; graph of a matrix;

D O I：

10.1137/050629793

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：731 / 740

页数：10

共 17 条

[1]

Barrett W, 2004, ELECTRON J LINEAR AL, V11, P258

[2]

BOLLOBAS B, 1984, GRAD TEXTS MATH, V184

[3]

de Verdiere YC, 1998, J COMB THEORY B, V74, P121

[4] MAXIMUM INDUCED TREES IN GRAPHS [J].