Graphs whose positive semi-definite matrices have nullity at most two

✍ Scribed by Hein van der Holst

• Book ID: 104155634
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 202 KB
• Volume: 375
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(03)00642-6

✦ Synopsis

Let G = (V , E) be a undirected graph containing n vertices, and let M G be the set of all Hermitian n × n matrices M = (m i,j ) with m i,j / = 0 if i and j are connected by one edge of G, with m i,j ∈ C if i and j are connected by at least two edges, with m i,j = 0 if i / = j , and i and j are not connected by an edge of G, and with m i,i for i = 1, . . . , n a real number. What is the largest nullity attained by any positive semi-definite matrix M ∈ M G ?

In this paper we characterize, for t = 1 and 2, those graphs G for which the maximum nullity is not greater than t.