Extermal positive semidefinite matrices with given sparsity pattern

Abstract

We prove a conjecture of Helton, Pierce and Rodman about the connection between the ranks of matrices generating extreme rays in the cone of positive semidefinite matrices with a given sparsity pattern and the amount of fill-in for the specific sparsity pattern. We also present a necessary condition on the given sparsity pattern for the existence of a rank k extermal in the cone.

Mathematics Subject Classifications:

• Primary,05C50
• Secondary,05B20, 15A57