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 spa rsity 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 gr aphs G called blocks and superblocks. The k-superblocks are defined to be sparsity graphs G that contain an extreme point of rank Ic while c ontaining (in an extremely strong sense) no graph with the same proper ty. The goal of this article is to write down all graphs that are supe rblocks. The article succeeds completely for k less than or equal to 4 and it lists necessary conditions in general as well as sufficient co nditions. 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 previo usly mentioned paper by Alger et al. Indeed, the paper is an extension of the findings of Alger et al.