Sparsity Patterns with High Rank Extremal Positive Semidefinite Matrices

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 Gcalled blocks and superblocks. The k-superblocks are defined to be sparsity graphs Gthat contain an extreme point of rank kwhile 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. Lovász, 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.