# An algorithm for determining copositive matrices111This research was
supported by the National Natural Science Foundation of
China(11001228,10901116).

Jia Xu<EMAIL_ADDRESS>Yong Yao<EMAIL_ADDRESS>College of Computer
Science and Technology, Southwest University for Nationalities, Chengdu,
Sichuan 610041, China  Chengdu Institute of Computer Applications, Chinese
Academy of Sciences, Chengdu, Sichuan 610041, China

###### Abstract

In this paper, we present an algorithm of simple exponential growth called
COPOMATRIX for determining the copositivity of a real symmetric matrix. The
core of this algorithm is a decomposition theorem, which is used to deal with
simplicial subdivision of $\widehat{T}^{-}=\\{y\in\Delta_{m}|\beta^{T}y\leq
0\\}$ on the standard simplex $\Delta_{m}$, where each component of the vector
$\beta$ is -1, 0 or 1.

###### keywords:

copositive matrices , copositive quadratic forms , simplicial subdivision of
convex polytope , complete algorithm

###### MSC:

15A48 , 15A57 , 15A63 , 65F30

††journal: Linear Algebra and its Applications, 435(2011) 2784-2792

##  1 Introduction

QUESTION 1 Let $A$ be a given $n\times n$ real symmetric matrix,
${\mathbb{R}}_{+}$ be the set of nonnegative real numbers, and

$Q(X)=X^{T}AX,\ X\neq 0$

be a quadratic form. What conditions should $A$ satisfy for $[\forall
X\in{\mathbb{R}}^{n}_{+},\ Q(X)\geq 0\ (>0)]$?

If $[\forall X\in{\mathbb{R}}^{n}_{+},\ Q(X)\geq 0\ (>0)]$, then the quadratic
form $Q(X)$ is called a (strictly) copositive quadratic form and the
corresponding matrix $A$ is called a (strictly) copositive matrix.

Copositive matrices have numerous applications in diverse fields of applied
mathematics, especially in mathematical programming and graph theory (see [3,
5, 7, 11, 13, 15, 16, 25, 26, 29, 39]). Therefore copositivity has been
studied thoroughly since 1950s (see [1, 6, 14, 17, 20, 22, 23, 27, 28, 33, 34,
36, 41, 42, 43, 48, 49]).

In general, it is an NP-complete problem to determine whether a given $n\times
n$ symmetric matrix is not copositive [37, 38]. This means that every
algorithm that solves the problem, in the worst case, will require at least an
exponential number of operations, unless P=NP. For that reason, it is still
valuable for the existence of so many incomplete algorithms discussing some
special kinds of matrices (see [3, 4, 10, 12, 18, 19, 21, 24, 30, 38]). For
small values of $n$($\leq 6$), some necessary and sufficient conditions have
been constructed (see [1, 14, 30, 49]). From another viewpoint, QUESTION 1 is
a typical real quantifier elimination problem [2, 8, 9, 32, 35, 40, 44, 45],
which can be solved by standard tools of real quantifier elimination (e.g.,
using CAD) [2, 8, 9, 46, 47]. Thus, there is a complete algorithm for
determining copositive matrices theoretically. Unfortunately, this algorithm
is not efficient in practice for the CAD algorithm is of doubly exponential
time complexity (see [2, 8, 9]). In this paper, we will construct a complete
algorithm with singly exponential time bound.

The standard simplex $\Delta_{m}(m\geq 2)$ is defined as the following set

$\Delta_{m}=\\{(y_{1},\ldots,y_{m})^{T}|\ y_{1}+\cdots+y_{m}=1,y_{1}\geq
0,\ldots,y_{m}\geq 0\\}.$

It is well known that the dimension of $\Delta_{m}$ is $m-1$. Denote the
vertices of $\Delta_{m}$ as $e_{1},\ldots,e_{m}$, namely,
$e_{1}=(1,0,\ldots,0)^{T},\ldots,e_{m}=(0,0,\ldots,1)^{T}$.

Let $A\in{\mathbb{R}}^{n\times n}$ be symmetric and be partitioned as

$A=[\alpha_{ij}]=\left[\begin{array}[]{cc}\alpha_{11}&\alpha^{T}\\\
\alpha&A_{2}\end{array}\right].$

Define $B=\alpha_{11}A_{2}-\alpha\alpha^{T}$. It is easy to see the following
facts (cf.[1])

1\. If $\alpha_{1i}\geq 0,\ i=2,\ldots,n$, then $A$ is (strictly) copositive
$\Longleftrightarrow\alpha_{11}\geq 0\ (>0)$ and $A_{2}$ is (strictly)
copositive.

2\. If at least one of $\alpha_{1i}$ is negative, then we need only to focus
on the set of points $T^{-}=\\{y\in\Delta_{n-1}|\ \alpha^{T}y\leq 0\\}$. It is
well known that $T^{-}$ is a convex polytope on $\Delta_{n-1}$ (see [1]). The
polytope $T^{-}$ can be subdivided into the simplices $S_{1},\ldots,S_{p}$,
that is,

$T^{-}=\bigcup_{i=1}^{p}S_{i},\ {\rm int}(S_{i})\bigcap{\rm
int}(S_{j})=\emptyset,{\rm for}\ i\neq j,$

where ${\rm int}(S_{i})$ denotes the interior of simplex $S_{i}$. The
coordinates of the vertices that span the simplex $S_{i}$ constitute a matrix
denoted as $W_{i}$. Andersson et al. ([1], p.23) proved the following results.

###### Lemma 1.1

(a) $A$ is copositive iff $\alpha_{11}\geq 0$ and $A_{2},\ W_{1}^{T}BW_{1},\
\ldots,\ W_{p}^{T}BW_{p}$ are all copositive.

(b) $A$ is strictly copositive iff $\alpha_{11}>0$ and $A_{2},\
W_{1}^{T}BW_{1},\ \ldots,\ W_{p}^{T}BW_{p}$ are all strictly copositive.

In order to formulate the algorithm of Lemma 1.1, we first consider how to
obtain the simplicial subdivision of the polytope $T^{-}=\\{y\in\Delta_{n-1}|\
\alpha^{T}y\leq 0\\}$. For small values of $n(\leq 6)$, Andersson et al.[1]
and Yang and Li [49] give the simplicial subdivision of $T^{-}$. However, they
do not provide a procedure for a simplicial subdivision of $T^{-}$ for
arbitrary values of n. We propose a simplicial subdivision of $T^{-}$ for all
values of $n$, and consequently construct a complete algorithm for determining
the copositivity of an $n\times n$ matrix.

We will adopt a flexible approach. Rather than subdivide $T^{-}$ into
simplices (of course our method is also valid for subdividing $T^{-}$ into
simplices), we first transform the matrix $A$ into the following matrix called
$\widehat{A}$.

Let $\alpha=(\alpha_{12},\ldots,\alpha_{1n})^{T}$ and $D={\rm
diag}(d_{2},\ldots,d_{n}),$ where

$d_{i}=\left\\{\begin{array}[]{ll}1,&{\rm if}\ \alpha_{1i}=0;\\\
1/|\alpha_{1i}|,&{\rm if}\ a_{1i}\neq 0.\end{array}\right.$

Then

$\widehat{A}=\left[\begin{array}[]{cc}1&0\\\
0&D\end{array}\right]A\left[\begin{array}[]{cc}1&0\\\
0&D\end{array}\right]=\left[\begin{array}[]{cc}\alpha_{11}&\widehat{\alpha}^{T}\\\
\widehat{\alpha}&DA_{2}D\end{array}\right].$ (1)

where $\widehat{\alpha}=({\rm sign}(\alpha_{12}),\ldots,{\rm
sign}(\alpha_{1n}))^{T}$.

Obviously, $A$ is (strictly) copositive $\Longleftrightarrow$$\widehat{A}$ is
(strictly) copositive. Apply Lemma 1.1 to $\widehat{A}$. Let

$\beta_{1}={\rm sign}(\alpha_{12}),\ldots,\ \beta_{n-1}={\rm
sign}(\alpha_{1n}).$

Thus we just need to subdivide $\widehat{T}^{-}$ into simplices, where

$\widehat{T}^{-}=\\{y\in\Delta_{n-1}|(\beta_{1},\ldots,\beta_{n-1})y\leq 0,\
\beta_{i}\in\\{-1,0,1\\}\\}.$

Next we make further simplification: separate -1,0,1 from
$\beta_{1},\ldots,\beta_{n-1}$, namely let

$\begin{array}[]{c}\beta_{a_{1}}=\cdots=\beta_{a_{s}}=1,\
\beta_{b_{1}}=\cdots=\beta_{b_{t}}=-1,\
\beta_{c_{1}}=\cdots=\beta_{c_{r}}=0.\\\ \\{a_{1},\ldots,a_{s},\
b_{1},\ldots,b_{t},\ c_{1},\ldots,\ c_{r}\\}=\\{1,\ldots,n-1\\},\\\ r,s,t\geq
0,\ t\geq 1,\ \ r+s+t=n-1.\end{array}$

In geometry it is easy to see that the convex polytope $\widehat{T}^{-}$ is
the convex hull of its surface $S^{-}$ and its vertices
$e_{c_{1}},\ldots,e_{c_{r}}$, that is,

$\widehat{T}^{-}={\rm conv}\\{e_{c_{1}},\ldots,e_{c_{r}},S^{-}\\}.$ (2)
$\begin{array}[]{l}S^{-}=\\{(y_{1},\ldots,y_{n-1})^{T}\in\Delta_{n-1}|y_{a_{1}}+\cdots+y_{a_{s}}-y_{b_{1}}-\cdots-
y_{b_{t}}\leq 0,\\\
\qquad\quad(y_{a_{1}},\ldots,y_{a_{s}},y_{b_{1}},\ldots,y_{b_{t}})^{T}\in\Delta_{s+t}\\}.\end{array}$
(3)

If the simplicial subdivision of $S^{-}$ is known, the simplicial subdivision
of $\widehat{T}^{-}$ is directly obtained by (2). So we just need to study the
simplicial subdivision of the polytope $S^{-}$.

##  2 A simplicial subdivision algorithm for the convex polytope $S^{-}$

###  2.1 Fundamental notations

The notation $S^{-}$ is simple, but it can not reveal the information of
convex polytopes. In order to simplify the descriptions, we will introduce a
new notation, which is fundamental to our study.

###### Definition 2.1

Suppose that two sequences of positive integers $[a_{1},a_{2},\ldots,a_{s}]$,
$[b_{1},b_{2},\ldots,b_{t}]$ satisfy

$\\{a_{1},\ldots,a_{s},\ b_{1},\ldots,b_{t}\\}\subseteq\\{1,2,\ldots,m\\},\
s\geq 0,t\geq 1,m\geq s+t\geq 2,$

where all of $s+t$ elements of $\\{a_{1},\ldots,a_{s},\ b_{1},\ldots,b_{t}\\}$
are distinct. Then the notation
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$ is defined as
the polytope $S^{-}$ in (3).

For example, let us compare the polytope $[[2,3],[5]]_{5}$ and the polytope
$[[2,3],[5]]_{6}$. $[[2,3],[5]]_{5}$ denotes the polytope

$\\{(y_{1},\ldots,y_{5})^{T}\in\Delta_{5}|y_{2}+y_{3}-y_{5}\leq
0,(y_{2},y_{3},y_{5})^{T}\in\Delta_{3}\\}.$

Here $(y_{2},y_{3},y_{5})^{T}\in\Delta_{3}$ implies that $y_{1}=0,y_{4}=0$.
$[[2,3],[5]]_{6}$ indicates the polytope

$\\{(y_{1},\ldots,y_{6})^{T}\in\Delta_{6}|y_{2}+y_{3}-y_{5}\leq
0,(y_{2},y_{3},y_{5})^{T}\in\Delta_{3}\\}.$

Here $(y_{2},y_{3},y_{5})^{T}\in\Delta_{3}$ implies that
$y_{1}=0,y_{4}=0,y_{6}=0$. It is clear that $[[2,3],[5]]_{5}$ and
$[[2,3],[5]]_{6}$ are congruent, although they are sets in simplices of
different dimensions.

For $0\leq k\leq m-1$, the polytope $L_{k}^{-}$ is defined as

$L_{k}^{-}=\\{(y_{1},\ldots,y_{m})^{T}\in\Delta_{m}|y_{1}+\cdots+y_{k}-y_{k+1}-\cdots-
y_{m}\leq 0\\}.$

$L_{k}^{-}$ is written as $[[1,\ldots,k],[k+1,\ldots,m]]_{m}$ by the notation
of Definition 2.1. $L_{k}^{-}$ is a special case of $S^{-}$, but this notation
is more convenient for our analysis.

In the following we will study the basic geometric properties of convex
polytope $[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$.

###  2.2 Geometric properties of $S^{-}$

Let $e_{1},\ldots,e_{m}$ be vertices of the standard simplex $\Delta_{m}$, and
$M_{i,j}=(e_{i}+e_{j})/2$ be the midpoint of the line segment
$\overline{e_{i}e_{j}}$.

The following result is stated in [1] without proof. For completeness, we give
a proof.

###### Lemma 2.1

[1] Given a convex polytope $L_{k}^{-}$, then all of its vertices are

$V=\\{e_{k+1},\ldots,e_{m},\ M_{i,j},i=1,2,\ldots,k,\ j=k+1,\ldots,m\\}.$

The number of the vertices is $|V|=(k+1)(m-k)$.

###### Proof 1

Note that the convex polytope $L_{k}^{-}$ is obtained by cutting the standard
simplex $\Delta_{m}$ with the hyperplane

$L_{=0}:\ y_{1}+\cdots+y_{k}-y_{k+1}-\cdots-y_{m}=0.$

Therefore the vertices of the polytope $L_{k}^{-}$ come from two parts: one
part is vertices of $\Delta_{m}$, that is, $\\{e_{k+1},\ldots,e_{m}\\}$; while
the other part is the intersection points of the hyperplane $L_{=0}$ and the
edges of standard simplex $\Delta_{m}$.

First consider the intersection point of $L_{=0}$ and the edge
$ae_{1}+be_{k+1}\ (a,b\geq 0,\ a+b=1)$. Substitute $ae_{1}+be_{k+1}$ into the
following equations,

$y_{1}+\cdots+y_{k}-y_{k+1}-\cdots-y_{m}=0,\ y_{1}+\cdots+y_{m}=1$

Therefore, the solutions are $a=1/2,b=1/2$, namely, the intersection point is
$M_{1,k+1}$.

In the same way, we get all intersection points of $L_{=0}$ and the edges of
$\Delta_{m}$. They are $\\{M_{i,j},i=1,2,\ldots,k,\ j=k+1,\ldots,m.\\}$.

Hence the number of vertices of $L_{k}^{-}$ is $|V|=m-k+k(m-k)=(k+1)(m-k)$.

Likewise, we can prove the following lemma.

###### Lemma 2.2

Given a convex polytope
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$, then all of its
vertices are

$V=\\{e_{b_{1}},\ldots,e_{b_{t}},\ M_{a_{i},b_{j}},i=1,2,\ldots,s,\
j=1,\ldots,t\\}.$

The number of the vertices is $|V|=(s+1)t$.

We see that the polytope
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$ and the polytope
$L_{k}^{-}$ are similar in many respects, which will be further discussed.

###### Lemma 2.3

The convex polytope $L_{k}^{-}$ is simplicial iff $k=0$, or $k=m-1$.

###### Proof 1

When $k=0$, $L_{0}^{-}=\Delta_{m}$ is simplicial.

When $k=m-1$, consider the convex polytope

$L_{m-1}^{-}:=\\{(y_{1},\ldots,y_{m})^{T}\in\Delta_{m}|\
y_{1}+\cdots+y_{m-1}-y_{m}\leq 0\\}.$

By Lemma 2.1, we know that all vertices of $L_{m-1}^{-}$ are $\\{e_{m},\
M_{i,m},i=1,2,\ldots,$
$m-1\\}$. Obviously all the vectors of $\\{M_{i,m}-e_{m},i=1,2,\ldots,m-1\\}$
are linearly independent, so $L_{m-1}^{-}$ is simplicial.

Conversely, we know that the dimension of the polytope $L_{k}^{-}$ is $m-1$.
If $k\neq 0,m-1$, then by Lemma 2.1, the number of the vertices of $L_{k}^{-}$
is $(k+1)(m-k)\neq m$, so $L_{k}^{-}$ is not simplicial.

###### Lemma 2.4

The convex polytope
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$ (here the
vertices are obtained by Lemma 2.2) is simplicial iff $s=0$, or $t=1$.

###### Lemma 2.5

The dimension of the polytope
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$ is $(s+t-1)$.

If the polytope $[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$
is not a simplex, we will subdivide it into simplices.

###### Lemma 2.6

If the polytope $[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$
is not a simplex, then there are only two $(s+t-2)$-dimensional surfaces that
do not include the vertex $M_{a_{1},b_{1}}$. They are

$[[a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m},\
[[a_{1},\ldots,a_{s}],[b_{2},\ldots,b_{t}]]_{m}.\ $

(obtained by deleting $a_{1},b_{1}$ from array
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$ respectively)

###### Proof 1

All the $(s+t-2)$-dimensional surfaces of the convex polytope
$[[a_{1},a_{2},\ldots,a_{s}],\ [b_{1},b_{2},\ldots,b_{t}]]_{m}$ are obviously

$[[\widehat{a}_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m},$

$[[a_{1},\widehat{a}_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m},$

$\ldots,$

$[[a_{1},a_{3},\ldots,a_{s}],[b_{1},b_{2},\ldots,\widehat{b}_{t}]]_{m}$
(where the notation
$[[\widehat{a}_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$ is the
polytope with $a_{1}$ removed) and

$\begin{array}[]{l}\\{(y_{1},\ldots,y_{m})^{T}\in\Delta_{m}|y_{a_{1}}+\cdots+y_{a_{s}}-y_{b_{1}}-\cdots-
y_{b_{t}}=0,\ (y_{a_{1}},\ldots,y_{a_{s}},\\\ \quad
y_{b_{1}},\ldots,y_{b_{t}})^{T}\in\Delta_{s+t}\\}.\end{array}$

That makes $s+t+1$ $(s+t-2)$-dimensional surfaces in all. We can verify that
only

$[[a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m},\
[[a_{1},\ldots,a_{s}],[b_{2},\ldots,b_{t}]]_{m}$

do not include the vertex $M_{a_{1},b_{1}}$.

Lemma 2.6 leads to the following decomposition theorem.

###  2.3 The decomposition process for the polytope $S^{-}$

######  Theorem 2.1 (decomposition theorem)

If the polytope $[[a_{1},a_{2},\ldots,a_{s}]$,
$[b_{1},b_{2},\ldots,b_{t}]]_{m}$ is not simplicial, then it can be decomposed
into the union of two convex polytopes (not always simplicial). The expression
is

$\begin{array}[]{l}\quad[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}\\\
={\rm
conv}\\{M_{a_{1},b_{1}},[[a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}\\}\bigcup\\\
\quad{\rm
conv}\\{M_{a_{1},b_{1}},[[a_{1},a_{2},\ldots,a_{s}],[b_{2},\ldots,b_{t}]]_{m}\\}.\end{array}$

Here ${\rm conv}\\{S\\}$ denotes the convex hull of the set $S$ of points .

###### Proof 1

This follows from Lemma 2.6.

Based on Theorem 2.1, the polytope $S^{-}$ can be easily subdivided into
simplices.

###### Example 1

Show the simplicial subdivision of the following convex polytope

$L_{2}^{-}:=\\{(y_{1},\ldots,y_{5})|\ y_{1}+y_{2}-y_{3}-y_{4}-y_{5}\leq
0,(y_{1},\ldots,y_{5})^{T}\in\Delta_{5}\\}.$

###### Solution 1

Denote $L_{2}^{-}$ as $[[1,2],[3,4,5]]_{5}$. We know that
$[[1,2],[3,4,5]]_{5}$ is not simplicial by Lemma 2.4. Using Theorem 2.1 we
have

$\begin{array}[]{l}[[1,2],[3,4,5]]_{5}={\rm
conv}\\{M_{1,3},[[2],[3,4,5]]_{5}\\}\bigcup{\rm
conv}\\{M_{1,3},[[1,2],[4,5]]_{5}\\}.\end{array}$

By Lemma 2.4 we know that both $[[2],[3,4,5]]_{5}$ and $[[1,2],[4,5]]_{5}$ are
not simplicial. Therefore we repeatedly apply Theorem 2.1 to them and have

$\begin{array}[]{l}[[2],[3,4,5]]_{5}\\\ ={\rm conv}\\{M_{2,3},[[\
],[3,4,5]]_{5}\\}\bigcup{\rm conv}\\{M_{2,3},[[2],[4,5]]_{5}\\}.\\\ ={\rm
conv}\\{M_{2,3},[[\ ],[3,4,5]]_{5}\\}\bigcup{\rm conv}\\{M_{2,3},M_{2,4},[[\
],[4,5]]_{5}\\}\bigcup\\\ \quad{\rm
conv}\\{M_{2,3},M_{2,4},[[2],[5]]_{5}\\}\\\ ={\rm
conv}\\{M_{2,3},e_{3},e_{4},e_{5}\\}\bigcup{\rm
conv}\\{M_{2,3},M_{2,4},e_{4},e_{5}\\}\bigcup\\\ \quad{\rm
conv}\\{M_{2,3},M_{2,4},M_{2,5},e_{5}\\}.\end{array}$

$\begin{array}[]{l}[[1,2],[4,5]]_{5}\\\ ={\rm
conv}\\{M_{1,4},[[2],[4,5]]_{5}\\}\bigcup{\rm
conv}\\{M_{1,4},[[1,2],[5]]_{5}\\}.\\\ ={\rm conv}\\{M_{1,4},M_{2,4},[[\
],[4,5]]_{5}\\}\bigcup{\rm conv}\\{M_{1,4},M_{2,4},[[2],[5]]_{5}\\}\bigcup\\\
\quad{\rm conv}\\{M_{1,4},[[1,2],[5]]_{5}\\}\\\ ={\rm
conv}\\{M_{1,4},M_{2,4},e_{4},e_{5}\\}\bigcup{\rm
conv}\\{M_{1,4},M_{2,4},M_{2,5},e_{5}\\}\bigcup\\\ \quad{\rm
conv}\\{M_{1,4},M_{1,5},M_{2,5},e_{5}\\}.\end{array}$

Finally we get the expression of simplicial subdivision of
$[[1,2],[3,4,5]]_{5}$,

$\begin{array}[]{l}[[1,2],[3,4,5]]_{5}\\\ ={\rm
conv}\\{M_{1,3},M_{2,3},e_{3},e_{4},e_{5}\\}\bigcup{\rm
conv}\\{M_{1,3},M_{2,3},M_{2,4},e_{4},e_{5}\\}\bigcup\\\ \quad{\rm
conv}\\{M_{1,3},M_{2,3},M_{2,4},M_{2,5},e_{5}\\}\bigcup{\rm
conv}\\{M_{1,3},M_{1,4},M_{2,4},e_{4},e_{5}\\}\bigcup\\\ \quad{\rm
conv}\\{M_{1,3},M_{1,4},M_{2,4},M_{2,5},e_{5}\\}\bigcup{\rm
conv}\\{M_{1,3},M_{1,4},M_{1,5},M_{2,5},e_{5}\\}.\end{array}$

So $[[1,2],[3,4,5]]_{5}$ is a union of six 4-dimensional simplices.

We summarize the decomposition process of Example 1 into the following
algorithm.

Algorithm 1 (Vmatrix)

Input: The expression of polytope
$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}$.

Output: Simplices $D_{1},D_{2},\ldots,D_{p}$(denoted by matrices) such that

$[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}=\bigcup_{i=1}^{p}D_{i},\
{\rm int}(D_{i})\bigcap{\rm int}(D_{j})=\emptyset,\ {\rm for}\ i\neq j.$

V1: Let
$F:=\\{[[a_{1},a_{2},\ldots,a_{s}],[b_{1},b_{2},\ldots,b_{t}]]_{m}\\}$, ${\rm
temp}:=\emptyset$.

V2: When $F\neq\emptyset$, repeat the following procedures

V21: Choose a polytope $N\in F$. If $N$ is simplicial, then

${\rm temp}:={\rm temp}\cup\\{N\\}$, $F:=F\setminus\\{N\\}$.

V22: If the polytope $N$ is not simplicial, then by Theorem 2.1 de-

compose it into two convex polytope $B_{1},B_{2}$.

$F:=F\setminus\\{N\\}\cup\\{B_{1},B_{2}\\}$. Go to step V2.

V3: Return ${\rm temp}$.

We have written a function in Maple [31] to implement the above algorithm.

Lastly, we will present a formula for computing the number of simplices given
by the polytope $L_{k}^{-}$ subdivision.

###### Lemma 2.7

According to algorithm Vmatrix, the convex polytope $[[1,\ldots,k]$,
$[k+1,\ldots,m]]_{m}$ $(0\leq k\leq m-1,m\geq 2)$ can be subdivided just into
$f(k,m)$ simplices, where

$f(k,m)=\left(\begin{array}[]{c}m-1\\\
k\end{array}\right)=\frac{(m-1)!}{k!(m-1-k)!}.$

We know that $f(k,m)$ has the same recurrence formula as binomial coefficients
by Theorem 2.1. Thus the proof of Lemma 2.7 is easy via an induction argument.
This formula will be used to estimate the cost of Algorithm 2 in the next
section.

##  3 Determining algorithm for copositive matrices

In this section, we will present the complete determining algrorithm of a
copositive matrix.

Given an $n\times n$ symmetric matrix

$A=[\alpha_{ij}]=\left[\begin{array}[]{cc}\alpha_{11}&\alpha^{T}\\\
\alpha&A_{2}\end{array}\right],$

compute $\widehat{A}$ (see (1))

$\widehat{A}=\left[\begin{array}[]{cc}\alpha_{11}&\widehat{\alpha}^{T}\\\
\widehat{\alpha}&DA_{2}D\end{array}\right].$

Let $B=\alpha_{11}DA_{2}D-\widehat{\alpha}\widehat{\alpha}^{T}$, and let

$\widehat{\alpha}=({\rm sign}(\alpha_{12}),\ldots,{\rm
sign}(\alpha_{1n}))^{T}=(\beta_{1},\ldots,\beta_{n-1})^{T}.$

Define the projection operator Proj of the matrix $A$ as follows,

$\bullet$ If $\beta_{i}\geq 0,\ i=1,\ldots,n-1$, then

${\rm Proj(A)}=\\{DA_{2}D\\}.$

$\bullet$ If there is at least one -1 in $\beta_{i}$, then

${\rm Proj(A)}=\\{DA_{2}D,\ W_{1}^{T}BW_{1},\ \ldots,\ W^{T}_{p}BW_{P}\\}.$

Here the matrices $W_{1},\ldots,W_{p}$ is fixed by the simplicial subdivision
of the convex polytope $\widehat{T}^{-}$ (see (2)).

Algorithm 2 (COPOMATRIX)

Input: Symmetric matrix $A\in{\mathbf{R}}^{n\times n}(n\geq 2)$.

Output: $A$ is copositive, or $A$ is not copositive.

C1: Let $F:=\\{A\\}$.

C2: Repeat the following steps for the set $F$.

C21: If the set $F$ is empty, then return “$A$ is copositive”.

C22: Check the (1,1)th entry of every matrix $K$ in set $F$. If at least

one of them is negative, then return “$A$ is not copositive”.

C23: Compute the projective set $P:=\bigcup_{K\in F}{\rm Proj}(K)$ of set $F$.

$F:=P\setminus\\{\hbox{the nonnegative matrices of $P$}\\}$. Go to step C21.

Note that the above algorithm is also valid for $2\times 2$ matrices.
Furthermore, for strictly copositive matrices we can also formulate a similar
algorithm.

The correctness of the algorithm COPOMATRIX is guaranteed by Lemma 1.1, and
the algorithm obviously terminates. The cost of the algorithm mainly depends
on the number of simplicial subdivisions of the polytope. According to Lemma
2.7, we can estimate that in the worst case it is at most:

$\begin{array}[]{l}(\left(\begin{array}[]{c}n-2\\\
\left[\frac{n-2}{2}\right]\end{array}\right)+1)(\left(\begin{array}[]{c}n-3\\\
\left[\frac{n-3}{2}\right]\end{array}\right)+1)\cdots(\left(\begin{array}[]{c}2\\\
1\end{array}\right)+1)\\\ \leq(2^{n-3})(2^{n-4})\cdots(2)(2)\\\
=2^{(n-2)(n-3)/2+1}.\end{array}$

The bound $2^{(n-2)(n-3)/2+1}$ is already much lower than doubly-exponential
cost of CAD [2,9]. We have written a function in Maple to implement the
algorithm COPOMATRIX. For non-commercial request, we will offer for free.
Please sent e-mail to the address

<EMAIL_ADDRESS>or,

<EMAIL_ADDRESS>
##  4 Acknowledgement

The work of the authors were supported by the Chinese National Science
Foundation under contracts 11001228 and 10901116. The authors also would like
to thank the referees for their helpful suggestions.

## References

  * [1] L.E. Andersson, G. Chang, T. Elfving, Criteria for copositive matrices using simplices and barycentric coordinates, Linear Algebra Appl. 220 (1995) 9-30.
  * [2] S. Basu, R. Pollack, M.F. Roy, Algorithms in Real Algebraic Geometry (2nd), Springer-Verlag, New York (Berlin, Heidelberg), 2006, 159-194, 533-562.
  * [3] I.M. Bomze, Block pivoting and shortcut strategies for detecting copositivity, Linear Algebra Appl. 248 (1996) 161-184.
  * [4] I.M. Bomze, Linear-time copositivity detection for tridiagonal matrices and extension to block-tridiagonality, SIAMJ. Matrix Anal. Appl. 21 (2000) 840-848.
  * [5] I.M. Bomze, M. D$\ddot{u}$r, E. de Klerk, C. Roos, A.J. Quist, T. Terlaky, On copositive programming and standard quadratic optimization problems, J. Global Optim. 18 (2000) 301-320.
  * [6] S. Bundfuss, M. D$\ddot{u}$r, Algorithmic copositivity detection by simplicial partition, Linear Algebra Appl. 428 (2008) 1511-1523.
  * [7] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming. 120 (2009) 479-495.
  * [8] G.E. Collins, Quantifier elimination for real closed fields by cylindric algebraic decomposition, In: Second GI Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Science, vol. 33, 134-183, Springer-Verlag, Berlin, 1975.
  * [9] G.E. Collins, H. Hong, Partial cylindrical algebraic decomposition for quantifier elimination, J.Symb.Comput. 12 (1991) 299-328.
  * [10] R.W. Cottle, G.J. Habetler, C.E. Lemke, On classes of copositive matrices, Linear Algebra Appl. 3 (1970) 295-310.
  * [11] G. Danninger, Role of copositivity in optimality criteria for nonconvex optimization problems, J. Optim. Theory Appl. 75 (1992) 535-558.
  * [12] G. Danninger, A recursve algorithm to detect (strict) copositivity of a matrix, in: U. Rieder, A. Peyerimhoff, F.J. Rademacher (Eds.), Methods of Operations Research, vol. 62, 1990, pp. 45-52.
  * [13] G. Eichfelder, J. Jahn, Set-semidefinite optimization. J. Convex Anal. 15 (2008) 767-801.
  * [14] K.P. Hadeler, On copositive matrices, Linear Algebra Appl. 49 (1983) 79-89.
  * [15] P. Hadjicostas, Copositive matrices and simpson’s paradox, Linear Algebra Appl. 264 (1997) 475-488.
  * [16] M. Hall Jr., M. Newman, Copositive and completely positive quadratic forms, Proc. Cambridge Philos. Soc. 59 (1963) 329-339.
  * [17] E. Haynsworth, A.J. Hoffman, Two remarks on copositive matrices. Linear Algebra Appl. 2 (1969) 387-392.
  * [18] A.J. Hoffman, F. Pereira, On copositive matrices with -1, 0, 1 entries, J. Combin. Theory Ser. A 14 (1973) 302-309.
  * [19] L. Hogben, C.R. Johnson, R. Reams, The copositive completion problem, Linear Algebra Appl. 408 (2005) 207-211.
  * [20] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1992.
  * [21] K.D. Ikramov, Linear-time algorithm for verifying the copositivity of an acyclic matrix, Comput. Math. Math. Phys. 42 (2002) 1701-1703.
  * [22] K.D. Ikramov, N.V. Savel’eva, Conditionally definite matrices, J. Math. Sci. 98 (2000) 1-50.
  * [23] C.R. Johnson, R. Reams, Constructing copositive matrices from interior matrices, Electronic Journal of Linear Algebra, 17 (2008) 9-20.
  * [24] C.R. Johnson, R. Reams, Spectral theory of copositive matrices, Linear Algebra Appl. 395 (2005) 275-281.
  * [25] B. J$\ddot{u}$ttler, Arbitrarily weak linear convexity conditions for multivariate polynomials, Stud. Sci. Math. Hungar. 36 (2000) 165-183.
  * [26] E. de Klerk, D.V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAMJ. Optim. 12 (2002) 875-892.
  * [27] W. Kaplan, A test for copositive matrices, Linear Algebra Appl. 313 (2000) 203-206.
  * [28] W. Kaplan, A copositivity probe, Linear Algebra Appl. 337 (2001) 237-251.
  * [29] C.E. Lemke, Bimatrix equilibrium points and mathematical programming, Manage. Sci. 11 (1965) 681-689.
  * [30] P. Li, Y.Y. Feng, Criteria for copositive matrices of order four, Linear Algebra Appl. 194 (1993) 109-124.
  * [31] Maple 14 user manual, Maplesoft. http: //www.maplesoft.com/ documentation/ _center/.
  * [32] M. Marshall, Positive Polynomials and Sums of Squares, AMS Press, NewYork 2008.
  * [33] D.H. Martin, Finite criteria for conditional definiteness of quadratic forms, Linear Algebra Appl. 39 (1981) 9-21.
  * [34] D.H. Martin, D.H. Jacobson, Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints, Linear Algebra Appl. 35 (1981) 227-258.
  * [35] B. Mishra, Algorithmic Algebra, Springer-Verlag, New York, 1993, 333-354.
  * [36] T.S. Motzkin, Copositive quadratic forms, National Bureau of Standards Report 1818 (1952) 11-22.
  * [37] K.G. Murty, S.N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Program. 39 (1987) 117-129.
  * [38] P.A. Parrilo, Semidefinite programming based test for matrix copositivity, Proceedings of the 39th IEEE Conference on Decision and Control 5 (2000) 4624-4629.
  * [39] A.J. Quist, E. de Klerk, C. Roos, T. Terlaky, Copositive relaxation for general quadratic programming, Optim. Methods Softw. 9 (1998) 185-208.
  * [40] A. Tarski, A Decision method for elementary algebra and geometry, University of California Press, California, 1951.
  * [41] H. V$\ddot{a}$liaho, Criteria for copositive matrices, Linear Algebra Appl. 81 (1986) 19-34.
  * [42] H. V$\ddot{a}$liaho, Testing the definiteness of matrices on polyhedral cones, Linear Algebra Appl. 101 (1988) 135-165.
  * [43] H. V$\ddot{a}$liaho, Quadratic programming criteria for copositive matrices, Linear Algebra Appl. 119 (1989) 163-182.
  * [44] L. Yang, B. Xia, Computational Real Algebraic Geometry, In: D.M. Wang (eds), Selected lecture in symbolic computation, Tusinghua Univ. Press, Beijing, 2003. (in Chinese)
  * [45] L. Yang, B. Xia, Automated Proving and Discovering on Inequalities, Science Press, Beijing, 2008. (in Chinese)
  * [46] L. Yang, J. Zhang, A practical program of automated proving for a class of geometric inequalities, Automated Deduction in Geometry, Lecture Notes in Artificial Intelligence 2061, Springer-Verlag, 2001, 41-57.
  * [47] L. Yang, Recent advances in automated theorem proving on inequalities, J. Comput Sci & Technol. 14 (1999), 434-446.
  * [48] S. Yang, X. Li, Some simple criteria for copositive matrices, in: Proceedings of the Seventh International Conference on Matrix Theory and Applications, Advances in Matrix Theory and Applications, World Academic Union, 2006.
  * [49] S. Yang, X. Li, Algorithms for determining the copositivity of a given symmetric matrix, Linear Algebra Appl. 430 (2009) 609-618.


# The inertia bound is far from tight

Matthew Kwan Institute of Science and Technology Austria (ISTA), 3400
Klosterneuburg, Austria. Email address<EMAIL_ADDRESS>Supported by
ERC Starting Grant “RANDSTRUCT” No. 101076777. Yuval Wigderson Institute for
Theoretical Studies, ETH Zürich, 8092 Zürich, Switzerland. Email address:
<EMAIL_ADDRESS>Supported by Dr. Max Rössler, the Walter
Haefner Foundation, and the ETH Zürich Foundation.

###### Abstract

The _inertia bound_ and _ratio bound_ (also known as the _Cvetković bound_ and
_Hoffman bound_) are two fundamental inequalities in spectral graph theory,
giving upper bounds on the independence number $\alpha(G)$ of a graph $G$ in
terms of spectral information about a weighted adjacency matrix of $G$. For
both inequalities, given a graph $G$, one needs to make a judicious choice of
weighted adjacency matrix to obtain as strong a bound as possible.

While there is a well-established theory surrounding the ratio bound, the
inertia bound is much more mysterious, and its limits are rather unclear. In
fact, only recently did Sinkovic find the first example of a graph for which
the inertia bound is not tight (for any weighted adjacency matrix), answering
a longstanding question of Godsil. We show that the inertia bound can be
extremely far from tight, and in fact can significantly underperform the ratio
bound: for example, one of our results is that for infinitely many $n$, there
is an $n$-vertex graph for which even the unweighted ratio bound can prove
$\alpha(G)\leq 4n^{3/4}$, but the inertia bound is always at least $n/4$. In
particular, these results address questions of Rooney, Sinkovic, and
Wocjan–Elphick–Abiad.

##  1 Introduction

Spectral graph theory contains a wide array of deep and surprising results
which relate certain combinatorial graph parameters to linear-algebraic
parameters of associated matrices. Of particular importance are those results
which bound the independence number $\alpha(G)$ of a graph $G$ in terms of its
spectrum, as such results have many applications in other areas of
combinatorics (see e.g. the monographs [23, 24, 8, 7]).

Probably the most famous such result is the _ratio bound_ (also known as the
_Hoffman bound_). To state it, we need some notation. If $G$ is a graph with
vertex set $\\{1,\dots,n\\}$, we say that $A$ is a _weighted adjacency matrix_
of $G$ if $A_{ij}=0$ whenever $ij$ is not an edge of $G$. In other words, we
can obtain $A$ by starting with the adjacency matrix of $G$, and replacing
every $1$ by an arbitrary real number (including zero and negative numbers),
while maintaining symmetry of the matrix.

######  Theorem 1.1 (Ratio bound).

Let $G$ be a graph and let $A$ be a weighted adjacency matrix of $G$ with
equal row sums. Let $\lambda_{\mathrm{min}}$ and $\lambda_{\mathrm{max}}$ be
the minimum and maximum eigenvalues of $A$, respectively. Then

$\alpha(G)\leq\left|\frac{\lambda_{\mathrm{min}}}{\lambda_{\mathrm{max}}-\lambda_{\mathrm{min}}}\right|n.$

The ratio bound was first proved by Hoffman (unpublished), who only stated it
in the case that $A$ is the (ordinary) adjacency matrix of $G$. Even this
result is surprisingly powerful; for example, it can be used to give a short
proof of the Erdős–Ko–Rado theorem [21] (see e.g. [23, Section 2.5] for
details). However, the flexibility of choosing an arbitrary weighted adjacency
matrix makes the ratio bound much more powerful (see e.g. [47]). Determining
the optimal weights to use for the ratio bound can be formulated as a
semidefinite program, and the rich theory of semidefinite optimization can
therefore be used to theoretically and computationally determine the optimal
choice of weights for any given graph.

In this paper we will mostly be concerned with a closely related, yet much
more mysterious, bound, known as the _inertia bound_ (or the _Cvetković
bound_). For a symmetric $n\times n$ matrix $A$, we denote by $n_{\geq 0}(A)$
the number of non-negative eigenvalues of $A$.

######  Theorem 1.2 (Inertia bound).

Let $G$ be a graph and let $A$ be a weighted adjacency matrix of $G$.
Then111In the literature, the inertia bound is often stated as
$\alpha(G)\leq\min\\{n-n_{>0}(A),n-n_{<0}(A)\\}$, but it is easy to see that
this statement is equivalent to Theorem 1.2, by replacing $A$ with $-A$ if it
has more negative than positive eigenvalues.

$\alpha(G)\leq n_{\geq 0}(A).$

In many ways, the story of the inertia bound parallels that of the ratio
bound. It was first proved by Cvetković [12], who stated it only for adjacency
matrices. This already has a number of interesting applications, including
another short proof of the Erdős–Ko–Rado theorem (see e.g. [23, Section 2.10]
for details), but the flexibility of general weighted adjacency matrices makes
the bound much more powerful. The general statement for arbitrary weighted
adjacency matrices was perhaps first noted by Calderbank and Frankl [9], who
used it to prove several results in extremal set theory.

Compared to the ratio bound, we know very little about optimal weight matrices
for the inertia bound: the search space is infinite, and it is unclear how to
minimize $n_{\geq 0}$ over this search space (though see [43] for some
heuristics). In many specific applications, such as recent work of
Huang–Klurman–Pohoata [29] and the Calderbank–Frankl result mentioned above
[9], the choice of weights can be guided by the symmetries inherent in the
problem. Specifically, in such applications, one can restrict to a natural
subset of the space of all weighted adjacency matrices, called the
_Bose–Mesner algebra_ , and apply representation-theoretic techniques to
understand the structure of this algebra (see e.g. [23, 7] for introductions
to this theory). Similarly, Huang’s breakthrough resolution of the sensitivity
conjecture [28] used ideas closely related to the inertia bound, and the
choice of weights comes from the inherent symmetries of the hypercube (see [5,
3, 26, 40, 46, 31, 33] for discussion on the connections to the inertia bound,
and on the theory behind the choice of weights). For more on the general
relationships between graphs and spaces of matrices supported on their edges,
see [36] and references therein.

Due to our lack of understanding of optimal weighted adjacency matrices, it is
unclear what the limits of the inertia bound really are, even for specific
small graphs. The most fundamental question in this direction is the following
(which seems to have been first explicitly asked by Godsil [22], and
reiterated in [16, 15, 43]).

######  Question 1.3 (Godsil [22]).

Is the inertia bound always tight? In other words, is it the case that for
every graph $G$, there exists a weighted adjacency matrix $A$ with
$\alpha(G)=n_{\geq 0}(A)$?

Godsil’s question was open for more than a decade, until it was finally
resolved in the negative by Sinkovic [45].

######  Theorem 1.4 (Sinkovic [45]).

Let $G$ be the _Paley graph_ on $17$ vertices. Then $\alpha(G)=3$, but
$n_{\geq 0}(A)\geq 4$ for every weighted adjacency matrix $A$ of $G$.

Sinkovic’s proof involves a great deal of casework, and as such is highly
specific to the 17-vertex Paley graph. However, in recent years, new
techniques were developed which shed more light on Godsil’s question. First,
Mančinska and Roberson [39] introduced a new graph parameter, the _quantum
independence number_ $\alpha_{q}$, which satisfies
$\alpha_{q}(G)\geq\alpha(G)$ for every graph $G$. Moreover, they proved [39,
Corollary 4.8] that for infinitely many $n$, there exists an $n$-vertex graph
with independence number $O(n^{1-\varepsilon})$ and quantum independence
number $\Omega(n/{\log n})$, for some small absolute constant $\varepsilon>0$.
More recently, Wocjan, Elphick and Abiad [48] proved that the inertia bound is
also an upper bound on the quantum independence number, even when one allows
_Hermitian_ weights. Namely, they proved [48, Theorem 3.3] that if $A$ is a
Hermitian weighted adjacency matrix222Here, we say that $A$ is a Hermitian
weighted adjacency matrix of $G$ if it is a Hermitian matrix with complex
entries such that $A_{ij}=0$ whenever $ij\notin E(G)$. of $G$, then
$\alpha_{q}(G)\leq n_{\geq 0}(A)$. Putting these results together, one obtains
the following, stronger, negative answer to 1.3.

######  Theorem 1.5 ([39, 48]).

There exist constants $C,c,\varepsilon>0$ such that the following holds. For
infinitely many values of $n$, there exists an $n$-vertex graph with

$\alpha(G)\leq Cn^{1-\varepsilon}\qquad\text{ and }\qquad n_{\geq
0}(A)\geq\alpha_{q}(G)\geq c\frac{n}{\log n}$

for every Hermitian weighted adjacency matrix $A$ of $G$.

Theorems 1.5 and 1.4 provide answers to 1.3, but this is really just the tip
of the iceberg. The most obvious follow-up question (raised by Rooney [43] and
Sinkovic [45]) is how large the gap in Theorem 1.2 can be; Theorem 1.5 implies
that this gap can be as large as $\Omega(n/{\log n})$, but perhaps it can be
even larger.

Second, there is the quantum analogue of 1.3, that is, the question of whether
the inertia bound333Here, and from now on, when we say “the inertia bound” we
will usually mean the minimum of $n_{\geq 0}(A)$ over all weighted adjacency
matrices $A$ of a given graph. is always tight for the quantum independence
number. This question was answered by Wocjan, Elphick, and Abiad [48], who
gave an example of an 18-vertex graph $G$ with $\alpha_{q}(G)<n_{\geq 0}(A)$
for all Hermitian weighted adjacency matrices $A$ of $G$. However, this
example does not rule out the possibility that every graph has a weighted
adjacency matrix for which the gap between the quantum independence number and
the inertia bound is always at most 1.

Third, even though we now know that the inertia bound is not always tight,
perhaps it is still the case that the inertia bound is in some sense “the best
possible spectral bound” on the independence number. Concretely, is the
inertia bound always stronger than the ratio bound? Actually, this question is
closely related to the previous one, since the ratio bound is also an upper
bound on the quantum independence number of a graph [39, Corollary 4.9].

As our main result, we address all the above questions, showing that in fact
the inertia bound can dramatically underperform the ratio bound, and thereby
also obtaining new bounds on the largest possible gap between the inertia
bound and independence number.

######  Theorem 1.6.

For infinitely many positive integers $n$, there exists an $n$-vertex regular
graph $G$, whose (ordinary) adjacency matrix has minimum and maximum
eigenvalues $\lambda_{\mathrm{min}}$ and $\lambda_{\mathrm{max}}$,
respectively, such that

$\alpha(G)\leq\alpha_{q}(G)\leq\left|\frac{\lambda_{\mathrm{min}}}{\lambda_{\mathrm{max}}-\lambda_{\mathrm{min}}}\right|n\leq
4n^{\frac{3}{4}}\qquad\text{ and }\qquad n_{\geq 0}(A)\geq\frac{n}{4}$

for every Hermitian weighted adjacency matrix $A$ of $G$.

In fact, our main technical result is substantially stronger than Theorem 1.6:
it shows that the inertia bound is very weak whenever $G$ is $C_{4}$-free,
i.e. does not contain $C_{4}$ as a subgraph. We can moreover obtain a small
constant-factor improvement when $G$ is also $C_{3}$-free, i.e. has girth at
least 5.

######  Theorem 1.7.

Let $G$ be an $n$-vertex graph and let $A$ be any Hermitian weighted adjacency
matrix of $G$.

  1. (i)

If $G$ is $C_{4}$-free, then

$n_{\geq 0}(A)\geq\beta n,$

where $\beta=\sqrt{3}-\frac{3}{2}\approx 0.232$.

  2. (ii)

If $G$ has girth at least 5, then

$n_{\geq 0}(A)\geq\frac{n}{4}.$

Theorem 1.7 immediately implies the existence of graphs for which the inertia
bound is far from tight, by letting $G$ be a $C_{4}$-free graph whose
independence number is $o(n)$. There are many examples of such graphs, defined
explicitly or obtained via the probabilistic method. In particular, the
statement of Theorem 1.6 follows from 1.7(ii), taking $G$ to be an edge-
transitive induced subgraph of at least half the vertices of the polarity
graph of a finite projective plane, with girth at least 5 (such a graph was
shown to exist by Parsons [42, Theorem 1(a)])444By [37, Theorem 9], the Lovász
theta number of $G$ is then
$|\lambda_{\mathrm{min}}/(\lambda_{\mathrm{max}}-\lambda_{\mathrm{min}})|n$,
where $\lambda_{\mathrm{min}},\lambda_{\mathrm{max}}$ are the minimum and
maximum eigenvalues, respectively, of the ordinary adjacency matrix. The
Lovász theta number is monotonic with respect to induced subgraphs, and it is
well-known (e.g. [41]) that the theta number of full polarity graph $G_{0}$ is
at most $2\lvert V(G_{0})\rvert^{3/4}$.. It is an interesting byproduct of our
results that the inertia bound is so weak for such algebraically-defined
graphs, as generally speaking, techniques from spectral graph theory seem
particularly well-suited to highly structured graphs with many symmetries.

We also remark that if one is interested in the largest possible
_multiplicative_ gap between the independence number and inertia bound, one
can combine 1.7(i) with a result of Bohman and Keevash [6]: they used the
_random $C_{4}$-free process_ to prove the existence of $C_{4}$-free graphs
with independence number $O((n\log n)^{\frac{2}{3}})$. It is a major open
problem, asked repeatedly by Erdős (e.g. [20, 19, 18, 17]), to determine
whether there exist $C_{4}$-free graphs with independence number
$n^{\frac{1}{2}+o(1)}$. We remark too that the constant factors $\beta$ and
$\frac{1}{4}$ in Theorem 1.7 appear to be the best possible with our
technique, although there is no reason to believe they are optimal.

Although our proof is quite short, we end this introduction with a high-level
sketch of the argument. Let $A$ be a weighted adjacency matrix of a
$C_{4}$-free graph $G$. If we let the eigenvalues of $A$ be
$\lambda_{1}\geq\dotsb\geq\lambda_{n}$, and let $X$ be a random variable
taking on value $\lambda_{i}$ with probability $1/n$ (this is the _empirical
spectral distribution_), then our task reduces to proving a lower bound on
$\operatorname{Pr}(X\geq 0)$. To this end, it suffices to study the _moments_
of this random variable: it turns out that $\operatorname{Pr}(X\geq 0)$ is
reasonably large whenever $\mathbb{E}[X^{4}]$ is not too much larger than
$(\mathbb{E}[X^{2}])^{2}$ (Lemma 2.3). So, it suffices to prove an upper bound
on the fourth moment of $X$. Using the hypothesis that $G$ is $C_{4}$-free,
one can obtain such an upper bound, as long as one has some control on the
sizes of entries of $A$ (see Lemma 3.1); however, this approach cannot work if
the entries of $A$ come from many very different scales. To overcome this
obstruction, we apply techniques from the field of matrix scaling (see Lemmas
2.7 and 2.6), together with Sylvester’s law of inertia (Lemma 2.4), to either
reduce to the case where the entries of $A$ have roughly the same size, or to
split the problem into smaller sub-problems and apply induction.

In the next section, we collect a few preliminaries we will need in the proof
of Theorem 1.7, which we prove in Section 3. We end in Section 4 with some
concluding remarks.

######  Remark.

Theorem 1.2 shows that the inertia bound can be much weaker than the ratio
bound. As suggested by Anurag Bishnoi (following an early version of this
paper), it is also natural to ask the opposite question: can the ratio bound
be much weaker than the inertia bound? Perhaps the easiest way to demonstrate
this is using graphs of the form $G=K_{d,d}\sqcup K_{d+1}\sqcup\dots\sqcup
K_{d+1}$ (i.e., the disjoint union of a $d$-regular complete bipartite graph
with several copies of the $d$-regular complete graph). Indeed, if there are
$d$ copies of $K_{d+1}$, then $G$ has $n=2d+d(d+1)$ vertices; one can compute
that the ratio bound is $n/2$ and that the inertia bound gives the exact
independence number, which is $d+(1+\dots+1)=2d=O(\sqrt{n})$. More
interestingly, Ihringer [32] showed that an $n$-vertex graph arising from a
so-called _association scheme_ introduced by Cameron and Seidel [10] has ratio
bound $\Omega(n^{3/4})$ and inertia bound $O(n^{1/2})$ (see also [14] for
another application of the same association scheme). This example is
significant because for graphs arising from association schemes, the ratio
bound coincides with two other important bounds on the independence number of
a graph: the Lovász theta function and Delsarte’s linear programming bound
(see [44] for details).

##  2 Preliminaries

We begin with a few preliminary results, which we mostly cite from previous
works.

###  2.1 Probabilistic bounds via moments

First, we need two inequalities, due respectively to He, Zhang, and Zhang [25]
and Zelen [49], related to the general phenomenon that if the fourth moment of
a random variable is commensurate to its second moment squared, then the
distribution of $X$ cannot be too “extreme”. In particular, if such a random
variable has mean zero, then it must have a reasonable proportion of its
probability mass on each side of zero. We remark that a simpler result with
worse quantitative dependencies appears in [2, Lemma 3.2(i)], and a general
approach to proving such inequalities is given in [4, 35].

######  Lemma 2.1 ([25, Theorem 2.1]).

For any real-valued random variable $Y$ and for any $y>0$, we have

$\operatorname{Pr}(Y\geq 0)\leq
1-\frac{4}{9}(2\sqrt{3}-3)\left(-\frac{2\mathbb{E}[Y]}{y}+\frac{3\mathbb{E}[Y^{2}]}{y^{2}}-\frac{\mathbb{E}[Y^{4}]}{y^{4}}\right).$

One can get stronger bounds if one is given information on
$\mathbb{E}[Y^{3}]$; the following such result is a special case of [49,
equation (12)], specialized to $\mathbb{E}[Y^{3}]=0$.

######  Lemma 2.2 ([49, equation (12)]).

For any real-valued random variable $Y$ with
$\mathbb{E}[Y]=0,\mathbb{E}[Y^{2}]=1$, and $\mathbb{E}[Y^{3}]=0$, and any
$a\in(-\sqrt{\mathbb{E}[Y^{4}]},\sqrt{\mathbb{E}[Y^{4}]})$, we have

$\operatorname{Pr}(Y<a)\geq\frac{1}{2\sqrt{\mathbb{E}[Y^{4}]}\left(\sqrt{\mathbb{E}[Y^{4}]}-a\right)}.$

We will apply Lemmas 2.1 and 2.2 in the following form, suited to our
purposes.

######  Lemma 2.3.

Let $X$ be a real-valued random variable satisfying
$\mathbb{E}[X]=0,\mathbb{E}[X^{2}]=1$, and $\mathbb{E}[X^{4}]\leq 2$.

  1. (i)

We have $\operatorname{Pr}(X>0)\geq\beta$, where $\beta=\sqrt{3}-\frac{3}{2}$
as in Theorem 1.7.

  2. (ii)

If moreover $\mathbb{E}[X^{3}]=0$, then
$\operatorname{Pr}(X>0)\geq\frac{1}{4}$.

###### Proof.

Let $Y=-X$, and note that $\mathbb{E}[Y]=0,\mathbb{E}[Y^{2}]=1$, and
$\mathbb{E}[Y^{4}]\leq 2$. We apply Lemma 2.1 with $y=2/\sqrt{3}$ (which is
chosen to yield the best possible bound). We find that

$\displaystyle\operatorname{Pr}(X>0)$
$\displaystyle=\operatorname{Pr}(Y<0)=1-\operatorname{Pr}(Y\geq
0)\geq\frac{4}{9}(2\sqrt{3}-3)\left(\frac{3}{y^{2}}-\frac{2}{y^{4}}\right)=\sqrt{3}-\frac{3}{2}=\beta,$

which proves 2.3(i). Under the added assumption that $\mathbb{E}[X^{3}]=0$, we
have that $\mathbb{E}[Y^{3}]=0$ as well. Applying Lemma 2.2 with $a=0$ shows
that

$\operatorname{Pr}(X>0)=\operatorname{Pr}(Y<0)\geq\frac{1}{2\mathbb{E}[Y^{4}]}\geq\frac{1}{4},$

proving 2.3(ii). ∎

###  2.2 Simple facts about eigenvalues

We will need two basic results of linear algebra. The first is called
Sylvester’s law of inertia; see e.g. [27, Theorem 4.5.8] for a proof.

######  Lemma 2.4.

Let $A$ be a Hermitian $n\times n$ matrix, let $Z$ be an invertible $n\times
n$ matrix, and let $B=ZAZ^{*}$. Then $A$ and $B$ have the same number of
positive, negative, and zero eigenvalues. In particular, $n_{\geq
0}(A)=n_{\geq 0}(B)$.

We will also use the following simple consequence of Cauchy’s interlacing
formula; see e.g. [24, Theorem 9.1.1] or [27, Theorem 4.3.28] for a proof. We
remark that it immediately implies the inertia bound if applied to a zero
principal submatrix, i.e. an independent set.

######  Lemma 2.5.

Let $A$ be a Hermitian matrix, and let $A^{\prime}$ be a principal submatrix
of $A$. Then $n_{\geq 0}(A)\geq n_{\geq 0}(A^{\prime})$.

###  2.3 Matrix scaling

Finally, we need a result about matrix scaling. Matrix scaling deals with
questions about when one can scale the rows and columns of a matrix in order
to obtain specified row and column sums. Somewhat surprisingly, it turns out
that such a scaling is possible if and only if the set of non-zero entries of
the matrix satisfies certain combinatorial conditions. For more on the general
matrix scaling problem, see e.g. the survey [30].

Specifically, we use the following result, which was proved by Datta [13] and
subsequently reproved by Csima and Datta [11]. Here and for the rest of the
paper, we use the notation $[n]=\\{1,\dots,n\\}$. Recall that a matrix is
_doubly stochastic_ if all its row and column sums are equal to $1$.

######  Lemma 2.6 ([13, 11]).

Let $M$ be a symmetric $n\times n$ matrix with non-negative real entries. The
following two conditions are equivalent.

  1. 1.

There exists a diagonal matrix $D$ with strictly positive diagonal entries
such that $DMD$ is doubly stochastic.

  2. 2.

For every $(a,b)\in[n]^{2}$ with $M_{ab}\neq 0$, there exists a permutation
$\pi\in S_{n}$ with $\pi(a)=b$ such that $M_{i\pi(i)}\neq 0$ for all
$i\in[n]$.

We will use the following simple corollary of Lemma 2.6. If $M$ is an $n\times
n$ matrix and $S,T\subseteq[n]$, we denote by $M[S,T]$ the submatrix of $M$ of
rows and columns in $S$ and $T$, respectively.

######  Lemma 2.7.

Let $M$ be a symmetric $n\times n$ matrix with non-negative entries. Suppose
that for all non-empty $S,T\subseteq[n]$ with $M[S,T]=0$, we have $\lvert
S\rvert+\lvert T\rvert<n$. Then there exists a diagonal matrix $D$ with
strictly positive diagonal entries such that $DMD$ is doubly stochastic.

###### Proof.

Let $G$ be the bipartite graph with parts $A,B$, where $A=B=[n]$, and where
$(x,y)\in E(G)$ if and only if $M_{xy}\neq 0$. Suppose for contradiction that
there exists no such $D$. By Lemma 2.6, there exists an $(a,b)\in[n]^{2}$ such
that $M_{ab}\neq 0$, but there is no permutation $\pi$ such that $\pi(a)=b$
and $M_{i\pi(i)}\neq 0$ for all $i$. Equivalently, the edge $(a,b)$
participates in no perfect matching of $G$.

Now, let $H$ be the subgraph of $G$ induced on the vertex set
$(A\setminus\\{a\\})\cup(B\setminus\\{b\\})$. Then $H$ has no perfect
matching. By Hall’s theorem (see e.g. [24, Theorem 15.15.3]), this implies
that there exists some non-empty $S\subseteq A$ with $\lvert
N_{H}(S)\rvert<\lvert S\rvert$. Letting $T=(B\setminus\\{b\\})\setminus
N_{H}(S)$, we find that there is no edge between $S$ and $T$, and

$\lvert S\rvert+\lvert T\rvert=\lvert S\rvert+((\lvert B\rvert-1)-\lvert
N_{H}(S)\rvert)>\lvert S\rvert+((n-1)-\lvert S\rvert)=n-1.$

Hence, we have found non-empty subsets $S,T\subseteq[n]$ with $\lvert
S\rvert+\lvert T\rvert\geq n$. Moreover, as there is no edge between $S$ and
$T$ in $H$, there is also no edge between them in $G$, and hence $M_{st}=0$
for all $s\in S,t\in T$, a contradiction. ∎

##  3 Proof of Theorem 1.7

In this section, we prove Theorem 1.7. We begin by proving the following
lemma, which implies Theorem 1.7 in case all rows of the weighted adjacency
matrix have the same $L^{2}$ norm. Later, we will see how this special case
actually implies the full theorem.

######  Lemma 3.1.

Let $G$ be an $n$-vertex graph, and let $B$ be a Hermitian weighted adjacency
matrix of $G$. Suppose that every row of $B$ has $L^{2}$ norm $1$, i.e. that
$\sum_{j=1}^{n}\lvert B_{ij}\rvert^{2}=1$ for all $i\in[n]$.

  1. (i)

If $G$ is $C_{4}$-free, then $n_{\geq 0}(B)\geq\beta n$, where
$\beta=\sqrt{3}-\frac{3}{2}$ as in Theorem 1.7.

  2. (ii)

If $G$ has girth at least $5$, then $n_{\geq 0}(B)\geq n/4$.

###### Proof.

We begin with 3.1(i), so let $G$ be a $C_{4}$-free graph. Let
$\lambda_{1}\geq\dotsb\geq\lambda_{n}$ be the eigenvalues of $B$. Let $X$ be
the random variable that takes value $\lambda_{i}$ with probability $1/n$, for
all $i\in[n]$. We have the identity

$n_{\geq 0}(B)=n\cdot\operatorname{Pr}(X\geq 0)\geq
n\cdot\operatorname{Pr}(X>0).$ (1)

Since $B$ has zero diagonal, we know that
$\mathbb{E}[X]=\operatorname{tr}(B)/n=0$. Similarly, by the assumption that
the rows of $B$ have $L^{2}$ norm $1$, we can compute

$\mathbb{E}[X^{2}]=\frac{1}{n}\operatorname{tr}(B^{2})=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}B_{ij}B_{ji}=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{2}=1.$

We would like to apply Lemma 2.3, so we need to estimate $\mathbb{E}[X^{4}]$,
which is equal to $\frac{1}{n}\operatorname{tr}(B^{4})$. Note that

$\operatorname{tr}(B^{4})=\sum_{i,j,k,\ell=1}^{n}B_{ij}B_{jk}B_{k\ell}B_{\ell
i}.$

Since $B$ is a weighted adjacency matrix of $G$, a tuple of vertices
$(i,j,k,\ell)$ can provide a nonzero contribution only if it represents a
closed walk in $G$.

We now use the fact that $G$ is $C_{4}$-free to find that the only closed
walks of length $4$ which provide a nonzero contribution to
$\operatorname{tr}(B^{4})$ are _degenerate_ (i.e. they repeat vertices). In
$G$, such walks come in two combinatorial types: those that traverse a single
edge four times, and those that traverse a _cherry_ (i.e. a 2-edge path)
twice. Each single-edge walk is counted twice, once for each of its starting
vertices. Each cherry walk is counted four times: once starting at each of its
outer vertices, and twice starting at its central vertex, since from there the
cherry can be traversed in two different orientations.

We can sum over (unlabeled) cherries by first summing over choices for the
central vertex, then summing over ordered pairs of candidates for the outer
vertices, then subtracting the contribution from non-distinct candidates for
the outer vertices (and then dividing by 2 to account for the fact that the
outer vertices should not be ordered). This yields

$\displaystyle\operatorname{tr}(B^{4})$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{4}+4\cdot\frac{1}{2}\left(\sum_{i=1}^{n}\left(\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{2}\right)^{2}-\sum_{i=1}^{n}\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{4}\right)$
$\displaystyle=2\sum_{i=1}^{n}\left(\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{2}\right)^{2}-\sum_{i=1}^{n}\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{4}$ $\displaystyle=2n-\sum_{i=1}^{n}\sum_{j=1}^{n}\lvert
B_{ij}\rvert^{4}\leq 2n.$

Therefore,

$\mathbb{E}[X^{4}]=\frac{1}{n}\operatorname{tr}(B^{4})\leq 2.$

We may therefore apply 2.3(i) to find that $\operatorname{Pr}(X>0)\geq\beta$.
Plugging this into (1) completes the proof of 3.1(i). Then, 3.1(ii) can be
proved in virtually the same way, using 2.3(ii) instead of 2.3(i). Indeed,
note that if $G$ has girth at least 5 then it has no closed walks of length 3,
so $\mathbb{E}[X^{3}]=0$. ∎

We are now ready to prove Theorem 1.7.

###### Proof of Theorem 1.7.

We begin with 1.7(i). Our proof is by induction on $n$, with the base case
$n=1$ being trivial as then $A$ must be the zero matrix. We now assume that
$n>1$, and that the result has been proved for all smaller values of $n$.

We split into two cases according to Lemma 2.7. Suppose first that there exist
non-empty sets $S,T\subseteq[n]$ with $\lvert S\rvert+\lvert T\rvert\geq n$
and $A[S,T]=0$. As $A$ is Hermitian, this implies that $A[T,S]=0$ as well. Let
us permute the rows of $A$ so that the rows in $S\setminus T$ come first, then
those in $S\cap T$, then those in $T\setminus S$, and finally those in
$[n]\setminus(S\cup T)$ (and apply the same permutation to the columns, so
that $A$ remains Hermitian). Then we can write $A$ in block form as

$\blockarray{ccccc}&S\setminus TS\cap TT\setminus S\\\
\block{c(cccc)}S\setminus TA_{1}00*\\\ S\cap T000*\\\ T\setminus S00A_{2}*\\\
****\\\ ~{},$

where $A_{1},A_{2}$ are principal submatrices of $A$ of sizes $\lvert
S\setminus T\rvert,\lvert T\setminus S\rvert$, respectively, and where $*$
denotes an arbitrary submatrix. By Lemma 2.5, we know that $n_{\geq 0}(A)\geq
n_{\geq 0}(A^{\prime})$, where $A^{\prime}$ is the principal submatrix on rows
and columns in $S\cup T$. Moreover, as $A^{\prime}$ is block-diagonal, its
eigenvalues are those of $A_{1}$, those of $A_{2}$, plus $\lvert S\cap
T\rvert$ additional zero eigenvalues. Applying the inductive hypothesis to
$A_{1}$ and $A_{2}$, which are Hermitian weighted adjacency matrices of
smaller $C_{4}$-free graphs, we find that

$\displaystyle n_{\geq 0}(A)$ $\displaystyle\geq n_{\geq 0}(A^{\prime})$
$\displaystyle=n_{\geq 0}(A_{1})+n_{\geq 0}(A_{2})+\lvert S\cap T\rvert$
$\displaystyle\geq\beta{\lvert S\setminus T\rvert}+\beta{\lvert T\setminus
S\rvert}+\lvert S\cap T\rvert$ $\displaystyle\geq\beta\left({\lvert S\setminus
T\rvert+\lvert T\setminus S\rvert+2\lvert S\cap T\rvert}\right)$
$\displaystyle[\text{as }\beta\leq\tfrac{1}{2}]$ $\displaystyle=\beta(\lvert
S\rvert+\lvert T\rvert)$ $\displaystyle\geq\beta n.$

This concludes the proof in this case. Therefore, we may assume that such sets
$S,T$ do not exist. Let $M$ be the matrix defined by $M_{ij}=\lvert
A_{ij}\rvert^{2}$, and note that $M$ has non-negative entries and the same set
of zero entries as $A$. In particular, if $M[S,T]=0$ for some
$S,T\subseteq[n]$, then $\lvert S\rvert+\lvert T\rvert<n$. By Lemma 2.7, we
conclude that there exists a diagonal matrix $D$ with strictly positive
diagonal entries such that $DMD$ is doubly stochastic. Let the diagonal
entries of $D$ be $d_{1},\dots,d_{n}$.

Now, let $Z$ be the diagonal matrix whose diagonal entries are
$\sqrt{d_{1}},\dots,\sqrt{d_{n}}$, and let $B=ZAZ=ZAZ^{*}$. By Lemma 2.4, we
have that $n_{\geq 0}(B)=n_{\geq 0}(A)$. Moreover, the $(i,j)$ entry of $B$ is
$\sqrt{d_{i}d_{j}}A_{ij}$, and hence for any $i\in[n]$,

$\sum_{j=1}^{n}\lvert B_{ij}\rvert^{2}=\sum_{j=1}^{n}d_{i}d_{j}\lvert
A_{ij}\rvert^{2}=\sum_{j=1}^{n}d_{i}d_{j}M_{ij}=\sum_{j=1}^{n}(DMD)_{ij}=1,$

since the matrix $DMD$ is doubly stochastic. We may now apply 3.1(i) to $B$ to
conclude that $n_{\geq 0}(A)=n_{\geq 0}(B)\geq\beta n$, which completes the
proof. The proof of 1.7(ii) is again virtually identical; one simply replaces
the application of 3.1(i) above by 3.1(ii). ∎

##  4 Concluding remarks

To end this paper, we would like to highlight two further questions about the
inertia bound that our techniques seem incapable of resolving. The first is a
question of Ihringer [31], who asked whether the inertia bound is tight for
almost all graphs. This is equivalent to asking about the tightness of the
inertia bound for the binomial random graph $\mathbb{G}(n,\frac{1}{2})$. We
make the following conjecture.

######  Conjecture 4.1.

For any $\varepsilon>0$, the following holds with probability $1-o(1)$ for
$G\sim\mathbb{G}(n,\frac{1}{2})$ as $n\to\infty$. Every weighted adjacency
matrix $A$ of $G$ has $n_{\geq 0}(A)\geq(\frac{1}{2}-\varepsilon)n$.

In particular, as $\alpha(\mathbb{G}(n,\frac{1}{2}))=O(\log n)$ with
probability $1-o(1)$, 4.1 would imply that the inertia bound is far from tight
for almost all graphs.

Theorem 1.7 (together with results on the $C_{4}$-free process [6]) implies
that there exist graphs $G$ for which $n_{\geq 0}(A)$ is larger than
$\alpha(G)^{\frac{3}{2}-o(1)}$ for any weighted adjacency matrix $A$ of $G$.
If 4.1 is true, it would imply that there exist graphs with $n_{\geq
0}(A)>2^{\alpha(G)/3}$ for any weighted adjacency matrix $A$. However, neither
of these rule out the possibility that $n_{\geq 0}(A)$ is upper-bounded by
_some_ function of $\alpha(G)$. We conjecture that no such upper bound exists.

######  Conjecture 4.2.

For every integer $k$, there exists a graph $G$ with $\alpha(G)=2$ and
$n_{\geq 0}(A)\geq k$ for every weighted adjacency matrix $A$ of $G$.

We remark that a result of Konyagin [34] implies the analogous statement for
the ratio bound, i.e. that for every $k\in\mathbb{N}$ there exists a graph $G$
with $\alpha(G)=2$ for which the ratio bound (with any weighted adjacency
matrix) cannot be used to prove $\alpha(G)<k$. Indeed, Konaygin showed that
there are graphs $G$ with $\alpha(G)=2$ which have arbitrarily large values of
the so-called _Lovász theta number_ [37]. For more details, see [1] or [38,
Chapter 11].

#### Acknowledgements:

We are grateful to Anurag Bishnoi, Clive Elphick, and Ferdinand Ihringer for
helpful comments and interesting discussions on an earlier draft of this
paper.

## References

  * [1] N. Alon, _Lovász, vectors, graphs and codes_ , Building bridges II—mathematics of László Lovász, Bolyai Soc. Math. Stud., vol. 28, Springer, Berlin, 2019, pp. 1–16.
  * [2] N. Alon, G. Gutin, and M. Krivelevich, _Algorithms with large domination ratio_ , J. Algorithms 50 (2004), no. 1, 118–131.
  * [3] N. Alon and K. Zheng, _Unitary signings and induced subgraphs of Cayley graphs of $\mathbb{Z}^{n}_{2}$_, Adv. Comb. (2020), Paper No. 11, 12pp.
  * [4] D. Bertsimas and I. Popescu, _Optimal inequalities in probability theory: a convex optimization approach_ , SIAM J. Optim. 15 (2005), no. 3, 780–804.
  * [5] A. Bishnoi, _Spectral proofs of theorems on the boolean hypercube_ , available online, 2019.
  * [6] T. Bohman and P. Keevash, _The early evolution of the $H$-free process_, Invent. Math. 181 (2010), no. 2, 291–336.
  * [7] A. E. Brouwer, A. M. Cohen, and A. Neumaier, _Distance-regular graphs_ , Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989.
  * [8] A. E. Brouwer and W. H. Haemers, _Spectra of graphs_ , Universitext, Springer, New York, 2012.
  * [9] A. R. Calderbank and P. Frankl, _Improved upper bounds concerning the Erdős-Ko-Rado theorem_ , Combin. Probab. Comput. 1 (1992), no. 2, 115–122.
  * [10] P. J. Cameron and J. J. Seidel, _Quadratic forms over $GF(2)$_, Indag. Math. 35 (1973), 1–8, Nederl. Akad. Wetensch. Proc. Ser. A 76.
  * [11] J. Csima and B. N. Datta, _The $DAD$ theorem for symmetric non-negative matrices_, J. Combinatorial Theory Ser. A 12 (1972), 147–152.
  * [12] D. M. Cvetković, _Graphs and their spectra_ , Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. (1971), no. 354, 1–50.
  * [13] B. Datta, _Diagonal representation of the doubly stochastic limit_ , M.Sc. thesis, McMaster University, 1970.
  * [14] D. de Caen, _Large equiangular sets of lines in Euclidean space_ , Electron. J. Combin. 7 (2000), Research Paper 55, 3.
  * [15] R. J. Elzinga, _The minimum Witt index of a graph_ , Ph.D. thesis, Queen’s University, 2007.
  * [16] R. J. Elzinga and D. A. Gregory, _Weighted matrix eigenvalue bounds on the independence number of a graph_ , Electron. J. Linear Algebra 20 (2010), 468–489.
  * [17] P. Erdős, _On the combinatorial problems which I would most like to see solved_ , Combinatorica 1 (1981), no. 1, 25–42.
  * [18] P. Erdős, _Extremal problems in number theory, combinatorics and geometry_ , Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983), PWN, Warsaw, 1984, pp. 51–70.
  * [19] P. Erdős, _On some problems in graph theory, combinatorial analysis and combinatorial number theory_ , Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, pp. 1–17.
  * [20] P. Erdős, _Problems and results in combinatorial analysis and graph theory_ , Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), vol. 72, 1988, pp. 81–92.
  * [21] P. Erdős, C. Ko, and R. Rado, _Intersection theorems for systems of finite sets_ , Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320.
  * [22] C. Godsil, _Interesting graphs and their colourings_ , Unpublished lecture notes, 2004.
  * [23] C. Godsil and K. Meagher, _Erdős-Ko-Rado theorems: algebraic approaches_ , Cambridge Studies in Advanced Mathematics, vol. 149, Cambridge University Press, Cambridge, 2016.
  * [24] C. Godsil and G. Royle, _Algebraic graph theory_ , Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001.
  * [25] S. He, J. Zhang, and S. Zhang, _Bounding probability of small deviation: a fourth moment approach_ , Math. Oper. Res. 35 (2010), no. 1, 208–232.
  * [26] Z.-M. Hong, H.-J. Lai, and J. Liu, _Induced subgraphs of product graphs and a generalization of Huang’s theorem_ , J. Graph Theory 98 (2021), no. 2, 285–308.
  * [27] R. A. Horn and C. R. Johnson, _Matrix analysis_ , second ed., Cambridge University Press, Cambridge, 2013.
  * [28] H. Huang, _Induced subgraphs of hypercubes and a proof of the sensitivity conjecture_ , Ann. of Math. (2) 190 (2019), no. 3, 949–955.
  * [29] H. Huang, O. Klurman, and C. Pohoata, _On subsets of the hypercube with prescribed Hamming distances_ , J. Combin. Theory Ser. A 171 (2020), 105156, 21pp.
  * [30] M. Idel, _A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps_ , arXiv:1609.06349, 2016.
  * [31] F. Ihringer, _Huang’s breakthrough, Cvetković’s bound, Godsil’s question, and Sinkovic’s answer_ , available online, 2019.
  * [32] F. Ihringer, _Ratio bound (Lovász number) versus inertia bound_ , arXiv:2312.09524, 2023.
  * [33] R. Karasev, _Huang’s theorem and the exterior algebra_ , arXiv:1907.11175, 2019.
  * [34] S. V. Konyagin, _Systems of vectors in Euclidean space and an extremal problem for polynomials_ , Mat. Zametki 29 (1981), no. 1, 63–74.
  * [35] M. G. Kreĭn and A. A. Nudel’man, _The Markov moment problem and extremal problems_ , Translations of Mathematical Monographs, vol. Vol. 50, American Mathematical Society, Providence, RI, 1977, translated from the Russian by D. Louvish.
  * [36] Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, _Connections between graphs and matrix spaces_ , Israel J. Math. 256 (2023), no. 2, 513–580.
  * [37] L. Lovász, _On the Shannon capacity of a graph_ , IEEE Trans. Inform. Theory 25 (1979), no. 1, 1–7.
  * [38] L. Lovász, _Graphs and geometry_ , American Mathematical Society Colloquium Publications, vol. 65, American Mathematical Society, Providence, RI, 2019.
  * [39] L. Mančinska and D. E. Roberson, _Quantum homomorphisms_ , J. Combin. Theory Ser. B 118 (2016), 228–267.
  * [40] D. V. Mathews, _The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras_ , J. Eur. Math. Soc. (JEMS) 24 (2022), no. 12, 4201–4205.
  * [41] D. Mubayi and J. Williford, _On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph_ , J. Graph Theory 56 (2007), no. 2, 113–127.
  * [42] T. D. Parsons, _Graphs from projective planes_ , Aequationes Math. 14 (1976), no. 1-2, 167–189.
  * [43] B. Rooney, _Spectral aspects of cocliques in graphs_ , Ph.D. thesis, University of Waterloo, 2014.
  * [44] A. Schrijver, _A comparison of the Delsarte and Lovász bounds_ , IEEE Trans. Inform. Theory 25 (1979), no. 4, 425–429.
  * [45] J. Sinkovic, _A graph for which the inertia bound is not tight_ , J. Algebraic Combin. 47 (2018), no. 1, 39–50.
  * [46] T. Tao, _Twisted convolution and the sensitivity conjecture_ , available online, 2019.
  * [47] R. M. Wilson, _The exact bound in the Erdős-Ko-Rado theorem_ , Combinatorica 4 (1984), no. 2-3, 247–257.
  * [48] P. Wocjan, C. Elphick, and A. Abiad, _Spectral upper bound on the quantum $k$-independence number of a graph_, Electron. J. Linear Algebra 38 (2022), 331–338.
  * [49] M. Zelen, _Bounds on a distribution function that are functions of moments to order four_ , J. Res. Nat. Bur. Standards 53 (1954), 377–381.