On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
Authors:
- Matthew BoothMBMatthew Booth
- Philip HackneyPHPhilip Hackney
- Benjamin HarrisBHBenjamin Harris
- Charles R. JohnsonCJCharles R. Johnson
- Margaret LayMLMargaret Lay
- Lon H. MitchellLMLon H. Mitchell
- Sivaram K. NarayanSNSivaram K. Narayan
- Amanda PascoeAPAmanda Pascoe
- Kelly SteinmetzKSKelly Steinmetz
- Brian D. SuttonBSBrian D. Sutton
- Wendy WangWWWendy Wang
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 30 (2) , 731-740
Abstract
Let $\mathcal{P}(G)$ be the set of all positive semidefinite matrices whose graph is G, and $\operatorname{msr}(G)$ be the minimum rank of all matrices in $\mathcal{P}(G)$. Upper and lower bounds for $\operatorname{msr}(G)$ are given and used to determine $\operatorname{msr}(G)$ for some well-known graphs, including chordal graphs, and for all simple graphs on less than seven vertices.
Keywords
This publication has 15 references indexed in Scilit:
- Converse to the Parter–Wiener theorem: The case of non-treesDiscrete Mathematics, 2006
- Eigenvalue multiplicities in principal submatricesLinear Algebra and its Applications, 2004
- Graphs whose minimal rank is twoThe Electronic Journal of Linear Algebra, 2004
- Inverse eigenvalue problems and lists of multiplicities of eigenvalues for matrices whose graph is a tree: the case of generalized stars and double generalized starsLinear Algebra and its Applications, 2003
- On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graphLinear Algebra and its Applications, 2003
- On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a treeLinear Algebra and its Applications, 2002
- Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrixThe Electronic Journal of Linear Algebra, 2002
- The maximum multiplicity of an eigenvalue in a matrix whose graph is a treeLinear and Multilinear Algebra, 1999
- Multiplicities of Eigenvalues and Tree-Width of GraphsJournal of Combinatorial Theory, Series B, 1998
- Maximum induced trees in graphsJournal of Combinatorial Theory, Series B, 1986