Journal article
Sparsity Patterns with High Rank Extremal Positive Semidefinite Matrices
SIAM journal on matrix analysis and applications, v 15(1), 299
01 Jan 1994
Abstract
This article concerns the positive semidefinite matrices $M_+ ( G )$ with zero entries in prescribed locations; that is, matrices with given sparsity graph $G$. The issue here is the rank of the extremals of the cone $M_+ ( G )$. It was shown in [J. Agler, J. W. Helton, S. McCullough, and L. Rodman, Linear Algebra Appl., 107 (1988), pp. 101-149] that the key in constructing high rank extreme points resides in certain atomic graphs $G$ called blocks and superblocks. The $k$-superblocks are defined to be sparsity graphs $G$ that contain an extreme point of rank $k$ while containing (in an extremely strong sense) no graph with the same property. The goal of this article is to write down all graphs that are superblocks. The article succeeds completely for $k \leq 4$ and it lists necessary conditions in general as well as sufficient conditions. The subject is closely related to orthogonal representations of graphs as studied earlier in [L. Lovasz, M. Saks, and A. Schrijver, Linear Algebra Appl., 114/115 (1989), pp. 439-454] and in the previously mentioned paper by Alger et al. Indeed, the paper is an extension of the findings of Alger et al.
Metrics
2 Record Views
Details
- Title
- Sparsity Patterns with High Rank Extremal Positive Semidefinite Matrices
- Creators
- J. William HeltonDaniel LamHugo J Woerdeman
- Publication Details
- SIAM journal on matrix analysis and applications, v 15(1), 299
- Publisher
- Society for Industrial and Applied Mathematics
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:A1994MV29600023
- Other Identifier
- 991021864946904721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Mathematics, Applied