# Conditions for eigenvalue configurations of two real symmetric matrices: a
symmetric function approach

Hoon Hong<EMAIL_ADDRESS>Department of Mathematics, North Carolina State
University, Raleigh, NC, USA  Daniel Profili<EMAIL_ADDRESS>Department of
Mathematics, North Carolina State University, Raleigh, NC, USA  J. Rafael
Sendra<EMAIL_ADDRESS>Department of Quantitative Methods, CUNEF-
University, Spain

###### Abstract

For two real symmetric matrices, their eigenvalue configuration is the
arrangement of their eigenvalues on the real line. We study the problem of
determining a quantifier-free necessary and sufficient condition for two real
symmetric matrices to realize a given eigenvalue configuration as a
generalization of Descartes’ rule of signs. We exploit the combinatorial
properties of our definition for eigenvalue configuration to reduce a two-
polynomial root counting problem into several single-polynomial root counting
problems of symmetric polynomials. We then leverage the fundamental theorem of
symmetric polynomials to derive a final quantifier-free necessary and
sufficient condition for two real symmetric matrices to realize a given
eigenvalue configuration.

##  1 Introduction

Let us take as a starting point for this introduction the problem of
determining quantifier-free necessary and sufficient conditions on the
coefficients of a polynomial such that its roots lie in a given subset of the
plane. This is a fundamental problem in computational algebra and geometry and
appears in the theory of stable polynomials, in combinatorics [9], in graph
theory [15], and in functional analysis [1], among others. A particularly
interesting case of this problem, that has been studied for centuries (see
e.g. [11]), is the root counting problem. This type of problem can be
addressed with quantifier elimination techniques, a very relevant area of
research since Tarski proved, and provided an algorithm for, its feasibility
over real closed fields (see [31] and [32]); see e.g. [22, 2, 14, 35, 13, 16,
17, 10, 18, 27, 7, 21, 34, 12, 23, 24, 3, 4, 29, 8, 6, 19] for further
contributions in this active research field. The main drawback to applied
these techniques is that the general algorithms in quantifier elimination have
still doubly exponential time complexity, and furthermore their outputs grow
very quickly toward being incomprehensible for even moderately sized inputs.
As a consequence of these limitations, it seems natural to address the problem
avoiding the use of general quantifier elimination techniques. This paper is
framed in that context.

In this paper we analyze the eigenvalue configuration of two real symmetric
matrices; that is, the arrangement of their eigenvalues on the real line. In
particular, the problem can be stated as follows: given an eigenvalue
configuration provide necessary and sufficient conditions on the entries of
two generic real symmetric matrices so that their eigenvalue configuration is
the prescribed one.

The main contribution of this paper is to provide a quantifier-free method to
solve the problem above. For this purpose, we exploit the combinatorial
structure of our definition of an eigenvalue configuration in order to
construct symmetric polynomials in the eigenvalues of the two matrices $F$ and
$G$ and then apply the Fundamental Theorem of Symmetric Polynomials to
transform these polynomials in the eigenvalues to polynomials in the entries
of $F$ and $G$. We then apply Descartes’ rule of signs to solve root counting
problems on these polynomials, the answers to which are combinatorially
related to the eigenvalue configuration of the original two matrices. As a
consequence, we produce a final parametric expression in the entries of $F$
and $G$ which is valid for any input size. Our contribution can be seen as a
natural way of generalizing Descartes’ rule of signs to more than one
univariate polynomial. There has been recent work on generalizing Descartes’
rule of signs to one multivariate polynomial [33], but to our knowledge, there
has not yet been work on generalizing Descartes’ rule of signs for multiple
univariate polynomials. In [20], we present a different solution to the same
problem, based on the use of the method proposed in [25].

The non-triviality of this problem comes for the fact that, for general real
symmetric matrices, there is no closed-form analytical expression for their
eigenvalues in terms of their entries. In addition, since our goal is to
parametrically characterize all possible matrices whose eigenvalues are
arranged in a certain way, numerical approaches cannot be used.

The structure of the paper is as follows. In Section 2, we state the problem
precisely. In Section 3, we state our main result (Theorem 8), which gives
necessary and sufficient conditions on two real symmetric matrices to have
their eigenvalues in a given order on the real line. In Section 4, we derive
Theorem 8, illustrating the key ideas. Finally, in Section 5 we provide
concise algorithms to illustrate the constructive nature of Theorem 8.

##  2 Problem

In this section, we will state the problem precisely. For this we first need a
few notations and a notion.

######  Notation 1.

  1. 1.

Let $F,G$ be $n\times n$ real symmetric matrices with simple and distinct
eigenvalues.

  2. 2.

Let $\alpha=\left(\alpha_{1},\ldots,\alpha_{n}\right)$ be the eigenvalues of$\
F$.

Let $\beta=\left(\beta_{1},\ldots,\beta_{n}\right)$ be the eigenvalues of $G$.

Since $F$ and $G$ are real symmetric, all their eigenvalues are real. Thus,
without losing generality, let us index the eigenvalues so that

$\displaystyle\alpha_{1}$ $\displaystyle<\alpha_{2}<\cdots<\alpha_{n}$
$\displaystyle\beta_{1}$ $\displaystyle<\beta_{2}<\cdots<\beta_{n}$

  3. 3.

Let $I_{t}=[\alpha_{t},\alpha_{t+1})$ for $t=1,\ldots,n$, where
$\alpha_{n+1}=\infty$.

######  Definition 2 (Eigenvalue Configuration).

The eigenvalue configuration, or eigen configuration, of $F$ and $G$, written
as $EC\left(F,G\right)$, is the tuple $c=(c_{1},\dots,c_{m})$ where
$c_{t}=\\#\\{i:\beta_{i}\in I_{t}\\}$.

######  Example 3.

Let $F,G\ $be such that the corresponding eigenvalues are given by

$\alpha=(1,3,7,9,12)\qquad\beta=(-1,2,8,10,11)$

Then

$\begin{array}[c]{ll}I_{1}=[\alpha_{1},\alpha_{2})=[1,3)&\ni\beta_{2}\\\
I_{2}=[\alpha_{2},\alpha_{3})=[3,7)&\\\
I_{3}=[\alpha_{3},\alpha_{4})=[7,9)&\ni\beta_{3}\\\
I_{4}=[\alpha_{4},\alpha_{5})=[9,12)&\ni\beta_{4},\beta_{5}\\\
I_{5}=[\alpha_{5},\infty)=[12,\infty)&\\\ \end{array}$

Therefore

$EC(F,G)=(1,0,1,2,0).$

The challenge is to develop an algorithm for the following problem.

######  Problem 4.

  1. In:

$n$ a positive integer

$c$ an eigenvalue configuration.

  2. Out:

a “simple condition” on the entries of $n\times n\ $real symmetric matrices
$F\ $and $G$ such that $c=EC\left(F,G\right)$.

######  Remark 5.

Here we clarify what the problem is precisely and what the challenge is.

  * •

What is the problem precisely? It amounts to clarifying what “simple”
condition means.

For this, we first write down the definition of $EC$ condition explicitly, by
stating all the implicit assumptions.

$c=EC\left(F,G\right)\ \ \ :\Longleftrightarrow\ \ \
\underset{\beta_{1},\ldots,\beta_{n}}{\underset{\alpha_{1},\ldots,\alpha_{n}}{\exists}}\bigwedge\left(\begin{array}[c]{l}\left|\alpha_{1}I_{n}-F\right|=0\\\
\,\,\,\,\vdots\\\ \left|\alpha_{n}I_{n}-F\right|=0\\\
\underset{x}{\forall}\left|xI_{n}-F\right|=0\Longrightarrow\left(x=\alpha_{1}\wedge\cdots\wedge
x=\alpha_{n}\right)\\\ \\\ \left|\beta_{1}I_{n}-G\right|=0\\\
\,\,\,\,\vdots\\\ \left|\beta_{n}I_{n}-G\right|=0\\\
\underset{x}{\forall}\left|xI_{n}-G\right|\
=0\Longrightarrow\left(x=\beta_{1}\wedge\cdots\wedge x=\beta_{n}\right)\\\ \\\
\beta_{1}<\cdots<\beta_{c_{0}}<\alpha_{1}\\\
\alpha_{1}<\beta_{c_{0}+1}<\cdots<\beta_{c_{0}+c_{1}}<\alpha_{2}\\\
\,\,\,\,\vdots\\\
\alpha_{m}<\beta_{c_{0}+c_{1}+\cdots+c_{m-1}+1}<\cdots<\beta_{n}\end{array}\right)$

where $c_{0}$ is a short hand for $n-c_{1}-\cdots-c_{n}$. The top block states
that all the eigenvalues of $F$ are exactly $\alpha_{1},\ldots,\alpha_{n}$.
The middle block states that all the eigenvalues of $G$ are exactly
$\beta_{1},\ldots,\beta_{n}$. The bottom block states that the eigen
configuration is given by $c$.

Note that the whole expression is a quantified boolean combination of
polynomial equations and inequalities, so-called “a well-formed formula in the
first order theory of real closed fields”. It involves the following
variables: the entries of $F$ and $G$ and the eigenvalues $\alpha$ and $\beta$
and another variable $x$. The condition is not “simple” in the sense that it
involves quantified variables, namely $\alpha,\beta$ and $x$.

Alfred Tarski’s celebrated theorem on real closed fields states that every
first order formula is equivalent to a quantifier-_free_ formula. [31]. Thus,
by “simple” condition, we mean a quantifier-_free_ formula in the entries of
$F,G$; more concretely, a boolean combination of polynomial equations and
inequalities in the entries of $F$ and $G$.

  * •

What is the challenge? Tarski’s proof was constructive, that is, the proof
provided the first algorithm for eliminating quantifiers [32]. Since then,
various alternative and/or improved algorithms have been developed, to list a
just a few [31, 32, 22, 2, 14, 35, 13, 16, 17, 10, 18, 27, 7, 21, 34, 12, 23,
24, 3, 4, 29, 8, 6, 19]. Some of them have fully implemented software
packages: QEPCAD [17, 10, 5], Reduce in Mathematica [29], RedLog [30], SyNRAC
[37], Discoverer [36], OpenCAD [26], RAGlib [28], Regular Chain [8] and so on.
Thus one might wonder whether we could just run those software on the above
quantified formula. However there are two major difficulties: (1) It requires
that we need to run the software on each $n$ from scratch. (2) Each run (on
each $n$) quickly becomes very time-consuming as and $n$ grows, making this
approach practically infeasible and (2) The output formula looks chaotic,
making it practically incomprehensible.

Thus, the challenge is to produce a quantifier-free formula for all $n$
efficiently and in a structured form.

##  3 Main Result

Before we state our main result, we first establish some notation.

######  Notation 6.

  1. 1.

$v(p)$, for a univariate polynomial $p$ with real coefficients, denotes the
sign variation count of $p$; that is, the number of times two consecutive
coefficients of $p$ have opposite sign, ignoring zeros.

$v(s)$, for a sign sequence $s\in\\{-,0,+\\}^{n}$, denotes the number of times
consecutive elements in $s$ have opposite sign, ignoring zeros.

  2. 2.

$\sigma_{j}(X)$, for a list of variables $X$, denotes the $j$-th elementary
symmetric polynomial in $X$; that is,

$\sigma_{j}(X):=\sum_{1\leq i_{1}<\dots<i_{j}\leq n}\
\prod_{k=1}^{j}X_{i_{k}}$

  3. 3.

$Q_{r}$, for a positive integer $r$, is defined as

$Q_{r}:=\left\\{\left(i_{1},\ldots,i_{r},j\right):1\leq
i_{1}<\cdots<i\,_{r}\leq n\ \ \wedge\ \ 1\leq j\leq n\right\\}$

  4. 4.

$q_{r}$, for a positive integer $r$, is defined as

$q_{r}:=\\#\left\\{\left(i_{1},\ldots,i_{r},j\right)\in
Q_{r}:\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)<0\right\\},$

where $\\#S$ denotes the number of elements of a finite set $S$.

  5. 5.

$h_{r}$, for a positive integer $r$, is defined as

$h_{r}:=\prod\limits_{\left(i_{1},\ldots,i_{r},j\right)\in
Q_{r}}\left(x-\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)\right)$

  6. 6.

For matrices $F$ and $G$, we label the coefficients in their respective
characteristic polynomials as follows.

$\displaystyle f=|xI-F|$
$\displaystyle=x^{n}-a_{1}x^{n-1}+a_{2}x^{n-2}-\cdots+(-1)^{n}a_{n}x^{0}$
$\displaystyle g=|xI-G|$
$\displaystyle=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}-\cdots+(-1)^{n}b_{n}x^{0}.$

Note the alternating signs and reverse indexing from the usual indexing of
polynomial coefficients.

  7. 7.

$T_{n}$, for a positive integer $n$, is the $n\times n$ matrix whose entries
are

$\displaystyle(T_{n})_{rs}=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}$

######  Example 7.

  1. 1.

$v(4x^{5}+3x^{2}+5x^{2}-3x+7)=2$

$v(0,0,-,0,-,0,+,-,+)=3$

  2. 2.

$\sigma_{2}(\alpha_{1},\alpha_{2},\alpha_{3})=\sum\limits_{1\leq
i_{1}<i_{2}\leq
3}\alpha_{i_{1}}\alpha_{i_{2}}=\alpha_{1}\alpha_{2}+\alpha_{1}\alpha_{3}+\alpha_{2}\alpha_{3}$

  3. 3.

Let $n=3$, so that $F$ has eigenvalues $\alpha_{1}<\alpha_{2}<\alpha_{3}$ and
$G$ has eigenvalues $\beta_{1}<\beta_{2}<\beta_{3}$. Then

$\displaystyle Q_{2}=\\{$ $\displaystyle(i_{1},i_{2},j):1\leq i_{1}<i_{2}\leq
3\,\wedge\,1\leq j\leq 3\\}$ $\displaystyle=\\{$
$\displaystyle(1,2,1),(1,3,1),(2,3,1),(1,2,2),(1,3,2),(2,3,2),(1,2,3),(1,3,3),(2,3,3)\\}$

  4. 4.

Continuing from the previous example, suppose in addition we have
$(\alpha_{1},\alpha_{2},\alpha_{3})=(1,2,4)$ and
$(\beta_{1},\beta_{2},\beta_{3})=(0,3,5)$. Then

$\displaystyle q_{2}$ $\displaystyle=\\#\left\\{\left(i_{1},i_{2},j\right)\in
Q_{2}:\prod_{p=1}^{2}\left(\alpha_{i_{p}}-\beta_{j}\right)<0\right\\}.$

We have

$\begin{array}[c]{|c|c|c|}\hline\cr(i_{1},i_{2},j)&\prod_{p=1}^{2}(\alpha_{i_{p}}-\beta_{j})&\text{Sign}\\\
\hline\cr(1,2,1)&(\alpha_{1}-\beta_{1})(\alpha_{2}-\beta_{1})=(1-0)(2-0)&>0\\\
(1,3,1)&(\alpha_{1}-\beta_{1})(\alpha_{3}-\beta_{1})=(1-0)(4-0)&>0\\\
(2,3,1)&(\alpha_{2}-\beta_{1})(\alpha_{3}-\beta_{1})=(2-0)(4-0)&>0\\\
(1,2,2)&(\alpha_{1}-\beta_{2})(\alpha_{2}-\beta_{2})=(1-3)(2-3)&>0\\\
(1,3,2)&(\alpha_{1}-\beta_{2})(\alpha_{3}-\beta_{2})=(1-3)(4-3)&{\color[rgb]{1,0,0}<0}\\\
(2,3,2)&(\alpha_{2}-\beta_{2})(\alpha_{3}-\beta_{2})=(2-3)(4-3)&{\color[rgb]{1,0,0}<0}\\\
(1,2,3)&(\alpha_{1}-\beta_{3})(\alpha_{2}-\beta_{3})=(1-5)(2-5)&>0\\\
(1,3,3)&(\alpha_{1}-\beta_{3})(\alpha_{3}-\beta_{3})=(1-5)(4-5)&>0\\\
(2,3,3)&(\alpha_{2}-\beta_{3})(\alpha_{3}-\beta_{3})=(2-5)(4-5)&>0\\\
\hline\cr\end{array}$

Thus

$\displaystyle q_{2}$ $\displaystyle=\\#\\{(1,3,2),(2,3,2)\\}=2.$

  5. 5.

Continuing from the running example, we have

$\displaystyle h_{2}=$
$\displaystyle\prod\limits_{\left(i_{1},i_{2},j\right)\in
Q_{2}}\left(x-\prod_{p=1}^{2}\left(\alpha_{i_{p}}-\beta_{j}\right)\right)$
$\displaystyle=$
$\displaystyle(x-(\alpha_{1}-\beta_{1})(\alpha_{2}-\beta_{1}))(x-(\alpha_{1}-\beta_{1})(\alpha_{3}-\beta_{1}))(x-(\alpha_{2}-\beta_{1})(\alpha_{3}-\beta_{1}))$
$\displaystyle(x-(\alpha_{1}-\beta_{2})(\alpha_{2}-\beta_{2}))(x-(\alpha_{1}-\beta_{2})(\alpha_{3}-\beta_{2}))(x-(\alpha_{2}-\beta_{2})(\alpha_{3}-\beta_{2}))$
$\displaystyle(x-(\alpha_{1}-\beta_{3})(\alpha_{2}-\beta_{3}))(x-(\alpha_{1}-\beta_{3})(\alpha_{3}-\beta_{3}))(x-(\alpha_{2}-\beta_{3})(\alpha_{3}-\beta_{3})).$

  6. 6.

Continuing from the running example, we have

$f=|xI-F|=(x-1)(x-2)(x-4)=x^{3}-7x^{2}+14x-8.$

Hence

$\displaystyle a_{1}$ $\displaystyle=7$ $\displaystyle a_{2}$
$\displaystyle=14$ $\displaystyle a_{3}$ $\displaystyle=8.$

We also have

$g=|xI-G|=(x-0)(x-3)(x-5)=x^{3}-8x^{2}+15x-0.$

Hence

$\displaystyle b_{1}$ $\displaystyle=8$ $\displaystyle b_{2}$
$\displaystyle=15$ $\displaystyle b_{3}$ $\displaystyle=0.$

######  Theorem 8 (Main Result).

Let $c=(c_{1},\dots,c_{n})$ be an eigenvalue configuration and let
$F,G\in\mathbb{R}^{n\times n}$ be symmetric.. Then

$EC(F,G)=c\iff\bigwedge_{r=1}^{n}v(p_{r}(-x))=(T_{n}c)_{r},$

where

$\displaystyle p_{r}$ $\displaystyle=\text{polynomial such that
}h_{r}(x,\alpha_{1},\dots,\alpha_{n},\beta_{1},\dots,\beta_{n})=p_{r}(x,a_{1},\dots,a_{n},b_{1},\dots,b_{n}).$

######  Remark 9.

The key idea of Theorem 8 is that in the logical equivalence

$\underbrace{EC(F,G)=c}_{\text{involves quantifiers (eigenvalues of
}F,G)}\iff\underbrace{\bigwedge_{r=1}^{n}v(p_{r}(-x))=(T_{n}c)_{r}}_{\text{involves
only polynomial operations, }c,\,\,\wedge,\,\,\vee,\text{ entries of }F,G},$

the left-hand side, when fully expanded in terms of the entries of $F$ and
$G$, involves quantifiers, since eigenvalue configurations are defined in
terms of the eigenvalues of $F$ and $G$. In contrast, the right-hand side
consists of a disjunction of conjunctions of polynomial equations and
inequalities involving the entries of $F$ and $G$, with no reference to the
eigenvalues of $F$ and $G$ and therefore no quantifiers.

##  4 Derivation of the Main Result

We present the proof of Theorem 8 in the style of a derivation. This approach
will allow us to better illustrate the key ideas behind this approach. To do
this, we split up the derivation into several lemmas, each of which
illustrates one key idea.

Our overall goal is to somehow express the information encoded in the
eigenvalue configuration in a way which does not refer directly to the
eigenvalues of $F$ and $G$. In order to do this, we will first define a vector
$q=(q_{1},\dots,q_{n})$ which encodes the information contained in the
eigenvalue configuration vector in a way that allows us to compute it via
counting the roots of a certain polynomial. We accomplish this via an
invertible linear transformation $T_{n}$ whose entries are defined
combinatorially. But first, we show that such a transformation exists.

######  Lemma 10 (Transform).

We have

$c=EC\left(F,G\right)\ \ \ \ \Longrightarrow\ \ \ \ q=T_{n}c$

where

$q=\begin{pmatrix}q_{1}\\\ \vdots\\\ q_{n}\end{pmatrix}\ \ \text{and
}c=\begin{pmatrix}c_{1}\\\ \vdots\\\ c_{n}\end{pmatrix}\ \ \text{and\ \
}T_{n}=\begin{pmatrix}(T_{n})_{11}&\cdots&(T_{n})_{1n}\\\ \vdots&&\vdots\\\
(T_{n})_{n1}&\cdots&(T_{n})_{nn}\end{pmatrix}$

and where

$(T_{n})_{rs}=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}.$

###### Proof.

Assume that $c=EC\left(F,G\right)$. It suffices to show $q=T_{n}c$. Recall
from Notation 6 that

$Q_{r}=\left\\{\left(i_{1},\ldots,i_{r},j\right):1\leq
i_{1}<\cdots<i\,_{r}\leq n\ \ \wedge\ \ 1\leq j\leq n\right\\},$

and

$q_{r}=\\#\left\\{\left(i_{1},\ldots,i_{r},j\right)\in
Q_{r}:\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)<0\right\\}.$

We proceed by repeatedly rewriting the definition of $q_{r}$, with the goal of
expressing it in terms of the eigenvalue configuration vector. We begin with
the definition of $q_{r}$.

$q_{r}=\\#\left\\{\left(i_{1},\ldots,i_{r},j\right)\in
Q_{r}:\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)<0\right\\}$

Note that for each $(i_{1},\dots,i_{r})$ satisfying $1\leq
i_{1}<\cdots<i_{r}\leq n$, we also have $(i_{1},\dots,i_{r},j)\in Q_{r}$
simply by appending each $j=1,\dots,n$. Hence, we can rewrite this action of
counting over the set $Q_{r}$ as a summation over all such tuples
$(i_{1},\dots,i_{r})$. Thus we obtain

$q_{r}=\sum_{1\leq i_{1}<\cdots<i_{r}\leq n}\
\\#\left\\{j:\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)<0\right\\}$

We can then introduce another summation by partitioning the set on the right-
hand side depending on which interval $I_{s}$ each $\beta_{j}$ belongs to.

$q_{r}=\sum_{1\leq s\leq n}\ \sum_{1\leq i_{1}<\cdots<i_{r}\leq n}\
\\#\left\\{j:\beta_{j}\in I_{s}\ \ \wedge\ \
\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)<0\right\\}$

Then, we eliminate the product symbol by observing that the product
$\prod_{p=1}^{r}(\alpha_{i_{p}}-\beta_{j})$ is negative if and only if there
are an odd number of $p$’s such that $\alpha_{i_{p}}-\beta_{j}<0$, or
equivalently $\alpha_{i_{p}}<\beta_{j}$.

$\displaystyle q_{r}$ $\displaystyle=\sum_{1\leq s\leq n}\ \sum_{1\leq
i_{1}<\cdots<i_{r}\leq n}\ \\#\left\\{j:\beta_{j}\in I_{s}\ \ \wedge\ \
\\#\left\\{p:\alpha_{i_{p}}<\beta_{j}\right\\}=odd\right\\}$

Next, we use the fact that the $\alpha$’s are indexed in ascending order, and
we note that $\alpha_{i_{p}}<\beta_{j}$ if and only if $i_{p}\leq s$, since
$\beta_{j}\in I_{s}$. Thus

$\displaystyle q_{r}$ $\displaystyle=\sum_{1\leq s\leq n}\ \sum_{1\leq
i_{1}<\cdots<i_{s}\leq n}\ \\#\left\\{j:\beta_{j}\in I_{s}\ \ \wedge\ \
\\#\left\\{p:i_{p}\leq s\right\\}=odd\right\\}$

Now, note that if $\\#\\{p:i_{p}\leq s\\}$ is even, then the size of the set
in the summand is zero. If $\\#\\{p:i_{p}\leq s\\}$ is odd, then the size of
the set in the summand equals $\\#\\{j:\beta_{j}\in I_{s}\\}$, which is
exactly $c_{s}$. Hence

$\displaystyle q_{s}$ $\displaystyle=\sum_{1\leq s\leq n}\ \sum_{1\leq
i_{1}<\cdots<i_{r}\leq n}\left\\{\begin{array}[c]{ll}0&\text{if\ \
}\\#\left\\{p:i_{p}\leq s\right\\}=even\\\ c_{s}&\text{if\ \
}\\#\left\\{p:i_{p}\leq s\right\\}=odd\end{array}\right.$

Next, we factor out the $c_{s}$ and move it outside the innermost summation.

$\displaystyle q_{r}$ $\displaystyle=\sum_{1\leq s\leq n}\ \sum_{1\leq
i_{1}<\cdots<i_{r}\leq n}\left(\left\\{\begin{array}[c]{ll}0&\text{if\ \
}\\#\left\\{p:i_{p}\leq s\right\\}=even\\\ 1&\text{if\ \
}\\#\left\\{p:i_{p}\leq s\right\\}=odd\end{array}\right.c_{s}\right)$
$\displaystyle=\sum_{1\leq s\leq n}\ \left(\sum_{1\leq i_{1}<\cdots<i_{r}\leq
n}\left\\{\begin{array}[c]{ll}0&\text{if\ \ }\\#\left\\{p:i_{p}\leq
r\right\\}=even\\\ 1&\text{if\ \ }\\#\left\\{p:i_{p}\leq
r\right\\}=odd\end{array}\right.\right)c_{s}$

Then, we fold the conditional into the summation.

$q_{r}=\sum_{1\leq s\leq n}\left(\sum_{\begin{subarray}{c}1\leq
i_{1}<\cdots<i_{r}\leq n\\\ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\end{subarray}}1\right)c_{s}$

Since the innermost summand is just a summation of 1’s, we can view it as
counting the elements of the set $\\{(i_{1},\dots,i_{r}):1\leq
i_{1}<\cdots<i_{r}\leq n\,\wedge\,\\#\\{p:i_{p}\leq s\\}=\text{odd}\\}$.

$q_{r}=\sum_{1\leq s\leq n}(T_{n})_{rs}c_{s}$

where

$(T_{n})_{rs}=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}.$

By the definition of matrix multiplication, this is just the multiplication of
the vector $c=(c_{1},\dots,c_{n})^{T}$ by the matrix $T_{n}$ whose entries are
defined as above. Thus

$\left(\begin{array}[c]{c}q_{1}\\\ \vdots\\\
q_{n}\end{array}\right)=\left(\begin{array}[c]{ccc}(T_{n})_{11}&\cdots&(T_{n})_{1n}\\\
\vdots&&\vdots\\\
(T_{n})_{n1}&\cdots&(T_{n})_{nn}\end{array}\right)\left(\begin{array}[c]{c}c_{1}\\\
\vdots\\\ c_{n}\end{array}\right)$

that is

$q=T_{n}c.$

∎

######  Lemma 11.

$T_{n}$ is invertible.

###### Proof.

It suffices to prove that $\left|T_{n}\right|\neq 0$. We prove it in several
stages. First, we establish a recurrence relation for the entries of $T_{n}$,
and then apply that to decompose $T_{n}$ into a product of triangular matrices
to more easily compute the determinant.

Claim 1: We have

$(T_{n})_{rs}=\left\\{\begin{array}[c]{ll}s&\text{if
}\left(r,s\right)\in\left\\{1\right\\}\times\left\\{1,\ldots,n\right\\}\\\
\left\\{\begin{array}[c]{ll}1&\text{if }s\ \text{is odd}\\\ 0&\text{if }s\
\text{is even}\end{array}\right.&\text{if
}\left(r,s\right)\in\left\\{n\right\\}\times\left\\{1,\ldots,n\right\\}\\\
\left\\{\begin{array}[c]{ll}\left(\begin{array}[c]{c}n\\\
r\end{array}\right)&\text{if }r\ \text{is odd}\\\ 0&\text{if }r\ \text{is
even}\end{array}\right.&\text{if
}\left(r,s\right)\in\left\\{2,\ldots,n-1\right\\}\par\times\left\\{n\right\\}\\\
(T_{n-1})_{r-1,s}+(T_{n-1})_{r,s}&\text{if
}\left(r,s\right)\in\left\\{2,\ldots,n-1\right\\}\times\left\\{1,\ldots,n-1\right.\\}.\end{array}\right.$

Proof of the claim: There are four cases in the above. We will prove them one
by one.

  1. 1.

$\left(r,s\right)\in\left\\{1\right\\}\times\left\\{1,\ldots,n\right\\}$.

By definition, we have

$(T_{n})_{1s}=\\#\left\\{\left(i_{1}\right):1\leq i_{1}\leq n\ \ \wedge\ \
\\#\left\\{p:i_{p}\leq s\right\\}=odd\right\\}.$

Since we are only considering $i_{1}$, then $\\#\\{p:i_{p}\leq s\\}$ can only
be zero or one. If that quantity is zero, then $(T_{n})_{1,s}$ is zero, since
zero is even. If instead $\\#\\{p:i_{p}\leq s\\}=1$, then $1\leq i_{1}\leq s$,
so there are $s$ choices for $i_{1}$. Thus $(T_{n})_{1,s}=s$.

  2. 2.

$\left(r,s\right)\in\left\\{n\right\\}\times\left\\{1,\ldots,n\right\\}$.

By definition, we have

$\displaystyle(T_{n})_{ns}$
$\displaystyle=\\#\left\\{\left(i_{1},\ldots,i_{n}\right):1\leq
i_{1}<\cdots<i_{n}\leq n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}$
$\displaystyle=\\#\left\\{\left(1,\ldots,n\right):\\#\left\\{p:p\leq
s\right\\}=odd\right\\}$
$\displaystyle=\\#\left\\{\left(1,\ldots,n\right):s=odd\right\\}$
$\displaystyle=\left\\{\begin{array}[c]{ll}1&\text{if }s\ \text{is odd}\\\
0&\text{if }s\ \text{is even}\end{array}\right.$

  3. 3.

$\left(r,s\right)\in\left\\{2,\ldots,n-1\right\\}\times\left\\{n\right\\}$.

By definition of $(T_{n})_{rs}$ we have

$(T_{n})_{rn}=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \ \wedge\ \ \ \\#\left\\{p:1\leq p\leq r\ \
\wedge\ \ i_{p}\leq n\right\\}=\text{odd}\right\\}.$

But $i_{p}\leq n$ trivially, so $\\#\\{p:1\leq p\leq r\ \wedge\ i_{p}\leq
n\\}=\\#\\{p:1\leq p\leq r\\}$. Therefore

$\displaystyle(T_{n})_{rn}$
$\displaystyle=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \ \wedge\ \ \
\\#\left\\{1,\ldots,r\right\\}=\text{odd}\right\\}$
$\displaystyle=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \ \wedge\ \ \ r=\text{odd}\right\\}$
$\displaystyle=\left\\{\begin{array}[c]{ll}\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\right\\}&\text{if }r\ \text{is odd}\\\
\\#\left\\{{}\right\\}&\text{if }r\ \text{is even}\end{array}\right.$
$\displaystyle=\left\\{\begin{array}[c]{ll}\left(\begin{array}[c]{c}n\\\
r\end{array}\right)&\text{if }r\ \text{is odd}\\\ 0&\text{if }r\ \text{is
even}\end{array}\right.$

  4. 4.

$\left(r,s\right)\in\left\\{2,\ldots,n-1\right\\}\times\left\\{1,\ldots,n-1\right\\}$.

By definition, we have

$(T_{n})_{rs}=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}.$

We can partition the set whose elements we are counting into elements with
$i_{r}<n$ and those with $i_{r}=n$.

$\displaystyle(T_{n})_{rs}$
$\displaystyle=\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}=n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}+$
$\displaystyle\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}<n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}.$

If $i_{r}=n$, then $(i_{1},\dots,i_{r-1})$ is a tuple such that $1\leq
i_{1}<\cdots<i_{r}\leq n-1$. In addition, we still have that
$\\#\\{p:i_{p}\leq s\\}$ is odd, because $s<n$. These are exactly the tuples
that are counted by $(T_{n-1})_{r-1,s}$; thus

$\displaystyle\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}=n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}$ $\displaystyle=$
$\displaystyle\\#\left\\{\left(i_{1},\ldots,i_{r-1}\right):1\leq
i_{1}<\cdots<i_{r-1}\leq n-1\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}$ $\displaystyle=$ $\displaystyle(T_{n-1})_{r-1,s}.$

On the other hand, if $i_{r}<n$, then $(i_{1},\dots,i_{r})$ is a tuple
satisfying $1\leq i_{1}<\cdots<i_{r}\leq n-1$ and again $\\#\\{p:i_{p}\leq
s\\}$ remains odd. These tuples are counted by $(T_{n})_{r,s}$, and so

$\displaystyle\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}<n\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}$ $\displaystyle=$
$\displaystyle\\#\left\\{\left(i_{1},\ldots,i_{r}\right):1\leq
i_{1}<\cdots<i_{r}\leq n-1\ \ \wedge\ \ \\#\left\\{p:i_{p}\leq
s\right\\}=odd\right\\}$ $\displaystyle=$ $\displaystyle(T_{n-1})_{r,s}.$

Putting those together, we get that

$(T_{n})_{rs}=(T_{n-1})_{r-1,s}+(T_{n-1})_{r,s}.$

We have proved Claim 1.

Claim 2: We have

$T_{n}=L_{n}U_{n}$

where

$(L_{n})_{rs}=\left(\begin{array}[c]{c}n-s\\\ r-s\end{array}\right)\ \ \
\,\text{and \ }\
(U_{n})_{rs}=\left(-2\right)^{r-1}\left(\begin{array}[c]{c}s\\\
r\end{array}\right)$

Proof of the claim. It suffices to show

$(T_{n})_{rs}=\sum_{t=1}^{n}(L_{n})_{rt}(U_{n})_{ts}$

We proceed by induction on $n$. Note that when $n=1$, we have

$1=(T_{1})_{11}=\binom{1-1}{1-1}(-2)^{1-1}\binom{1}{1}=L_{1}U_{1}.$

For the induction hypothesis, suppose the claim is true for some $n-1$. We
will prove the claim for $n$. There are four cases in the above. We will prove
them one by one.

  1. 1.

$\left(r,s\right)\in\left\\{1\right\\}\times\left\\{1,\ldots,n\right\\}$.

We have

$\displaystyle\sum_{t=1}^{n}(L_{n})_{1t}(U_{n})_{ts}$
$\displaystyle=\sum_{t=1}^{n}\binom{n-t}{1-t}(-2)^{t-1}\binom{s}{t}$
$\displaystyle=\binom{n-1}{1-1}(-2)^{1-1}\binom{s}{1}\ \ \ \ \text{since
}\binom{n-t}{1-t}=0\ \text{for }t>1$ $\displaystyle=s$
$\displaystyle=(T_{n})_{1s}$

  2. 2.

$\left(r,s\right)\in\left\\{n\right\\}\times\left\\{1,\ldots,n\right\\}$.

We have

$\displaystyle\sum_{t=1}^{n}(L_{n})_{nt}(U_{n})_{ts}$
$\displaystyle=\sum_{t=1}^{n}\left(\begin{array}[c]{c}n-t\\\
n-t\end{array}\right)\left(-2\right)^{t-1}\left(\begin{array}[c]{c}s\\\
t\end{array}\right)$
$\displaystyle=\sum_{t=1}^{s}\left(-2\right)^{t-1}\left(\begin{array}[c]{c}s\\\
t\end{array}\right)\ \ \,\,\,\text{since }\left(\begin{array}[c]{c}s\\\
t\end{array}\right)=0\ \,\text{for }t>s$
$\displaystyle=\frac{1}{-2}\left(-1+\sum_{t=0}^{s}\left(1\right)^{s-t}\left(-2\right)^{t}\left(\begin{array}[c]{c}s\\\
t\end{array}\right)\right)$
$\displaystyle=\frac{1}{-2}\left(-1+\left(1-2\right)^{s}\right)$
$\displaystyle=\left\\{\begin{array}[c]{ll}1&\text{if }s\ \text{is odd}\\\
0&\text{if }s\ \text{is even}\end{array}\right.$
$\displaystyle=\left(T_{n}\right)_{ns}$

  3. 3.

$\left(r,s\right)\in\left\\{2,\ldots,n-1\right\\}\times\left\\{n\right\\}$.

We have

$\displaystyle\sum_{t=1}^{n}(L_{n})_{rt}(U_{n})_{tn}$
$\displaystyle=\sum_{t=1}^{n}\binom{n-t}{r-t}(-2)^{t-1}\binom{n}{t}$
$\displaystyle=\sum_{t=1}^{n}\frac{\left(n-t\right)!}{\left(n-r\right)!\left(r-t\right)!}(-2)^{t-1}\frac{n!}{\left(n-t\right)!t!}$
$\displaystyle=\sum_{t=1}^{n}\frac{n!}{\left(n-r\right)!}\frac{1}{\left(r-t\right)!t!}(-2)^{t-1}$
$\displaystyle=\sum_{t=1}^{n}\frac{n!}{\left(n-r\right)!r!}\frac{r!}{\left(r-t\right)!t!}(-2)^{t-1}$
$\displaystyle=\sum_{t=1}^{n}\left(\begin{array}[c]{c}n\\\
r\end{array}\right)\left(\begin{array}[c]{c}r\\\
t\end{array}\right)(-2)^{t-1}$ $\displaystyle=\left(\begin{array}[c]{c}n\\\
r\end{array}\right)\sum_{t=1}^{n}\left(\begin{array}[c]{c}r\\\
t\end{array}\right)(-2)^{t-1}$ $\displaystyle=\left(\begin{array}[c]{c}n\\\
r\end{array}\right)\left(\frac{1}{-2}\left(-1+\sum_{t=0}^{n}\left(\begin{array}[c]{c}r\\\
t\end{array}\right)\left(1\right)^{r-t}(-2)^{t}\right)\right)$
$\displaystyle=\left(\begin{array}[c]{c}n\\\
r\end{array}\right)\left(\frac{1}{-2}\left(-1+\left(1-2\right)^{r}\right)\right)$
$\displaystyle=\left\\{\begin{array}[c]{ll}\left(\begin{array}[c]{c}n\\\
r\end{array}\right)&\text{if }r\ \text{is odd}\\\ 0&\text{if }r\ \text{is
even}\end{array}\right.$ $\displaystyle=\left(T_{n}\right)_{rn}$

  4. 4.

$\left(r,s\right)\in\left\\{2,\ldots,n-1\right\\}\times\left\\{1,\ldots,n-1\right\\}$.

Recall that we have

$(T_{n})_{rs}=(T_{n-1})_{r-1,s}+(T_{n-1})_{r,s}.$

By the induction hypothesis, we have

$\displaystyle(T_{n})_{rs}$
$\displaystyle=\sum_{t=1}^{n-1}(L_{n-1})_{r-1,t}(U_{n-1})_{t,s}+\sum_{t=1}^{n-1}(L_{n-1})_{r,t}(U_{n-1})_{t,s}$
$\displaystyle=\sum_{t=1}^{n-1}(L_{n-1})_{r-1,t}(U_{n-1})_{t,s}+(L_{n-1})_{r,t}(U_{n-1})_{t,s}$
$\displaystyle=\sum_{t=1}^{n-1}((L_{n-1})_{r-1,t}+(L_{n-1})_{r,t})(U_{n-1})_{t,s}$
$\displaystyle=\sum_{t=1}^{n-1}\left(\binom{n-1-t}{r-1-t}+\binom{n-1-t}{r-t}\right)(U_{n-1})_{t,s}$
$\displaystyle=\sum_{t=1}^{n-1}\binom{n-t}{r-t}(U_{n-1})_{t,s}$
$\displaystyle=\sum_{t=1}^{n-1}(L_{n})_{r,t}(U_{n-1})_{t,s}.$

But $(U_{n-1})_{t,s}$ does not depend on $n$. Thus
$(U_{n-1})_{t,s}=(U_{n})_{t,s}$. Hence

$\displaystyle(T_{n})_{rs}$
$\displaystyle=\sum_{t=1}^{n-1}(L_{n})_{r,t}(U_{n})_{t,s}$
$\displaystyle=\sum_{t=1}^{n-1}(L_{n})_{r,t}(U_{n})_{t,s}+\underbrace{\binom{n-n}{r-n}(-2)^{r-1}\binom{s}{n}}_{=0\text{
since }s<n}$ $\displaystyle=\sum_{t=1}^{n}(L_{n})_{r,t}(U_{n})_{t,s}.$

We have proved Claim 2.

Now note that $L_{n}$ is lower triangular, since if $s>r$ then $r-s<0$ and so
$\binom{n-s}{r-s}=0$. Similarly, $U_{n}$ is upper triangular, since if $r>s$
then $\binom{s}{r}=0$. Further, we have

$|L_{n}|=\prod_{t=1}^{n}(L_{n})_{tt}=\prod_{t=1}^{n}\binom{n-t}{t-t}=\prod_{t=1}^{n}\binom{n-t}{0}=\prod_{t=1}^{n}1=1,$

and

$|U_{n}|=\prod_{t=1}^{n}(U_{n})_{tt}=\prod_{t=1}^{n}(-2)^{t-1}\binom{t}{t}=\prod_{t=1}^{n}(-2)^{t-1}=(-2)^{0+1+\dots+n-1}=(-2)^{\binom{n}{2}}.$

Thus we have

$|T_{n}|=|L_{n}||U_{n}|=(-2)^{\binom{n}{2}}\neq 0\text{.}$

Hence $T_{n}$ is invertible. ∎

######  Remark 12.

In the previous proof, as a stepping stone toward proving that $T_{n}$ is
invertible we showed that $T_{n}$ has the decomposition $T_{n}=L_{n}U_{n}$
where

$(L_{n})_{rs}=\left(\begin{array}[c]{c}n-s\\\ r-s\end{array}\right)\ \
\text{and\ \ }(U_{n})_{rs}=\left(-2\right)^{r-1}\left(\begin{array}[c]{c}s\\\
r\end{array}\right).$

These are combinatorially beautiful matrices for which we provided no
combinatorial interpretation. This is one focus of our future work in this
area, as the matrix $T_{n}$ has many interesting combinatorial aspects which
we did not have time or space to address in this paper.

Now, we can summarize Lemmas 10 and 11 into the following lemma.

######  Lemma 13.

We have

$EC(F,G)=c\ \ \iff\ \ q=T_{n}c.$

###### Proof.

Lemma 10 shows that $EC(F,G)=c\implies q=T_{n}c$. Lemma 11 shows that $T_{n}$
is invertible, hence $T_{n}$ is a 1-1 linear map. Therefore, we have that
$q=T_{n}c\implies EC(F,G)=c.$ ∎

At this point, we have found an equivalent condition for $EC(F,G)=c$. However,
this condition still contains quantifiers, as it references the eigenvalues of
$F$ and $G$. The remainder of the derivation will focus on solving this issue,
by introducing symmetric polynomials $h_{r}$ whose roots can be counted to
produce an equivalent condition in terms of the entries of $F$ and $G$ only,
and not their eigenvalues.

######  Lemma 14.

We have

$q_{r}=\\#\text{ of negative roots of }h_{r}.$

###### Proof.

Recall that by definition we have

$h_{r}:=\prod\limits_{\left(i_{1},\ldots,i_{r},j\right)\in
Q_{r}}\left(x-\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)\right).$

The roots of $h_{r}$ are, by construction, exactly the products
$\prod_{p=1}^{r}(\alpha_{i_{p}}-\beta_{j})$. Hence the negative roots of
$h_{r}$ are exactly what is counted by $q_{r}$. ∎

Notice that $h_{r}$ is a symmetric polynomial with real roots. This is the
crucial fact which allows us to construct another polynomial $p_{r}$ involving
the entries of $F$ and $G$ rather than their eigenvalues. This will eliminate
the quantifiers.

######  Proposition 15.

For each $r=1,\dots,n$, there exists
$p_{r}\in\mathbb{R}\left[x,a_{1},\dots,a_{n},b_{1},\dots,b_{n}\right]$ such
that

$h_{r}=p_{r}(x,a_{1},\dots,a_{n},b_{1},\dots,b_{n}).$

###### Proof.

For the purposes of this proof, we view $h_{r}$ as being a polynomial in
$x,\alpha_{1},\dots,\alpha_{n},\beta_{1},\dots,\beta_{n}$, with real
coefficients.

Note that by construction $h_{r}$ is symmetric in
$\alpha_{1},\dots,\alpha_{n}$. Recall that by the Fundamental Theorem of
Symmetric Polynomials, this means that there exists a polynomial
$p_{\alpha}\in\mathbb{Z}[x,y_{1},\dots,y_{n}]$ such that

$h_{r}(x,\alpha_{1},\dots,\alpha_{n},\beta_{1},\dots,\beta_{n})=p_{\alpha}(x,\sigma_{1}(\alpha),\dots,\sigma_{n}(\alpha)).$

Further note $h_{r}$ is also symmetric in $\beta_{1},\dots,\beta_{n}$; hence
$p_{\alpha}$ is symmetric in $\beta_{1},\dots,\beta_{n}$. Thus by again
applying the Fundamental Theorem of Symmetric Polynomials, there exists a
polynomial $p_{r}\in\mathbb{Z}[x,y_{1},\dots,y_{n}][z_{1},\dots,z_{n}]$ such
that

$p_{\alpha}(x,y_{1},\dots,y_{n})=p_{r}(x,\sigma_{1}(\alpha),\dots,\sigma_{n}(\alpha),\sigma_{1}(\beta),\dots,\sigma_{n}(\beta)).$

Now, combining these together, we have that

$\displaystyle
p_{r}(x,\sigma_{1}(\alpha),\dots,\sigma_{n}(\alpha),\sigma_{1}(\beta),\dots,\sigma_{1}(\beta))$
$\displaystyle=p_{\alpha}(x,\sigma_{1}(\alpha),\dots,\sigma_{n}(\alpha))$
$\displaystyle=h_{r}(x,\alpha_{1},\dots,\sigma_{n},\beta_{1},\dots,\beta_{n}).$

Finally, note that

$\displaystyle a_{1}$ $\displaystyle=\sum_{1\leq i_{1}\leq
n}\alpha_{i_{1}}=\alpha_{1}+\cdots+\alpha_{n}=\sigma_{1}(\alpha)$
$\displaystyle a_{2}$ $\displaystyle=\sum_{1\leq i_{1}<i_{2}\leq
n}\alpha_{i_{1}}\alpha_{i_{2}}=\sigma_{2}(\alpha)$ $\displaystyle\vdots$
$\displaystyle a_{n}$ $\displaystyle=\sum_{1\leq i_{1}<\cdots<i_{n}\leq
n}\alpha_{i_{1}}\cdots\alpha_{i_{n}}=\alpha_{1}\cdots\alpha_{n}=\sigma_{n}(\alpha).$

Similarly

$\displaystyle b_{1}$ $\displaystyle=\sigma_{1}(\beta)$ $\displaystyle\vdots$
$\displaystyle b_{n}$ $\displaystyle=\sigma_{n}(\beta).$

Hence, we have that

$\displaystyle h_{r}(x,\alpha_{1},\dots,\alpha_{n},\beta_{1},\dots,\beta_{n})$
$\displaystyle=p_{r}(x,\underbrace{\sigma_{1}(\alpha)}_{a_{1}},\dots,\underbrace{\sigma_{n}(\alpha)}_{a_{n}},\underbrace{\sigma_{1}(\beta)}_{b_{1}},\dots,\underbrace{\sigma_{n}(\beta)}_{b_{n}})$
$\displaystyle=p_{r}(x,a_{1},\dots,a_{n},b_{1},\dots,b_{n})$

∎

With that, we are ready to prove the main result (Theorem 8).

###### Proof of Main Result (Theorem 8).

Let $q=\begin{pmatrix}q_{1}\\\ \vdots\\\ q_{n}\end{pmatrix}=T_{n}c$. For each
$r=1,\dots,n$, by Proposition 15 there exists
$p_{r}\in\mathbb{R}[x,a_{1},\dots,a_{n},b_{1},\dots,b_{n}]$ such that

$h_{r}(x,\alpha_{1},\dots,\alpha_{n},\beta_{1},\dots,\beta_{n})=p_{r}(x,a_{1},\dots,a_{n},b_{1},\dots,b_{n}).$

Note by Lemma 14

$\displaystyle q_{r}$ $\displaystyle=\\#\text{ negative roots of }h_{r}(x)$
$\displaystyle=\\#\text{ negative roots of }p_{r}(x)$ $\displaystyle=\\#\text{
positive roots of }p_{r}(-x)$ $\displaystyle=v(p_{r}(-x))\,\text{by Descartes'
rule of signs, since all roots of }p_{r}\text{ are real}.$

Therefore, we have that

$q=T_{n}c\,\,\iff\,\,\bigwedge_{r=1}^{n}v(p_{r}(-x))=(T_{n}c)_{r}.$

Finally, by Lemmas 10 and 11, we have

$EC(F,G)=c\,\,\iff\,\,q=T_{n}c\,\,\iff\,\,\underbrace{\bigwedge_{r=1}^{n}v(p_{r}(-x))=(T_{n}c)_{r}}_{P}.$

Note that each $v(p_{r}(-x))=(T_{n}c)_{r}$ is a logical disjunction (see
Algorithm 19 and Remark 20) involving the coefficients of $p_{r}$ as viewed as
a polynomial in $x$, whose coefficients are themselves polynomials in
$a_{1},\dots,a_{n},b_{1},\dots,b_{n}$. Hence the expression $P$ is a
quantifier-free condition which is equivalent to $EC(F,G)=c$. ∎

##  5 Algorithms

######  Algorithm 16 (TM).

  * In :

$n,$ positive integer

  * Out:

$T_{n}\in\mathbb{Z}^{n\times n}$ such that $q=T_{n}c$ for any eigenvalue
configuration $c$ of $n\times n$ matrices.

  1. 1.

$(T_{n})_{rs}\longleftarrow\sum_{t=1}^{n}\binom{n-t}{r-t}(-2)^{r-1}\binom{s}{t}$

  2. 2.

Return $T_{n}$

######  Algorithm 17 (pv).

  * In :

    1. 1.

$n\geq 1$

    2. 2.

$r\in\\{1,\dots,n\\}$

  * Out:

$p_{r}\in\mathbb{R}[x,\alpha_{1},\dots,a_{n},b_{1},\dots,b_{n}]$ such that
$h_{r}=p_{r}(x,a_{1},\dots,a_{n},b_{1},\dots,b_{n})$

  1. 1.

$h_{r}\longleftarrow\prod\limits_{\left(i_{1},\ldots,i_{r},j\right)\in
Q_{r}}\left(x-\prod_{p=1}^{r}\left(\alpha_{i_{p}}-\beta_{j}\right)\right)$

  2. 2.

$p_{\alpha}\longleftarrow$ polynomial such that
$h_{r}=p_{\alpha}(x,\sigma_{1}(\alpha),\dots,\sigma_{1}(\beta))$

  3. 3.

$p_{r}\longleftarrow$ polynomial such that
$p_{\alpha}=p_{r}(x,\sigma_{1}(\beta),\dots,\sigma_{1}(\beta))$

  4. 4.

Return $p_{r}\in\mathbb{R}[x,a_{1},\dots,a_{n},b_{1},\dots,b_{n}]$

######  Remark 18.

Lines 2 and 3 of the previous algorithm rely on the Fundamental Theorem of
Symmetric Polynomials, the proof and algorithm for which can be found in many
algebra texts.

######  Algorithm 19 (EC).

  * In:

$c,\ $the eigen configuration

  * Out:

$P,$ condition on $F$ and $G$ such that $c=EC\left(F,G\right)$

  1. 1.

$F\longleftarrow$ with indeterminate entries

$G\longleftarrow$ with indeterminate entries

  2. 2.

$f\longleftarrow\left|xI-F\right|$ where
$f=x^{n}-a_{1}x^{n-1}+a_{2}x^{n-2}+\cdots+\left(-1\right)^{n}a_{n}x^{0}$

$g\longleftarrow\left|xI-G\right|\ \ $where
$g=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\cdots+\left(-1\right)^{n}b_{n}x^{0}$

  3. 3.

$q\longleftarrow TM(n)\ast c$

  4. 4.

for $r=1,\ldots,n$ do

    1. (a)

$p_{r}\longleftarrow pv(n,r)$

    2. (b)

$P_{r}\longleftarrow$ the condition on $a_{1},\ldots,a_{n},b_{1},\ldots,b_{n}$
such that # of negative roots of $p_{r}$ is $q_{r}$.

  5. 5.

$P\longleftarrow\underset{r}{\wedge}P_{r}$

  6. 6.

Return $P$

######  Remark 20.

Line 4b of the previous algorithm is a succinct way of expressing the
following procedure, which enumerates all possibilities for the signs of the
coefficients $p_{r}(-x)$ satisfying a given sign variation count.

  1. 1.

For each sign sequence $s\in\\{-,0,+\\}^{n}$ such that $v(s)=q_{r}$ do

$P_{r}\longleftarrow
P_{r}\vee\left(\bigwedge_{i=1}^{n}sign(\text{coeff}(p_{r}(-x),x^{i}))=s_{i}\right)$

Acknowledgements. Third author partially supported by the research project
PID2020-113192GB-I00 (Mathematical Visualization: Foundations, Algorithms and
Applications) from the Spanish MICINN.

## References

  * [1] Alexandru Aleman, Karl-Mikael Perfekt, Stefan Richter, Carl Sundberg, and James Sunkes.  Cyclicity in the drury-arveson space and other weighted besov spaces, 2023\.
  * [2] M. Ben-Or, D. Kozen, and J. H. Reif.  The complexity of elementary algebra and geometry.  J. Comput. System Sci., 32(2):251–264, 1986.
  * [3] Christopher W. Brown.  Improved projection for cylindrical algebraic decomposition.  J. Symb. Comput., 32(5):447–465, 2001.
  * [4] Christopher W. Brown.  Simple cad construction and its applications.  J. Symb. Comput., 31(5):521–547, 2001.
  * [5] Christopher W. Brown.  Qepcad b: a system for computing with semi-algebraic sets via cylindrical algebraic decomposition.  ACM SIGSAM Bulletin, 38(1), 2004.
  * [6] Christopher W. Brown.  Fast simplifications for tarski formulas based on monomial inequalities.  J. Symb. Comput., 47(7):859–882, 2012.
  * [7] J. F. Canny.  Improved algorithms for sign and existential quantifier elimination.  Computer Journal, 36:409–418, 1993.  In a special issue on computational quantifier elimination, edited by H. Hong.
  * [8] Changbo Chen, Marc Moreno Maza, Bican Xia, and Lu Yang.  Computing cylindrical algebraic decomposition via triangular decomposition.  In ISSAC, pages 95–102, 2009.
  * [9] Giulia Codenotti, Stephan Gardoll, and Thorsten Theobald.  Combinatorics and preservation of conically stable polynomials, 2022.
  * [10] G. E. Collins and H. Hong.  Partial cylindrical algebraic decomposition for quantifier elimination.  Journal of Symbolic Computation, 12(3):299–328, sep 1991.
  * [11] R. Descartes.  Géométrie.  1636\.  In A source book in Mathematics, pages 90-131. Harvard University Press, 1969.
  * [12] L. Gonzalez-Vega.  A combinatorial algorithm solving some quantifier elimination problems.  In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer Verlag, 1996.  Texts and Monographs in Symbolic Computation.
  * [13] L. Gonzalez-Vega, H. Lombardi, T. Recio, and M.-F. Roy.  Sturm-Habicht sequences.  In Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebriaic Computation, pages 136–146, July 1989.
  * [14] D. Yu. Grigor’ev.  The complexity of deciding Tarski algebra.  Journal of Symbolic Computation, 5(1,2):65–108, 1988.
  * [15] Leonid Gurvits, Nathan Klein, and Jonathan Leake.  From trees to polynomials and back again: New capacity bounds with applications to tsp, 2023.
  * [16] H. Hong.  An improvement of the projection operator in cylindrical algebraic decomposition.  In International Symposium of Symbolic and Algebraic Computation (ISSAC-90), pages 261–264. ACM, 1990.
  * [17] H. Hong.  Improvements in CAD–based Quantifier Elimination.  PhD thesis, The Ohio State University, 1990.
  * [18] H. Hong.  Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination.  In International Conference on Symbolic and Algebraic Computation ISSAC-92, pages 177–188, 1992.
  * [19] Hoon Hong and Mohab Safey El Din.  Variant quantifier elimination.  J. Symb. Comput., 47(7):883–901, 2012.
  * [20] Hoon Hong, Daniel Profili, and J. Rafael Sendra.  Conditions for eigenvalue configurations of two real symmetric matrices: a signature approach.  Preprint, 2023.
  * [21] R. Loos and V. Weispfenning.  Applying linear quantifier elimination.  Computer Journal, 36(5):450–462, 1993.  In a special issue on computational quantifier elimination, edited by H. Hong.
  * [22] S. McCallum.  An Improved Projection Operator for Cylindrical Algebraic Decomposition.  PhD thesis, University of Wisconsin-Madison, 1984.
  * [23] Scott McCallum.  Factors of iterated resultants and discriminants.  J. Symb. Comput., 27(4):367–385, 1999.
  * [24] Scott McCallum and Christopher W. Brown.  On delineability of varieties in cad-based quantifier elimination with two equational constraints.  In ISSAC, pages 71–78, 2009.
  * [25] John Reif Michael Ben-Or, Dexter Kozen.  The complexity of elementary algebra and geometry.  Journal of Computer and System Sciences, 32(2):251–264, 1986.
  * [26] G. Moroz and F. Rouillier.  OpenCAD.  package, 2007.
  * [27] J. Renegar.  On the computational complexity and geometry of the first-order theory of the reals.  Journal of Symbolic Computation, 13(3):255–352, 1992.
  * [28] M. Safey El Din.  RAGLib (Real Algebrw-salsaaic Geometry Library), Maple package.  http://ww.lip6.fr/$\sim$safey/RAGLib, 2007.
  * [29] A. Strzebonski.  Cylindrical algebraic decomposition using validated numerics.  J. Symb. Comput., 41(9):1021–1038, 2006.
  * [30] T. Sturm and V. Weispfenning.  Computational geometry problems in redlog.  In ADG, pages 58–96, 1996.
  * [31] A. Tarski.  The completeness of elementary algebra and geometry.  1930\.  Reprinted in 1967.
  * [32] A. Tarski.  A Decision Method for Elementary Algebra and Geometry.  Univ. of California Press, Berkeley, second edition, 1951.
  * [33] Máté L Telek.  Geometry of the signed support of a multivariate polynomial and descartes’ rule of signs.  arXiv preprint arXiv:2310.05466, 2023.
  * [34] V. Weispfenning.  Quantifier elimination for real algebra – the cubic case.  In International Symposium on Symbolic and Algebraic Computation 94, pages 258–263, 1994.
  * [35] V. Weispfenning.  A new approach to quantifier elimination for real algebra.  In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer Verlag, 1996.  Texts and Monographs in Symbolic Computation.
  * [36] Bican Xia.  Discoverer: a tool for solving semi-algebraic systems.  ACM Communications in Computer Algebra, 41:102–103.
  * [37] Hitoshi Yanami and Hirokazu Anai.  The maple package synrac and its application to robust control design.  Future Generation Computer Systems, 23(5):721–726, 2007.