  A successful computational approach for solving large-scale positive
semidefinite (PSD) programs is to enforce PSD-ness on only a collection of
submatrices. For our study, we let $\mathcal{S}^{n,k}$ be the convex cone of
$n\times n$ symmetric matrices where all $k\times k$ principal submatrices are
PSD. We call a matrix in this $k$-\emph{locally PSD}. In order to compare
$S^{n,k}$ to the of PSD matrices, we study eigenvalues of $k$-{locally PSD}
matrices. The key insight in this paper is that there is a convex cone
$H(e_k^n)$ so that if $X \in \mathcal{S}^{n,k}$, then the vector of eigenvalues
of $X$ is contained in $H(e_k^n)$. The cone $H(e_k^n)$ is the hyperbolicity
cone of the elementary symmetric polynomial $e^k_n$ (where $e_k^n(x) = \sum_{S
\subseteq [n] : |S| = k} \prod_{i \in S} x_i$) with respect to the all ones
vector. Using this insight, we are able to improve previously known upper
bounds on the Frobenius distance between matrices in $\mathcal{S}^{n,k}$ and
PSD matrices. We also study the quality of the convex relaxation $H(e^n_k)$. We
first show that this relaxation is tight for the case of $k = n -1$, that is,
for every vector in $H(e^n_{n -1})$ there exists a matrix in $\mathcal{S}^{n, n
-1}$ whose eigenvalues are equal to the components of the vector. We then prove
a structure theorem on nonsingular matrices in $\mathcal{S}^{n,k}$ all of whose
$k\times k$ principal minors are zero, which we believe is of independent
interest. %We then prove a structure theorem that precisely characterizes the
non-singular matrices in $\mathcal{S}^{n,k}$ whose vector of eigenvalues
belongs to the boundary of $H(e^n_k)$. This result shows shows that for $1< k <
n -1$ "large parts" of the boundary of $H(e_k^n)$ do not intersect with the
eigenvalues of matrices in $\mathcal{S}^{n,k}$.
