# Certified Hermite Matrices from Approximate Roots

Tulay Ayyildiz Akoglu111The research of Tulay Ayyildiz Akoglu is partially
supported by TUBITAK grant 119F211. Karadeniz Technical University, Trabzon,
Turkey<EMAIL_ADDRESS>Agnes Szanto222The research of Agnes Szanto is
partially supported by NSF grant CCF-1813340. North Carolina State University,
Raleigh, NC, USA<EMAIL_ADDRESS>
###### Abstract

Let $\mathcal{I}=\langle
f_{1},\ldots,f_{m}\rangle\subset\mathbb{Q}[x_{1},\dots,x_{n}]$ be a zero
dimensional radical ideal defined by polynomials given with exact rational
coefficients. Assume that we are given approximations
$\\{z_{1},\ldots,z_{k}\\}\subset\mathbb{C}^{n}$ for the common roots
$\\{\xi_{1},\ldots,\xi_{k}\\}=V(\mathcal{I})\subseteq{\mathbb{C}}^{n}$. In
this paper we show how to construct and certify the rational entries of
Hermite matrices for $\mathcal{I}$ from the approximate roots
$\\{z_{1},\ldots,z_{k}\\}$. When $\mathcal{I}$ is non-radical, we give methods
to construct and certify Hermite matrices for $\sqrt{\mathcal{I}}$ from
approximate roots. Furthermore, we use signatures of these Hermite matrices to
give rational certificates of non-negativity of a given polynomial over a
(possibly positive dimensional) real variety, as well as certificates that
there is a real root within an $\varepsilon$ distance from a given point
$z\in\mathbb{Q}^{n}$.

###### keywords:

Symbolic–Numeric Computation $\cdot$ Polynomial Systems $\cdot$ Approximate
Roots $\cdot$ Hermite Matrices $\cdot$ Certification

##  1 Introduction

The development of numerical and symbolic techniques to solve systems of
polynomial equations resulted in an explosion of applicability, both in terms
of the size of the systems efficiently solvable and the reliability of the
output. Nonetheless, many of the results produced by numerical methods are not
certified. In this paper, we show how to compute exact Hermite matrices from
approximate roots of polynomials, and how to certify that these Hermite
matrices are correct.

Hermite matrices and Hermite bilinear forms were introduced by Hermite in 1850
[14] for univariate polynomials and were extended to the multivariate zero-
dimensional setting in [7, 23]. Hermite matrices have many applications,
including counting real roots [7, 15, 16] and locating them [4]. Assume that
we are given the ideal $\mathcal{I}:=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ generated by
rational polynomials, and assume that
$\dim_{\mathbb{Q}}{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}=k<\infty$.
Hermite matrices have two kinds of definitions (see the precise formulation in
Section 2.1 ):

  1. 1.

The first definition of Hermite matrices uses the traces of $k^{2}$
multiplication matrices, each of them of size $k\times k$. The advantage of
this definition is that it can be computed exactly, working with rational
numbers only. The disadvantage is that it requires the computation of the
traces of $k^{2}$ multiplication matrices.

  2. 2.

The second definition uses symmetric functions of the $k$ common roots of
${\mathcal{I}}$, counted with multiplicity. The advantage of this definition
is that it gives a very efficient way to evaluate the entries of the Hermite
matrix, assuming that we know the common roots of ${\mathcal{I}}$ exactly. The
disadvantage is that we need to compute the common roots exactly, which may
involve working in field extensions of ${\mathbb{Q}}$.

In this paper we propose to use the second definition to compute Hermite
matrices, but instead of using exact roots, we use approximate roots that can
be computed with numerical methods efficiently [12]. Once we obtain an
approximate Hermite matrix, we use rational number reconstruction to construct
a matrix with rational entries of bounded denominators. Finally, we give a
symbolic method which certifies that the rational Hermite matrix we computed
is in fact the correct one, corresponding to the exact roots of
${\mathcal{I}}$.

The novelty of this work and the difficulty of this problem is to certify the
correctness of the Hermite matrix that we computed with the above heuristic
approach. This part of the algorithm is purely symbolic. The main idea is that
we use the relationship between multiplication matrices and Hermite matrices
to compute a system of multiplication matrices from Hermite matrices and vice
versa. As multiplication matrices, which are also rational matrices, act as
roots of the polynomial system, we can certify their correctness, which in
turn gives us a method to certify Hermite matrices.

Note that both of the above definitions of Hermite matrices are continuous in
the presence of root multiplicities. However, our use of approximate roots and
multiplication matrices necessitate that we first consider the case when
${\mathcal{I}}$ is radical. To handle the non-radical case, we use the fact
that the maximal non-singular submatrix of the Hermite matrix of
${\mathcal{I}}$ gives the Hermite matrix of $\sqrt{I}$, so this is what we
compute and certify. In both the radical and non-radical cases we were able to
give sufficient conditions in terms of the quality of the root approximations
and the size of the rational numbers in the Hermite matrices that guarantee
that our Hermite matrix construction and certification algorithms do not fail.

Another contribution of this paper is the presentation of two novel
applications using the signature of the certified Hermite matrices. The first
application is to give a rational certificate that a polynomial
$g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ is non-negative over a smooth real
variety $V(f_{1},\ldots,f_{s})\cap{\mathbb{R}}^{n}$ where
$f_{1},\ldots,f_{s}\in{\mathbb{Q}}[x_{1},\ldots,x_{n}].$ This application was
inspired by [10] where the authors give a method to compute a degree $d$ sum
of squares (SOS) decomposition (if one exists) for a non-negative polynomial
over a real algebraic set using a finite set of sample points from the
(complex) algebraic set. While the SOS decomposition constructed in [10] is
approximate, the construction we give here is exact, using Hermite matrices
with rational entries.

The second application is to give a rational certificate that for a given
point $z\in{\mathbb{Q}}^{n}$, $\varepsilon\in{\mathbb{Q}}_{+}$ and
${\mathcal{I}}:=\langle
f_{1},\ldots,f_{m}\rangle\subset\mathbb{Q}[x_{1},\dots,x_{n}]$ zero
dimensional, there exists $\xi\in V(f_{1},\ldots,f_{m})\cap{\mathbb{R}}^{n}$
such that

$\|z-\xi\|_{2}^{2}\leq\varepsilon.$

A natural question arises about the advantage of this hybrid symbolic–numeric
approach over purely symbolic methods to compute Hermite matrices. The answer
to this question is not black and white, it depends on the situation. For
example, one could use a purely symbolic method computing a Gröbner bases, and
then computing a system of multiplication matrices of the input polynomials
and then the traces of certain multiplication matrices give the entries of
Hermite matrices symbolically (just as in the first definition above).
Instead, in this study, we use a symbolic-numeric approach as we assume that
we have an efficient and parallelizable numerical method that can compute high
precision approximations to all common complex roots for square subsystems of
$f$, i.e. for $n$ random linear combinations of $f_{1},\ldots,f_{m}$. From
these approximate roots we select in a certified manner a subset
$z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ (given with floating point numbers as
coordinates) that are approximations solutions of
$f\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]^{m}$. The worst case arithmetic
complexity for both the purely symbolic and the hybrid methods are similar
(asymptotically bounded by $D^{n}$ where $D$ is the maximum of the degrees of
the input polynomials). In [5, 6] the authors give some evidence that Gröbner
basis techniques for highly overdetermined systems ($m>>n$) can be highly
efficient. The underlying idea behind this is that if one is given many
polynomials already, there is only a little more work needed to generate a
Gröbner basis. On the other hand, for systems that are square or close to
square, the limited accuracy and parallelizability of the numerical approach
allows to handle larger polynomial systems in practice than with purely
symbolic approaches. In [8] they compare the two different approaches to
computing and representing the solutions of polynomial systems: numerical
homotopy continuation and symbolic computation.333We thank Jonathan Hauenstein
for pointing out to us the subtleties of using symbolic vs. numeric methods
for solving polynomial systems

This paper is a generalization of our paper [2], where we considered only the
univariate radical case.

The paper is organized as follows. In the next section we introduce some
preliminaries with fundamental definitions such as the Hermite matrices,
rational number reconstruction and numerical computation of roots of
overdetermined polynomial systems. In Section 3, we explain how one can
construct the exact Hermite matrix using the approximate solutions of the
given polynomial system. In Section 4 we give an algorithm to certify that the
obtained Hermite matrix is the exact one corresponding to our input
polynomials. So far we assume that the ideal ${\mathcal{I}}$ is radical. In
Section 5 we generalize the Hermite matrix computation and certification
algorithm to the case when ${\mathcal{I}}$ is not radical. In Section 6 we
present the application of Hermite matrices to give a rational certificate
that a given rational polynomial is non-negative over a real algebraic variety
defined by rational polynomials. Finally, in Section 7 we give another
application that is a rational certificate for the existence of an exact
common root of a zero-dimensional ideal within $\varepsilon$ distance from a
given point in ${\mathbb{Q}}^{n}$.

##  2 Preliminaries

###  2.1 Hermite Matrices

In this section we give two definitions for the Hermite matrix of a zero-
dimensional ideal. The first one defines the matrix from the common roots of
the ideal, and in fact can be used to define Hermite matrices from any set of
points. The second definition uses the traces of multiplication matrices of
the factor ring of the ideal, and thus it gives a definition where the entries
of the Hermite matrices are rational functions of the coefficients of the
polynomial system.

Everything in this section is valid for polynomials over ${\mathbb{R}}$, so
while in the rest of the paper we assume that our input polynomials are
rational, in this section we present the preliminaries over ${\mathbb{R}}$. We
use the following notation. Let
$f=(f_{1},\ldots,f_{m})\in\mathbb{R}[x_{1},\dots,x_{n}]^{m}$ with
$\mathcal{I}=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{R}}[x_{1},\dots,x_{n}]$ a zero-
dimensional ideal and $\mathcal{B}=\\{x^{\alpha_{1}},\dots,x^{\alpha_{k}}\\}$
be a monomial basis for $\mathbb{R}[x_{1},\dots,x_{n}]/\mathcal{I}$.

Let $\xi_{1},\xi_{2},\dots,\xi_{k}\in{\mathbb{C}}^{n}$ be the common roots of
${\mathcal{I}}$, here each root listed as many times as their multiplicity. If
${\mathcal{I}}$ is radical (which we assume in most of the later sections),
each root is distinct. We denote by $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$
approximations to the exact roots $\xi_{1},\xi_{2},\dots,\xi_{k}$.

The first definition of Hermite matrices is given for any multiset of points
in ${\mathbb{C}}^{n}$ as follows:

######  Definition 2.1.

Let $g\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$ and
$\mathcal{B}=\\{x^{\alpha_{1}},\dots,x^{\alpha_{k}}\\}$ be a set of monomials
in $\mathbb{R}[x_{1},\dots,x_{n}]$. Let
$z_{1},z_{2},\dots,z_{k}\in{\mathbb{C}}^{n}$ be points, not necessary
distinct. Then the Hermite matrix of $z_{1},z_{2},\dots,z_{k}$ with respect to
$g$, written in the basis ${\mathcal{B}}$ is

$H_{g}^{\mathcal{B}}(z_{1},z_{2},\dots,z_{k}):=V^{T}GV$ (1)

where

$V:=V_{\mathcal{B}}(z_{1},z_{2},\dots,z_{k})=[z_{i}^{\alpha_{j}}]_{i,j=1,\ldots,k}$

is the Vandermonde matrix of $z_{1},z_{2},\dots,z_{k}\in\mathbb{C}^{n}$ with
respect to a monomial set $\mathcal{B}$ and $G$ is a $k\times k$ diagonal
matrix with $[G]_{i,i}=g(z_{i})$ for $i=1,\dots,k$. We may omit
${\mathcal{B}}$ from the notation if it is clear from the context.

######  Example 2.2.

When ${\mathcal{B}}=\\{1,x_{1},\ldots,x_{1}^{k-1}\\}$ and $g=g(x_{1})$ is also
univariate, then the Hermite matrices are the same as in the univariate case.
If $z_{l}=(z_{l,1},\ldots,z_{l,n})\in{\mathbb{C}}^{n}$ for $l=1,\ldots,k$ then
the entries of the $k\times k$ univariate Hermite matrices are defined by

$[H^{\mathcal{B}}_{g}(z_{1},\ldots,z_{k})]_{i,j}=\sum_{l=1}^{k}g(z_{l,1})z_{l,1}^{i+j-2}.$

In particular, for $g(x)=1$, if $z_{1,1},\ldots,z_{k,1}$ all distinct, the
entries of the Hermite matrix are the power sum elementary symmetric functions
of the first coordinates:

$[H^{\mathcal{B}}_{1}(z_{1},\ldots,z_{k})]_{i,j}=\sum_{l=1}^{k}z_{l,1}^{i+j-2}.$
(2)

The second definition of Hermite matrices implies that the the entries of the
Hermite matrix are rational functions of the coefficients of the defining
polynomials of ${\mathcal{I}}$.

######  Definition 2.3.

Let ${\mathcal{I}}\subset{\mathbb{R}}[x_{1},\ldots,x_{n}]$ be a zero
dimensional ideal and denote $A:={\mathbb{R}}[x_{1},\ldots,x_{n}]/I$, a finite
dimensional vectors space over ${\mathbb{R}}$ with $k:=\dim_{\mathbb{R}}A$.
For any $f\in A$ let $\mu_{f}:A\rightarrow A,$ $p+{\mathcal{I}}\mapsto p\cdot
f+{\mathcal{I}}$ be the multiplication map by $f$ on $A$. Fix a monomial basis
${\mathcal{B}}=\\{x^{\alpha_{1}},\dots,x^{\alpha_{k}}\\}$ of $A$, and denote
by $M^{\mathcal{B}}_{f}$ the $k\times k$ matrix of $\mu_{f}$ in the basis
${\mathcal{B}}$. The Hermite matrix of ${\mathcal{I}}$ with respect to $g$,
written in the basis ${\mathcal{B}}$ is

$H_{g}^{\mathcal{B}}({\mathcal{I}})=\left[{\rm Tr}(\mu_{g\cdot
x^{\alpha_{i}+\alpha_{j}}})\right]_{i,j=1}^{k}=\left[{\rm
Tr}(M^{\mathcal{B}}_{g\cdot x^{\alpha_{i}+\alpha_{j}}})\right]_{i,j=1}^{k},$

where ${\rm Tr}$ denotes both the trace of a linear transformation and the
trace of a matrix (note that the trace of a linear transformation is the trace
of its matrix in _any_ basis). We may omit ${\mathcal{B}}$ from the notation
when it is clear from the context.

The next theorem asserts that the two definitions give the same matrix if we
take the exact common roots of a zero dimensional polynomial system.

######  Theorem 2.4 ([7]).

Let ${\mathcal{I}}\subset{\mathbb{R}}[x_{1},\ldots,x_{n}]$ be a zero
dimensional ideal and $g\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$. Let
$k:=\dim{\mathbb{R}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$ and
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ be a monomial basis
for ${\mathbb{R}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$. Let
$\xi_{1},\ldots,\xi_{k}\in{\mathbb{C}}^{n}$ be the roots of ${\mathcal{I}}$,
each root listed as many times as their multiplicity. Then

$H_{g}^{\mathcal{B}}(\xi_{1},\ldots,\xi_{k})=H_{g}^{\mathcal{B}}({\mathcal{I}}).$

######  Remark 2.5.

Note that if $f_{1},\ldots,f_{m},g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ then
for ${\mathcal{I}}=\langle f_{1},\ldots,f_{m}\rangle$ we have
$H_{g}({\mathcal{I}})\in{\mathbb{Q}}^{k\times k}$, thus
$H_{g}(\xi_{1},\ldots,\xi_{k})\in{\mathbb{Q}}^{k\times k}$, even if the roots
are not rational.

Next we present the classical Hermite theorem that uses the signature of
Hermite matrices to count real roots of a real polynomial system. First we
define the signature of a matrix.

######  Definition 2.6.

Let $A$ be a real and symmetric matrix. Then the signature of A is

$\sigma(A):=\\#\\{{\rm positive~{}eigenvalues~{}of}A\\}-\\#\\{{\rm
negative~{}eigenvalues~{}of}A\\}$

Definition 2.3 implies that Hermite Matrices of real polynomial ideals are
real and symmetric. The classical univariate Hermite Theorem [16] was
generalized to the multivariate case by Pedersen, Roy and Szpirglas [20], and
was also proved in [7] and [11]:

######  Theorem 2.7 (Multivariate Hermite Theorem).

Let ${\mathcal{I}}\subset{\mathbb{R}}[x_{1},\dots,x_{n}]$ be zero dimensional
and ${\mathcal{B}}$ be a monomial basis of
${\mathbb{R}}[x_{1},\dots,x_{n}]/{\mathcal{I}}$. If $H_{g}({\mathcal{I}})$ is
the Hermite matrix of $~{}{\mathcal{I}}$ with respect to $g$ in the basis
${\mathcal{B}}$, then

$\sigma(H_{g}({\mathcal{I}}))=\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)>0\\}-\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)<0\\}.$

######  Remark 2.8.

There are several ways to obtain the signature of a $k\times k$ real and
symmetric matrix $M$ without computing the eigenvalues explicitly. We will
describe two of these methods here. Note that if $M$ is a rational symmetric
matrix, then both of these methods can be computed with exact arithmetic over
the rationals.

  1. 1.

Using Descartes rule of signs: Let $p(x)$ be the characteristic polynomial of
the given $k\times k$ real and symmetric matrix. Since all eigenvalues of real
symmetric matrices are real their characteristic polynomials have only real
roots. Then the Descartes Rule of Signs provides that $\sigma(M)$ is the
difference between the number of sign variation of the coefficients of $p(x)$
and the number of sign variations of the coefficients of $p(-x)$ (see
Proposition 8.4 in [7]). The complexity of this computation is bounded by
$\mathcal{O}(k^{4}).$

  2. 2.

Using $LU$ decomposition: The LU decomposition of real symmetric matrices can
be written as $LDL^{T}$ where $L$ is a special lower triangular matrix with
1’s on the diagonal entries and $D$ is a diagonal matrix with the entries
$\\{u_{11},\ldots,u_{kk}\\}$. These entries are the diagonal entries of the
upper triangular matrix $U$ obtained from the LU decomposition. By Sylvester
Law of inertia, the signature of $M$ is the difference between
$\\#\\{u_{ii}~{}:~{}u_{ii}>0\\}$ and $\\#\\{u_{ii}~{}:~{}u_{ii}<0\\}$. The
complexity of this computation only comes from the cost of the $LU$
decomposition which can be found via Gaussian Elimination. The complexity of
Gaussian elimination is bounded by $\mathcal{O}(k^{3}).$

We close this subsection with some definitions that will be used later in this
paper. First, in our certification algorithm we need the following property of
${\mathcal{B}}$ (see [19]):

######  Definition 2.9.

Let $\mathcal{B}\subset\mathbb{R}[x_{1},\dots,x_{n}]$. We say that
${\mathcal{B}}$ (or ${\rm span}_{\mathbb{R}}({\mathcal{B}})$) is connected to
1 if for all $b\in{\rm span}_{\mathbb{R}}({\mathcal{B}})$ there exists
$b_{1},\ldots,b_{n}\in{\mathcal{B}}$ such that

$b=\sum_{i=1}^{n}x_{i}b_{i}$

and $\deg(b_{i})<\deg(b)$ for $i=1,\ldots,n$.

######  Definition 2.10.

$\mathcal{B}\subset\mathbb{R}[x_{1},\dots,x_{n}]$ be a finite set of
monomials. The extension of $\mathcal{B}$ is defined by

$\mathcal{B}^{+}:=\mathcal{B}\cup\bigcup_{i=1}^{n}x_{i}\mathcal{B}=\left\\{b,x_{1}b,\ldots,x_{n}b~{}|~{}b\in\mathcal{B}\right\\}.$
(3)

######  Definition 2.11.

Let ${\mathcal{B}}$ be a finite set of monomials and assume that
$|{\mathcal{B}}^{+}|=l$. The extended Hermite matrix associated to points
$~{}z_{1},\ldots,z_{k}\in\mathbb{C}^{n}$ (not necessarily distinct) is

$H^{+}_{g}:=H^{{\mathcal{B}}^{+}}_{g}(z_{1},\ldots,z_{k}):=(V^{+})^{T}GV^{+}\in{\mathbb{C}}^{l\times
l}$ (4)

where $V^{+}=V_{\mathcal{B}^{+}}(z_{1},\dots,z_{k})\in{\mathbb{C}}^{k\times
l}$ and G is the $k\times k$ diagonal matrix with $[G]_{j,j}=g(z_{j})$ for
$j=1,\dots,k$.

###  2.2 Rational Number Reconstruction

The continued fraction method for a real number $\alpha>0$ can be described as
the computation of

$\alpha=\gamma_{1}=\lfloor\gamma_{1}\rfloor+\frac{1}{\gamma_{2}}=\lfloor\gamma_{1}\rfloor+\frac{1}{\lfloor\gamma_{2}\rfloor+\frac{1}{\gamma_{3}}}=\cdots$

where $\gamma_{1}=\alpha$ and
$\gamma_{i+1}=\frac{1}{\gamma_{i}-\lfloor\gamma_{i}\rfloor}$. We call the
rational numbers

$\lfloor\gamma_{1}\rfloor,\lfloor\gamma_{1}\rfloor+\frac{1}{\lfloor\gamma_{2}\rfloor},\lfloor\gamma_{1}\rfloor+\frac{1}{\lfloor\gamma_{2}\rfloor+\frac{1}{\lfloor\gamma_{3}\rfloor}},\ldots$

the convergents for $\alpha$. The following theorem (c.f. [22, Corollary
6.3a]) gives bounds on the distance from $\alpha$ that guarantees uniqueness
of a rational number with bounded denominator, and shows that if such rational
number exists, it is a convergent for $\alpha$.

######  Theorem 2.12.

[22] There exists a polynomial time algorithm which, for a given rational
number $\alpha$ and a natural number $B$ tests if there exists a pair of
integers $(p,q)$ with $1\leq q\leq B$ and

$\left|\alpha-\frac{p}{q}\right|<\frac{1}{2B^{2}},$

and if so, finds this unique rational number $\frac{p}{q}$ as a convergent for
$\alpha$.

Approximate solutions are floating point numbers which are obtained from
numerical computations. Using an absolute error bound $E>0$ on numerical
computations, we can set the denominator bound $B$ such that Theorem 2.12
provide the unique rational approximation of $\alpha$ as follows:

######  Corollary 2.13.

Given $\alpha\in{\mathbb{R}}$ and $E>0$ in ${\mathbb{R}}$ there is at most one
rational number with its denominator bounded by
$B:=\left\lceil(2E)^{-1/2}\right\rceil$ within the distance $E$ from $\alpha$.

###  2.3 Numerical certification of non-roots of overdetermined systems

In this subsection we summarize some numerical methods from the literature to
compute approximations of a superset of the common roots of an overdetermined
system of polynomials
$f=(f_{1},\ldots,f_{m})\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ where $m>n$ and to
give a method to certify that a given point $z$ is _not_ an approximate root
of $f$. Here we need to assume that ${\mathcal{I}}=\langle
f_{1},\ldots,f_{m}\rangle$ is radical and zero dimensional. The difficulty
lies in the fact that numerical methods, such as the homotopy continuation
method [12], are designed to compute the common roots of square, well-
conditioned polynomial systems. Here we describe the approach presented in
[13] to handle overdetermined systems.

The main idea is that even though the consistency of an overdetermined system
is a non-continuous property, the converse, inconsistency of an overdetermined
system is a continuous property that can be certified with numerical methods.
Similarly, while certifying that a point is approximating an exact root of an
overdetermined system with exact rational coefficients cannot be certified
with purely numerical methods, certifying that a point is not an approximate
root can be done numerically. This allows us to eliminate in a certified
manner roots of a square subsystem of $(f_{1},\ldots,f_{m})$ that are not
roots of all polynomials and to give a certified upper bound $k$ on the number
of common roots of $(f_{1},\ldots,f_{m})$. With this upper bound we can
guarantee that our certification algorithm of Hermite matrices in Section 4 is
correct when it gives a certification (although it may also return “fail”).

More precisely, [13] suggests to consider two square systems, each are random
linear combinations of the polynomials $f_{1},\ldots,f_{m}$: If
$R_{1},R_{2}:{\mathbb{C}}^{m}\rightarrow{\mathbb{C}}^{n}$ two linear maps
(represented by two random matrices), then for $R_{i}(f):=R_{i}\circ f$ we can
assume that

$V(f)=V(R_{1}(f))\cap V(R_{2}(f)),$

which property is satisfied unless $R_{1}$ and $R_{2}$ are from Zariski closed
subsets of all linear transformations. Similarly, for $i=1,2$, we can assume
that the roots of $V(R_{i}(f))$ are finite and all distinct, this property is
also satisfied unless $R_{i}$ is from a Zariski closed subset of all linear
transformations (c.f. [13, Section 3]). Using numerical homotopy continuation
methods and $\alpha$-theory, one can compute and certify all approximate roots
of both $R_{1}(f)$ and $R_{2}(f)$, see details on this part of the algorithm
in [13, Section 2].

The following idea is a slight modification of [13, Section 3] allowing to
discard approximate roots of $R_{1}(f)$ and $R_{2}(f)$ that do not approximate
roots in $V(f)$. First note that for any approximate root $z$ approximating an
exact root $\xi\in V(R_{i}(f))$ for $i=1,2$, we can give upper bounds for
$\|{z}-{\xi}\|$ using two times the $\beta$ function defined in
$\alpha$-theory (c.f. [9, Ch 8, Theorem 2]), even without knowing the exact
root. Thus, for $i=1,2$ denote by $\tilde{V}(R_{i}(f))$ the set of pairs
$(z,\varepsilon)\in{\mathbb{C}}^{n}\times{\mathbb{R}}_{+}$ where $z$ is one of
the approximate roots computed for $R_{i}(f)$ and $\varepsilon$ is an upper
bound of the distance of $z$ from the exact root it approximates. Fix
$(z,\varepsilon)\in\tilde{V}(R_{1}(f))$ and define

$S_{(z,\varepsilon)}:=\left\\{(z^{\prime},\varepsilon^{\prime})\in\tilde{V}(R_{2}(f))\;:\>\|z-z^{\prime}\|\leq\varepsilon+\varepsilon^{\prime}\right\\}.$

If $|S_{(z,\varepsilon)}|>1$ then we need to refine $z$ and all $z^{\prime}$
such that $(z^{\prime},\varepsilon^{\prime})\in S_{(z,\varepsilon)}$ using
Newton’s method w.r.t $R_{1}(f)$ and $R_{2}(f)$ respectively, until one gets
$S_{(z,\varepsilon)}=\emptyset$ or $|S_{(z,\varepsilon)}|=1$. If
$S_{z}=\emptyset$ then we can discard $(z,\varepsilon)$ since it cannot
approximate an exact root in $V(f)=V(R_{1}(f))\cap V(R_{2}(f))$. If $S_{z}$
has one element $(z^{\prime},\varepsilon^{\prime})$, suppose $z$ approximates
an exact root $\xi\in V(R_{1}(f))$, $z^{\prime}$ approximates an exact root
$\xi^{\prime}\in V(R_{2}(f))$ but $\xi\neq\xi^{\prime}$. Then we can compute
refinements $z_{k}$ and $z^{\prime}_{k}$ using $k$ iterations of Newton’s
method starting from $z$ and $z^{\prime}$ w.r.t $R_{1}(f)$ and $R_{2}(f)$
respectively, such that

$\|{z}_{k}-{z^{\prime}}_{k}\|>\varepsilon_{k}+\varepsilon^{\prime}_{k}.$ (5)

where $\varepsilon_{k}\leq\frac{1}{2^{2^{k}-1}}\varepsilon$ is a bound on
$\|z_{k}-\xi\|$, and $\varepsilon^{\prime}_{k}$ is a bound for
$\|z^{\prime}_{k}-\xi^{\prime}\|$. If we find a $k$ such that the inequality
(5) is satisfied then we discard $(z,\varepsilon)$, otherwise we keep it. We
repeat the above procedure for all elements in
$\tilde{V}(R_{1}(f))\cup\tilde{V}(R_{2}(f))$.

Note that the above method never eliminates points that were approximating
roots in $V(f)$, but may leave in points that were not near $V(f)$. Thus, as a
consequence, we can always guarantee that the input $z_{1},\ldots,z_{k}$ for
Algorithm 3.1 below, to compute an approximate Hermite matrix, is a superset
of an approximation of $V(f)$, and in particular the above method gives a
certification that $k\geq\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$.
On the other hand, our main symbolic-numeric certification Algorithm 4.1 for
Hermite matrices will always fail when there are superfluous points among the
input. Thus, using the assumption
$k\geq\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$, the Hermite
matrices that we certify successfully will correspond to all roots of $V(f)$
(see Theorem 4.2).

In the rest of the paper we assume that we already computed a set
$\\{z_{1},\ldots,z_{k}\\}\subset{\mathbb{C}}^{n}$ that contain an approximate
root for each root in $V(f)$, i.e. if
$V(f)=\\{\xi_{1},\ldots,\xi_{k^{\prime}}\\}$ then $k^{\prime}\leq k$ and for
$i=1,\ldots,k^{\prime}$ there exists $j_{i}\in\\{1,\ldots,k\\}$ such that the
Newton iteration starting from $z_{j_{i}}$ quadratically converges to
$\xi_{i}$. Moreover, using the $\beta$ function from $\alpha$-theory as above,
we assume that we have a certified bound $E\in{\mathbb{R}}_{+}$ that we call
accuracy, such that

$\left\|\xi_{i}-z_{j_{i}}\right\|_{2}\leq E\quad i=1,\ldots,k^{\prime}.$ (6)

##  3 Constructing Rational Hermite Matrices

In this section we construct a rational matrix
$H_{1}^{+}\in{\mathbb{Q}}^{l\times l}$ from points $z_{1},\ldots,z_{k}$ given
with limited precision, using the definition of Hermite matrices in Defintion
2.11 and rational number reconstruction.

Let $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ with
$z_{i}=(z_{i,1},\ldots,z_{i,n})$ for $i=1,\ldots,k$. Let
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ be basis for
${\mathbb{R}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}(z_{1},\ldots,z_{k})$, and we
use ${\mathcal{B}}^{+}$ as described in (3). In the certification algorithm
below we will assume that ${\mathcal{B}}$ is connected to 1 as in Definition
2.9, but the algorithm of this section works for arbitrary ${\mathcal{B}}$.
Algorithm 3.1 below computes the matrix $H_{1}^{+}$ from the Hermite matrix
$H_{1}^{{\mathcal{B}}^{+}}(z_{1},z_{2},\ldots,z_{k})$ with respect to
${\mathcal{B}}^{+}$ by applying rational number reconstruction.

As part of the input of Algorithm 3.1, we also use quantities
$E,M\in{\mathbb{R}}_{+}$, where $E$ is an upper bound for the accuracy of each
$z_{i}$ for $i=1,\ldots,k$ and $M$ is an upper bound for the absolute values
of the coordinates of the exact common roots of ${\mathcal{I}}$. We assume
that $E$ is computed as part of the numerical method computing
$z_{1},\ldots,z_{k}$, as described in Section 2.3. In this section we use $E$
and $M$ to estimate the denominator in the rational number reconstruction for
each entry of $H_{1}^{+}$ using Proposition 3.2 below.

######  Algorithm 3.1 (Hermite Matrix Computation).

Input:

${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ and
${\mathcal{B}}^{+}$ as in (3) with $|{\mathcal{B}}^{+}|=l$ for
$k,l\in{\mathbb{N}}$.
$E,M\in{\mathbb{R}}_{+}$ and $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ such that
$\|z_{i}\|_{\infty}\leq M-E$ for $i=1,\ldots,k$ and $E$ is as in (6).

Output:

$H_{1}^{+}\in{\mathbb{Q}}^{l\times l}$ with rows and columns indexed by the
elements of ${\mathcal{B}}^{+}$.

1:

Compute the extended Hermite matrix
$H_{1}^{{\mathcal{B}}^{+}}(z_{1},z_{2},\ldots,z_{k})$ using Definition 2.11
with respect to the auxiliary function $g=1$ and the monomials in
$\mathcal{B}^{+}$.

2:

Rationalize each entry of the approximate Hermite matrix
$H_{1}^{{\mathcal{B}}^{+}}(z_{1},z_{2},\ldots,z_{k})$ using rational number
reconstruction as explained in Subsection 2.2. For the $(i,j)$-th entry of the
$H_{1}^{{\mathcal{B}}^{+}}(z_{1},z_{2},\ldots,z_{k})$, we use the following
denominator bound:

$B_{ij}:=\left\lceil(2Eknd_{i,j}M^{d_{i,j}-1})^{-1/2}\right\rceil,$ (7)

where $d_{i,j}=\deg b_{i}+\deg b_{j}$ and $b_{i}$ and $b_{j}$ are the $i$-th
and $j$-th elements of ${\mathcal{B}}^{+}$ respectively, for $1\leq i,j\leq
l$. (See Proposition 3.2 below for obtaining this bound.) Return the resulting
rational matrix.

We need the following proposition to get the bounds in (7) for the
denominators of the entries of the Hermite matrix.

######  Proposition 3.2.

Given ${\mathcal{I}}=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ zero
dimensional radical ideal with
$V({\mathcal{I}})=\\{\xi_{1},\ldots,\xi_{k}\\}\subset{\mathbb{C}}^{n}.$
Suppose $E>0$ and $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ are such that

$\|\xi_{i}-z_{i}\|_{2}<E.$

Let $M>0$ such that for all $i=1,\ldots,k$ and $y\in{\rm
Ball}(z_{i},E)=\\{x\in{\mathbb{C}}^{n}:\|x-z_{i}\|_{2}<E\\}$

$\|y\|_{\infty}\leq M.$

Let $\alpha\in{\mathbb{N}}^{n}$ with $d:=|\alpha|$. Then we have

$\displaystyle\left|\sum_{i=1}^{k}\xi_{i}^{\alpha}-\sum_{i=1}^{k}z_{i}^{\alpha}\right|\leq
EkndM^{d-1}.$ (8)

Furthermore, there is at most one rational number within $EkndM^{d-1}$
distance from $\sum_{i=1}^{k}z_{i}^{\alpha}$ with denominator bounded by

$B:=\left\lceil(2EkndM^{d-1})^{-1/2}\right\rceil.$

###### Proof.

Fix $\alpha\in{\mathbb{N}}^{n}$ with $d:=|\alpha|$. First note that
$\sum_{i=1}^{k}z_{i}^{\alpha}$ is a polynomial in the $nk$ coordinates of
$z_{1},\ldots,z_{k}$ of degree $d$. Using a multivatiate version of Taylor’s
Theorem [1], there exist $R_{i,j}(z_{1},\ldots,z_{k})$ for $i=1,\ldots,k$ and
$j=1,\ldots,n$ such that

$\sum_{i=1}^{k}z_{i}^{\alpha}-\sum_{i=1}^{k}\xi_{i}^{\alpha}=\sum_{i=1}^{k}\sum_{j=1}^{n}R_{i,j}(z_{1},\ldots,z_{k})(z_{i,j}-\xi_{i,j}).$

Moreover,

$|R_{i,j}(z_{1},\ldots,z_{k})|\leq\max_{s,t}\max_{y_{s}\in{{\rm
Ball}}(z_{s},E)}\left|\frac{\partial z_{s}^{\alpha}}{\partial
z_{s,t}}(y_{s})\right|\leq dM^{d-1}.$

Thus we get

$\left|\sum_{i=1}^{k}z_{i}^{\alpha}-\sum_{i=1}^{k}\xi_{i}^{\alpha}\right|\leq\sum_{j=1}^{n}\sum_{i=1}^{k}dM^{d-1}\left|z_{i,j}-\xi_{i,j}\right|\leq
kndM^{d-1}E.$

The second claim is straightforward from Corollary 2.13 using
$E^{\prime}=EkndM^{d-1}$. ∎

The next theorem gives sufficient conditions for Algorithm 3.1 to correctly
compute the exact Hermite matrices $H_{1}^{+}$ for ${\mathcal{I}}$ from the
approximate points $z_{1},\ldots,z_{k}$.

######  Theorem 3.3.

Let ${\mathcal{I}}=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{Q}}[x_{1},\dots,x_{n}]$ be a zero
dimensional radical ideal with
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ a basis for
${\mathbb{Q}}[x_{1},\dots,x_{n}]/{\mathcal{I}}.$ Denote
$V_{\mathbb{C}}({\mathcal{I}})=\\{\xi_{1},\ldots,\xi_{k}\\}\subset{\mathbb{C}}^{n}$.
Let $E>0$ and $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ such that for each
$i\in\\{1,\ldots,k\\}$ there exists a unique $j_{i}$ such that

$\|z_{j_{i}}-\xi_{i}\|_{2}<E.$

Assume further that $\|z_{i}\|_{\infty}\leq M-E$ for all $i=1,\ldots,k$.
Finally, assume that for $x^{\alpha}=x_{i}x_{j}x^{\alpha_{t}}\,x^{\alpha_{s}}$
for $i,j=1,\ldots n$ and $t,s=1,\ldots,k$, the denominator of
$\sum_{j=1}^{k}\xi_{i}^{\alpha}\in{\mathbb{Q}}$ is at most
$\lceil(2Ekn|\alpha|M^{|\alpha|-1})^{-1/2}\rceil$. Then Algorithm 3.1 computes
the exact Hermite matrices $H_{1}^{{\mathcal{B}}^{+}}({\mathcal{I}})$.

###### Proof.

Since $\|z_{i}-\xi_{j_{i}}\|_{2}<E$ and $\|z_{i}\|_{\infty}\leq M-E$, we have
that $\|\xi_{i}\|_{\infty}\leq M$, thus the assumptions of Proposition 3.2 are
satisfied. Therefore, for all $\alpha\in{\mathbb{N}}^{n}$ as in the claim, we
have that there is at most one rational number within
$Ekn|\alpha|M^{|\alpha|-1}$ distance from $\sum_{i=1}^{k}z_{i}^{\alpha}$ with
denominators bounded by $\lceil(2Ek|\alpha|M^{|\alpha|-1})^{-1/2}\rceil$. By
Proposition 3.2 we can see that $\sum_{i=1}^{k}\xi_{i}^{\alpha}$ is within
that distance from $\sum_{i=1}^{k}z_{i}^{\alpha}$, and using our assumption on
the denominator of $\sum_{i=1}^{k}\xi_{i}^{\alpha}\in{\mathbb{Q}}$, by Theorem
2.12 the rational number reconstruction algorithm finds
$\sum_{i=1}^{k}\xi_{i}^{\alpha}$. Thus, the entries of $H_{1}^{+}$ computed by
Algorithm 3.1 are the same as the entries of
$H_{1}^{{\mathcal{B}}^{+}}({\mathcal{I}})$ as claimed. ∎

######  Remark 3.4.

The assumption of Theorem 3.3 that the denominator of
$\sum_{j=1}^{k}\xi_{i}^{\alpha}\in{\mathbb{Q}}$ is at most
$\lceil(2Ekn|\alpha|M^{|\alpha|-1})^{-1/2}\rceil$ can be achieved by improving
the accuracy $E$ of the approximate roots $z_{1},\ldots,z_{k}$. If we assume
that $z_{1},\ldots,z_{k}$ are all approximate roots for a square subsystem of
$f$, we can use Newton iterations to quadratically converge to the exact
roots, thus decrease $E$. Meanwhile, the other quantities in this bound
($k,n,|\alpha|,M$) are fixed, so with enough iterations we increase
$\lceil(2Ekn|\alpha|M^{|\alpha|-1})^{-1/2}\rceil$ to satisfy the condition of
the Theorem. One could in theory study a priori bounds on how small $E$ has to
be to satisfy this condition, (we did a similar analysis in [3]), but in this
paper we let our Hermite matrix certification algorithm reject cases when the
accuracy of the root approximation is not sufficiently good.

##  4 Certification of the Exact Hermite Matrix

Let $f=(f_{1},\ldots,f_{m})\in\mathbb{Q}[x_{1},\dots,x_{n}]^{m}$ be a rational
polynomial system with zero dimensional radical ideal $\mathcal{I}=\langle
f_{1},\ldots,f_{m}\rangle$. In the previous section we computed a matrix
$H_{1}^{+}$ with rows and columns corresponding to ${\mathcal{B}}^{+}$, where
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$. In this section we
certify if this matrix is the the extended Hermite matrix of ${\mathcal{I}}$
and we also compute $H_{g}({\mathcal{I}})$ for any polynomial
$g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$, as long as
$k\geq\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$. Here we assume that
${\mathcal{B}}$ is connected to 1 as in Definition 2.9. The following
algorithm is purely symbolic:

######  Algorithm 4.1 (Hermite Matrix Certification).

Input:

${f}=(f_{1},\ldots,f_{m})\in{\mathbb{Q}}[x_{1},\dots,x_{n}]^{m}$ with
${\mathcal{I}}=\langle f_{1},\ldots,f_{m}\rangle$ zero dimensional and
radical;
$g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$,
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ connected to 1 with
$|{\mathcal{B}}^{+}|=l$ for some $k,l\in{\mathbb{N}}$
$H_{1}^{+}\in{\mathbb{Q}}^{l\times l}$ with rows and columns indexed by the
elements of ${\mathcal{B}}^{+}$.

Output:

The certified $H_{1}({\mathcal{I}})$ and $H_{g}({\mathcal{I}})$, or Fail.

1:

$H_{1}\leftarrow k\times k$ submatrix of $H_{1}^{+}$ with rows and columns
corresponding to ${\mathcal{B}}$.
$H_{1}^{x_{s}}\leftarrow$ $k\times k$ submatrix of $H_{1}^{+}$ with rows
corresponding to ${\mathcal{B}}$ and columns corresponding to
$x_{s}{\mathcal{B}}$ for $s=1,\ldots,n$.

2:

If ${\rm rank}~{}H_{1}={\rm rank}~{}H_{1}^{+}=k,$ then $M_{s}\leftarrow
H_{1}^{-1}\cdot H_{1}^{x_{s}}$ for $s=1,\ldots,n$. else return Fail.

3:

For $s=1,\ldots,n$, $i,j=1,\ldots,k$
if $x_{s}x^{\alpha_{i}}=x^{\alpha_{j}}$ and $\left[M_{s}\right]_{i,*}\neq{\bf
e}_{j}^{T}$ then return Fail.

4:

Let $c_{1},\ldots,c_{n}$ be either new parameters or generic elements of
${\mathbb{Q}}$.
$p(\lambda)\leftarrow$ characteristic polynomial polynomial to
$\sum_{i=1}^{n}c_{i}M_{i}$.
if $\gcd(p(\lambda),p^{\prime}(\lambda))\neq 1$ return Fail.

5:

If

$M_{i}\cdot M_{j}=M_{j}\cdot M_{i}\quad 1\leq i<j\leq n$

and

$f_{i}(M_{1},M_{2},\ldots,M_{n})=0\hbox{ for }i=1,\ldots,m,$

then we certified that $M_{i}$ is the transpose of the multiplication matrix
of ${\mathcal{I}}$ with respect to $x_{i}$ in the basis ${\mathcal{B}}$ for
all $i=1,\ldots,n$.
Else return Fail.

6:

For $i,j=1,\ldots,l$ if

${\rm Tr}((b_{i}\cdot
b_{j})(M_{1},M_{2},\ldots,M_{n}))\neq\left[H_{1}\right]_{i,j}$

where $b_{i}$ and $b_{j}$ are the $i$-th and $j$-th elements of
${\mathcal{B}}$ respectively, and $(b_{i}\cdot
b_{j})(M_{1},M_{2},\ldots,M_{n})$ is the matrix obtained by evalutaing the
polynomial $b_{i}\cdot b_{j}$ in the matrices $M_{1},M_{2},\ldots,M_{n}$
then return  Fail.
Else we certified $H_{1}=H_{1}({\mathcal{I}})$.

7:

Return $H_{1}$ and $H_{g}\leftarrow H_{1}\cdot g(M_{1},\ldots,M_{n}).$

We have the following result on the correctness of Algorithm 4.1.

######  Theorem 4.2.

Let $f=(f_{1},\ldots,f_{m})\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ with
${\mathcal{I}}=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{Q}}[x_{1},\dots,x_{n}]$,
$g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$,
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ connected to 1 with
$|{\mathcal{B}}^{+}|=l$ for some $k,l\in{\mathbb{N}}$. Let
$H_{1}^{+}\in{\mathbb{Q}}^{l\times l}$ be a matrix with rows and columns
indexed by the elements of ${\mathcal{B}}^{+}$. If
$k\geq\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$ and Algorithm 4.1
does not return Fail then ${\mathcal{I}}$ is radical, ${\mathcal{B}}$ is a
basis for ${\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$ and the output
satisfies

$H_{1}=H_{1}^{\mathcal{B}}({\mathcal{I}})\;\text{ and
}\;H_{g}=H_{g}^{\mathcal{B}}({\mathcal{I}}).$

###### Proof.

Assume Algorithm 4.1 did not fail, and let $M_{1},\ldots,M_{n}$ be the
matrices computed in Step 2. Define the set of polynomials ${\mathcal{F}}$
from the columns of $M_{1},\ldots,M_{n}$ as follows

${\mathcal{F}}:=\left\\{x_{j}x^{\alpha_{t}}-\sum_{i=1}^{k}[M_{j}]_{i,t}\,x^{\alpha_{i}}\;:\;j=1,\ldots,n,t=1,\ldots,k\right\\}.$

Let $J:=\langle{\mathcal{F}}\rangle\subset{\mathbb{Q}}[x_{1},\ldots,x_{n}]$.
In [19, Theorem 3.1] it is proved that ${\mathcal{B}}$ forms a basis for
${\mathbb{Q}}[x_{1},\ldots,x_{n}]/J$ and ${\mathcal{F}}$ is a border basis for
$J$ if the following three conditions are satisfied: 1. the map $N:{\rm
span}({\mathcal{B}}^{+})\rightarrow{\rm span}({\mathcal{B}})$ defined as
$N(x_{j}x^{\alpha_{t}}):=\sum_{i=1}^{k}[M_{j}]_{i,t}x^{\alpha_{i}}$ satisfy
$N\left|{}_{\mathcal{B}}\right.={\rm Id};\;$ 2\. the space spanned by
${\mathcal{B}}$ is connected to $1;\;$ 3\. $\\{M_{1},\ldots,M_{n}\\}$ is a set
of pairwise commuting matrices. The first condition is certified in Step 3,
the second is an assumption, and the third is certified in Step 5. Also by
Step 5 we have

$f_{i}(M_{1},M_{2},\ldots,M_{n})=0\hbox{ for }i=1,\ldots,m,$

thus ${\mathcal{I}}\subset J$. Since
$\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/J=k$ and
$\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}\leq k$ by assumption, we
must have that ${\mathcal{I}}=J$ and for $s=1,\ldots,n$, $M_{s}$ is the
transpose of the matrix of the multiplication map

$\mu_{x_{s}}:{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}\rightarrow{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}},\quad[p]\mapsto[x_{s}p],$

with respect to the basis ${\mathcal{B}}$. Step 6 certifies that the entries
of $H_{1}^{+}$ are correct using Definition 2.3. Let $p$ be the characteristic
polynomial as in Step 4. Since $\gcd(p(\lambda),p^{\prime}(\lambda))\neq 1$ we
have that $p$ has $k$ distinct roots, so $M_{1},\ldots,M_{n}$ are
simultaneously diagonalizable, and we have for
$g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$

$g(M_{1},\ldots,M_{n})=V^{-1}GV$

where $V=V_{\mathcal{B}}(\xi_{1},\ldots,\xi_{k})$ is the Vandermonde matrix of
the exact roots of $V({\mathcal{I}})=\\{\xi_{1},\ldots,\xi_{k}\\}$ with
respect to ${\mathcal{B}}$ and $G$ is the diagonal matrix ${\rm
diag}(g(\xi_{1}),\ldots,g(\xi_{k}))$. This gives

$H_{1}\cdot g(M_{1},\ldots,M_{n})=(V^{T}V)\cdot(V^{-1}GV)=V^{T}GV=H_{g}.$

Thus, once $H_{1}$ and $M_{1},\ldots,M_{n}$ are certified, we have computed
the certified matrix $H_{g}({\mathcal{I}})$. ∎

######  Remark 4.3.

For ${\mathcal{B}}=\\{1,x_{1},\ldots,x_{1}^{k-1}\\}$ we can guarantee that

${\rm rank}(H_{1})={\rm rank}(H_{1}^{+})=k$

by checking that the difference between the first coordinates of $z_{i}$ and
$z_{j}$ is at least $2E$ for all $1\leq i<j\leq n$. In this case, since we
assume that $\|z_{i}-\xi_{j_{i}}\|_{2}<E$, then we must have that the first
coordinates of $\xi_{1},\ldots,\xi_{k}$ are all distinct. Since
$H_{1}({\mathcal{I}})=V^{T}V$ where $V$ is the usual univariate Vandermonde
matrix of these first coordinates of $\xi_{1},\ldots,\xi_{k}$, we get that
$H_{1}({\mathcal{I}})$ is invertible. Since
$H_{1}^{+}({\mathcal{I}})=V_{{\mathcal{B}}^{+}}^{T}V_{{\mathcal{B}}^{+}}$, and
${\rm rank}(V_{{\mathcal{B}}^{+}})=k$, we have that ${\rm rank}(H_{1})={\rm
rank}(H_{1}^{+})=k.$ For general ${\mathcal{B}}$ there are no such simple
conditions, but the SVD of the Vandermonde matrix of $z_{1},\ldots,z_{k}$ with
respect to ${\mathcal{B}}$ gives a good indication that ${\mathcal{B}}$ is a
basis for both ${\mathbb{C}}[x_{1},\ldots,x_{n}]/I(z_{1},\ldots,z_{k})$ and
${\mathbb{C}}[x_{1},\ldots,x_{n}]/I(\xi_{1},\ldots,\xi_{k})$. Also for
${\mathcal{B}}=\\{1,x_{1},\ldots,x_{1}^{k-1}\\}$, Step 3 is simply checking if
$M_{1}$ has a companion matrix structure. In this case, in Step 6 we can
certify $H_{1}^{+}$ using the Newton-Girard formulae (c.f. [18]), computing
the power sum elementary symmetric functions for degrees $1,\ldots,2k$ from
the coefficients of $p(x_{1})$, and constructing the matrix $H_{1}^{+}$
according to (2).

##  5 Extension to the non-radical case

So far in this paper we assumed that the ideal ${\mathcal{I}}$ is radical and
zero-dimensional. In this section, we describe what we can certify when we
drop the assumption of radicality.

First note that Definition 2.1 for the Hermite matrix in terms of roots is
well defined and continuous even if some of the roots are repeated. This is no
longer true when we try to define the multiplication matrices from the roots.
Using a notation similar to the previous section, for ${\mathcal{B}}$ a basis
for ${\mathbb{R}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}$ and
$g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$, denote by $M^{\mathcal{B}}_{g}$ the
transpose of the matrix of multiplication
$\mu_{g}:{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}}\rightarrow{\mathbb{Q}}[x_{1},\ldots,x_{n}]/{\mathcal{I}},\;[p]\mapsto[gp]$
in the basis ${\mathcal{B}}$. While in the case when ${\mathcal{I}}$ is
radical we have

$M^{\mathcal{B}}_{g}=V_{\mathcal{B}}\,G\,V_{\mathcal{B}}^{-1},$

with $V_{\mathcal{B}}=[b(\xi)]_{\xi\in V({\mathcal{I}}),b\in{\mathcal{B}}}$
and $G={\rm diag}(g(\xi)\,:\,\xi\in V({\mathcal{I}}))$, $M^{\mathcal{B}}_{g}$
is not diagonalizable when ${\mathcal{I}}$ is not radical. In particular,
$V_{\mathcal{B}}({\mathcal{I}})$ and $H_{1}^{\mathcal{B}}(I)$ are not
invertible, so we cannot use them to compute multiplication matrices in the
certification algorithm as above.

To overcome this difficulty, we notice that while in the non-radical case
$H_{1}^{\mathcal{B}}({\mathcal{I}})$ is not invertible, its maximal non-
singular submatrix is the Hermite matrix
$H_{1}^{\bar{{\mathcal{B}}}}(\sqrt{{\mathcal{I}}})$ of the radical of
${\mathcal{I}}$, with respect to a subset
$\bar{{\mathcal{B}}}\subset{\mathcal{B}}$ that is a basis for
${\mathbb{R}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$ (c.f. [17]). Denote by
$\bar{H}_{1}$ this maximal non-singular submatrix of
$H_{1}^{\mathcal{B}}({\mathcal{I}})$, with rows and columns corresponding to
$\bar{{\mathcal{B}}}\subset{\mathcal{B}}$ and by $\bar{H}_{1}^{x_{i}}$ the
submatrix of $H_{1}^{{\mathcal{B}}+}({\mathcal{I}})$ corresponding to rows
indexed by $\bar{{\mathcal{B}}}$ and columns indexed by
$x_{i}\cdot\bar{{\mathcal{B}}}$. Then we get the transpose of the matrix of
multiplication by $x_{i}$ in
${\mathbb{Q}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$ w.r.t. the basis
$\bar{{\mathcal{B}}}$ by

$\bar{M}_{i}:=M_{x_{i}}^{\bar{{\mathcal{B}}}}=\bar{H}_{1}^{-1}\cdot\bar{H}_{1}^{x_{i}}\quad
i=1,\ldots,n.$

Thus we can use $\bar{H}_{1}^{\bar{{\mathcal{B}}}^{+}}$ to compute the
multiplication matrices of the radical $\sqrt{{\mathcal{I}}}$ and certify
them.

We modify Algorithm 3.1 to output the maximal non-singular submatrix
$\bar{H}_{1}$ of $H_{1}$ with rows and columns corresponding to
$\bar{{\mathcal{B}}}\subset{\mathcal{B}}$, and its extension $\bar{H}^{+}_{1}$
to the basis $\bar{{\mathcal{B}}}^{+}$.

######  Algorithm 5.1 (Hermite Matrix Computation - Non Radical Case).

Input:

$k\in{\mathbb{N}}$, ${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$
connected to 1, $E,M\in{\mathbb{R}}_{+}$ and
$z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ such that $E$ is a bound on the
accuracy of $z_{i}$ and $\|z_{i}\|_{\infty}\leq M-E$ for $i=1,\ldots,k$.

Output:

Fail or $\bar{k}\leq k\in{\mathbb{N}}$,
$\bar{{\mathcal{B}}}\subset{\mathcal{B}}$ connected to 1, and
$\bar{H}_{1}^{+}\in{\mathbb{Q}}^{\bar{l}\times\bar{l}}$ with rows and columns
indexed by the elements of $\bar{{\mathcal{B}}}^{+}$such that

${\rm rank}~{}\bar{H}_{1}={\rm rank}~{}\bar{H}_{1}^{+}=\bar{k},$

where $\bar{H}_{1}$ is the submatrix of $\bar{H}_{1}^{+}$ with rows and
columns corresponding to $\bar{{\mathcal{B}}}$.

1:

$H_{1}^{{\mathcal{B}}^{+}}(z_{1},z_{2},\ldots,z_{k})\leftarrow\text{\sc
Hermite Matrix
Computation}\left({\mathcal{B}},{\mathcal{B}}^{+},E,M,\\{z_{1},\ldots,z_{k}\\}\right)$
(see Algorithm 3.1). Denote the resulting matrix by $H_{1}^{+}$ and its
submatrix corresponding to rows and columns of ${\mathcal{B}}$ by $H_{1}$.

2:

Find $\bar{k}$ maximal and $\bar{{\mathcal{B}}}\subset{\mathcal{B}}$ connected
to 1 with $|\bar{{\mathcal{B}}}|=\bar{k}$ such that the submatrix
$\bar{H}_{1}$ of $H_{1}$, corresponding to rows and and columns in
$\bar{{\mathcal{B}}}$, have the same rank as $H_{1}$.

3:

If ${\rm rank}(H_{1}^{+})>\bar{k}$ return Fail. Else return $\bar{H}_{1}^{+}$,
the submatrix of $H_{1}^{+}$ with rows and columns corresponding to
$\bar{{\mathcal{B}}}^{+}$.

######  Theorem 5.2.

Let ${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$,
${\mathcal{I}}=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{Q}}[x_{1},\dots,x_{n}]$ be a zero
dimensional ideal
$V_{\mathbb{C}}({\mathcal{I}})=\\{\xi_{1},\ldots,\xi_{\bar{k}}\\}\subset{\mathbb{C}}^{n}$
for some $\bar{k}\in{\mathbb{N}}$ with the multiplicity of $\xi_{i}$ denoted
by $k_{i}$, where
$k:=\sum_{i=1}^{\bar{k}}k_{i}=\dim{\mathbb{Q}}[x_{1},\dots,x_{n}]/{\mathcal{I}}$.
Let $E>0$ and $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$, not necessarily all
distinct. Assume that for each $i\in\\{1,\ldots,\bar{k}\\}$ there exists a
multi-subset $Z_{i}$ of the multiset $\\{z_{1},\ldots,z_{k}\\}$ such that for
$z\in Z_{i}$

$\|z-\xi_{i}\|_{2}<E.$

Furthermore, assume that the multiset $Z_{i}$ has $k_{i}$ elements, counted
with multiplicity, $Z_{i}\cap Z_{j}=\emptyset$ for $1\leq i<j\leq\bar{k}$ and
$k=\sum_{i=1}^{\bar{k}}k_{i}$. Assume further that $\|z_{i}\|_{\infty}\leq
M-E$ for all $i=1,\ldots,k$. Finally, assume that for
$x^{\alpha}=x_{i}x_{j}x^{\alpha_{t}}\,x^{\alpha_{s}}$ for $i,j=1,\ldots n$ and
$t,s=1,\ldots,k$, the denominator of
$\sum_{j=1}^{\bar{k}}k_{i}\xi_{i}^{\alpha}\in{\mathbb{Q}}$ is at most
$\lceil(2Ekn|\alpha|M^{|\alpha|-1})^{-1/2}\rceil$. Then Step 1 computes the
exact Hermite matrices $H_{1}^{+}=H_{1}^{{\mathcal{B}}^{+}}({\mathcal{I}})$.
Moreover, if $\bar{{\mathcal{B}}}$ defined in Step 2 forms a basis of
${\mathbb{Q}}[x_{1},\dots,x_{n}]/\sqrt{{\mathcal{I}}}$ then ${\rm
rank}(H_{1}^{+})={\rm rank}(\bar{H}_{1})=\bar{k}$ and
$\bar{H}_{1}^{+}=H_{1}^{\bar{{\mathcal{B}}}^{+}}(\sqrt{{\mathcal{I}}})$.

###### Proof.

Since $\|z_{i}-\xi_{j_{i}}\|_{2}<E$ and $\|z_{i}\|_{\infty}\leq M-E$, we have
that $\|\xi_{i}\|_{\infty}\leq M$, thus the assumptions of Proposition 3.2 are
satisfied. Therefore, for all $\alpha\in{\mathbb{N}}^{n}$ as in the claim, we
have that there is at most one rational number within
$Ekn|\alpha|M^{|\alpha|-1}$ distance from $\sum_{i=1}^{k}z_{i}^{\alpha}$ with
denominators bounded by $\lceil(2Ek|\alpha|M^{|\alpha|-1})^{-1/2}\rceil$. We
can take a limit argument from $k$ distinct points to the multiset
$\\{(\xi_{1},k_{1}),\ldots,(\xi_{\bar{k}},k_{\bar{k}})\\}$ and apply
Proposition 3.2 to this multiset and get that
$\sum_{i=1}^{\bar{k}}k_{i}\xi_{i}^{\alpha}$ is within that distance from
$\sum_{i=1}^{k}z_{i}^{\alpha}$. Using our assumption on the denominator of
$\sum_{i=1}^{k}\xi_{i}^{\alpha}\in{\mathbb{Q}}$, by Theorem 2.12 the rational
number reconstruction algorithm finds
$\sum_{i=1}^{\bar{k}}k_{i}\xi_{i}^{\alpha}$. Thus, the entries of $H_{1}^{+}$
computed by Algorithm 3.1 are the same as the entries of
$H_{1}^{+}({\mathcal{I}})$ as claimed.
To prove the last claim, if $\bar{{\mathcal{B}}}$ forms a basis for
${\mathbb{Q}}[x_{1},\dots,x_{n}]/\sqrt{{\mathcal{I}}}$ then
$V_{\bar{{\mathcal{B}}}}=[b(\xi_{i})]_{i=1,\ldots,\bar{k},\,b\in\bar{{\mathcal{B}}}}$
is a square submatrix of maximal rank of
$V_{{\mathcal{B}}^{+}}(I)=[b(\xi)]_{\xi\in
V({\mathcal{I}}),\,b\in{\mathcal{B}}^{+}}$ with each roots in
$V({\mathcal{I}})$ listed as many times as their multiplicity. Since
$H_{1}^{+}=H_{1}^{{\mathcal{B}}+}({\mathcal{I}})=V_{{\mathcal{B}}^{+}}(I)^{T}V_{{\mathcal{B}}^{+}}(I)$,
and $\bar{H}_{1}=V_{\bar{{\mathcal{B}}}}^{T}V_{\bar{{\mathcal{B}}}}$ which
proves ${\rm rank}(H_{1}^{+})={\rm rank}(\bar{H}_{1})=\bar{k}$ and
$\bar{H}_{1}^{+}=H_{1}^{\bar{{\mathcal{B}}}^{+}}(\sqrt{{\mathcal{I}}})$. ∎

We can use Algorithm 4.1 unchanged with input $f,g$, $\bar{{\mathcal{B}}}$,
and $\bar{H}_{1}^{+}$ to compute certified Hermite matrices $H_{1}$ and
$H_{g}$ for $\sqrt{{\mathcal{I}}}$. We have the following theorem.

######  Theorem 5.3.

Let $f=(f_{1},\ldots,f_{m})\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]^{m}$,
${\mathcal{I}}=\langle
f_{1},\ldots,f_{m}\rangle\subset{\mathbb{Q}}[x_{1},\dots,x_{n}]$ a zero
dimensional ideal, $g\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$. Let ${\mathcal{B}}$
connected to 1 with $|{\mathcal{B}}|=k$ and $|{\mathcal{B}}^{+}|=l$ for some
$k,l\in{\mathbb{N}}$. Suppose Algorithm 5.1 returns $\bar{k}\leq k$,
$\bar{{\mathcal{B}}}$ connected to 1 with $|\bar{{\mathcal{B}}}|=\bar{k}$ and
$\bar{H}_{1}^{+}$ with rows and columns indexed by the elements of
$\bar{{\mathcal{B}}}^{+}$. If
$\bar{k}\geq\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$ and
Algorithm 4.1 with inputs $f,g$, $\bar{{\mathcal{B}}}$, and $\bar{H}_{1}^{+}$
returns $H_{1}$ and $H_{g}$ then $\bar{{\mathcal{B}}}$ is a basis for
${\mathbb{Q}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$ and

$H_{1}=H_{1}^{\bar{{\mathcal{B}}}}(\sqrt{{\mathcal{I}}})\;{\rm
and}\;H_{g}=H_{g}^{\bar{{\mathcal{B}}}}(\sqrt{{\mathcal{I}}}).$

###### Proof.

Assume Algorithm 5.1 did not fail, and returns $\bar{k}\leq k$,
$\bar{{\mathcal{B}}}$ connected to 1 with $|\bar{{\mathcal{B}}}|=\bar{k}$ and
$\bar{H}_{1}^{+}$. Then by Step 3 of Algorithm 5.1 we have ${\rm
rank}(H_{1}^{+})={\rm rank}(\bar{H}_{1}^{+})={\rm rank}(\bar{H}_{1})=\bar{k}$
so we can define the $\bar{k}\times\bar{k}$ matrices $M_{1},\ldots,M_{n}$ in
Step 2 of Algorithm 4.1. The same argument as in the proof of Theorem 4.2
shows that $M_{1},\ldots,M_{n}$ forms a system of (transpose) multiplication
matrices for an ideal $J$ such that
$\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/J=\bar{k}$, and $M_{1},\ldots,M_{n}$ are
simultaniously diagonalizable and their eigenvalues are the coordinates of the
$\bar{k}$ distinct roots of $J$. Since $f_{i}(M_{1},\ldots,M_{n})=0$ for all
$i=1,\ldots m$ we have that these $\bar{k}$ distinct roots are also common
roots of ${\mathcal{I}}$. By assumption,
$\bar{k}\geq\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$, so
${\mathcal{I}}$ has at most $\bar{k}$ distinct roots, so we must have
$\bar{k}=\dim{\mathbb{Q}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$ and
$\bar{B}$ forms a basis
${\mathbb{Q}}[x_{1},\ldots,x_{n}]/\sqrt{{\mathcal{I}}}$. Thus
$J=\sqrt{{\mathcal{I}}}$. The rest of the proof is the same as the proof of
Theorem 4.2 with $\sqrt{{\mathcal{I}}}$ replacing ${\mathcal{I}}$. ∎

##  6 Application: Rational certificate of non-negativity over real varieties

As mentioned in the Introduction, the following application was inspired by
[10] where the authors give a method to compute a degree $d$ sum of squares
(SOS) decomposition (if one exists) for a non-negative polynomial over a real
algebraic set using a finite set of sample points from the (complex) algebraic
set. In [10] they also give bounds on the number of sample points needed to
decide whether a degree $d$ SOS decomposition exists. Their method uses
semidefinite programming.

The application we present below also gives a certificate for the non-
negativity of a polynomial over a real algebraic set, and also uses sample
points of the complex algebaric set. However, it does not give an SOS
decomposition, instead it uses Hermite matrices reconstructed and certified
from the sample points. While the SOS decomposition constructed in [10] is
approximate, the construction we give here is exact, using rational numbers.

Consider the following problem:

######  Problem 6.1.

Given $f=(f_{1},\ldots,f_{s})\in{\mathbb{Q}}[x]^{s}$ and $g\in{\mathbb{Q}}[x]$
for $x=(x_{1},\ldots,x_{n})$. Decide if $g(z)\geq 0$ for all $z\in
V(f)\cap{\mathbb{R}}^{n}$ and give a rational certificate.

We use the following notion of critical points of $g$ in
$V(f)\subset{\mathbb{C}}^{n}$:

######  Definition 6.2.

Let $f=(f_{1},\ldots,f_{s})\in{\mathbb{Q}}[x]^{s}$ and $g\in{\mathbb{Q}}[x]$,
and assume that ${\mathcal{I}}:=\langle f_{1},\ldots,f_{s}\rangle$ is a
radical ideal. $z\in{\mathbb{C}}^{n}$ is a critical point of $g$ in $V(f)$ if
$z\in V(f)$, $z$ is non-singular in $V(f)$, i.e. the Jacobian matrix $Jf(z)$
of $f$ has rank $c:=n-\dim V(f)$, and the Jacobian matrix $Jf(z)$ augmented
with the row vector $\nabla g(z)$ has also rank $c$.

We can solve Problem 6.1 using the following assumptions on
$f=(f_{1},\ldots,f_{s})$ and $g$:

######  Assumption 6.3.

Let $f=(f_{1},\ldots,f_{s})\in{\mathbb{Q}}[x]^{s}$ and $g\in{\mathbb{Q}}[x]$
for $x=(x_{1},\ldots,x_{n})$. We assume

  1. 1.

For all $z\in V(f)$, the Jacobian matrix $Jf(z)$ of $f$ has rank $s\leq n$,
i.e., $f$ is a regular sequence and $V(f)$ is smooth.

  2. 2.

$V(f)\cap{\mathbb{R}}^{n}$ is bounded,

  3. 3.

$g$ has finitely many critical points on $V(f)$.

We need the following lemma:

######  Lemma 6.4.

Let $f\in{\mathbb{Q}}[x]^{s}$ and $g\in{\mathbb{Q}}[x]$ satisfying Assumption
6.3. Then, the set of polynomials in
${\mathbb{Q}}[x_{1},\ldots,x_{n},\lambda_{1},\ldots,\lambda_{s}]$

$L(x,\lambda)=\\{f_{1},\ldots,f_{s}\\}\cup\left\\{\frac{\partial g}{\partial
x_{i}}+\sum_{j=1}^{s}\lambda_{j}\frac{\partial f_{j}}{\partial
x_{i}}\;:\;i=1,\ldots,n\right\\}$

has finitely many roots in ${\mathbb{C}}^{n+s}$, and their projections to the
$x$ coordinates contain all real points where $g$ attains its extreme values
on each connected component of $\,\left(V(f)\setminus
V(g)\right)\cap{\mathbb{R}}^{n}$.

###### Proof.

First we prove that the projection $V(L)\subset{\mathbb{C}}^{n+s}$ onto the
$x$-coordinates are the critical points of $g$ in $V(f)$. Let $(x,\lambda)\in
V(L)\subset{\mathbb{C}}^{n+s}$. Then clearly $x\in V(f)$, and because of our
first assumption and that $s\geq c=n-\dim V(f)$ we have that $s=c$ and $x$ is
non-singular in $V(f)$. By $(x,\lambda)\in V(L)$ we also have that $Jf(x)$
augmented with $\nabla g(x)$ has rank at most $c$, thus $x$ is a critical
point. Conversely, let $x$ be a critical point of $g$ on $V(f)$. Then
$f_{1},\ldots,f_{s}$ vanishes at $x$, and since both $Jf(x)$ and the augmented
matrix $Jf(x)$ by $\nabla g(x)$ has rank $s$, $\nabla g(x)$ is in the row
space of $Jf(x)$, thus there exists $\lambda\in{\mathbb{C}}^{s}$ such that
$(x,\lambda)\in V(L)$.

Next we prove that $V(L)\subset{\mathbb{C}}^{n+s}$ is finite. By assumption,
$g$ has finitely many critical points in $V(f)$, thus the projection of $V(L)$
onto the $x$ coordinates is finite. Since $Jf(x)$ has full row rank for every
$x\in V(f)$, for every critical point $x$ there is a unique
$\lambda\in{\mathbb{C}}^{s}$ such that $(x,\lambda)\in V(L)$. Thus $V(L)$ is
finite.

To prove the second claim, assume that $\,\left(V(f)\setminus
V(g)\right)\cap{\mathbb{R}}^{n}\neq\emptyset$ and let $C$ be a connected
component of the set $(V(f)\setminus V(g))\cap{\mathbb{R}}^{n}$. Since
$V(f)\cap{\mathbb{R}}^{n}$ is bounded, $C$ is bounded as well. Since
$C\not\subset V(g)$, there exists $x\in C$ with $g(x)\neq 0$. Let
$\overline{C}$ be the Euclidean closure of $C$ so that $\overline{C}\subset
V\cap{\mathbb{R}}^{n}$ is closed and bounded, and $g$ vanishes identically on
$\overline{C}\setminus C$. By the extreme value theorem, $g$ attains both a
minimum and a maximum on $\overline{C}$. Since $g$ is not identically zero on
$\overline{C}$, either the minimum or the maximum value of $g$ on
$\overline{C}$ must be nonzero, so $g$ attains a non-zero extreme value on
$C$. By the Lagrange multiplier theorem, using our assumptions, the points in
$C$ where $g$ attains its extreme values are critical points of $g$ in $V(f)$,
which proves the claim. ∎

Now we are ready to prove the main result of the section:

######  Theorem 6.5.

Let $f\in{\mathbb{Q}}[x]^{s},g\in{\mathbb{Q}}[x]$ and
$L\subset{\mathbb{Q}}[x,\lambda]$ as in Lemma 6.4. Let $J$ be the ideal
generated by $L$ in ${\mathbb{Q}}[x,\lambda]$, and
${\mathcal{B}}\subset{\mathbb{Q}}[x,\lambda]$ be any finite monomial basis for
${\mathbb{Q}}[x,\lambda]/J$. Then

$\sigma(H^{\mathcal{B}}_{g})=\sigma(H^{\mathcal{B}}_{g^{2}})\text{ if and only
if }g(x)\geq 0\text{ for all }x\in V(f)\cap{\mathbb{R}}^{n}.$

###### Proof.

First we prove that $g(x)\geq 0$ for all $x\in V(f)\cap{\mathbb{R}}^{n}$ if
and only if $g(x,\lambda)\geq 0$ for all $(x,\lambda)\in
V(L)\cap{\mathbb{R}}^{n+s}$. Assume that $g(x)\geq 0$ for all $x\in
V(f)\cap{\mathbb{R}}^{n}$. Let $(x,\lambda)\in V(L)\cap{\mathbb{R}}^{n+s}$.
Then $x\in V(f)\cap{\mathbb{R}}^{n}$ and since $g\in{\mathbb{Q}}[x]$,
$g(x,\lambda)=g(x)\geq 0$. Conversely, assume $g(x,\lambda)\geq 0$ for all
$(x,\lambda)\in V(L)\cap{\mathbb{R}}^{n+s}$. Suppose there exists $x\in
V(f)\cap{\mathbb{R}}^{n}$ such that $g(x)<0$. Let $C$ be the bounded connected
component of $\,\left(V(f)\setminus V(g)\right)\cap{\mathbb{R}}^{n}$ that
contains $x$ and $\overline{C}$ its Euclidean closure. Let
$x^{*}\in\overline{C}$ where $g$ attains its minimum on $\overline{C}$. Then
$g(x^{*})\leq g(x)<0$, so $x^{*}\in C$ and $x^{*}$ is a critical point of $g$
in $V(f)$. Thus there exists a unique $\lambda\in{\mathbb{R}}^{s}$, the
solution of a linear system, such that $(x^{*},\lambda)\in
V(L)\cap{\mathbb{R}}^{n+s}$. But then $g(x^{*},\lambda)=g(x^{*})\geq 0$, a
contradiction.

By Lemma 6.4 we have $V(L)$ is finite, so ${\mathcal{B}}$ is finite. Since $L$
has real (rational) coefficients, by Hermite’s theorem

$\displaystyle\sigma(H^{\mathcal{B}}_{g})=\\#\\{(x,\lambda)\in
V(L)\cap{\mathbb{R}}^{n+s}\;:\;g(x)>0\\}-\\#\\{(x,\lambda)\in
V(L)\cap{\mathbb{R}}^{n+s}\;:\;g(x)<0\\}$
$\displaystyle\sigma(H^{\mathcal{B}}_{g^{2}})=\\#\\{(x,\lambda)\in
V(L)\cap{\mathbb{R}}^{n+s}\;:\;g(x)>0\\}.$

Thus, $\sigma(H^{\mathcal{B}}_{g})=\sigma(H^{\mathcal{B}}_{g^{2}})$ if and
only if $\\#\\{(x,\lambda)\in V(L)\cap{\mathbb{R}}^{n+s}\;:\;g(x)<0\\}=0$,
i.e. for all $(x,\lambda)\in V(L)\cap{\mathbb{R}}^{n+s}$ we have $g(x)\geq 0$.
This proves the theorem. ∎

######  Corollary 6.6.

Let $f\in{\mathbb{Q}}[x]^{s},g\in{\mathbb{Q}}[x]$ and
$L\subset{\mathbb{Q}}[x,\lambda]$ as in Lemma 6.4 and
${\mathcal{B}}\subset{\mathbb{Q}}[x,\lambda]$ as in Theorem 6.5. Then
$H^{\mathcal{B}}_{g}$ and $H^{\mathcal{B}}_{g^{2}}$ have rational entries, and
can be computed and certified from approximate roots for the system $L$.
Moreover, $\sigma(H^{\mathcal{B}}_{g})=\sigma(H^{\mathcal{B}}_{g^{2}})$ can be
also certified exactly over the rationals, giving a rational certificate for
$g(x)\geq 0$ for all $x\in V(f)\cap{\mathbb{R}}^{n}$.

###### Proof.

Since $L$ and $g$ has rational coefficients, the matrices
$H^{\mathcal{B}}_{g}$ and $H^{\mathcal{B}}_{g^{2}}$ have rational entries. One
can find their signature by computing their LU-decomposition for example,
again resulting in rational matrices. These give a rational certificate for
$\sigma(H^{\mathcal{B}}_{g})=\sigma(H^{\mathcal{B}}_{g^{2}})$ and by the
previous theorem for $g(x)\geq 0$ for all $x\in V(f)\cap{\mathbb{R}}^{n}$. ∎

######  Remark 6.7.

The size $k$ of the matrices $H^{\mathcal{B}}_{g}$ and
$H^{\mathcal{B}}_{g^{2}}$ is equal to the number of critical points of $g$ in
$V(f)$. A brute estimate is given by $|V(L)|\leq d^{n+s}$ with
$d=\max\\{\deg(g),\deg(f_{1}),\ldots,\deg(f_{s})\\}$, using the Bezout bound
for the polynomial system $L$.

The following proposition is needed in the algorithm below.

######  Proposition 6.8.

Let
$\\{z_{1},\ldots,z_{k}\\},\\{\xi_{1},\ldots,\xi_{k}\\}\subset{\mathbb{C}}^{n}$
be such that for some $E,M>0$

$\|\xi_{i}-z_{i}\|_{2}<E\text{ and }\|z_{i}\|_{2}\leq M-E\quad i=1,\ldots,k.$

Let
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}\subset{\mathbb{Q}}[x_{1},\ldots,x_{n}]$
be a set of monomials such that $\deg(x^{\alpha_{i}})\leq d$ for some $d>0$.
Then the Frobenious distance of the Vandermonde matrices is bounded by

$\|V_{\mathcal{B}}(\xi_{1},\ldots,\xi_{k})-V_{\mathcal{B}}(z_{1},\ldots,z_{k})\|_{F}\leq
kndM^{d-1}E.$

###### Proof.

As in the proof of Proposition 3.2 we can see that for
$\alpha\in{\mathbb{N}}^{n}$, $|\alpha|\leq d$ we have

$\left|\xi_{i}^{\alpha}-z_{i}^{\alpha}\right|\leq ndM^{d-1}E.$

Taking the Frobenius norm of the difference of the Vandermonde matrices gives

$\|V_{\mathcal{B}}(\xi_{1},\ldots,\xi_{k})-V_{\mathcal{B}}(z_{1},\ldots,z_{k})\|_{F}\leq\sqrt{k^{2}(ndM^{d-1}E)^{2}}=kndM^{d-1}E.$

∎

######  Algorithm 6.9.

(Certification that $g$ is non-negative over $V(f)\cap{\mathbb{R}}^{n}$)

Input:

$n\in{\mathbb{N}}$, $f\in{\mathbb{Q}}[x]^{s},g\in{\mathbb{Q}}[x]$ for
$x=(x_{1},\ldots,x_{n})$ satisfying Assumption 6.3.

Output:

True: $g(z)\geq 0$ for all $z\in V(f)\cap{\mathbb{R}}^{n}$
False: $g(z)$ is not $\geq 0$ for all $z\in V(f)\cap{\mathbb{R}}^{n}$
or Fail

1:

Construct $L(x,\lambda)$ as defined in Lemma 6.4.

2:

Compute
$\\{(z_{1},\mu_{1})\ldots,(z_{k},\mu_{k})\\}\subset{\mathbb{C}}^{n+s}$,
finitely many approximate roots of the real polynomial system $L(x,\lambda)$
as defined in Lemma 6.4, together with their precision $E$ and a bound $M$
such that $\|z_{i}\|\leq M-E$ for $i=1,\ldots,k$. Return Fail if
$L(x,\lambda)$ has infinitely many roots or $z_{i}=z_{j}$ for some $1\leq
i<j\leq k$.

3:

Compute ${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ connected
to 1, such that the Vandermonde matrix $V_{\mathcal{B}}(z_{1},\ldots,z_{k})$
has smallest singular value is greater than $kndM^{d-1}E$, where $d$ is the
maximal degree of the monomials in ${\mathcal{B}}$ (see Proposition 6.8). Let
${\mathcal{B}}^{+}:=\bigcup_{i}x_{i}{\mathcal{B}}\cup\bigcup_{j}\lambda_{j}{\mathcal{B}}$.

4:

$H_{1}^{+}\leftarrow\text{\sc Hermite Matrix
Computation}\left({\mathcal{B}},{\mathcal{B}}^{+},E,M,\\{(z_{1},\mu_{1}),\ldots,(z_{k},\mu_{k})\\}\right)$
(see Algorithm 3.1)

5:

For $J:=\langle L(x,\lambda)\rangle$ compute $H_{g}(J)$ and $H_{g^{2}}(J)$ by
calling Hermite Matrix Certification with input
$L(x,\lambda),g,{\mathcal{B}},{\mathcal{B}}^{+},H_{1}^{+}$ and
$L(x,\lambda),g^{2},{\mathcal{B}},{\mathcal{B}}^{+},H_{1}^{+}$ respectively,
which algorithm can also return Fail (see Algorithm 4.1)

6:

Calculate the signatures $\sigma(H_{g}(J)$ and $\sigma(H_{g^{2}}(J))$ (see
Remark 2.8)

7:

if $\sigma(H_{g}(J))$=$\sigma(H_{g^{2}}(J))$, then return True
else return False

##  7 Application: Real Root Certification with Hermite Matrices

Let ${f}=(f_{1},\ldots,f_{m})$ $\in{\mathbb{Q}}[x_{1},\dots,x_{n}]^{m}$ such
that ${\mathcal{I}}=\langle f_{1},\ldots,f_{m}\rangle$ is a zero dimensional
radical ideal. The certification problem is the following: We are given
$z^{*}\in{\mathbb{Q}}^{n}$ and $\varepsilon\in{\mathbb{Q}}_{+}$ , we would
like to know if there is any exact root of ${f}$ within the $\varepsilon$ ball
of $z^{*}$ in ${\mathbb{R}}^{n}$. In this section, we present how one can use
the signature of Hermite matrices to answer this certification problem as an
application of Hermite matrices.

Now we introduce the certification theorem as a corollary of the Multivariate
Hermite Theorem 2.7.

######  Corollary 7.1.

Let ${f}=(f_{1},\ldots,f_{m})$, $f_{i}\in{\mathbb{Q}}[x_{1},\dots,x_{n}]$ for
all $i=1,\dots m$, and ${\mathcal{I}}=\langle f_{1},\ldots,f_{m}\rangle$ is a
zero dimensional radical ideal. Given $z^{*}\in{\mathbb{Q}}^{n}$ and
$\varepsilon\in{\mathbb{Q}}_{+}$, define
$g(x):=\|x-z^{*}\|_{2}^{2}-\varepsilon^{2}\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$.
Then

$\sigma(H_{1}({\mathcal{I}}))=\sigma(H_{g}({\mathcal{I}}))$

if and only if there is no real root within the closed ball in
${\mathbb{R}}^{n}$ of radius $\varepsilon$ around $z^{*}$.

###### Proof.

By Theorem 2.7, $\sigma(H_{g}({\mathcal{I}}))=\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)>0\\}-\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)<0\\}$. Since 1 is greater than 0, the
signature of $H_{1}({\mathcal{I}})$ gives the number of all real roots of
${\mathcal{I}}$. Thus, it can be written as

$\sigma(H_{1}({\mathcal{I}}))=\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)>0\\}+\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)<0\\}+\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)=0\\}$ (9)

for any $g(x)\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$. Now, let
$g(x)=\|x-z^{*}\|_{2}^{2}-\varepsilon^{2}\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$.
Assume that $\sigma(H_{1}({\mathcal{I}}))=\sigma(H_{g}({\mathcal{I}}))$. Using
the definitions above and cancelling the terms $\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)>0\\}$ from both sides, we yield
$2\\#\\{x\in V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)<0\\}=-\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)=0\\}.$ The only solution to this
equation is

$\\#\\{x\in V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)<0\\}=0\text{ and
}\\#\\{x\in V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)=0\\}=0,$

since these terms are nonnegative integers by definition. This implies that
there is no real solution to ${\mathcal{I}}$, when $g(x)<0$ and $g(x)=0$. By
the definition of $g(x)=\|x-z^{*}\|_{2}^{2}-\varepsilon^{2}$, there is no
$x\in{\mathbb{R}}^{n}$ such that $\|x-z^{*}\|^{2}_{2}\leq\varepsilon^{2}$.
Thus we conclude that there is no real root within the closed ball of radius
$\varepsilon$.
Assume that there is no real root to ${\mathcal{I}}$ within the closed ball in
${\mathbb{R}}^{n}$ of radius $\varepsilon$ around $z^{*}$. It implies that any
$x\in V_{\mathbb{R}}({\mathcal{I}})$ satisfies the inequality
$\|x-z^{*}\|_{2}^{2}>\varepsilon^{2}$. Then
$g(x)=\|x-z^{*}\|_{2}^{2}-\varepsilon^{2}$ is always positive, and $\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)\leq 0\\}=0$. By Theorem 2.7 and (9),
we have

$\sigma(H_{1}({\mathcal{I}}))=\sigma(H_{g}({\mathcal{I}}))=\\#\\{x\in
V_{\mathbb{R}}({\mathcal{I}})~{}|~{}g(x)>0\\}.$

∎

######  Algorithm 7.2 (Real Root Certification).

Input:

${f}=(f_{1},\ldots,f_{m})\in{\mathbb{Q}}[x_{1},\dots,x_{n}]^{m}$;
$z^{*}\in{\mathbb{Q}}[i]^{n}$; $\varepsilon^{2}\in{\mathbb{Q}}_{+}$;
${\mathcal{B}}=\\{x^{\alpha_{1}},\ldots,x^{\alpha_{k}}\\}$ connected to 1 with
$|{\mathcal{B}}^{+}|=l$ for some $k,l\in{\mathbb{N}}$
$E,M\in{\mathbb{R}}_{+}$ and $z_{1},\ldots,z_{k}\in{\mathbb{C}}^{n}$ such that
$\|z_{i}\|_{\infty}\leq M-E$ for $i=1,\ldots,k$ and the accuracy of $z_{i}$ is
at least $E$.

Output:

True: $\exists z\in V_{\mathbb{R}}({\mathcal{I}})$ such that $z$ is in the
closed ball of radius $\varepsilon$ around $z^{*}$
False: No real root of ${\mathcal{I}}$ within the closed ball of radius
$\varepsilon$ around $z^{*}$
or Fail.

1:

Define
$g(x):=\|x-z^{*}\|_{2}^{2}-\varepsilon^{2}\in{\mathbb{Q}}[x_{1},\ldots,x_{n}]$

2:

$H_{1}^{+}:=H_{1}^{{\mathcal{B}}^{+}}(z_{1},\ldots,z_{k})\leftarrow\text{\sc
Hermite Matrix
Computation}\left({\mathcal{B}},{\mathcal{B}}^{+},E,M,\\{z_{1},\ldots,z_{k}\\}\right)$
(see Algorithm 3.1)

3:

For $I:=\langle f_{1},\ldots,f_{m}\rangle$ call $\text{\sc Hermite Matrix
Certification}(f,g(x),B,H_{1}^{+})$ to obtain certified $H_{1}(I)$ and
$H_{g}(I)$, that algorithm can also return Fail (see Algorithm 4.1)

4:

Compute $\sigma(H_{1}({\mathcal{I}}))$ and $\sigma(H_{g}({\mathcal{I}}))$. See
Remark 2.8 for computational details.

5:

If $\sigma(H_{1}({\mathcal{I}}))=\sigma(H_{g}({\mathcal{I}}))$ then return
False
else return True.

## References

  * [1] Apostol, T. M. : Calculus, volume II: multi-variable calculus and linear algebra, with applications to differential equations and probability. John Wiley & Sons (1969)
  * [2] Ayyildiz Akoglu, T., and Szanto, A. : Certified Hermite Matrices from Approximate Roots-Univariate Case. MACIS 2019, Lecture Notes in Computer Science book series, vol. 11989, pp. 3–9 (2020).
  * [3] Ayyildiz Akoglu, T., Hauenstein, J.D., Szanto, A. : Certifying solutions to overdetermined and singular polynomial systems over ${\mathbb{Q}}$. Journal of Symbolic Computation, 84, 147–171 (2018)
  * [4] Ayyildiz Akoglu, T. : Certifying solutions to polynomial systems over ${\mathbb{Q}}$. PhD thesis, North Carolina State University (2016)
  * [5] Bardet, M., Faugère, JC. and Salvy, B. :  On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations.  In Proceedings of the International Conference on Polynomial System Solving, ICPSS’04, pages 71–75, 2004.
  * [6] Bardet, M., Faugère, JC., Salvy, B. and Yang, BY. :  Asymptotic Behavior of the Degree of Regularity of Semi-Regular Polynomial Systems.  in MEGA 2005 , Eighth International Symposium on Effective Methods in Algebraic Geometry, 15 p., 2005.
  * [7] Basu, S., Pollack, R., Roy, M.-F. : Algorithms in real algebraic geometry. Springer-Verlag, Berlin Heidelberg (2006)
  * [8] Bates, D.J., Decker, W., Hauenstein, J.D., Peterson, C., Pfister, G., Schreyer, F.O., Sommese, A.J. and Wampler, C.W., : Comparison of probabilistic algorithms for analyzing the components of an affine algebraic variety. Applied Mathematics and Computation, 231, pp.619-633.(2014)
  * [9] Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. With a foreword by Richard M. Karp. Springer-Verlag, New York, (1998).
  * [10] Cifuentes, D. and Parrilo, P. Sampling algebraic varieties for sum of squares programs. SIAM J. Optimization. 27(4):2381-2404. (2017).
  * [11] Cox, D. A., Little, J., O’shea, D. : Using algebraic geometry (Vol. 185). Springer Science & Business Media (2006)
  * [12] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W., : Numerically solving polynomial systems with Bertini (Vol. 25). SIAM, (2013)
  * [13] Hauenstein, J.D., Sottile F..  Algorithm 921: alphaCertified: certifying solutions to polynomial systems.  ACM Trans. Math. Software, 38(4):28, 2012.
  * [14] Hermite, C. : Sur le nombre des racines d’une équation algébrique comprise entre des limites données, J. Reine Angew. Math. 52 (1850), 39-51; also in Oeuvres completes, Vol. 1, pp. 397-414.
  * [15] Hermite, C. : Remarques sur le théorème de Sturm. CR Acad. Sci. Paris, 36(52-54), 171 (1853)
  * [16] Hermite, C. : Extrait d’une lettre de Mr. Ch. Hermite de Paris à Mr. Borchardt de Berlin sur le nombre des racines d’une équation algébrique comprises entre des limites données. Journal für die reine und angewandte Mathematik 52 39–51 (1856)
  * [17] Janovitz-Freireich, I., Rónyai, L., Szántó, A. : Approximate Radical for Clusters: A Global Approach Using Gaussian Elimination or SVD, Math.comput.sci. (2007) 1: 393.
  * [18] Macdonald, I. G. : Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. Oxford: The Clarendon Press, Oxford University Press. 1979.
  * [19] Mourrain, B. : A new criterion for normal form algorithms. In M. Fossorier, H. Imai, Shu Lin, and A. Poli, editors, Proc. AAECC, volume 1719 of LNCS, pp. 430–443. Springer, Berlin, 1999.
  * [20] Pedersen, P., Roy, M. F., Szpirglas, A. : Counting real zeros in the multivariate case. In Computational algebraic geometry (pp. 203-224). Birkhäuser, Boston, MA (1993)
  * [21] Rosen, K. H. : Elementary number theory and its applications. 6th Edition. Reading, Massatchusets (1993)
  * [22] Schrijver, A. : Theory of linear and integer programming. JohnWiley & Sons, New York (1998)
  * [23] Stickelberger, L. : Ueber eine Verallgemeinerung der Kreistheilung. Math. Ann., 37, pp. 312– 367 (1890)