# Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices

Grigoriy Blekherman∗ School of Mathematics, Georgia Institute of Technology
<EMAIL_ADDRESS>,  Santanu S. Dey∗∗ School of Industrial and Systems
Engineering, Georgia Institute of Technology<EMAIL_ADDRESS>,
Kevin Shu∗<EMAIL_ADDRESS>and  Shengding Sun∗<EMAIL_ADDRESS>
###### Abstract.

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$-_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. 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}$.

Grigoriy Blekherman and Kevin Shu were partially supported by NSF grant
DMS-1901950. Santanu S. Dey was supported by ONR under grant No. N4458-NV-ONR.
Shengding Sun was supported by ARC-TRIAD Fellowship.

Keywords. Hyperbolicity cone, Positive semidefinite matrix, Eigenvalue bounds
AMS Subject Classification. 68Q25, 68R10, 68U05

##  1\. Introduction

###  1.1. $k$-Locally positive semidefinite matrices

Positive semidefinite (PSD) matrices are of fundamental interest in a wide
variety of fields, ranging from optimization [32] to physics [8]. Formally, a
symmetric matrix $X\in\operatorname{Sym}_{n}$ is PSD if and only if

$u^{\top}Xu\geq 0\,\,\text{ for all }\,\,u\in\mathbb{R}^{n}.$

The property of being positive semidefinite is very strong, and implies a
large amount of structure in a matrix. For example, all the eigenvalues of a
PSD matrix are non-negative. Another important property of a PSD matrix is
that all its principal submatrices are also PSD. There are various conceivable
converses to this fact which fail to hold; for instance, even if all of the
proper submatrices of a matrix are PSD, it is still possible for the matrix to
have a negative eigenvalue. Nevertheless, one might be interested in a partial
converse: if enough submatrices of a matrix are PSD, we should expect that the
matrix is ‘close’ to being PSD, in some sense. Such a result would help
explain a phenomenon observed in various recent computational experiments,
where the constraint of a matrix being PSD is relaxed to that of some
principal submatrices being PSD. It has been empirically observed that the
resulting relaxation has an optimal objective function value close to the
optimal objective function of the original problem. See [17, 18, 29] for
examples involving SDP relaxation of optimal electrical power flow problem and
[2, 9, 23] for examples involving SDP relaxation of box quadratic programs.

To formally understand the relaxation of enforcing positive semidefiniteness
on submatrices, we investigate a class of matrices, where we impose the
conditions that all $k\times k$ principal submatrices of an $n\times n$ matrix
are PSD. We will call such a matrix $k$-_locally PSD_. This terminology is
meant to suggest that we only check the PSD conditions locally on some small
parts of the matrix rather than globally. Let

(1)
$\displaystyle\mathcal{S}^{n,k}:=\\{X\in\operatorname{Sym}_{n}\,|\,\textup{every
}k\times k\textup{ principal submatrix of }X\textup{ is PSD}\\}$

be the set of $k$-locally PSD matrices. The set $\mathcal{S}^{n,k}$ is a
closed convex cone and its dual cone is the set of symmetric matrices with
factor width $k$, defined and studied in [6, 22, 11]. The set of symmetric
matrices with factor width 2 is the set of scaled diagonally dominant matrices
[6, 31], i.e., symmetric matrices $A$ such that $DAD$ is diagonally dominant
for some positive diagonal matrix $D$. The paper [1] uses scaled diagonally
dominant matrices for constructing inner approximation of the PSD cone for use
in solving polynomial optimization problems. See [15, 26, 27] for related
papers.

For $X\in\operatorname{Sym}_{n}$, we let
$\lambda(X)=(\lambda_{1}(X),\dots,\lambda_{n}(X))$, where
$\lambda_{1}(X)\leq\lambda_{2}(X)\leq\dots\lambda_{n}(X)$ are the eigenvalues
of $X$ counting multiplicity. We say that a vector $\lambda\in\mathbb{R}^{n}$
is a vector of eigenvalues of $X$ if it can be obtained from $\lambda(X)$ by
permuting its coordinates.

_Our main goal is to understand properties of eigenvalues of $k$-locally PSD
matrices. _ In particular, we would like to understand how as $k$ gets closer
to $n$, the matrices in $\mathcal{S}^{n,k}$ become closer to PSD matrices in
terms of eigenvalues. This work extends (and improves) results in a recent
paper [3], by identifying a relaxation of the set of eigenvalues of
$k$-locally PSD matrices. This relaxation is based on the machinery of
hyperbolic polynomials and hyperbolicity cones, which we discuss next.

###  1.2. The Hyperbolic Relaxation

In order to motivate the the machinery of hyperbolic polynomials and
corresponding hyperbolicity cones (which we formally define later), let us
first construct a natural relaxation of the set of eigenvalues of matrices in
$\mathcal{S}^{n,k}$.

Given an $n\times n$ matrix $X$, recall the definition of the characteristic
polynomial of $X$:

$p_{X}(t)=\det(X-tI)=\sum_{{\ell}=0}^{n}(-1)^{n-\ell}c_{\ell}^{n}(X)t^{n-\ell},$

where

$c_{\ell}^{n}(X)=\sum_{\genfrac{}{}{0.0pt}{2}{S\subseteq[n]}{|S|={\ell}}}\det(X|_{S}).$

Here, $X|_{S}$ is the principal submatrix of $X$ obtained by restricting $X$
to the rows and columns contained in $S$. Notice that if $X\in S^{n,k}$, then
for all $S\subseteq[n]$ with $|S|\leq k$, $X|_{S}$ is PSD and in particular,
then $\det(X|_{S})\geq 0$. This implies that $c_{\ell}^{n}(X)\geq 0$ for
$\ell\leq k$.

Let us introduce the set

$H(c_{k}^{n})=\\{X\in\operatorname{Sym}_{n}:\forall\ell\leq
k,\;c_{\ell}^{n}(X)\geq 0\\}.$

Our first observation is then that:

(2) $\displaystyle\mathcal{S}^{n,k}\subseteq H(c_{k}^{n}).$

The roots of $p_{X}$ are precisely the negatives of the eigenvalues of $X$, so
we have that

$p_{X}(t)=\prod_{i=1}^{n}(\lambda_{i}-t)=\sum_{\ell=0}^{n}(-1)^{n-\ell}e_{k}^{n}(\lambda_{1},\dots,\lambda_{n})t^{n-\ell},$

where $\lambda_{1},\lambda_{2},\dots\lambda_{n}$ are the eigenvalues of $X$ in
any order, counting multiplicity, and
$e^{n}_{k}\in\mathbb{R}[x_{1},\dots,x_{n}]$ is the elementary symmetric
polynomial

$e_{k}^{n}(x)=\sum_{\genfrac{}{}{0.0pt}{2}{S\subseteq[n]}{|S|={\ell}}}\prod_{i\in
S}x_{i}.$

Comparing coefficients of the $t^{k}$ terms, we see that for $0\leq k\leq n$,

$c_{k}^{n}(X)=e_{k}^{n}(\lambda_{1},\dots,\lambda_{n}).$

Combining our previous observations, we see that $X\in H(c_{k}^{n})$ if and
only if, $e_{\ell}^{n}(\lambda_{1},\dots,\lambda_{n})\geq 0$ for $\ell\leq k$.

We will define the set

$H(e_{k}^{n})=\\{\lambda\in\mathbb{R}^{n}:\forall\ell\leq
k,\;e_{\ell}^{n}(\lambda)\geq 0\\}.$

Combining these observations, we obtain the following:

######  Observation 1.

$\mathcal{S}^{n,k}\subseteq H(c_{k}^{n})$. Also,
$\lambda=(\lambda_{1},\dots,\lambda_{n})$ is a vector of eigenvalues of some
$X\in H(c_{k}^{n})$ if only if $\lambda\in H(e_{k}^{n})$.

The set $H(e_{k}^{n})$ will turn out to be the hyperbolicity cone of the
polynomial $e_{k}^{n}$ with respect to the all ones vector, and in particular
will turn out to be invariant to permutations of the coordinates and convex
[10, 13]. We will refer to $H(e_{k}^{n})$ as the _hyperbolic relaxation_ for
the eigenvalues of $\mathcal{S}^{n,k}$ Similarly, $H(c_{k}^{n})$ will be the
hyperbolicity cone of $c_{k}^{n}$ with respect to the identity matrix. The
cone $H(c_{k}^{n})$ is well-known in the literature and is sometimes referred
to as the $(n-k)^{th}$ Renegar derivative of the PSD cone [24].

By exploiting properties of these convex cones, we obtain bounds that indicate
that if $X\in\mathcal{S}^{n,k}$, then in fact, $X$ is close to being PSD in a
number of different norms.

As an example, notice that $e_{n}^{n}=\prod_{i=1}^{n}x_{i}$, and
$H(e_{n}^{n})=\mathbb{R}^{n}_{+}$, the nonnegative orthant. Similarly,
$H(c_{n}^{n})$ is the PSD cone, and we have that $H(e_{n}^{n})$ is exactly the
set of possible eigenvalue vectors for matrices in $H(c_{n}^{n})$.

This observation motivates us to ask the following related questions that tie
in with our goal of understanding properties of $\lambda(X)$ for
$X\in\mathcal{S}^{n,k}$:

  * •

_Is it possible to obtain understanding of
$\\{\lambda(X)\,|\,X\in\mathcal{S}^{n,k}\\}$ in comparison to eigenvalues of
PSD matrices, by studying properties of $H(e_{k}^{n})$?_

  * •

_How good is the approximation of the set
$\\{\lambda(X)\,|\,X\in\mathcal{S}^{n,k}\\}$ by $H(e_{k}^{n})$?_

In this paper, we answer ‘yes’ to the first question by improving on results
in [3] via the hyperbolic relaxation of the set of eigenvalues of matrices in
$\mathcal{S}^{n,k}$. This motivates us to delve further into the second
question and we verify various structural results that give a better
understanding of relationship between the sets
$\\{\lambda(X)\,|\,X\in\mathcal{S}^{n,k}\\}$ and $H(e_{k}^{n})$. One
particularly interesting result that we would like to highlight is a structure
theorem for matrices in $\mathcal{S}^{n,k}$ all of whose principal $k\times k$
minors vanish (Theorem 2.3). This theorem has relations to previous results in
linear algebra: Theorem 13 in [30] and results of [21].

###  1.3. Notation

For a positive integer $n$, let $[n]:=\\{1,\dots,n\\}$. Let
$\operatorname{Sym}_{n}$ denote the vector space of $n\times n$ symmetric
matrices. Let $\mathcal{S}^{n}$ denote the cone of PSD matrices inside of
$\operatorname{Sym}_{n}$. Note that $\mathcal{S}^{n,n}=\mathcal{S}^{n}$. If
$M\in\mathcal{S}^{n}$, we write $M\succeq 0$. We use $S^{n,k}$ to refer to the
$k$-locally PSD matrices, which are defined above in equation (1). We will
refer to $k$-locally PSD matrices for convenience as locally PSD matrices if
$k$ is clear from context. An important example of a non-PSD matrix lying in
$\mathcal{S}^{n,k}$ is given by

(3) $\displaystyle G(n,k)=\frac{k}{k-1}I-\frac{1}{k-1}\vec{1}\vec{1}^{\top}.$

Here, $\vec{1}$ denotes the all ones vector of dimension $n$. All diagonal
entries of $G(n,k)$ are identically 1, and all off-diagonal entries are
identically $-\frac{1}{k-1}$. Notice that all $k\times k$ principal minors of
$G(n,k)$ vanish, but the matrix is nonsingular.

Given a matrix $M\in\mathcal{S}^{n,k}$ and a diagonal matrix $D$ with non-zero
diagonal entries, observe that

$DMD\in\mathcal{S}^{n,k}.$

We say that the matrix $DMD$ is _diagonally congruent_ to $M$. By applying
Sylvester’s law of inertia to any submarix of $M$, the number of positive and
negative eigenvalues are conserved for the same submatrix of a diagonally
congruent matrix. In particular, a principal submatrix of a diagonally
congruent matrix is singular iff the same submatrix is singular in the
original matrix.

The rest of the paper is organized as follows: Section 2 lists all our main
results and Section 3 concludes with some open questions. Then Section 4
presents background results needed for proving the main results. The remaining
sections present our proofs of the main results.

##  2\. Main results

###  2.1. Bounds on minimum eigenvalues of matrices in $\mathcal{S}^{n,k}$

The primary way we can measure the distance between a matrix in
$\mathcal{S}^{n,k}$ and the cone of PSD matrices is by considering the
smallest eigenvalue of such a matrix. Certainly, if the minimum eigenvalue of
a matrix is nonnegative, then the matrix is positive semidefinite, and we will
say that a (suitably normalized) matrix is close to being PSD if its minimum
eigenvalue is close to being nonnegative. We show that if $k$ is sufficiently
close to $n$, then the $k$-locally PSD matrices are close to the PSD matrices.
Let $\lambda_{1}(M)$ be the minimum eigenvalue of a matrix
$M\in\mathcal{S}^{n,k}$. Because $\lambda_{1}$ is 1-homogeneous, i.e., if
$a\geq 0$, then $\lambda_{1}(aM)=a\lambda_{1}(M)$, we should try to compare
$\lambda_{1}(M)$ for $M\in\mathcal{S}^{n,k}$ to other 1-homogeneous (also
called positively homogeneous) quantities on $M$.

Formally, let $\mathcal{F}$ be the class of functions
$F:\operatorname{Sym}_{n}\rightarrow\mathbb{R}$ so that $F$ is a unitarily
invariant matrix norm (thus, a norm depending entirely on the eigenvalues) or
the trace function. Examples of unitarily invariant matrix norms are the
Schatten $p$-norms, $\|M\|_{p}=\sqrt[p]{\sum_{i=1}^{n}|\lambda_{i}(M)|^{p}}$
for $p\geq 1$. Note that the Frobenius norm is a special case of the Schatten
$p$-norm when $p=2$. Also, recall that $G(n,k)$ is defined in equation (3)

######  Theorem 2.1.

Let $k\in\\{2,\dots,n\\}$. Let $F\in\mathcal{F}$ and let
$\tilde{G}(n,k)=\frac{G(n,k)}{F(G(n,k))}$. For any $M\in\mathcal{S}^{n,k}$
with $F(M)=1$, the minimum eigenvalue of $M$ is at least as large as the
minimum eigenvalue of $\tilde{G}(n,k)$, that is,

$\lambda_{1}(M)\geq\lambda_{1}(\tilde{G}(n,k))\quad\text{for all}\quad
M\in\mathcal{S}^{n,k}\quad\text{such that}\quad F(M)=1.$

The bound on $\lambda_{1}(M)$ is tight since
$\tilde{G}(n,k)\in\mathcal{S}^{n,k}$ achieves this bound.

An immediate corollary of Theorem 2.1 in the case when $F$ is the trace
function is the following:

######  Corollary 1.

Let $k\in\\{2,\dots,n\\}$. For any $M\in\mathcal{S}^{n,k}$ such that
$\textup{Trace}(M)=1$, we have

$\lambda_{1}(M)\geq\frac{k-n}{n(k-1)}.$

The proof of Theorem 2.1 is a direct application of the fact that
$H\left(e_{k}^{n}\right)$ is a convex relaxation of the set of eigenvalues of
matrices in $\mathcal{S}^{n,k}$. This allows us to write a convex relaxation
of the optimization problem minimizing $\lambda_{1}(M)$ over
$M\in\mathcal{S}^{n,k}$. The optimal solution of this convex relaxation is the
bound obtained in the above theorem.

######  Remark 1.

The bound on $\lambda_{1}(M)$ presented in Theorem 2.1 holds for $M\in
H(e^{n}_{k})$. Therefore, this bound can be used to provide upper bounds on
the distance between the PSD cone and the Renegar derivative $H(c^{n}_{k})$ of
the PSD cone.

We can use Theorem 2.1 to bound Frobenius distances of matrices in
$\mathcal{S}^{n,k}$ from those in $\mathcal{S}^{n}$ (when we normalize the
matrices using the Frobenius norm) as in the following result.

######  Corollary 2.

Let
$\overline{\textup{dist}}(\mathcal{S}^{n,k},\mathcal{S}^{n})=\textup{max}_{A\in\mathcal{S}^{n,k}:\|A\|_{F}=1}\left(\textup{min}_{G\in\mathcal{S}^{n}}\|A-G\|_{F}\right)$.
Then
$\overline{\textup{dist}}(\mathcal{S}^{n,k},\mathcal{S}^{n})\leq\frac{(n-k)^{3/2}}{\sqrt{(n-k)^{2}+(n-1)k^{2}}}$.

This corollary improves upon Theorem 2 in a previous paper [3]. Our new result
has a better constant factor, and applies to all regimes of $k$ and $n$.

###  2.2. Tightness of the relaxation $H\left(e_{k}^{n}\right)$ for the set of
eigenvalues of matrices in $\mathcal{S}^{n,k}$

We have seen that the vector of eigenvalues of matrices in $S^{n}_{k}$ is
precisely $H(e^{n}_{k})$ for $n=k$. We next show that this observation holds
for two additional cases of $k$.

######  Theorem 2.2.

If $k$ is one of $1,n-1$ or $n$, and $x\in H(e_{k}^{n})$, then $x$ is the
vector of eigenvalues of some matrix in $\mathcal{S}^{n,k}$.

Since $H(e_{k}^{n})$ is a convex set for all $k$, in particular, Theorem 2.2
implies that the set of possible vectors of eigenvalues for matrices in
$\mathcal{S}^{n,n-1}$ is convex, although there does not seem to be an easy
way to see this directly. Therefore we have:

######  Corollary 3.

The set of all vectors of eigenvalues of matrices in $\mathcal{S}^{n,n-1}$ is
convex.

On the other hand, we show that $\\{\lambda(X)\,|\,X\in\mathcal{S}^{n,k}\\}$
is strictly contained in $H(e_{k}^{n})$ for $2<k<n-1$, and thus completely
characterize the tightness of this hyperbolic relaxation.

In order to do so, we examine the boundary of the cone $H(e_{k}^{n})$, and
obtain a result which is of independent interest. Recall that the boundary of
$H(e_{k}^{n})$ is precisely the set of points in the hyperbolicity cone on
which the polynomial $e_{k}^{n}$ vanishes.

Recall that if $M$ is a matrix, and $\lambda(M)$ is a vector of eigenvalues of
$M$, we have that

$e_{k}^{n}(\lambda(M))=\sum_{S\subseteq[n]:|S|=k}\det(M|_{S}).$

Because of this, we see that if $e_{k}^{n}(\lambda(M))=0$, and
$M\in\mathcal{S}^{n,k}$, then we have that $\det(M|_{S})=0$ for all subsets
$S$ of size $k$. We formalize this notion:

######  Definition 1.

We say that a matrix $M$ is $(n,k)$-locally singular if it lies in
$\mathcal{S}^{n,k}$ and all of the $k\times k$ minors of $M$ are singular.

We see that for $M\in\mathcal{S}^{n,k}$, $\lambda(M)$ is on the boundary of
$H(e_{k}^{n})$ if and only if $M$ is $(n,k)$-locally singular. Sometimes
$(n,k)$ is omitted and we say a matrix is locally singular if $n$ and $k$ are
clear from context.

The simplest class of examples of locally singular matrices are matrices of
rank less than $k$. In particular, rank 1 PSD matrices will be locally
singular for any $n$ and $k$. A more interesting example of locally singular
matrices are the $G(n,k)$ matrices defined in equation (3). Not only are these
matrices locally singular, but they are also non-singular. From this example
we can construct an $n$-dimensional space of locally singular matrices by
taking an arbitrary invertible diagonal matrix $D$, and considering

$DG(n,k)D\in\mathcal{S}^{n,k},$

that is the set of matrices that are _diagonally congruent_ to $G(n,k)$. It
follows from Sylvester’s law of inertia, applied to the various submatrices of
$G(n,k)$, that any matrix diagonally congruent to $G(n,k)$ is in fact locally
singular and nonsingular.

On the other hand, it is worth performing a quick dimension counting heuristic
to estimate how many possible matrices satisfy these conditions: Each
submatrix that is constrained to be singular imposes a single polynomial
equation on the possible solution set. If $n-1>k>2$, then we see that the
number of equations is $\binom{n}{k}$, which is in fact greater than the
dimension of the space of $n\times n$ symmetric matrices, which is
$\binom{n}{2}$. This indicates that solutions to this type of system should be
somewhat “uncommon”. Therefore, it is perhaps not surprising that in the cases
when $n-1>k>2$, we are able to show that all of the locally singular matrices
in $\mathcal{S}^{n,k}$, which are not singular, are diagonally congruent to
$G(n,k)$.

The following theorem formalizes this idea. Both the statement and the proof
of this theorem seem closely related to Theorem 13 in [30]. More generally,
the theorem can be viewed as giving semialgebraic relations between the
various principal minors of a symmetric matrix. A complete characterization of
the algebraic relations between the principal minors of a symmetric matrix was
given in [21].

######  Theorem 2.3.

Let $n-1>k>2$ or $(n,k)=(4,2)$. Suppose that $M\in\mathcal{S}^{n,k}$, $M$ is
$(n,k)$-locally singular, and $M$ is invertible. Then $M$ must be diagonally
congruent to $G(n,k)$.

Note that this immediately implies that there are points on the boundary of
$H(e_{k}^{n})$ which are not the eigenvalues of any matrix in
$\mathcal{S}^{n,k}$: since $G(n,k)$ has only one negative eigenvalue, any
matrix diagonally congruent to $G(n,k)$ has at most one negative eigenvalue,
and there are points on the boundary of $H(e_{k}^{n})$ with as many as $n-k$
negative entries and no zero entries.

When $k=2$ and $n=4$, locally singular matrices in $\mathcal{S}^{4,2}$ are
diagonally congruent to a symmetric matrix with diagonal entries identically
one and $\pm 1$ off-diagonal entries. We can numerically check that a such
matrix has at most one negative eigenvalue. Thus by Cauchy’s Interlacing
Theorem, for any $n>4$ and $k=2$, any locally singular matrix in
$\mathcal{S}^{n,2}$ can have at most $n-3$ negative eigenvalues, whereas the
boundary of $H(e_{2}^{n})$ contains points with as many as $n-2$ negative
eigenvalues. Thus we get the following corollary.

######  Corollary 4.

If $n-1>k\geq 2$, then the set of possible eigenvalue vectors for matrices in
$\mathcal{S}^{n,k}$ is strictly contained in $H(e_{k}^{n})$.

###  2.3. Eigenvalues of matrices in $\mathcal{S}^{4,2}$ whose eigenvalues lie
on the boundary of $H(e^{4}_{2})$

Theorem 2.3 implies that if $X$ is a nonsingular matrix in $\mathcal{S}^{n,k}$
whose eigenvalues lie on the boundary of $H(e^{n}_{k})$, then $X$ is in fact
diagonally congruent to the matrix $G(n,k)$. Because $G(n,k)$ has only one
nonnegative eigenvalue, Sylvester’s law of inertia [14] implies that a matrix
of this form has at most one negative eigenvalue.

The next lemma is a converse to the previous observation when $n=4$ and $k=2$.

######  Lemma 1.

If $\lambda\in H(e^{4}_{2})$, so that $e^{4}_{2}(\lambda)=0$ and $\lambda$ has
at most one negative eigenvalue, then $\lambda$ is a vector of eigenvalues for
matrix which is diagonally congruent to $G(4,2)$.

The idea of the proof is to use a characterization of the coefficients of real
rooted polynomials to reduce the problem to proving that there exist real
rooted polynomials having certain properties. These properties can be
described entirely in terms of polynomial inequalities, so we can use
algorithms for quantifier elimination over real closed fields to solve this
problem. We do not know of a proof of this result that does not rely on
computational methods.

##  3\. Conclusions and open questions

The key insight in this paper is the observation that $H(e^{n}_{k})$, i.e.,
the hyperbolicity cone of the elementary symmetric polynomial $e^{n}_{k}$, is
a convex relaxation of the set of the eigenvalue of matrices in
$\mathcal{S}^{n,k}$. Using this insight, we are able to improve upper bounds
on the distance of the matrices in $\mathcal{S}^{n,k}$ from PSD matrices
$\mathcal{S}^{n}$ given in [3]. The next question that was considered is how
good is the relaxation $H(e^{n}_{k})$: We first show that this relaxation
(apart from the trivial case of $n=k$) is tight for the case of $k=n-1$.
Indeed, in this case, we are able to show that $H(e^{n}_{n-1})$ is exactly the
set of eigenvalues of matrices in $\mathcal{S}^{n,n-1}$. However, in general
we prove that if $\lambda(M)$ belongs to the boundary of $H(e^{n}_{k})$ and
$M\in\mathcal{S}^{n,k}$, then either $M$ is non-singular or $M$ is diagonally
congruent to $G(n,k)$. Since there are points on the boundary of
$H(e_{k}^{n})$ with as many as $n-k$ negative entries and no zero entries,
this shows that “large parts” of the boundary of $H(e_{k}^{n})$ do not
intersect with the eigenvalues of matrices in $\mathcal{S}^{n,k}$.

There are many interesting open questions. As discussed above, we have shown
that the set of eigenvalues of matrices in $\mathcal{S}^{n,n-1}$ is convex. It
was recently shown in [19] that the set of eigenvalue vectors of matrices in
$\mathcal{S}^{4,2}$ is not convex, but it is still an open question for all
other values of $k<n-1$. Another question vis-á-vis the structure theorem is
to classify singular matrices in $\mathcal{S}^{n,k}$ that lie on the boundary
of $H(e^{n}_{k})$. Finally, instead of enforcing PSD-ness on all submatrices,
we can enforce PSD-ness of a smaller set of submatrices. Are there similar
relaxations like $H(e^{n}_{k})$ for specially structured collections of
submatrices?

##  4\. Preliminaries

###  4.1. Introduction to hyperbolic polynomials and hyperbolicity cones

Hyperbolic multivariate polynomials are a rich collection of polynomials with
connections to convex optimization, combinatorics and theoretical computer
science. We give a brief description of the important properties of hyperbolic
polynomials here. We say that a polynomial $p\in\mathbb{R}[x_{1},\dots,x_{n}]$
is _hyperbolic_ with respect to a fixed vector $v$ if $p(v)>0$, and for any
fixed $x\in\mathbb{R}^{n}$, the univariate polynomial
$p(x-tv)\in\mathbb{R}[t]$ has only real roots. An important example of this
comes from the determinant of symmetric matrices,
$\det(X)\in\mathbb{R}[x_{ij}:i\leq j]$, which is hyperbolic with respect to
the identity matrix, by the spectral theorem. Another example which is
critical for our purposes is the elementary symmetric polynomial
$e_{k}^{n}(x)$, defined as

$e_{k}^{n}(x)=\sum_{S\subseteq[n]:|S|=k}\prod_{i\in S}x_{i}.$

This polynomial is hyperbolic with respect to $\vec{1}$, the all ones vector.

Let $V(p)\subset\mathbb{R}^{n}$ be the set of zeros of the polynomial $p$. Let
$p$ be hyperbolic with respect to $v\in\mathbb{R}^{n}$. The closed
hyperbolicity cone of polynomial $p$ with respect to $v$, is the closure of
the connected component of $\mathbb{R}^{n}\setminus V(p)$ containing $v$ [10,
13, 25]. We will denote it by $H_{v}(p)$. When $p$ is the determinant or sum
of certain principal subdeterminants of a symmetric matrix, we will abbreviate
$H(p)=H_{I}(p)$, where $I$ is the identity matrix.

The hyperbolicity cone of elementary symmetric polynomial $e_{k}^{n}(x)$ with
respect to $\vec{1}$ will be denoted by $H(e_{k}^{n})$. A simple algebraic
characterization of $H(e_{k}^{n})$ is given by (see for example [34])

$H(e_{k}^{n})=\\{x\in\mathbb{R}^{n}:e_{l}^{n}(x)\geq 0\textup{ for all }1\leq
l\leq k\\}.$

It is also known that $H(e_{k}^{n})$ is spectrahedral [7] for all $1\leq k\leq
n$, i.e., an affine slice of a higher dimensional PSD cone.

The key fact for our purposes is Proposition 1 in [25] originally proved by
Gårding in [10].

######  Lemma 2.

If $p$ is hyperbolic with respect to $v$, then $H_{v}(p)$ is convex, and its
boundary is precisely $H_{v}(p)\cap V(p)$.

###  4.2. Linear algebra

We use the following standard results in the paper.
Proofs can be found in [14].

######  Theorem 4.1 (Schur-Horn theorem).

Let $d,\lambda\in\mathbb{R}^{n}$ such that $d_{i}\geq d_{i+1}$ and
$\lambda_{i}\geq\lambda_{i+1}$, $i\in[n-1]$. There is a symmetric matrix with
diagonal values $d$ and eigenvalues $\lambda$ if and only if:

  * •

$\sum_{i=1}^{j}d_{i}\leq\sum_{i=1}^{j}\lambda_{i}$ for all $j\in[n-1]$,

  * •

$\sum_{i=1}^{n}d_{i}=\sum_{i=1}^{n}\lambda_{i}$.

Note that the original theorem in [14] proves the existence of a real
symmetric matrix (not just Hermitian) that achieves the desired eigenvalues
and diagonal entries.

We next present the famous Cauchy’s Interlacing Theorem.

######  Theorem 4.2 (Cauchy’s Interlacing theorem).

Consider an $n\times n$ symmetric matrix $A$ and let $A|_{J}$ be any of its
$k\times k$ principal submatrices. Then for all $1\leq i\leq k$,

$\lambda_{n-k+i}(A)\leq\lambda_{i}(A|_{J})\leq\lambda_{i}(A).$

We also present the symmetric case of Jacobi Complementary Minors formula. The
proof for general case can be found in [20]:

######  Theorem 4.3 (Jacobi’s Complementary Minors Formula, symmetric case).

Let $M$ be an invertible $n\times n$ matrix and $\emptyset\subsetneq
S\subsetneq[n]$.

(4) $\det(M|_{S})=\det(M)\det(M^{-1}|_{S^{c}}).$

This theorem states that the minor of $M$ corresponding to a subset $S$, can
be written in terms of the minor of $M^{-1}$ with respect to the complement
$S^{c}$. In the simplest case when $|S|=n-1$, this is simply Cramer’s rule for
the diagonal entries of the inverse matrix.

##  5\. Proof of Theorem 2.1 and Corollary 2

###  5.1. Proof of Theorem 2.1

For the remainder of this section, fix $n>k\geq 2$ and an $F\in\mathcal{F}$.
Let $f$ be the function so that $f(\lambda(M))=F(M)$ for each
$M\in\operatorname{Sym}_{n}$.

In order to prove the theorem, we would like to verify an appropriate lower
bound on $z^{*}$ defined as:

$\displaystyle z^{*}:=\text{minimize }$ $\displaystyle\lambda_{1}(M)$ s.t.
$\displaystyle f(\lambda(M))=1$ $\displaystyle M\in\mathcal{S}^{n,k},$

where $\lambda_{1}(M)$ is the smallest eigenvalue of $M$.

In order to provide a lower bound on $z^{*}$, we apply (i) the hyperbolic
relaxation for the eigenvalues of $\mathcal{S}^{n,k}$ to replace
$\\{\lambda(M)\,|\,M\in\mathcal{S}^{n,k}\\}$ with $H(e^{n}_{k})$, (ii) replace
$f(\lambda(M))=1$ by $f(\lambda(M))\leq 1$ to obtain the following convex
optimization problem:

(9) $\displaystyle\begin{array}[]{rl}z^{l}:=\text{minimize }&\lambda_{1}\\\
\text{s.t. }&\lambda_{1}\leq\lambda_{i}\ \forall i\in\\{2,\dots,n\\}\\\
&f(\lambda)\leq 1\\\ &(\lambda_{1},\lambda_{2},\dots,\lambda_{n})\in
H(e_{k}^{n}).\end{array}$

It is straightforward to verify that the set $\\{\lambda\,|\,f(\lambda)\leq
1,\lambda\in H(e^{n}_{k})\\}$ is compact. Thus $z^{l}$ is finite and at least
one optimal solution exists. Also note that since (9) is a convex program
which is symmetric with regards to variables $\lambda_{2},\dots,\lambda_{n}$,
it is straightforward to verify that there exists an optimal solution where
$\lambda_{2}=\dots=\lambda_{n}$. Therefore, we arrive at the following two
variable optimization problem:

(14) $\displaystyle\begin{array}[]{rl}z^{l}:=\text{minimize }&\lambda_{1}\\\
\text{s.t. }&\lambda_{1}\leq\lambda_{2}\\\
&f(\lambda_{1},\lambda_{2},\dots,\lambda_{2})\leq 1\\\
&(\lambda_{1},\lambda_{2},\dots,\lambda_{2})\in H(e_{k}^{n}).\end{array}$

Next observe that if we remove the constraint
$(\lambda_{1},\lambda_{2},\dots,\lambda_{2})\in H(e_{k}^{n})$ from (14), then

  * •

If $f$ corresponds to a norm, then the optimal solution of the resulting
problem is of the form $(a,0,\dots,0)$ where $a<0$, which is infeasible for
(14) since it does not satisfy the constraint
$(\lambda_{1},\lambda_{2},\dots,\lambda_{2})\in H(e_{k}^{n})$. Thus, the
optimal solution of (14) belongs to the boundary of of $H(e_{k}^{n})$.

  * •

If $f$ corresponds to the trace function, then the optimal solution of the
resulting problem is unbounded. Thus, again we can conclude that the optimal
solution of (14) belongs to the boundary of $H(e_{k}^{n})$.

Simple computation shows that for
$(\lambda_{1},\lambda_{2},\dots,\lambda_{2})$ to be on the boundary of
$H(e^{n}_{k})$, we have $\lambda_{1}=-\frac{n-k}{k}\lambda_{2}$. Thus, we
obtain that
$z^{l}=-\frac{1}{f\left(-1,\frac{k}{n-k},\dots,\frac{k}{n-k}\right)}$. Since
$f$ is $1$-homogeneous, it is easy to verify that
$\lambda_{1}(\tilde{G}(n,k))=-\frac{1}{f\left(-1,\frac{k}{n-k},\dots,\frac{k}{n-k}\right)}$,
which completes the proof of the theorem.

###  5.2. Proof of Corollary 2

Let $A\in\mathcal{S}^{n,k}$ with $\|A\|_{F}=1$. If $A$ is PSD then the
distance is zero, so we assume $A$ has at least one negative eigenvalue. By
the Cauchy interlacing theorem (Theorem 4.2), $A$ has at most $n-k$ negative
eigenvalues. So
$\textup{dist}(A,\mathcal{S}^{n}_{+})\leq|\lambda_{1}(A)|\sqrt{n-k}$. By
Theorem 2.1 we have that
$|\lambda_{1}(A)|\leq\frac{1}{\sqrt{1+(n-1)\frac{k^{2}}{(n-k)^{2}}}}$, which
completes the proof.

##  6\. Proof of Theorem 2.2

When $k=n$ the statement is clear, since $x\in H(e_{n}^{n})$ if and only if
$x\geq 0$, and it is the eigenvalues of $\operatorname{diag}(x)$ which is PSD.
When $k=1$, let $x\in H(e_{1}^{n})=\\{y:\sum_{i=1}^{n}y_{i}\geq 0\\}$. By the
Schur-Horn theorem (Theorem 4.1), there exists a symmetric matrix $M_{0}$ with
identically zero diagonal entries and eigenvalues
$x-\frac{\sum_{i=1}^{n}x_{i}}{n}$. Thus,
$M_{0}+\frac{\sum_{i=1}^{n}x_{i}}{n}I$ has eigenvalues $x$ and is in
$\mathcal{S}^{n,1}$, since all of its diagonal entries are nonnegative.

Now let $k=n-1$. First, we reduce to the case when $x$ is on the boundary of
$H(e_{n-1}^{n})$. To do that, we note that if $x$ is any point in
$H(e_{n-1}^{n})$, then for some $t>0$, $x-t\vec{1}$ will lie on the boundary
of the cone. If $x-t\vec{1}$ is a vector of eigenvalues of a matrix $M$ in
$\mathcal{S}^{n,n-1}$, then $x$ is a vector of eigenvalues of $M+tI$, also in
$\mathcal{S}^{n,n-1}$.

We apply a corollary 3.2 in [34] to argue that if $x$ is in $H(e_{n-1}^{n})$,
then it has at most one negative eigenvalue.

######  Lemma 3.

If $x\in H(e_{n-1}^{n})$, and $x$ has a negative entry, then all other entries
of $x$ are strictly positive.

###### Proof.

By Theorem 1.1 in [28], we have that $x\in H(e_{n-1}^{n})$ if and only if

$X=\operatorname{diag}(x_{1},\dots,x_{n-1})+x_{n}\vec{1}_{n-1}\vec{1}_{n-1}^{\intercal}\succeq
0.$

Here, we use $\vec{1}_{n-1}$ to denote the all ones vector in $n-1$ dimensions
for emphasis.

By permuting the coordinates, we can assume that $x_{n}$ is an entry so that
$x_{n}<0$. Then, we have that the diagonal entries of $X$ are nonnegative, so
for $i\neq n$,

$x_{i}+x_{n}\geq 0.$

So, $x_{i}\geq-x_{n}>0$, concluding the theorem.

∎

Thus, if $x$ lies on the boundary, we will consider two cases: either all
entries of $x$ are nonnegative, or exactly one entry of $x$ is negative and
others are positive. If all entries of $x$ are nonnegative, then there is a
PSD matrix whose vector of eigenvalues is $x$, and in particular, a matrix in
$\mathcal{S}^{n,n-1}$ with these eigenvalues.

If $x$ lies on the boundary and exactly one entry of $x$ is negative, then
consider

$e_{n-1}^{n}(x)=\sum_{i\in[n]}\prod_{j\in[n]\setminus
i}x_{j}=\left(\prod_{j\in[n]}x_{j}\right)\sum_{i\in[n]}\frac{1}{x_{i}}=0,$

which is well defined since in the previous lemma, we showed that all entries
of $x$ are nonzero. Thus, $\sum_{i\in[n]}\frac{1}{x_{i}}=0$.

Now, we can apply the Schur-Horn theorem (Theorem 4.1), which implies that
there is a matrix $L$ whose diagonal entries are all zeros, and whose
eigenvalues are $\\{\frac{1}{x_{i}}\\}$. In particular, $L$ is invertible, so
let $M=L^{-1}$. Since all of the diagonal entries of $L$ are 0, all of the
$(n-1)\times(n-1)$ minors of $M$ are zero by Cramer’s rule for the diagonal
entries of the inverse matrix. Also note that $x$ has $(n-1)$ positive
entries, so by eigenvalue interlacing, all of the $(n-1)\times(n-1)$ minors of
$M$ have at most 1 non-positive eigenvalue. Now, simply by noting that they
all have 0 as an eigenvalue, this in particular implies that all
$(n-1)\times(n-1)$ minors of $M$ have nonnegative eigenvalues, and hence are
PSD. Thus, $M$ is a matrix in $\mathcal{S}^{n,n-1}$ with the desired
eigenvalues.

##  7\. Proof of the structure theorem for $\mathcal{S}^{n,k}$

###  7.1. Proof roadmap

Given a matrix in $\mathcal{S}^{n,k}$, which is nonsingular and locally
singular – we will abbreviate by saying that $M$ is an NLS matrix.

We show Theorem 2.3 in three steps. We first prove base cases $n-k=2$ and
$k=3$, and then we use double induction on $n-k$ and $k$ to prove the
statement for general $k$. For the base case $n-k=2$, there is a very
interesting step of taking the inverse of a given NLS matrix, and using some
facts about the structure of the inverse matrix.

The inductive step for this argument relies on some observations about Schur
complements. The Schur complement of a symmetric matrix $M$ with respect to a
nonzero diagonal entry $M_{ii}$ is defined to be  the $(n-1)\times(n-1)$
matrix

$M\setminus\\{i\\}=M|_{[n]\setminus\\{i\\}}-\frac{1}{M_{ii}}\tilde{M}_{i}\tilde{M}_{i}^{\top},$

where  $\tilde{M}_{i}$ is obtained from the $i^{th}$ column of $M$ after
removing $i^{th}$ entry.

Now, we recall some facts for matrices $M$ with strictly positive diagonal
entries [33].

  * •

Schur complements preserve PSD-ness. $M$ is PSD if and only if
$M\setminus\\{i\\}$ is PSD.

  * •

Schur complements preserve singularness. $M$ is nonsingular if and only if
$M\setminus\\{i\\}$ is nonsingular.

  * •

Schur complements commute with taking submatrices. If $i\notin S$, then
$(M\setminus\\{i\\})|_{S}=(M|_{S\cup\\{i\\}})\setminus\\{i\\}$.

The previous three properties imply the following: a matrix in
$\mathcal{S}^{n,k}$ is NLS, if and only if for each $i\in[n]$,
$M\setminus\\{i\\}$ is in $\mathcal{S}^{n-1,k-1}$ and NLS.

###  7.2. Structure theorem when $k=n-2$

Let $M$ be a matrix in $\mathcal{S}^{n,n-2}$, which is NLS. Observe that NLS
matrices in $\mathcal{S}^{n,n-2}$ must have strictly positive diagonal
entries. If any diagonal entry is zero, then since $2\times 2$ minors of $M$
are nonnegative, an entire row and column of $M$ are filled with zeros, and
then $M$ is singular, which is a contradiction.

As a base case when $n=4$, consider an NLS matrix $M\in\mathcal{S}^{4,2}$. We
can perform a diagonal congruence transformation to obtain a matrix
$\tilde{M}$, such that all of the diagonal entries of $\tilde{M}$ are 1, and
since all $2\times 2$ minors of $M$ are zero, we see that all off diagonal
entries of $\tilde{M}$ are $\pm 1$. There are 6 off-diagonal entries, so that
there are 64 distinct possibilities for locally singular matrices, up to
diagonal congruence. All of these 64 matrices are either singular or congruent
to $G(4,2)$, which can be checked using direct computation.

######  Lemma 4.

Let $M\in\mathcal{S}^{n,n-2}$ be an NLS matrix. Then the following hold:

  1. (1)

$\det(M)<0$.

  2. (2)

All $(n-1)\times(n-1)$ principal minors of $M$ are strictly negative.

  3. (3)

All $(n-3)\times(n-3)$ principal minors of $M$ are strictly positive.

###### Proof.

We prove these facts by inducting on $n$, with the base case
$\mathcal{S}^{4,2}$ following from direct checking of the $64$ cases above.
For the inductive step we take the Schur complement of an NLS matrix $M$ with
respect to a diagonal entry. Observe that a diagonal entry of the Schur
complement cannot be zero. Otherwise the whole row of the Schur complement
must be zero as all $2\times 2$ minors are nonnegative, and this is a
contradiction since $M$ is nonsingular, and Schur complements preserve
nonsingularity. Since taking Schur complements with respect to a positive
diagonal entry preserves the property of being NLS, preserves the signs of
determinants, and commutes with the operation of taking submatrices, all three
above statements follow by induction. ∎

Now we are ready to prove the main theorem of this Section.

######  Theorem 7.1.

Let $M\in\mathcal{S}^{n,n-2}$ be an NLS matrix. Then $M$ is diagonally
congruent to $G(n,n-2)$.

###### Proof.

Let $M\in\mathcal{S}^{n,n-2}$ be an NLS matrix and consider the inverse matrix
$M^{-1}$. Using Lemma 4 and Theorem 4.3 and what we know about principal
minors of $M$, we have the following:

  1. (1)

All diagonal entries of $M^{-1}$ are strictly positive.

  2. (2)

All $2\times 2$ principal minors of $M^{-1}$ are zero.

  3. (3)

All $3\times 3$ principal minors of $M^{-1}$ are strictly negative.

Observe that (1) and (2) together imply that all off-diagonal entries of
$M^{-1}$ are nonzero. We conjugate $M^{-1}$ by a diagonal matrix $D$ given by
$D_{11}=-1/\sqrt{(M^{-1})_{11}}$ and
$D_{ii}=\operatorname{sgn}(M_{1i})/\sqrt{(M^{-1})_{ii}}.$ to obtain matrix $T$
with $1$’s on the diagonal, and $-1$’s in first row and column other than the
$(1,1)$ entry. By Theorem 4.3, all $2\times 2$ principal minors of $T$ are
zero, so of its off-diagonal entries must be $\pm 1$.

Now for all distinct $i,j\neq 1$, we consider the principal submatrix with
rows and columns indexed by $\\{1,i,j\\}$. It has form
$\begin{pmatrix}1&-1&-1\\\ -1&1&x\\\ -1&x&1\end{pmatrix}$ where $x$ is either
$1$ or $-1$. Since this submatrix has negative determinant, we must have
$x=-1$. Thus $T$ is $G(n,2)$, and $M^{-1}$ is diagonally congruent to
$G(n,2)$.

Finally, notice that inverting a matrix sends diagonally congruent matrices to
diagonally congruent matrices, and that for $n\geq 4$,

$G(n,2)^{-1}=\frac{n-3}{2(n-2)}G(n,n-2).$

Thus, we have shown that $M$ is diagonally congruent to $G(n,n-2)$, as
desired.

∎

###  7.3. Structure theorem for $k=3$

In this section we prove the structure theorem for $k=3$:

######  Theorem 7.2.

Let $M\in\mathcal{S}^{n,3}$ with $n\geq 5$ be an NLS matrix. Then $M$ is
diagonally congruent to $G(n,3)$.

Our proof proceeds by induction on $n$. As a base case, note that the result
holds for $\mathcal{S}^{5,3}$ by Theorem 7.1.

To finish the induction we need the following lemma.

######  Lemma 5.

If $M$ is a nonsingular symmetric matrix, then either one of its
$(n-1)\times(n-1)$ principal minors is nonzero, or one of its
$(n-2)\times(n-2)$ principal minors is nonzero.

###### Proof.

Let $M$ be a nonsingular matrix and consider $M^{-1}$. If all of the principal
$(n-1)\times(n-1)$ minors of $M$ are zero, then by Theorem 4.3 all of the
diagonal entries of $M^{-1}$ are 0. If, in addition, all $(n-2)\times(n-2)$
principal minors of $M$ are zero, then all $2\times 2$ minors of $M^{-1}$ are
zero, and then $M^{-1}$ is the zero matrix, which is a contradiction. ∎

Now for an inductive hypothesis, assume that for $5\leq m<n$, any NLS $M\in
S^{m,3}$ is diagonally congruent to $G(m,3)$. Fix $n$ and let
$M\in\mathcal{S}^{n,3}$ be any NLS matrix. If the submatrix of $M$ given by
Lemma 5 has size at least 5, then it must be diagonally congruent to
$G(n-1,3)$ or $G(n-2,3)$ due to the inductive hypothesis. We divide the
remaining proof into three cases:

  1. (1)

$n\geq 6$, and there exists an $(n-1)\times(n-1)$ submatrix of $M$ that is
diagonally congruent to $G(n-1,3)$. Then after permutation and suitable
diagonal congruence we may assume

$M=\left(\begin{array}[]{c|c}G(n-1,3)&v\\\ \hline\cr
v^{\top}&1\end{array}\right),$

for some vector $v\in\mathbb{R}^{n-1}$.

Let $M^{\prime}$ be any $5\times 5$ principal submatrix of $M$ which includes
index $n$. Then $M^{\prime}$ must have the form

$M^{\prime}=\begin{pmatrix}1&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&v_{1}\\\
-\frac{1}{2}&1&-\frac{1}{2}&-\frac{1}{2}&v_{2}\\\
-\frac{1}{2}&-\frac{1}{2}&1&-\frac{1}{2}&v_{3}\\\
-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&1&v_{4}\\\
v_{1}&v_{2}&v_{3}&v_{4}&1\end{pmatrix}.$

If we look at the $3\times 3$ submatrix corresponding to entries
$\\{i,j,5\\}$, we get

$\begin{pmatrix}1&-\frac{1}{2}&v_{i}\\\ -\frac{1}{2}&1&v_{j}\\\
v_{i}&v_{j}&1\end{pmatrix}.$

The determinant of this matrix is

(15) $\frac{3}{4}-v_{i}^{2}-v_{i}v_{j}-v_{j}^{2}.$

Because all $3\times 3$ submatrices of $M^{\prime}$ are singular, this
determinant must equal 0 for all $i,j\in\\{1,2,3,4\\}$. Notice that this is a
quadratic equation in $v_{i}$ and $v_{j}$. If we fix a value for $v_{1}$, then
(15) implies that the remaining three $v_{i}$ can take on at most 2 other
values (which only depend on $v_{1}$). By the pigeonhole principle, at least
two of these $v_{i}$ must be equal. After permuting entries we may assume
$v_{2}=v_{3}$. Plugging this into (15), we see that either
$v_{2}=v_{3}=\frac{1}{2}$ or $v_{2}=v_{3}=-\frac{1}{2}$. In the first case we
may conjugate $M^{\prime}$ by $\operatorname{diag}(1,1,1,1,-1)$. Therefore we
may assume $v_{2}=v_{3}=-\frac{1}{2}$.

Now, we can consider the equation (15) for the cases when $i=2$ and $j=1$, or
$i=2$ and $j=4$. Because we assume $v_{2}=-\frac{1}{2}$, equation 15 implies
that

$\frac{3}{4}-v_{2}^{2}-v_{1}v_{2}-v_{1}^{2}=-(v_{1}-1)(v_{1}+\frac{1}{2}),$

and

$\frac{3}{4}-v_{2}^{2}-v_{2}v_{4}-v_{4}^{2}=-(v_{4}-1)(v_{4}+\frac{1}{2}).$

We then get that both $v_{1},v_{4}$ are either $1$ or $-\frac{1}{2}$. They
cannot both be 1, otherwise the equation fails for $i=1,j=4$. Therefore at
least one of them must be $-\frac{1}{2}$, and after permuting entries we may
assume $v_{1}=-\frac{1}{2}$.

Summarize above, we see that $M^{\prime}$ can only take on two values up to
diagonal congruence and permutation: either $M^{\prime}=G(5,3)$, or

$M^{\prime}=\begin{pmatrix}1&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\\\
-\frac{1}{2}&1&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\\\
-\frac{1}{2}&-\frac{1}{2}&1&-\frac{1}{2}&-\frac{1}{2}\\\
-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&1&1\\\
-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&1&1\end{pmatrix}.$

Now, because this holds for all $5\times 5$ submatrices of $M$, it is clear
that $v$ must have the properties that all entries of $v$ are either
$-\frac{1}{2}$ or $1$, and that at most one entry of $v$ can be $1$. If the
$i^{th}$ entry of $v$ is 1, then notice that rows $i$ and row $n$ of $M$ are
the same, meaning that $M$ is singular, a contradiction. We conclude that all
entries of $v$ are $-\frac{1}{2}$, and we have shown that $M$ is diagonally
congruent to $G(n,3)$.

  2. (2)

$n\geq 7$, and there exists an $(n-2)\times(n-2)$ submatrix of $M$ which is
nonsingular. By induction, this implies that this submatrix is diagonally
congruent to $G(n-2,3)$. Then after permutation and suitable diagonal
congruence we may assume

$M=\begin{pmatrix}G(n-2,3)&v&w\\\ v^{\top}&1&x\\\ w^{\top}&x&1\\\
\end{pmatrix}.$

If either $v$ or $w$ has all entries $-\frac{1}{2}$, then $M$ has an
$(n-1)\times(n-1)$ principal submatrix equal to $G\big{(}(n-1),3\big{)}$, and
we are back to the previous case.

Upon considering any $5\times 5$ principal submatrix of $M$ that has exactly
one index from $\\{n-1,n\\}$, and using observations from the previous case,
we may assume $v$ and $w$ to both have exactly one entry that is 1, with the
remaining entries are $-\frac{1}{2}$, and $x$ is some scalar number. There are
two cases of interest: either $v$ and $w$ have the 1 entry in the same
position, or in different positions.

If they are both in the same place, then without loss of generality, let us
assume that they are in position $(n-2)$. Now, if we look at the $3\times 3$
block corresponding to entries $\\{n-2,n-1,n\\}$, then we will see the
$3\times 3$ matrix

$\begin{pmatrix}1&1&1\\\ 1&1&x\\\ 1&x&1\end{pmatrix}.$

The determinant of this matrix is $-(x-1)^{2}$. We can see that if this matrix
is singular, then $x$ must in fact be equal to $1$, and so we see that the
last 3 rows of $M$ are all the same, implying $M$ is singular. Now, suppose
that $v$ and $w$ have these 1 entries in two different positions. Then we see
that there is a $3\times 3$ submatrix of the form

$\begin{pmatrix}1&1&-\frac{1}{2}\\\ 1&1&x\\\ -\frac{1}{2}&x&1\end{pmatrix}.$

The determinant of this matrix is
$1+x-x^{2}-\frac{1}{4}-1=-(x+\frac{1}{2})^{2}$, and we must then have
$x=-\frac{1}{2}$. In this case, we see that the $(n-2)$ and $(n-3)$ rows of
$M$ are equal, and so $M$ is singular. In other words, if
$M\in\mathcal{S}^{n,3}$ is locally singular, and $M$ is nonsingular, and some
$(n-2)\times(n-2)$ minor of $M$ is diagonally congruent to $G(n-2,3)$, then
$M$ is diagonally congruent to $G(n,3)$.

  3. (3)

$n=6$, and all $(n-1)\times(n-1)$ principal minors of $M$ are zero. Then using
Theorem 4.3, all diagonal entries of $M^{-1}$ are zero. Since
$M\in\mathcal{S}^{6,3}$ is NLS, again using Theorem 4.3, we also see that all
$3\times 3$ minors of $M^{-1}$ are zero. Any $3\times 3$ submatrix of $M^{-1}$
must be of the form

$\begin{bmatrix}0&a&b\\\ a&0&c\\\ b&c&0\end{bmatrix},$

which has determinant $2abc$. Since the determinant must be 0, this means that
there cannot be any $3\times 3$ submatrix of $M^{-1}$ where all off-diagonal
entries are nonzero. Now we define an edge coloring on $K_{6}$, the complete
graph with 6 vertices, as follows. An edge $(i,j)$ is colored red if
$(M^{-1})_{ij}=0$, and blue otherwise. Our previous result shows that there
cannot be any blue triangles in this colored graph. Therefore using the fact
that the Ramsey number $R(3,3)$ is at most $6$ [12], there must exist a red
triangle.

In other words, there must exist an identically zero $3\times 3$ submatrix
within $M^{-1}$. After permuting rows and columns we may assume its index to
be $\\{1,2,3\\}$. Now consider the submatrix of $M^{-1}$ indexed by
$\\{1,2,3,4,5\\}$. The span of first three rows is at most two dimensional, so
this submatrix is singular. Using Theorem 4.3 we get $M_{66}=0$. But this is a
contradiction since all diagonal entries of $M$ must be nonzero.

###  7.4. Structure theorem in general

We have shown the structure theorem in the cases when $k=3$ or $n-k=2$. Now we
use induction to prove the general case.

######  Theorem 7.3.

Fix integers $n\geq 5$ and $3\leq k\leq n-2$. Let $M\in\mathcal{S}^{n,k}$ be
NLS. Then $M$ is diagonally congruent to $G(n,k)$.

###### Proof.

We will use induction. The base cases are when $k=3$ or $k=n-2$, and they are
already proven. These include all cases when $n=5$ or $n=6$.

For induction, fix $n\geq 7$ and $3<k<n-2$. Assume the theorem statement holds
for $(n-1,k)$ and $(n-1,k-1)$. Let $M\in\mathcal{S}^{n,k}$ be NLS. The Schur
complement of $M$ with respect to any diagonal entry is NLS in
$\mathcal{S}^{n-1,k-1}$, and is therefore diagonally congruent to
$G(n-1,k-1)$. Because all $(n-2)\times(n-2)$ principal submatrices of
$G(n-1,k-1)$ are nonsingular for $k<n-1$, all of the $(n-2)\times(n-2)$ minors
of the Schur complement of $M$ are nonsingular. This implies that all of
$(n-1)\times(n-1)$ minors of $M$ are nonsingular, since Schur complements
preserve the property of being singular.

Thus, if we consider any $(n-1)\times(n-1)$ principal submatrix of $M$, we see
that it is NLS in $\mathcal{S}^{n-1,k}$, and by our inductive hypothesis, all
$(n-1)\times(n-1)$ submatrices of $M$ are diagonally congruent to $G(n-1,k)$.
This in particular shows that all entries of $M$ must be nonzero, and all
diagonal entries strictly positive.

Let $D^{\prime}$ be a non-singular diagonal matrix so that
$DM|_{\\{1,\dots,n-1\\}}D=G(n-1,k)$. Since we may freely choose between
$D^{\prime}$ and $-D^{\prime}$, without loss of generality we may assume
$D^{\prime}_{11}$ is negative. Let
$c=\frac{\textup{sgn}(M_{1n})}{\sqrt{M_{nn}}}$ (where $\textup{sgn}(x)$ is
$-1$ if $x$ is negative, 1 if $x$ is positive, and $\textup{sgn}(0)=0$). We
then have

$\left[\begin{array}[]{rl}D^{\prime}&0\\\
0&c\end{array}\right]M\left[\begin{array}[]{rl}D^{\prime}&0\\\
0&c\end{array}\right]=M^{\prime}=\left[\begin{array}[]{rl}G(n-1,k)&v\\\
v^{\top}&1\end{array}\right],$

for some vector $v$, and we know $v_{1}<0$. Our goal now is to show that all
entries of $v$ must be $-\frac{1}{k-1}$, and $M$ is therefore diagonally
congruent to $G(n,k)$.

Consider any size $n-1$ principal submatrix of $M^{\prime}$ containing columns
$1$ and $n$. It is diagonally congruent to $G(n-1,k)$ so there exists diagonal
matrix $D=\textup{diag}(d_{1},...,d_{n})$ such that

$D\left[\begin{array}[]{rl}G(n-2,k)&\hat{v}\\\
\hat{v}^{\top}&1\end{array}\right]D=G(n-1,k),$

where $\hat{v}$ is obtained from $v$ by truncating one entry other than the
first coordinate, and $\hat{v}_{1}<0$. We may also choose $d_{1}>0$. Now
comparing diagonal entries of both sides we get $d_{i}^{2}=1$ for all $i$. Now
for all $i>1$ the $(1,i)$ entry on both sides is negative, so $d_{i}d_{1}>0$
for all $i>1$. This shows in fact $D=I$, and all entries of $\hat{v}$ are
$-\frac{1}{k-1}$. Now varying over all possible choices of principal
submatrices containing columns $1$ and $n$, we see all entries of $v$ must be
$-\frac{1}{k-1}$. This concludes the proof. ∎

##  8\. Eigenvalues of Locally Singular Matrices in $\mathcal{S}^{4,2}$

In the previous section, we found that all locally singular matrices in
$\mathcal{S}^{4,2}$ are either singular or congruent to $G(n,k)$. In this
section, we consider the eigenvalues of NLS matrices in $\mathcal{S}^{4,2}$.

In general, we may ask the following question: what are the possible
eigenvalues of a matrix of the form $DG(n,k)D$, where $D$ is a nonsingular
diagonal matrix. We know that $DG(n,k)D$ is locally singular and in
$\mathcal{S}^{n,k}$, which implies that its eigenvalues lie on the boundary of
$H(e^{n}_{k})$.

Furthermore, by Sylvester’s law of inertia, for any nonsingular diagonal
matrix $D$, $DG(n,k)D$ has exactly one negative eigenvalue, and the remainder
are positive. Hence, if $\lambda$ is the eigenvalue vector of a $DG(n,k)D$,
then $\lambda$ has exactly one negative entry. We conjecture that this is in
fact sufficient for $\lambda$ to be the vector of eigenvalues for an NLS
matrix in $S^{n,k}$.

######  Conjecture 1.

If $\lambda\in H(e^{n}_{k})$, $e^{n}_{k}(\lambda)=0$, and $\lambda$ has at
most 1 negative entry, then $\lambda$ is a vector of eigenvalues for
$DG(n,k)D$ for some diagonal matrix $D$.

As evidence for this conjecture, we will give a computational proof of the
following theorem:

######  Theorem 8.1.

If $\lambda\in H(e_{2}^{4})$ lies on the boundary of the hyperbolicity cone of
$e_{2}^{4}$ and $\lambda$ has exactly 1 negative entry, then $\lambda$ is an
eigenvalue vector of some matrix in $\mathcal{S}^{4,2}$.

We prove this by converting the question into a question about real rooted
polynomials. We should think of these as being the characteristic polynomials
of certain types of symmetric matrices, and these characteristic polynomials
completely characterize their eigenvalues. We defer the proofs of these
characterizations to the appendix.

We say that a univariate polynomial of degree $4$,
$p=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+x^{4}$, has  good roots if it is real
rooted, $a_{0}<0$, $a_{2}=0$ and $a_{3}\leq 0$.

######  Lemma 6.

A real rooted polynomial $p$ has good roots if and only if $p$ has no zero
roots, exactly one negative root, and the roots of $p$ lie on the boundary of
$H(e_{2}^{4})$.

We then say that a polynomial $p=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+x^{4}$ is
almost-nonnegative rooted if there is some $k\in\mathbb{R}$ so that the
polynomial $q=\frac{a_{0}}{-16}+\frac{a_{1}}{-4}x+kx^{2}+a_{3}x^{3}+x^{4}$ has
nonnegative real roots.

######  Lemma 7.

$p$ is almost-nonnegative rooted if and only if there is some nonsingular
diagonal matrix $D$, so that $p$ is the characteristic polynomial of
$DG(4,2)D$.

Now, Theorem 8.1 is easily seen to be equivalent to the following lemma.

######  Lemma 8.

A polynomial $p$ has good roots if and only if it is almost-nonnegative
rooted.

We will prove Lemma 8 precisely in the appendix, but sketch the ideas here. In
principle, Lemma 8 is a statement in the first order theory of real closed
fields. That is, it can expressed entirely in terms of universal and
existential quantifiers applied to real polynomial inequalities. Such
questions are well known to be answerable algorithmically through quantifier
elimination techniques. The first such algorithm for deciding such statements
was found by Tarksi and Seidenberg, and further developments in this field can
be found, for example in [5]. We used the quantifier elimination methods in
Mathematica[16] to solve this problem.

The main technical difficulty in applying these quantifier elimination methods
is reducing the number of variables needed to express the inequalities so that
the problem becomes tractable on a computer. For this purpose, we prove a
number of polynomial inequalities in the coefficients of a degree 4 univariate
polynomial which imply both good-rootedness and almost-real-rootedness in the
appendix. Once these polynomial inequalities have been proven, the problem can
be directly solved by a computer.

## Acknowledgments

We wish to thank the reviewers for their valuable comments which improved the
paper and simplified some proofs.

## References

  * [1] Amir Ali Ahmadi and Anirudha Majumdar.  Dsos and sdsos optimization: more tractable alternatives to sum of squares and semidefinite optimization.  SIAM Journal on Applied Algebra and Geometry, 3(2):193–230, 2019\.
  * [2] Radu Baltean-Lugojan, Pierre Bonami, Ruth Misener, and Andrea Tramontani.  Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks.  2018\.
  * [3] Grigoriy Blekherman, Santanu S Dey, Marco Molinaro, and Shengding Sun.  Sparse PSD approximation of the PSD cone.  Mathematical Programming, 2020.
  * [4] Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas.  Semidefinite Optimization and Convex Algebraic Geometry.  Society for Industrial and Applied Mathematics, USA, 2012.
  * [5] Jacek Bochnak, Michel Coste, and Marie-Françoise Roy.  Real algebraic geometry, volume 36.  Springer Science & Business Media, 2013.
  * [6] Erik G Boman, Doron Chen, Ojas Parekh, and Sivan Toledo.  On factor width and symmetric h-matrices.  Linear algebra and its applications, 405:239–248, 2005.
  * [7] Petter Brändén.  Hyperbolicity cones of elementary symmetric polynomials are spectrahedral.  Optimization Letters, page 1773–1782, 2014.
  * [8] Daniel Cavalcanti and Paul Skrzypczyk.  Quantum steering: a review with focus on semidefinite programming.  Reports on Progress in Physics, 80(2):024001, 2016.
  * [9] Santanu S. Dey, Aleksandr Kazachkov, Andrea Lodi, and Gonzalo Munoz.  Sparse cutting planes for quadratically-constrained quadratic programs.  2019\.
  * [10] Lars Gårding et al.  Linear hyperbolic partial differential equations with constant coefficients.  Acta Mathematica, 85:1–62, 1951.
  * [11] João Gouveia, Alexander Kovačec, and Mina Saee.  On sums of squares of $k$-nomials.  arXiv preprint arXiv:1912.01371, 2019.
  * [12] Ronald L Graham, Bruce L Rothschild, and Joel H Spencer.  Ramsey theory, volume 20.  John Wiley & Sons, 1990.
  * [13] Osman Güler.  Hyperbolic polynomials and interior point methods for convex programming.  Mathematics of Operations Research, 22(2):350–377, 1997.
  * [14] Roger Horn and Charles Johnson.  Matrix analysis.  Cambridge University Press, 1985.
  * [15] Adolf Hurwitz.  About the comparison of the arithmetic and geometric mean.  Journal for pure and applied mathematics, 1891(108):266–268, 1891\.
  * [16] Wolfram Research, Inc.  Mathematica, Version 12.1.  Champaign, IL, 2020.
  * [17] Burak Kocuk, Santanu S Dey, and X Andy Sun.  Strong socp relaxations for the optimal power flow problem.  Operations Research, 64(6):1177–1196, 2016.
  * [18] Burak Kocuk, Santanu S. Dey, and Xu A. Sun.  Matrix minor reformulation and socp-based spatial branch-and-cut method for the ac optimal power flow problem.  arXiv preprint arXiv:1703.03050, 2017.
  * [19] Kazhgali Kozhasov.  On eigenvalues of symmetric matrices with psd principal submatrices.  arXiv preprint arXiv:2103.15811, 2021.
  * [20] Pierre Lalonde.  A non-commutative version of Jacobi’s equality on the cofactors of a matrix.  Discrete Math., 158(1-3):161–172, 1996.
  * [21] Luke Oeding.  Set-theoretic defining equations of the variety of principal minors of symmetric matrices.  Algebra & Number Theory, 5(1):75–109, Aug 2011.
  * [22] Frank Permenter and Pablo Parrilo.  Partial facial reduction: simplified, equivalent sdps via approximations of the psd cone.  Mathematical Programming, 171(1):1–54, Sep 2018.
  * [23] Andrea Qualizza, Pietro Belotti, and François Margot.  Linear programming relaxations of quadratically constrained quadratic programs.  In Mixed Integer Nonlinear Programming, pages 407–426. Springer, 2012.
  * [24] James Renegar.  Hyperbolic programs, and their derivative relaxations.  Foundations of Computational Mathematics, 6:59–79, 2006.
  * [25] James Renegar.  Hyperbolic programs, and their derivative relaxations.  Foundations of Computational Mathematics, 283(6):59–79, 2006.
  * [26] Bruce Reznick.  A quantitative version of hurwitz’theorem on the arithmetic-geometric inequality.  J. reine angew. Math, 377(108-112), 1987.
  * [27] Bruce Reznick.  Forms derived from the arithmetic-geometric inequality.  Mathematische Annalen, 283(3):431–464, 1989.
  * [28] Raman Sanyal.  On the derivative cones of polyhedral cones, 2011.
  * [29] Somayeh Sojoudi and Javad Lavaei.  Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure.  SIAM Journal on Optimization, 24(4):1746–1778, 2014.
  * [30] RC Thompson.  Principal submatrices v: Some results concerning principal submatrices of arbitrary matrices.  J. Res. Nat. Bur. Standards Sect. B, 72(2):115–125, 1968.
  * [31] Yuzhu Wang, Akihiro Tanaka, and Akiko Yoshise.  Polyhedral approximations of the semidefinite cone and their applications.  arXiv preprint arXiv:1905.00166, 2019.
  * [32] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe.  Handbook of semidefinite programming: theory, algorithms, and applications, volume 27.  Springer Science & Business Media, 2012.
  * [33] Fuzhen Zhang.  The Schur complement and its applications, volume 4.  Springer Science & Business Media, 2006.
  * [34] Yuriy Zinchenko.  On hyperbolicity cones associated with elementary symmetric polynomials.  Optimization Letters, 2(3):389–402, 2008.

##  Appendix A Proofs of results in Section 8

We first prove the characterization of the eigenvalues of matrices diagonally
congruent to $G(4,2)$ in terms of characteristic polynomials.

###### Proof.

(of lemma 6) Suppose that $p(x)=(x-r_{1})(x-r_{2})(x-r_{3})(x-r_{4})$, so that
the roots of $p$ are $r_{1},r_{2},r_{3},r_{4}$.

Note that the condition that $a_{2}\geq 0,a_{3}\leq 0$ is equivalent to the
condition that
$e_{2}^{4}(r_{1},r_{2},r_{3},r_{4}),e_{1}^{4}(r_{1},r_{2},r_{3},r_{4})\geq 0$.
These inequalities are equivalent to the condition that
$(r_{1},r_{2},r_{3},r_{4})\in H(e_{2}^{4})$ [13]. Once we know that
$(r_{1},r_{2},r_{3},r_{4})\in H(e^{4}_{2})$,
$a_{2}=e_{2}^{4}(r_{1},r_{2},r_{3},r_{4})=0$ is equivalent to the condition
that $(r_{1},r_{2},r_{3},r_{4})$ lies on the boundary of the hyperbolicity
cone.

Every $(r_{1},r_{2},r_{3},r_{4})\in H(e_{2}^{4})$ has at most 2 negative
entries, and if there were exactly 2 negative negative entries, then
$r_{1}r_{2}r_{3}r_{4}>0$ (it cannot be the case that there are two negative
entries and a zero entry by interlacing). Therefore, the condition that
$a_{0}<0$ is equivalent to there being at most 1 negative entry in
$(r_{1},r_{2},r_{3},r_{4})$. ∎

###### Proof.

(of 7)

Consider the characteristic polynomial of the matrix $DG(4,2)D$. By
definition, it is

$p(\lambda)=\det(DG(4,2)D-I\lambda)=\sum_{i=0}^{4}\sum_{S\subseteq[n],|S|=i}(-1)^{i}\det\big{(}(DG(4,2)D)|_{S}\big{)}\lambda^{4-i}.$

Now, note that because $D$ is diagonal,

$\det\big{(}(DG(4,2)D)|_{S}\big{)}=\det(D|_{S})^{2}\det(G(4,2)|_{S}).$

Also, because $G(n,k)$ is symmetric with respect to permutations of the
coordinates, $\det(G(n,k)|_{S})$ only depends on the size of $S$. So, we have
that

$p(\lambda)=\sum_{i=0}^{4}\det(G(4,2)|_{[i]})\sum_{S\subseteq[n],|S|=i}(-1)^{i}\det\big{(}(D)^{2}|_{S}\big{)}\lambda^{4-i}.$

Now, we simply compute

$\det(G(4,2)|_{\\{1\\}})=1,$ $\det(G(4,2)|_{\\{1,2\\}})=0,$
$\det(G(4,2)|_{\\{1,2,3\\}})=-4,$ $\det(G(4,2)|_{\\{1,2,3,4\\}})=-16.$

Now, consider the polynomial

$q(\lambda)=\sum_{i=0}^{4}\sum_{S\subseteq[n],|S|=i}(-1)^{i}\det\big{(}(D)^{2}|_{S}\big{)}\lambda^{i}=b_{0}+b_{1}\lambda+b_{2}\lambda^{2}+b_{3}\lambda^{3}+\lambda^{4}.$

This is equal to the characteristic polynomial of the matrix $D^{2}$. As
$D^{2}$ is a diagonal matrix with nonnegative real entries, its eigenvalues
are nonnegative. Moreover, if $q$ is a polynomial with nonnegative real roots,
then there is a diagonal matrix $D$ so that $q$ is its characteristic
polynomial.

Finally, note that from our above characterization of the coefficients of $p$,

$p(\lambda)=-16b_{0}+-4b_{1}\lambda+b_{3}\lambda^{3}+\lambda^{4}.$

On the other hand, if $p$ has almost-nonnegative roots, then we can construct
the desired $D$ from the roots of $q$, and then $DG(n,k)D$ will have the
desired eigenvalues. ∎

We now prove a number of polynomial inequalities which are equivalent to the
good-rooted and almost-real-rooted conditions.

######  Lemma 9.

$p=a_{0}+a_{1}x-x^{3}+x^{4}$ has good roots if and only if $a_{0}<0$, and

$-4a_{1}^{3}-27a_{1}^{4}-6a_{1}^{2}a_{0}-27a_{0}^{2}-192a_{1}a_{0}^{2}+256a_{0}^{3}\geq
0.$

###### Proof.

This polynomial
$-4a_{1}^{3}-27a_{1}^{4}-6a_{1}^{2}a_{0}-27a_{0}^{2}-192a_{1}a_{0}^{2}+256a_{0}^{3}$
is the discriminant of $p$, which is nonnegative if and only if the number of
real roots of $p$ is a multiple of $4$, or $p$ has a double root.

If $p$ has 4 nonreal roots, say $r_{1},r_{2},r_{3},r_{4}$, then they must come
in conjugate pairs, so that, say, $r_{1}=\bar{r_{2}}$ and $r_{3}=\bar{r_{4}}$,
which would imply that then

$a_{0}=r_{1}r_{2}r_{3}r_{4}=|r_{1}|^{2}|r_{3}|^{2},$

is nonnegative, a contradiction.

Similarly, if $p$ has a double root, say $r_{3}=r_{4}$, and a pair of complex
conjugate roots, say $r_{1}=\bar{r_{2}}$ then we see that

$a_{0}=r_{3}^{2}|r_{1}|^{2}\geq 0,$

which is a contradiction. ∎

######  Lemma 10.

$p=a_{0}+a_{1}x-x^{3}+x^{4}$ has almost-nonnegative roots if and only if
$a_{0}<0$, $a_{1}<0$, and there is $k>0$, so that the following 4 inequalities
are satisfied:

$\displaystyle\Big{(}-\frac{27a_{1}^{4}}{256}-\frac{9a_{1}^{3}k}{32}+\frac{a_{1}^{3}}{16}-\frac{9}{16}a_{1}^{2}a_{0}k+\frac{3a_{1}^{2}a_{0}}{128}-\frac{a_{1}^{2}k^{3}}{4}+\frac{a_{1}^{2}k^{2}}{16}+\frac{3a_{1}a_{0}^{2}}{16}$
$\displaystyle-\frac{5}{4}a_{1}a_{0}k^{2}+\frac{9a_{1}a_{0}k}{32}-\frac{a_{0}^{3}}{16}-\frac{a_{0}^{2}k^{2}}{2}+\frac{9a_{0}^{2}k}{16}-\frac{27a_{0}^{2}}{256}-a_{0}k^{4}+\frac{a_{0}k^{3}}{4}\Big{)}\geq
0,$
$\displaystyle\Big{(}\frac{27a_{1}^{4}}{256}+\frac{9a_{1}^{3}k}{32}+\frac{a_{1}^{3}}{8}+\frac{45}{128}a_{1}^{2}a_{0}k-\frac{9a_{1}^{2}a_{0}}{128}+\frac{a_{1}^{2}k^{3}}{4}+\frac{45a_{1}^{2}k^{2}}{16}+a_{1}^{2}k+$
$\displaystyle\frac{37a_{1}^{2}}{8}-\frac{9a_{1}a_{0}^{2}}{128}+\frac{11}{16}a_{1}a_{0}k^{2}-\frac{43a_{1}a_{0}k}{32}-\frac{53a_{1}a_{0}}{32}+9a_{1}k^{3}+\frac{27a_{1}k}{2}-$
$\displaystyle
3a_{1}+\frac{a_{0}^{3}}{64}+\frac{3a_{0}^{2}k^{2}}{16}+\frac{23a_{0}^{2}k}{128}+\frac{77a_{0}^{2}}{256}+\frac{a_{0}k^{4}}{2}+\frac{27a_{0}k^{3}}{8}-3a_{0}k^{2}+\frac{3a_{0}k}{8}-$
$\displaystyle\frac{3a_{0}}{8}+8k^{5}-2k^{4}+16k^{3}-4k^{2}\Big{)}\leq 0,$
$\displaystyle\Big{(}-\frac{3a_{1}^{3}}{16}+\frac{3a_{1}^{2}a_{0}}{64}-\frac{19a_{1}^{2}k^{2}}{16}-a_{1}^{2}k-\frac{17a_{1}^{2}}{16}+\frac{11a_{1}a_{0}k}{32}+\frac{17a_{1}a_{0}}{32}-$
$\displaystyle\frac{9a_{1}k^{3}}{2}-a_{1}k^{2}+3a_{1}k-\frac{15a_{1}}{2}-\frac{3a_{0}^{2}k}{32}-\frac{17a_{0}^{2}}{256}-\frac{5a_{0}k^{3}}{4}+\frac{9a_{0}k^{2}}{8}-$
$\displaystyle\frac{11a_{0}k}{8}+\frac{21a_{0}}{8}-4k^{5}+k^{4}-16k^{3}+33k^{2}-38k+9\Big{)}\geq
0,$
$\displaystyle\left(-\frac{3a_{1}^{2}}{16}-3a_{1}k+\frac{5a_{1}}{2}+\frac{3a_{0}k}{8}-\frac{5a_{0}}{8}+2k^{3}-11k^{2}+12k-7\right)\leq
0.$

###### Proof.

The classical results that we need about real rooted univariate polynomials,
such as the Newton identities and the Hermite-Sylvester conditions can be
found at [4, Section 3.1].

If we have the sign conditions on the coefficients, $a_{0}<0$, $a_{1}<0$,
$k>0$, then the polynomial
$q=\frac{a_{0}}{-16}+\frac{a_{1}}{-4}x+kx^{2}-x^{3}+x^{4}$ has coefficients
which alternate in sign. If $q$ is real rooted, then we can apply Descartes’
rule of signs to conclude that $q$ has nonnegative real roots.

The remaining inequalities cut out the space of real-rooted polynomials. This
follows from the Hermite-Sylvester criterion for the polynomial having real
roots. It states that if we let $m_{k}=\sum_{i=1}^{4}r_{i}^{k}$, where
$r_{1},r_{2},r_{3},r_{4}$ are the roots of $q$, then $p$ has nonnegative real
roots if and only if the $4\times 4$ matrix $M$ given by

$M_{ij}=m_{i+j}.$

is positive semidefinite.

We can then use the Newton identities to determine the $m_{k}$ in terms of
$a_{0}$, $a_{1}$ and $k$.

Once $M$ has been computed, the 4 polynomials above are the 4 coefficients of
the characteristic polynomial of $M$. $M$ being positive semidefinite is
equivalent to these 4 polynomials alternating in sign, which results in the
four inequalities listed. ∎

###### Proof.

(Of lemma 8)

We want to show that for all $a_{0}$ and $a_{1}$ satisfying the conditions of
9, there exists $k$ satisfying the conditions of 10.

We are now at the point where we can directly apply any quantifier elimination
algorithm to solve this problem, say the one included in Mathematica[16]. The
results of this computation show that the lemma holds. ∎