# Truncated Normal Forms for Solving Algebraic Equations

Bernard Mourrain

► To cite this version:

Bernard Mourrain. Truncated Normal Forms for Solving Algebraic Equations. 2025. hal-05135952

HAL Id: hal-05135952

https://hal.science/hal-05135952v1

Preprint submitted on 8 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Truncated Normal Forms for Solving Algebraic Equations

Bernard Mourrain

Inria at Université Côte d'Azur

**Abstract.** We present an overview of algebraic methods for computing the solutions of a zero-dimension ideal *I*. We analyse algebraic solvers, such as Grobner basis solvers, border basis solvers, resultant-based solvers, moment matrix solvers, through the lens of Truncated Normal Forms (TNF). We provide new characterizations of TNF in terms of commuting matrices and stable Atiyah-Drinfel'd-Hitchin-Mani datum. These new characterisations apply for any finitely generated commutative $K$-algebra $R$. We detail how TNF appear naturally in the different algebraic solvers, providing a common foundation for the different approaches. We analyze the scheme defined by the commutation equations and parametric normal form equations and show that it is the simple point associated to the TNF.

## 1 Introduction

Solving polynomial equations is ubiquitous in many domains, e.g. in robotics, chemistry, signal processing, polynomial optimization, ... (see e.g. [SW05,EM07], [Cox20,Las09,Dum17]). In such applications, the modelisation of a problem can lead to a system of non-linear equations, which solution set yields the necessary information to tackle effectively and practically the problem. In this paper, we are interest in polynomial equations defining a *finite* set of solutions and in methods which allow to recover *all* these solutions. There exists a large variety of non-linear equations solvers.

Local or iterative methods, such as Newton-Raphson method [Ded15], start from an initial point and usually converge to a fixed point. Such methods are very efficient in practice to find a solution, but suffer from certain pitfalls. The convergence is not guaranteed and depends highly on the initialization. The fixed point is not necessarily a solution of the system. It is very difficult to find all the solutions of a system, unless one knows sufficiently good approximations of all these solutions.

Homotopy solvers [SW05] exploit local methods in a more controlled way. They are deforming a system with known solutions into the system to be solved, tracking the paths of the solutions by iterative methods. They rely on the evaluation of the (polynomial) functions and their derivatives. They are efficient event for high dimensional problems, can be parallelized, but can suffer from the proximity of singularities.
Algebraic solvers, based on algebraic computation on the polynomial equa-
tions, exploit the properties of the quotient algebra $\mathcal{A} = R/I$ by the ideal $I$
generated by these equations. They allow to compute all the roots of a zero-
dimensional system and even analyse their multiplicities. They can be tuned to
specific classes of polynomial systems. We will focus on this family of methods,
which includes Grobner basis solvers, border basis solvers, resultant solvers and
moment matrix solvers.

Gröbner basis solvers are used with exact coefficients (e.g., coefficients in a
finite field or in $\mathbb{Q}$). They provide general engines to analyse properties of ideals
and algebraic varieties [CLO92]. Their computations have been optimized over
several decades [EF17] to reach a high level of performance. But they are not
well adapted to polynomial equations with approximate coefficients.

Border basis have been developed to tackle the numerical instability issue of
Gröbner bases [Mou99]. They generalize the concept of polynomial reductions,
beyond the scope of monomial ordering. They are adapted to zero-dimensional
ideals, computing the reduction of all monomials of the border $\partial b$ of a monomial
basis $b$ of the quotient $\mathcal{A} = R/I$.

Resultant solvers are devised to solve a class of polynomial systems (e.g. generic polynomials with a given support) [EM99,Cox20]. They construct specific elements in the ideal $I$ generated by the equations and produce matrices, which can be exploited to recover the solutions by eigencomputation. Their efficiency decreases significantly with the increase of the number of variables and the degree of the equations. However they produce robust solvers for polynomial equations with approximate coefficients.

Moment matrix solvers are used in domains such as polynomial optimization
[Las09] or tensor decomposition [IK99]. No equation is given, but instead the
pseudo-moments of a linear functional (usually up to some degree) are used
to recover the minimizers in a polynomial optimization problem or the parts
of the tensor decomposition. The moments can be given approximately. The
bottlenecks of these methods are the number of variables, the degree and the
number of terms in the decomposition compared to the number of given pseudo-
moments.

We present an unified overview of these techniques, through the lens of Trun-
cated Normal Forms (TNF). Truncated Normal Forms can be seen as restrictions
of linear functionals vanishing on the ideal I generated by the polynomial equa-
tions. We provide new characterizations of TNF (in Section 2) formalising the
characterisation of [Mou99] in terms of commuting matrices and stable Atiyah-
Drinfel'd-Hitchin-Mani datum [HJ18]. We recall in particular, the characteri-
sation of TNF used in [TMB18,MTVB21]. These new characterisations apply
for any finitely generated commutative $\mathbb{K}$-algebra $R$, extending the scope of the
approach beyond the classical case of polynomial rings.

We illustrate (in Section 3) how TNF appear naturally in the different alge-
braic solvers, providing a common foundation for the different approaches.

Next (in Section 4), we introduce parameters for the coefficients of the TNF
and analyse properties of the algebraic variety of TNF. We provide a new re-
sult (see Theorem 4.5), showing that the algebraic variety, defined by the com-
mutation relations and the orthogonality to generators of the zero-dimensional
ideal *I*, is a simple point corresponding to the TNF of *I*. This result general-
izes [HMS16, Theorem 4.8] to non-necessarily local Artinian algebras. It can be
used for the deflation of multiple points (see [HMS16] for a single isolated sin-
gular point) and for certified iterative numerical methods for computing TNF
(see [MMS22, MMS20] for local Artinian algebras and inverse systems of isolated
singular points).

The different concepts and algorithms presented hereafter are accompanied
with illustrative examples and computations performed with the packgage
AlgebraicSolvers.jl<fnref n="1" />.

1.1 Notation

Let $R$ be a finitely generated commutative $\mathbb{K}$-algebra, with generators $x_1, \dots, x_n$.
For instance, $R$ can be the ring $\mathbb{K}[x_1, \dots, x_n] = \mathbb{K}[\mathbf{x}]$ of polynomials in the
variables $\mathbf{x} = \{x_1, \dots, x_n\}$ with coefficients in the field $\mathbb{K}$.

Hereafter, we will also consider the ring $\mathbb{K}[x_1^{\pm 1}, \dots, x_n^{\pm 1}] = \mathbb{K}[\mathbf{x}^{\pm 1}]$ of La-
rent polynomials, isomorphic to the quotient $\mathbb{K}[x_1, \dots, x_n, y_1, \dots, y_n]/(x_1 y_1 -
1, \dots, x_n y_n - 1)$ of polynomials in the variables $x_1, \dots, x_n, y_1, \dots, y_n$ modulo the
relations $x_i y_i - 1 \equiv 0$ for $i = 1, \dots, n$.

If $x_1, \dots, x_n$ are generators of $R$, an element $p \in R$ can be represented as a
finite sum of terms $p = \sum_{\alpha \in S} p_\alpha \mathbf{x}^\alpha$ where $\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^n$, $S \subset \mathbb{N}^n$ is
finite, $\mathbf{x}^\alpha = x_1^{\alpha_1} \cdots x_n^{\alpha_n}$, and $p_\alpha \in \mathbb{K}$ with $p_\alpha \neq 0$ if $\alpha \in S$. $S$ is called the *support*
of $p$.

We say that **α** ⊂ **N**<sup>n</sup> is **stably connected** if **0** ∈ **α** and for any **α** ∈ **α** with
**α** ≠ **0**, there exists **e**<sub>i**α**</sub> = [0, ..., 0, 1, 0, ..., 0] and **α'** ∈ **α** such that **α** = **α'** + **e**<sub>i**α**</sub>.
We also say that a set of monomials **b** = {**x**<sup>**α**</sup>, **α** ∈ **α**} is **stably connected** if the
set of exponents **α** ⊂ **N**<sup>n</sup> is **stably connected**.

For a subset **b** of (monomials of) R, **b**<sup>+</sup> = **b** ∪ x<sub>1</sub>**b** ∪ ... ∪ x<sub>n</sub>**b**, where
x<sub>1</sub>, ..., x<sub>n</sub> are generators of the K-algebra R. If B is a vector space B ⊂ R, we
denote B<sup>+</sup> = ⟨B, x<sub>1</sub>B, ..., x<sub>n</sub>B⟩.

The dual space is $R^* = \hom_{\mathbb{K}}(R, \mathbb{K})$. The (pseudo-)moment $\Lambda_\alpha$ of a linear
functional $\Lambda \in R^*$ is the value of the linear functional $\Lambda$ on the monomial $\mathbf{x}^\alpha$.

The dual space $R^*$ of the ring $R$ is also equipped with a co-product defined
as follows: $\forall p \in R, \forall \Lambda \in R^*, p \star \Lambda : q \in R \mapsto \Lambda(pq) \in \mathbb{K}$.

For an ideal $I \subset R$, we define $I^{\perp} = \{ \Lambda \in R^* | \forall p \in I, (\Lambda, p) = 0 \}$, that we identify with the dual $\mathcal{A}^*$ of $\mathcal{A} = R/I$. We verify that $\forall p \in R, \forall \Lambda \in I^{\perp} \ni p \star \Lambda \in I^{\perp}$. Given $\Lambda \in R^*$, we define the inverse system spanned by $\Lambda$ as $\langle\langle\Lambda\rangle\rangle = \{p \star \Lambda | p \in R\}$. We can notice that $\langle\langle\Lambda\rangle\rangle^{\perp} = \{p \in R | \forall \Lambda' \in \langle\langle\Lambda\rangle\rangle, (\Lambda', p) = 0\}$ is an ideal of $R$.

The algebraic closure of $\mathbb{K}$ is denoted $\bar{\mathbb{K}}$.

<footnote n="1">¹ https://github.com/AlgebraicGeometricModeling/AlgebraicSolvers.jl</footnote>
## 1.2 Structure of an Artinian algebra

An Artinian algebra $\mathcal{A}$ is a commutative $\mathbb{K}$-algebra of finite dimension as a $\mathbb{K}$-vector space. As it is finite dimensional, $\mathcal{A}$ is also a finitely generated algebra. Suppose that the Artinian algebra $\mathcal{A}$ is generated by $a_1, \dots, a_n$ as an algebra. Then we have the exact sequence:

$$0 \longrightarrow I \longrightarrow \mathbb{K}[x_1, \dots, x_n] \longrightarrow \mathcal{A} \longrightarrow 0$$
$$x_i \longmapsto a_i$$

where $I$ is a zero-dimensional ideal in $\mathbb{K}[\mathbf{x}]$ such that $\mathcal{A} = \mathbb{K}[\mathbf{x}]/I$ is of finite dimension. Conversely a zero-dimensional ideal $I \subset \mathbb{K}[\mathbf{x}]$ defines the Artinian algebra $\mathcal{A} = R/I$. The algebraic set $V_{\mathbb{K}}(I) = \{\xi \in \mathbb{K}^n | \forall p \in I, p(\xi) = 0\}$ is finite iff $I$ is zero dimensional, iff $\mathbb{K}[\mathbf{x}]/I$ is Artinian. Let $r = \dim \mathcal{A}$ and $V_{\mathbb{K}}(I) = \{\xi_1, \dots, \xi_{r'}\} \subset \mathbb{K}^n$ with $r' \le r$.

Given $p \in R$ (or $p \in \mathcal{A}$), we define the operator $M_p$ of multiplication by $p$ and its transposed $M_p^*$ as

$$M_p : \mathcal{A} \longrightarrow \mathcal{A} \qquad M_p^* : \mathcal{A}^* \longrightarrow \mathcal{A}^*$$
$$a \longmapsto pa \qquad \mathcal{A} \longmapsto p \star \mathcal{A}$$

identifying $p \in R$ with its class in $\mathcal{A} = R/I$ and $\mathcal{A}^*$ with $I^{\perp} \subset R^*$.

We use the following classical theorem for solving polynomial systems:

**Theorem 1.1 ([AS88,Mou98,EM07]).** For any $p \in R = \mathbb{K}[\mathbf{x}]$, the eigenvalues of $M_p$ repeated with multiplicity, are $\{\underbrace{p(\xi_1), \dots, p(\xi_1)}_{\mu_1}, \dots, \underbrace{p(\xi_{r'}, \dots, p(\xi_{r'})}_{\mu_{r'}}\}$, where $\mu_i$ is the multiplicity of the root $\xi_i$.

The common eigenvectors of all $(M_p^*)_{p \in R}$ are, up to a scalar, the evaluation linear functionals $e_{\xi_i} : q \in \mathbb{K}[\mathbf{x}] \mapsto q(\xi_i)$.

This allows us to recover the roots $\Xi = \{\xi_1, \dots, \xi_{r'}\}$ by eigencomputation, using the operators of multiplication $M_{x_i}$ for $i = 1, \dots, n$. In particular, when the roots are simple, we have the following:

**Proposition 1.2 (see e.g. [EM07]).** If the roots $\{\xi_1, \dots, \xi_r\} = V_{\mathbb{K}}(I)$ are simple (i.e. $\mu_i = 1$ and $r = r'$),

- The operators $M_{x_i}$ for $i = 1, \dots, n$ have a joint diagonalization.

- Their common eigenvectors are, up to a scalar, the interpolation polynomials $\mathbf{u}_i$ at the roots. They form a basis of orthogonal idempotents of $\mathcal{A}$ (i.e. $\mathbf{u}_i^2 = \mathbf{u}_i$, $\mathbf{u}_i\mathbf{u}_j \equiv 0$ if $i \ne j$, $\sum_{i=1}^r \mathbf{u}_i \equiv 1$).

- The common eigenvectors of the transposed of the matrices of $(M_{x_i})_{i=1, \dots, n}$ in a basis $B$ of $\mathcal{A}$ are, up to a scalar, the vectors $B(\xi_j)$ representing the evaluation linear functionals $e_{\xi_1}, \dots, e_{\xi_r}$ in the basis of of $\mathcal{A}^* = I^{\perp}$ dual to $B$.
We illustrate these results on the computation of roots by eigencomputation in the following example.

*Example 1.3.* In $R = \mathbb{K}[x_1, x_2]$, we consider the ideal $I$ generated by $f_1 = x_1^2 - 3x_1+2$, $f_2 = x_1x_2 - x_2 + x_1 - 1$, $f_3 = x_2^2 - 3x_2 - 6x_1 + 8$. We check, using properties of normal forms that we will detail in Example 3.8, that $B = \{1, x_1, x_2\}$ is a basis of $\mathcal{A} = \mathbb{K}[\mathbf{x}]/I$ where $I = (f_1, f_2, f_3)$.

Using the relations $f_1, f_2, f_3$, we compute the matrices of multiplication by $x_1, x_2$ in the basis $B$:

$$M_1 = \begin{array}{c|c} \begin{array}{cccc} x_1 & x_1^2 & x_1x_2 & \end{array} & \begin{array}{c} 1 \\ x_1 \\ x_2 \end{array} \begin{bmatrix} 0 & -2 & 1 \\ 1 & 3 & -1 \\ 0 & 0 & 1 \end{bmatrix} \end{array}, M_2 = \begin{array}{c|c} \begin{array}{cccc} x_2 & x_1x_2 & x_2^2 & \end{array} & \begin{array}{c} 1 \\ x_1 \\ x_2 \end{array} \begin{bmatrix} 0 & 1 & -8 \\ 0 & -1 & 6 \\ 1 & 1 & 3 \end{bmatrix} \end{array}$$

Common eigenvectors of the matrices of $M_1^t, M_2^t$ expressed in the basis of $\mathcal{A}^*$ dual to $B$ are the columns of

$$E = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 2 & -1 \end{bmatrix}.$$

They represent the linear functionals $\mathbf{e}_{(1,1)}, \mathbf{e}_{(1,2)}, \mathbf{e}_{(2,-1)}$ in the basis of $\mathcal{A}^*$ dual to $B$, as it can be read from the last two rows of $E$.

Common eigenvectors of the operators $M_1, M_2$ are represented in the basis $B$ by the columns of

$$U = E^{-t} = \begin{bmatrix} 5 & -3 & -1 \\ -3 & 2 & 1 \\ -1 & 1 & 0 \end{bmatrix}$$

defining the interpolation polynomials

$$\mathbf{u}_1 = 5 - 3x_1 - x_2, \mathbf{u}_2 = -3 + 2x_1 + x_2, \mathbf{u}_3 = -1 + x_1$$

at the solutions

$$\Xi = \{(1, 1), (1, 2), (2, -1)\}.$$

This illustrates how the roots of $I$ can be computed by a joint diagonalization of the operators of multiplication $M_1, M_2$ (or their transposed).

## 2 Representations of a quotient algebra

In this section, we study the representations of a quotient algebra $\mathcal{A} = R/I$ associated to an ideal $I \subset R$.
## 2.1 Normal Form

Describing the structure of a quotient algebra $\mathcal{A}$ can be done via a Normal Form, which associates to any polynomial $p \in \mathbb{R}$ a unique representative of its class $[p] \in \mathcal{A}$ in a vector space $V$. We define it more formally as follows:

**Definition 2.1 (Normal Form).** Given an ideal $I \subset \mathbb{R}$ and a $\mathbb{K}$-vector space $V$. A Normal Form for $I$ from $\mathbb{R}$ to $V$ is a $\mathbb{K}$-linear map $\mathbf{N} : \mathbb{R} \to V$ such that the sequence $0 \to I \to \mathbb{N} \to V \to 0$ is exact.

From this definition, it follows that for any space $B \subset \mathbb{R}$ such that $\overline{\mathbf{N}}|_B : B \to V$ is an isomorphism, we have $B \simeq R/I$.

**Lemma 2.2.** Let $B \subset \mathbb{R}$ such that $\mathbf{N}|_B : B \to V$ is an isomorphism. Let $\mathbf{N}^* = (\mathbf{N}|_B)^{-1} \circ \mathbf{N} : \mathbb{R} \to B$. Then we have $\mathbf{N}^* \circ \mathbf{N}^* = \mathbf{N}^*$ and $\ker \mathbf{N}^* = I$, i.e. $\mathbf{N}^*$ is a projector on $B$ along $I$.

*Proof.* By definition of $\mathbf{N}^*$, $\mathbf{N}^* : \mathbb{R} \to B$ is such that $\mathbf{N}^*|_B = \mathrm{Id}$ and $\ker \mathbf{N}^* = \ker \mathbf{N} = I$. This implies that $\mathbf{N}^* \circ \mathbf{N}^* = \mathbf{N}^*$, and $\mathbf{N}^*$ is a projector on $B$ along $I$.

The map $\mathbf{N}^* : \mathbb{R} \to B$ is a Normal Form, equivalent to $\mathbf{N}$. In the literature, it is also called an ideal projector (see e.g. [DB04]).

Choosing a basis $\mathbf{v} = (v_j)_{j \in J}$ of $V$, we denote by $\nu_j$ the $j$th coordinate function of $\mathbf{N}$ in the basis $\mathbf{v}$ ($\forall p \in \mathbb{R}, N(p) = \sum_{j \in J} \nu_j(p)v_j$). By construction, $\nu_j : \mathbb{R} \to \mathbb{K}$ is a linear functional $\in \mathbb{R}^*$ vanishing on $I$.

**Proposition 2.3.** Let $I^{\perp} = \{ \Lambda \in \mathbb{R}^* | \forall p \in I, \Lambda(p) = 0 \}$ and let $\mathbf{b} = (\mathbf{N}|_B)^{-1}(\mathbf{v}) = (b_j)_{j \in J}$. Then $(\nu_j)_{j \in J}$ is a basis of $I^{\perp}$, which is dual to $\mathbf{b}$.

*Proof.* By definition, we have $\nu(b_j) = v_j$ for $j \in I$. Thus for $i \in I$, $\nu_i(b_j) = \delta_{i,j}$ where $\delta_{i,j}$ is the Kronecker symbol ($\delta_{i,j} = 1$ if $i = j$ and $\delta_{i,j} = 0$ otherwise). This implies that $(\nu_i)_{i \in J}$ are linearly independent. Since $\mathbf{N}$ is a NF for $I$, $\mathbf{N}(I) = \{0\}$ and $\nu_j \in I^{\perp}$. For $\Lambda \in I^{\perp}$ and $p \in \mathbb{R}$, we have

$$ \Lambda(p) = \Lambda(\mathbf{N}^*(p)) = \Lambda\left(\sum_{j \in J} (\mathbf{N}|_B)^{-1}(v_j)\nu_j(p)\right) = \sum_{j \in J} \Lambda(b_j)\nu_j(p) $$

so that $\Lambda = \sum_{j \in J} \Lambda(b_j)\nu_j$. This proves that $(\nu_j)_{j \in J}$ is a basis of $I^{\perp}$, dual to $\mathbf{b}$.

*Example 2.4.* Let $n = 2$, $R = \mathbb{K}[x_1, x_2]$, $B = \langle 1, x_1, x_2, x_1x_2 \rangle$ and $N : \mathbb{R} \to B$ such $\mathbf{N}(x_1^{\alpha_1} x_2^{\alpha_2}) = x_1^{\alpha_1 \mod 2} x_2^{\alpha_2 \mod 2}$ for $\alpha = (\alpha_1, \alpha_2) \in \mathbb{N}^2$.

As $\mathbf{N}|_B = \mathrm{Id}$, we have $\mathbf{N} \circ \mathbf{N} = \mathbf{N}$. We deduce that the sequence

$$ 0 \to I \to \mathbb{N} \to B \to 0 $$
is exact with $I := \ker \mathbf{N}$ and that $I \oplus B = R$. We verify that $\mathbf{N}(x_1^2 - 1) = \mathbf{N}(x_2^2 - 1) = 0$ and that $\forall p \in (x_1^2 - 1, x_2^2 - 1)$, $\mathbf{N}(p) = 0$. Thus $(x_1^2 - 1, x_2^2 - 1) \subset I$. Since for any $p \in R$, $p - \mathbf{N}(p) \in (x_1^2 - 1, x_2^2 - 1)$, we deduce that $I = \ker \mathbf{N} = \langle p - \mathbf{N}(p), p \in R \rangle = (x_1^2 - 1, x_2^2 - 1)$.

A basis of $I^{\perp}$ dual to $(1, x_1, x_2, x_1x_2)$ represented as formal power series is $(\nu_i(\mathbf{y}))_{0 \le i \le 3}$ where

$$ 
\begin{aligned}
\nu_0(\mathbf{y}) &= \sum_{\alpha \in \mathbb{N}^2} y_1^{2\alpha_1} y_2^{2\alpha_2} = 1 + y_1^2 + y_2^2 + y_1^2 y_2^2 + \dots \\
\nu_1(\mathbf{y}) &= y_1 \nu_0(\mathbf{y}) \\
\nu_2(\mathbf{y}) &= y_2 \nu_0(\mathbf{y}) \\
\nu_3(\mathbf{y}) &= y_1 y_2 \nu_0(\mathbf{y})
\end{aligned}
$$

## 2.2 Truncated Normal Forms

From a computational point of view, it could be interesting to define a Normal Form only partially on a subspace $W$ of $R$. We introduce, hereafter, the corresponding concept of *Truncated Normal Form*:

**Definition 2.5 (Truncated Normal Form).** Let $W \subset R$ and $V$ be a $\mathbb{K}$-vector space. A Truncated Normal Form (TNF) for the ideal $I := (\ker \mathbf{N})$ from $W$ to $V$ is a linear map $\mathbf{N}: W \to V$ such that the sequence

$$ 0 \to K \to W \xrightarrow{\mathbf{N}} V \to 0 $$

is exact, $I \cap W = K$ and $I + W = R$ where $I = (K)$ is the ideal of $R$ generated by $K := \ker \mathbf{N}$.

We verify easily that a NF $\mathbf{N}: R \to V$ for an ideal $I$ is a TNF for $I$ from $W = R$ to $V$ such that $\ker \mathbf{N} = I$, since $I = (I) \cap R$ is an ideal of $R$ and $(I) + R = R$.

**Lemma 2.6.** If $G: V \to V'$ is invertible and $\mathbf{N}: W \to V$ is a TNF for $I = (\ker \mathbf{N})$, then $\mathbf{N}' = G \circ \mathbf{N}: W \to V'$ is a TNF for $I$. In this case, we say that $\mathbf{N}$ and $\mathbf{N}'$ are equivalent TNF.

*Proof.* $\mathbf{N}'$ is a TNF since $G$ is invertible and $\ker \mathbf{N}' = \ker \mathbf{N}$.

**Lemma 2.7.** If $\mathbf{N}: W \to V$ is a Truncated Normal Form, then there exists a unique Normal Form $\overline{\mathbf{N}}: R \to V$ for $(\ker \mathbf{N})$ extending $\mathbf{N}$.

*Proof.* Let $K = \ker \mathbf{N}$ and $B \subset W$ such that $\mathbf{N}_{|B}: B \to V$ is an isomorphism. Then $W = B \oplus K$. Since $(K) \cap W = K$ and $W + (K) = R$, we have $R = B \oplus (K)$. We define $\overline{\mathbf{N}}: R \to V$ as follows:

$$ \overline{\mathbf{N}}(p) = 0 \text{ for } p \in (K) \qquad (1) $$

$$ \overline{\mathbf{N}}(b) = \mathbf{N}(b) \text{ for } b \in B \qquad (2) $$
Since $N|_B : B \to V$ is an isomorphim, we verify that $\ker \bar{N} = (K)$ and $\mathrm{Im}(\bar{N}) = V$. Therefore $\bar{N}$ is a Normal Form for $(K)$. Moreover, $\bar{N}(p) = N(p)$ for $p \in W$ so that $\bar{N}$ extends $N$.

Such an extension is unique, since a NF for $(K)$ extending $N$, must satisfy (1) and (2), and thus coincides with $\bar{N}$.

**Theorem 2.8.** Let $N : W \to V$ be a $K$-linear map such that $W + (K) = R$ where $K = \ker N$ and $I$ an ideal of $R$ such that $K \subset I$ and $\dim R/I = \dim V = r < \infty$. Then $N$ is a TNF for $I$ from $W$ to $V$ and $(K) = I$.

*Proof.* Let $B \subset W$ such that $N|_B : B \to V$ is an isomorphism. Then $W = B \oplus K$. As $W + (K) = B + (K) = R$, there exists a supplementary space $B' \subset B$ to $B \cap (K)$ such that $R = B' \oplus (K)$. Since $K \subset I$, we have $r = \dim(R/I) \le \dim(R/(K)) = \dim(B')$. As $B' \subset B$, $\dim(B') \le \dim(B) = \dim(V) = r$. This implies that $B' = B$ and $I = (K)$. Therefore $(K) \cap W = K$ and $N$ is a TNF from $W$ to $V$.

This is the characterisation of TNF used in [TMB18,MTVB21].

**Definition 2.9 (Operators of multiplication).** For a map $N : W \to V$ such that there exists $B \subset W$ with $B^+ \subset W$, $N|_B : B \to V$ bijective, we define the multiplication operators associated to $N$ as

$$M_k : B \to B \\ b \mapsto (N|_B)^{-1} \circ N(x_k b).$$

They are well defined since $B^+ \subset W$.

Let $S_k : b \in B \mapsto x_k b \in W$ be the shift operator by the variable $x_k$ for $k = 1, \dots, n$. Then $M_k$ decomposes as

$$M_k = (N|_B)^{-1} \circ N \circ S_k$$

**Proposition 2.10.** Let $N : W \to V$ be a TNF such that there exists $B \subset W$ with $B^+ \subset W$ and $N|_B : B \to V$ bijective. Then $M_k$ is the operator of multiplication by $x_k$ in the quotient $R/(\ker N)$.

*Proof.* Let $K = \ker N$. By Lemma 2.7 there exists a unique NF $\bar{N} : R \to V$ for $(K)$ extending $N$. We have $R = B \oplus (K)$ and $R/(K) \simeq B$. Let $N^*$ be the projector on $B$ along $(K)$ as defined in Definition 2.9. The operators of multiplication in $B \simeq R/(K)$ are $b \in B \mapsto N^*(x_k b) = (N|_B)^{-1} \circ \bar{N}(x_k b) = (N|_B)^{-1} \circ N(x_k b) = M_k(b)$ since $x_k b \in B^+ \subset W$ and $\bar{N}|_W = N$.

As a consequence, if $N : W \to V$ is a TNF as in Proposition 2.10, then as $\mathcal{A} = R/(\ker N)$ is commutative and by Theorem 1.1,

- the operators $M_k$ are commuting,

- the eigenvalues of $M_k$ are the $k^{\text{th}}$ coordinates of the roots $\xi \in \mathcal{V}(K)$,

- the common eigenvectors of $M_{x_k}^t$ are, up to a scalar, the evaluations at the roots $\xi \in \mathcal{V}(K)$.
## 2.3 Families of commuting endomorphisms

Let $V$ be a $\mathbb{K}$ vector space of dimension $r > 0$. For $M_1, \dots, M_n \in \text{End}(V)$ and $\mathbf{u} \in V$, we say that $(M_1, \dots, M_n, \mathbf{u})$ is stable if there is no proper subspace $S$ of $V$ such that $M_k(S) \subset S$ for $k = 1, \dots, n$ and $\mathbf{u} \in S$.

**Definition 2.11.** The algebraic variety of Commuting endomorphism is

$$C_{r,n} = \{(M_1, \dots, M_n) \in \text{End}(V)^n \mid M_i \circ M_j - M_j \circ M_i = 0, 1 \le i < j \le n\}.$$

The element $(\mathbf{M}, \mathbf{u}) \in C_{r,n} \times V$ is called an Atiyah-Drinfel'd-Hitchin-Mani (ADHM) datum.

See e.g. [HJ18] for more details. For $M_1, \dots, M_n \in \text{End}(V)$, and $\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^n$, we denote $\mathbf{M}^{\alpha} = M_1^{\alpha_1} \circ \cdots \circ M_n^{\alpha_n}$. More generally, for $p = \sum_{\alpha} p_{\alpha} \mathbf{x}^{\alpha} \in \mathbb{K}[\mathbf{x}]$, $p(\mathbf{M}) = \sum_{\alpha} p_{\alpha} \mathbf{M}^{\alpha}$.

**Lemma 2.12.** Let $\mathbf{M} \in C_{r,n}$ and $\mathbf{u} \in V$. $(\mathbf{M}, \mathbf{u})$ is stable iff $\langle \mathbf{M}^{\alpha}(\mathbf{u}), \alpha \in \mathbb{N}^n \rangle = V$.

*Proof.* If $S = \langle \mathbf{M}^{\alpha}(\mathbf{u}), \alpha \in \mathbb{N}^n \rangle \subset V$, then $S$ is a proper subspace of $V$ such that $M_k(S) \subset S$ for $k = 1, \dots, n$ and $\mathbf{u} \in S$. Thus $(\mathbf{M}, \mathbf{u})$ is not stable.

Conversely, if $\langle \mathbf{M}^{\alpha}(\mathbf{u}), \alpha \in \mathbb{N}^n \rangle = V$, then any subspace $S$ of $V$ such that $M_k(S) \subset S$ for $k = 1, \dots, n$ and $\mathbf{u} \in S$ contains $\langle \mathbf{M}^{\alpha}(\mathbf{u}), \alpha \in \mathbb{N}^n \rangle = V$. Thus $S$ cannot be a proper subspace of $V$, $(\mathbf{M}, \mathbf{u})$ is stable.

Using Cayley-Hamilton identity, we verify that $(\mathbf{M}, \mathbf{u})$ is stable iff $\langle \mathbf{M}^{\alpha}(\mathbf{u}), \alpha \in \mathbb{N}^n \rangle = V$.

**Lemma 2.13.** If $(\mathbf{M}, \mathbf{u}) \in C_{r,n} \times V$ is stable, then $V$ admits a basis of the form $\{\mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta_i\}$ with $\beta_i \subset \mathbb{N}^n$ stably connected of size $r$.

*Proof.* Let $V_i = \langle \mathbf{M}^{\alpha}(\mathbf{u}), |\alpha| \le i \rangle$. We have $V_0 := \langle \mathbf{u} \rangle \subset V_1 \subset \cdots \subset V$.

Let us prove by induction that $V_i$ has a basis of the form $\{\mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta_i\}$ with $\beta_i$ stably connected.

This is true for $i = 0$ with $\beta_0 = \{0\}$. Assume that the property is true for $i - 1$ so that $\{\mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta_{i-1}\}$ is a basis of $V_{i-1}$ with $\beta_{i-1}$ stably connected. Let $\beta_{i-1}^{+} = \beta_{i-1} \cup (\beta_{i-1} + \mathbf{e}_1) \cup \cdots \cup (\beta_{i-1} + \mathbf{e}_n)$.

Since $V_{i-1} = \langle \mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta_{i-1} \rangle$, we have $V_i = \langle \mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta_{i-1}^{+} \rangle$. Let us choose $\beta' \subset \beta_{i-1}^{+} \setminus \beta_{i-1}$ such that $\{\mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta_i\}$ is a basis of $V_i$ with $\beta_i = \beta_{i-1} \cup \beta'$. By construction, $\beta_i$ is stably connected. This proves the induction hypothesis and concludes the proof.

**Definition 2.14.** For an ADHM datum $(\mathbf{M}, \mathbf{u})$, we define the Multiplication Operator Form (MOF) $\mathcal{N} = \mathcal{N}_{(\mathbf{M}, \mathbf{u})}$ associated to $(\mathbf{M}, \mathbf{u})$ as

$$\mathcal{N}: R \to V \\ p(\mathbf{x}) \mapsto p(\mathbf{M})(\mathbf{u}).$$
Let $B = \{b_1, \dots, b_r\}$ be a basis of $V$. The $i^{th}$ coordinate $N_i : p \in \mathbb{K}[\mathbf{x}] \mapsto (N(p))_i \in \mathbb{K}$ in the basis $B$ is a linear functional vanishing on $\mathcal{K}$.

**Proposition 2.15.** If $(\mathbf{M}, \mathbf{u})$ is a stable ADHM datum, then $\mathcal{N} := \mathcal{N}_{(\mathbf{M}, \mathbf{u})}$ is a Normal Form for $I = \ker \mathcal{N}$. Moreover, there exists $B \subset W$ stably connected such that $\mathcal{N}_{|B} : B \to V$ is an isomorphism and $I = (\ker \mathcal{N}_{|B^+})$.

*Proof.* The map $\mathcal{N}$ is surjective since $(\mathbf{M}, \mathbf{u})$ is stable and by Lemma 2.12, $\mathrm{Im}(\mathcal{N}) = \langle \mathbf{M}^{\alpha}(\mathbf{u}), \alpha \in \mathbb{N}^n \rangle = V$.

The kernel $\ker \mathcal{N}$ is an ideal of $R$, since the operators $\mathbf{M}_k \in \mathrm{End}(V)$ are commuting, and we have for any $p \in \mathbb{K}[\mathbf{x}]$ and $q \in \ker \mathcal{N}$,

$$ \mathcal{N}(pq) = p(\mathbf{M})(\mathcal{N}(q)) = 0 $$

so that $pq \in \ker \mathcal{N}$.

As $(\mathbf{M}, \mathbf{u})$ is stable, by Lemma 2.13, there exists $\alpha \subset \mathbb{N}^n$ stably connected such that $\{\mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta\}$ is a basis of $V$.

Let $\mathbf{b} = \{\mathbf{x}^{\beta}, \beta \in \beta\} = \mathbf{x}^{\beta}$ and $B = \langle \mathbf{x}^{\beta} \rangle$. Then $\mathcal{N}(B) = V$, and $\mathcal{N}$ is an isomorphism between $B$ and $V$. This concludes the proof of the proposition.

By Proposition 2.3, if $\mathbf{b} = \mathbf{x}^{\beta}$ is stably connected such $\{\mathbf{M}^{\beta}(\mathbf{u}), \beta \in \beta\}$ is a basis of $V$, then the coordinate functionals $(N_i)$ are a basis of $I^{\perp}$, which is dual to $\mathbf{b}$.

We can now provide an intrinsic characterization of a Truncated Normal Form, without knowing the underlying ideal.

**Theorem 2.16.** Let $\mathbf{N} : W \to V$ be a linear map from $W \subset R$ to a vector space $V$. Assume that there exists $B \subset W$ stably connected such that $B^+ \subset W$ and $\mathbf{N}_{|B} : B \to V$ is an isomorphism, and that the associated operators of multiplication $\mathbf{M}_k$ (see Definition 2.9) pairwise commute, then $\mathbf{N}$ is a TNF for $(\ker \mathbf{N}_{|B^+})$ from $B^+$ to $V$.

*Proof.* Let $\mathbf{N}^* = (\mathbf{N}_{|B})^{-1} \circ \mathbf{N} : W \to B$. We show that $\mathbf{N}^*$ is a TNF, which implies that $\mathbf{N}$ is a TNF since it is equivalent to $\mathbf{N}^*$. As $B$ is stably connected, $B \ni 1$. Let us show that $(\mathbf{M}, 1)$ is a stable ADHM datum. By Lemma 2.13, it is sufficient to show that $\langle \mathbf{M}^{\beta}(1), \beta \in \mathbb{N}^n \rangle = B$, since the operators $\mathbf{M}_k$ are commuting. By definition, $\mathbf{N}^*(b) = b$ for any $b \in B$. Let us prove by induction on the degree that for $\mathbf{x}^{\beta} \in B$, $\mathbf{M}^{\beta}(1) = \mathbf{x}^{\beta}$. This is true for $\beta = \mathbf{0}$ since $\mathbf{M}^{\mathbf{0}}(1) = 1$. As $B$ is stably connected, $\mathbf{x}^{\beta} = x_{i_{\beta}}\mathbf{x}^{\beta'}$ with $i_{\beta} \in [1, \dots, n]$ and $\mathbf{x}^{\beta'} \in B$. Then we have, by induction,

$$ \mathbf{M}^{\beta}(1) = \mathbf{M}_{i_{\beta}} \circ \mathbf{M}^{\beta'}(1) = \mathbf{M}_{i_{\beta}}(\mathbf{x}^{\beta'}) = \mathbf{N}^{*}(x_{i_{\beta}}\mathbf{x}^{\beta'}) = \mathbf{N}^{*}(\mathbf{x}^{\beta}) = \mathbf{x}^{\beta}. $$

Consequently, $\langle \mathbf{M}^{\beta}(1), \beta \in \mathbb{N}^n \rangle = B$ and $(\mathbf{M}, 1)$ is a stable ADHM datum.

By Proposition 2.15, $\mathcal{N} := \mathcal{N}_{(\mathbf{M}, 1)}$ is a Normal Form w.r.t. $(K)$ where $K = \ker(\mathcal{N}_{|B^+})$. For $\mathbf{x}^{\alpha} \in B^+$ with $\alpha \neq \mathbf{0}$, we have $\mathbf{x}^{\alpha} = x_{i_{\alpha}}\mathbf{x}^{\beta}$ for some $i_{\alpha} \in [1, \dots, n]$ and $\mathbf{x}^{\beta} \in B$. Then, similarly as above,

$$ \mathcal{N}(\mathbf{x}^{\alpha}) = \mathbf{M}_{i_{\alpha}} \circ \mathbf{M}^{\beta}(1) = \mathbf{M}_{i_{\beta}}(\mathbf{x}^{\beta}) = \mathbf{N}^{*}(x_{i_{\alpha}}\mathbf{x}^{\beta}) = \mathbf{N}^{*}(\mathbf{x}^{\alpha}). $$
This shows that $\mathcal{N}$ coincides with $\mathbf{N}^*$ on $B^+$. As $\mathcal{N}$ is a Normal Form with respect to $(K)$, we have $(K) \oplus B = R$ so that $(K) + B^+ = (K) + B = R$ and

$$(K) \cap B^+ = \ker \mathcal{N} \cap B^+ = \ker \mathcal{N}_{|B^+} \cap B^+ = \ker(\mathbf{N}^*)_{|B^+} \cap B^+ = K.$$

This shows that $\mathbf{N}^*$ (resp. $\mathbf{N}$) is a TNF from $B^+$ to $B$ (resp. from $B^+$ to $V$).

**Corollary 2.17.** If in addition to the assumptions of Theorem 2.16, we have $\ker(\mathbf{N}) \subset (\ker \mathbf{N}_{|B^+})$, then $\mathbf{N}$ is a TNF for $(\ker \mathbf{N}_{|B^+})$ from $W$ to $V$.

*Proof.* Let $K = \ker \mathbf{N}_{|B^+}$ and $K' = \ker \mathbf{N}$. We have $B^+ = B \oplus K$ and $W = B \oplus K'$ since $N_{|B} : B \to V$ is an isomorphism. As $K \subset K'$ and $N_{|B^+}$ is a TNF, we have $R = (K) + B^+ \subset (K') + W \subset R$ so that $(K') + W = R$. As $K \subset K' \subset (K)$, $(K') = (K)$. Then as $W = B \oplus K'$, $K' \subset (K)$ and $B \cap (K) = B \cap (B^+ \cap (K)) = B \cap K = \{0\}$, we have

$$W \cap (K') = W \cap (K) = (B \oplus K') \cap (K) = (B \cap (K)) \oplus K' = K.$$

This proves that $\mathbf{N}$ is a TNF for $(K)$ from $W$ to $V$.

# 3 Construction of Truncated Normal Forms

## 3.1 Sylvester maps

Let $\mathbf{f} = (f_1, \dots, f_s) \in \mathbb{R}^s$ be such that $I = (f_1, \dots, f_s)$ is a zero-dimensional ideal with $\dim R/I = r < \infty$. We consider vector spaces $V_1, \dots, V_s \subset R$ and $W \subset R$ containing $\sum_{i=1}^s f_i V_i$. The associated Sylvester map $\mathcal{S}_{\mathbf{f}}$ is defined as

$$\mathbf{S}_{\mathbf{f}} : V_1 \times \dots \times V_s \to W \\ (p_1, \dots, p_s) \mapsto \sum_{i=1}^s f_i p_i$$

Let us consider the co-kernel of $\mathbf{S}_{\mathbf{f}}$, that is, the kernel of $\mathbf{S}_{\mathbf{f}}^t : W^* \to (\prod_{i=1}^s V_i)^*$ and a basis $\nu_i, \dots, \nu_\kappa$ of $\ker \mathbf{S}_{\mathbf{f}}^t \subset W^*$. It defines a co-kernel map

$$\mathbf{N}_{\mathbf{f}} : W \to \mathbb{K}^{\kappa} \\ p \mapsto [\nu_1(p), \dots, \nu_{\kappa}(p)].$$

Notice that this construction depends on the choice of the basis of $\ker \mathbf{S}_{\mathbf{f}}$ but any two co-kernel maps $\mathbf{N}_{\mathbf{f}}$, $\mathbf{N}_{\mathbf{f}}^t$ are equivalent: $\mathbf{N}_{\mathbf{f}}^t = P \mathbf{N}_{\mathbf{f}}$ for some $P \in \mathrm{Gl}(\mathbb{K}^{\kappa})$.

**Lemma 3.1.** We have $\mathrm{Im} \mathbf{N}_{\mathbf{f}} = \mathbb{K}^{\kappa}$ and $\ker \mathbf{N}_{\mathbf{f}} = \mathrm{Im} \mathbf{S}_{\mathbf{f}}$.

*Proof.* Since $\nu_1, \dots, \nu_\kappa$ form a basis of $\ker \mathbf{S}_{\mathbf{f}}^t$, they are linearly independent so that $\mathrm{Im} \mathbf{N}_{\mathbf{f}} = \mathbb{K}^{\kappa}$.

By construction, $\langle \nu_1, \dots, \nu_\kappa \rangle = (\mathrm{Im} \mathbf{S}_{\mathbf{f}})^\perp \subset W^*$ so that $\langle \nu_1, \dots, \nu_\kappa \rangle^\perp = \mathrm{Im} \mathbf{S}_{\mathbf{f}}$, that is, $\ker \mathbf{N}_{\mathbf{f}} = \mathrm{Im} \mathbf{S}_{\mathbf{f}}$, which concludes the proof.

Such maps appear in the construction of resultants [EM99,Cox20]. We recall briefly some of these constructions.
*Univariate Sylvester maps.* For a univariate polynomial $f = \sum_{i=0}^{d} f_i x^i \in \mathbb{K}[x]$ with $f_d \neq 0$, we consider $V = \langle 1 \rangle$, $W = \langle 1, \dots, x^d \rangle$ and the matrix of $\mathbf{S}_f^t$ in the monomial basis is $[f_0, \dots, f_d]$. The matrix of a co-kernel map, deduced from a basis of $\ker \mathbf{S}_f^t$, is

$$ \mathbf{N}_f = \begin{bmatrix} 1 & -\frac{f_0}{f_d} \\ \vdots & \vdots \\ 1 - \frac{f_{d-1}}{f_d} \end{bmatrix}. $$

The $d$ last columns of $\mathbf{N}_f$ yields the companion matrix of $f$, that is, the matrix of multiplication by $x$ modulo $f$ in the basis $B = \{1, \dots, x^{d-1}\}$ of $\mathcal{A} = \mathbb{K}[x]/(f)$. We easily verify that $\mathbf{N}_f$ is a TNF for $(f)$ from $\langle 1, \dots, x^d \rangle$ to $\mathbb{K}^d$.

For two univariate polynomials $f_k = \sum_{i=0}^{d_k} f_{k,i} x^i \in \mathbb{K}[x]$ with $f_{k,d_k} \neq 0$ for $k = 1, 2$, let us take $V_k = \langle 1, x, \dots, x^{d_k-1} \rangle$ and $W = \langle 1, \dots, x^{d_1+d_2-1} \rangle$. The matrix of $\mathbf{S}_f$ is the *Sylvester matrix* in the monomial basis of $V_1 \times V_2$ and $W$ is

$$ \mathbf{S}_f = \begin{bmatrix} f_{1,0} & f_{2,0} & & & \\ & \ddots & & & \\ \vdots & \vdots & \ddots & & \\ f_{1,d_1} & f_{1,0} & f_{2,d_2} & f_{2,0} & \\ & & \ddots & \ddots & \\ & & & f_{1,d_1} & f_{2,d_2} \end{bmatrix}. $$

It is a $(d_1+d_2) \times (d_1+d_2)$ matrix, which determinant is the resultant of $f_1, f_2$.

If the determinant vanishes, then $\text{gcd}(f_1, f_2) = \prod_{l=1}^{\gamma}(x - \xi_l)$ where $\gamma = \text{deg}(\text{gcd}(f_1, f_2)) > 0$ and $\xi_l \in \overline{\mathbb{K}}$. In this case, $\text{rank}(\mathbf{S}_f) = d_1 + d_2 - \gamma$. If the roots $\xi_l$ are distinct, the co-kernel of $\mathbf{S}_f$ admits as basis the evaluations $\nu_l : p \mapsto p(\xi_l)$, $l = 1, \dots, \gamma$, defining the co-kernel map

$$ \mathbf{N}_{f_1, f_2} : W \to \overline{\mathbb{K}}^{\gamma} \\ p \mapsto [p(\xi_1), \dots, p(\xi_{\gamma})] $$

We verify that $\mathbf{N}_{f_1, f_2}$ is a TNF for $(f_1, f_2) = (\text{gcd}(f_1, f_2))$ from $\langle 1, \dots, x^{d_1+d_2-1} \rangle$ to $\overline{\mathbb{K}}^{\gamma}$.

*Projective Sylvester maps.* We consider now $n$ multivariate polynomials $f_1, \dots, f_n \in \mathbb{K}[\mathbf{x}] = \mathbb{K}[x_1, \dots, x_n]$ respectively of degree $d_1, \dots, d_n$. Let $\rho = \sum_{i=1}^n (d_i - 1) + 1$. This is the critical degree used in Macaulay computation of the projective resultant of $f_0, f_1, \dots, f_n$ where $f_0$ is of degree 1 (See e.g., [Mac02]). We recall this construction. Let $V_i$ be the vector space of monomials of degree $\le \rho - d_i$, which are not divisible by $x_{i+1}^{d_{i+1}}, \dots, x_n^{d_n}$ (in particular, $V_n = \mathbb{K}[\mathbf{x}]_{\le \rho - d_n}$), and let $W = \mathbb{K}[\mathbf{x}]_{\le \rho}$ be the space of polynomials of degree $\le \rho$.

We verify that for $f_i = x_i^{d_i}, i = 1, \dots, n$, and thus for generic polynomials $f_1, \dots, f_n$, we have the following properties:

- $\mathbf{S}_f$ is of rank $\dim(W) - r$ where $r = \prod_{i=1}^n d_i$, so that $\mathbf{N}_f : W \to \mathbb{K}^r$;

- $(\mathbf{N}_f)|_{B}$ is invertible where $B = \{x_1^{\alpha_1} \cdots x_n^{\alpha_n}, 0 \le \alpha_i \le d_i - 1\}$;

- A basis of $\mathcal{A} = R/(\mathbf{f})$ is $B$ so that $W + (\mathbf{f}) = \langle B \rangle + (\mathbf{f}) = R$.

Then by Theorem 2.8, $\mathbf{N}_f$ is a TNF for $(\mathbf{f})$ from $\mathbb{K}[\mathbf{x}]_{\le \rho}$ to $\mathbb{K}^r$.
Toric Sylester maps. Let $R = \mathbb{K}[x_1^{\pm 1}, \dots, x_n^{\pm 1}]$ be the ring of Laurent polynomials in the variables $x_1, \dots, x_n$. We consider $n$ Laurent polynomials $f_i = \sum_{\alpha \in A_i} f_\alpha \mathbf{x}^\alpha \in R$ where $A_i \subset \mathbb{Z}^n$ are the set of integer points of bounded polytopes $\text{conv}(A_i)$ for $i = 1, \dots, n$. Let $A = \bigoplus_{i=1}^n A_i$ be the integer points of the Minkowski sum of the polytopes $\text{conv}(A_i)$. The Sylvester map $\mathbf{N}_f$ associated to $V_i = \langle \mathbf{x}^\alpha, \alpha \in \bigoplus_{j \neq i} A_j \rangle$ for $i = 1, \dots, n$ and $W = \langle \mathbf{x}^\alpha, \alpha \in A \rangle$ is well-defined since $\sum_{i=1}^n f_i V_i \subset W$.

We recall classical properties of this construction, which are valid for generic $f_i$ with support $A_i$:

- $\mathbf{S}_f$ is of rank $\dim(W) - \mu$ where $\mu = \text{MV}(A_1, \dots, A_n)$ is the mixed volume of $A_1, \dots, A_n$, so that $\mathbf{N}_f : W \to \mathbb{K}^\mu$ is surjective with $\ker \mathbf{N}_f = \text{Im} \mathbf{S}_f$ (see [Kus75,Ber79,GKZ94]);

- $(\mathbf{N}_f)_{|B}$ is invertible where $B$ is a set of monomials with exponents in the mixed cells of a regular subdivision of $A$ (see [CE93,ER94,PS96]);

- $B$ is a basis of $R/(\mathbf{f})$ so that $W + (\mathbf{f}) = R$ (see [CE93,ER94,PS96]).

Then, by Theorem 2.8, $\mathbf{N}_f$ is a TNF for $(\mathbf{f})$ from $W = \langle \mathbf{x}^\alpha, \alpha \in A \rangle$ to $\mathbb{K}^r$.

The spaces $V_i$ used in this construction are not "optimal". Constructions involving spaces of smaller dimension, used in sparse resultant computation, can be found e.g. in [CE93,DS15,CE24]. See also the related eigensolver approaches [Mas16,BT22].

The construction described above avoids the computation of regular subdivisions, at the cost of producing Sylvester matrices with more columns but with the same co-kernel. We illustrate it in the following example.

**Example 3.2.** We consider $R = \mathbb{K}[x_1, x_2]$ and $f_1 = x_1x_2 - x_2 + x_1 - 1$, $f_2 = x_2^2 - 3x_2 - 6x_1 + 8$. The Sylvester map associated to $V_1 = \langle 1, x_1, x_2, x_2^2 \rangle$, $V_2 = \langle 1, x_1, x_2, x_1x_2 \rangle$ and $W = \langle 1, x_2, x_1, x_2^2, x_1x_2, x_1^2, x_2^3, x_1x_2^2, x_1^2x_2, x_1x_2x_2^3 \rangle$ is

$$ \mathbf{S}^t = \begin{bmatrix} 1 & x_2 & x_1 & x_2^2 & x_1x_2 & x_1^2 & x_2^3 & x_1x_2^2 & x_1^2x_2 & x_1x_2^3 \\ f_1 & -1 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ x_2f_1 & 0 & -1 & 0 & -1 & 1 & 0 & 0 & 1 & 0 \\ x_1f_1 & 0 & 0 & -1 & 0 & -1 & 1 & 0 & 0 & 1 \\ x_2^2f_1 & 0 & 0 & 0 & -1 & 0 & 0 & -1 & 1 & 0 \\ f_2 & 8 & -3 & -6 & 1 & 0 & 0 & 0 & 0 & 0 \\ x_2f_2 & 0 & 8 & 0 & -3 & -6 & 0 & 1 & 0 & 0 \\ x_1f_2 & 0 & 0 & 8 & 0 & -3 & -6 & 0 & 1 & 0 \\ x_1x_2f_2 & 0 & 0 & 0 & 0 & 8 & 0 & 0 & -3 & -6 \end{bmatrix} $$

A basis of $\ker \mathbf{S}^t$ yields the co-kernel map

$$ \mathbf{N} \approx \begin{bmatrix} -0.12684 & -0.13171 & -0.06287 & 0.24239 & -0.19569 & 0.06508 & 0.60674 & 0.30636 & -0.32364 & 0.54277 \\ 0.30228 & 0.38563 & 0.24538 & 0.21099 & 0.44253 & 0.1316 & 0.20305 & 0.15409 & 0.55632 & 0.25995 \\ -0.27393 & -0.00714 & -0.39292 & -0.18749 & 0.11185 & -0.63089 & 0.16574 & -0.30647 & 0.34982 & 0.28473 \end{bmatrix} $$

We check that for $B = \{1, x_2, x_1\}$, $N_0 = \mathbf{N}_{|B} = \mathbf{N}[:, [1, 2, 3]]$. Let $N_1 = \mathbf{N}_{|x_1 B} = \mathbf{N}[:, [3, 5, 6]]$ and $N_2 = \mathbf{N}_{|x_2 B} = \mathbf{N}[:, [2, 4, 5]]$. We check that $M_1 = N_0^{-1}N_1$ and $M_2 = N_0^{-1}N_2$ commute. By Theorem 2.16, $\mathbf{N}$ is a TNF for $(\ker \mathbf{N}_{|B^+}) = (f_1, f_2)$
from W to $\mathbb{K}^3$. The join diagonalization of $M_1, M_2$ yields the solution of the equations $f_1 = f_2 = 0$.

$$ \Xi = \begin{bmatrix} \operatorname{eigen}(M_1) \\ \operatorname{eigen}(M_2) \end{bmatrix} = \begin{bmatrix} 1.0 & 1.0 & 2.0 \\ 1.0 & 2.0 & -1.0 \end{bmatrix} $$

This computation has been performed using the package `AlgebraicSolvers.jl`.

## 3.2 Grobner bases

For $f_1, \dots, f_s \in R = \mathbb{K}[\mathbf{x}]$ and a monomial ordering $\prec$ of $R$, let $\mathbf{g} = \{g_1, \dots, g_l\}$ be a Groebner basis of $I = (f_1, \dots, f_s)$ (see [CLO92]). Let $\mathrm{In}(I) \subset R$ be the initial ideal of $I$, which is generated by the leading monomials $\mathrm{In}(\mathbf{g}) := \{\mathrm{In}(g_i), i = 1, \dots, l\}$ since $\mathbf{g}$ is a Groebner basis of $I$. Let $\mathbf{b} = \{\mathbf{x}^\alpha, \alpha \notin \mathrm{expo}_\prec(I)\}$ be the set of monomials not in $\mathrm{In}(I)$, where $\mathrm{expo}_\prec(I)$ is the set of exponents of the monomials in $\mathrm{In}(I)$. They form a basis of $\mathcal{A} = R/I$. We assume hereafter that $I$ is zero-dimensional or equivalently that $\dim B = \dim \mathcal{A} = r < \infty$ where $B = \langle \mathbf{b} \rangle$.

For $p \in R$, we defined $\mathrm{rem}(p; \mathbf{g}) \in B$ as the reduction of $p$ by $\mathbf{g}$, that is, the unique linear combination of monomials not divisible by one of the leading monomials $\mathrm{In}(\mathbf{g})$ such that $p - r \in I$. The reminder can be written as

$$ \mathrm{rem}(p; \mathbf{g}) = \sum_{\beta \notin \mathrm{expo}_\prec(I)} \nu_\beta(p) \mathbf{x}^\beta $$

where $\nu_\beta \in R^*$ is the linear functional, which maps $p \in R$ to the coefficient of $\mathbf{x}^\beta$ in $\mathrm{rem}(p; \mathbf{g})$.

**Lemma 3.3.** $\mathbf{N}_g := [\nu_\beta]_{\beta \notin \mathrm{expo}_\prec(I)}$ is a Normal Form for $I$, which defines a basis of $I^\perp = \mathcal{A}^*$ dual to the basis $(\mathbf{x}^\beta)_{\beta \notin \mathrm{expo}_\prec(I)}$ of $\mathcal{A}$.

*Proof.* Since $\mathrm{rem}(p; \mathbf{g}) = 0$ for $p \in I$ and $\mathrm{rem}(\mathbf{x}^\beta; \mathbf{g}) = \mathbf{x}^\beta$ for $\beta \notin \mathrm{expo}_\prec(I)$, we deduce that $\mathbf{N}_g : R \to \mathbb{K}^r$ is surjective and $\mathrm{ker}(\mathbf{N}_g) = I$. Thus it defines a Normal Form with respect to $I$.

In particular, we have $\nu_\beta(\mathbf{x}^{\beta'}) = \delta_{\beta, \beta'}$ for $\beta, \beta' \notin \mathrm{expo}_\prec(I)$ and $\delta_{\beta, \beta'} = 1$ if $\beta = \beta'$ and 0 otherwise. This proves that $(\nu_\beta)_{\beta \notin \mathrm{expo}_\prec(I)}$ is a basis of $\mathcal{A}^*$ dual to the basis $(\mathbf{x}^\beta)_{\beta \notin \mathrm{expo}_\prec(I)}$ of $\mathcal{A}$.

A Truncated Normal Form on $B^+$ can be deduced from the Groebner basis $\mathbf{g}$ by the following incremental algorithm:
**Algorithm 1** Truncated Normal Form from a Groebner basis for $\prec$

**Input:** $\mathbf{g}$ a Groebner basis of $I$ for $\prec$ and $\mathbf{b} = [\mathbf{x}^\beta]_{\beta \in \text{expo}_\prec(I)} = [\mathbf{x}^{\beta_1}, \dots, \mathbf{x}^{\beta_r}]$.

1. Compute $\partial \mathbf{b} = \mathbf{b}^+ \setminus \mathbf{b}$ sorted by increasing order for $\prec$;

2. For $j \in 1:r$, let $\mathbf{N}(\mathbf{x}^{\beta_j}) := [\delta_{i,j}, i = 1, \dots, r]$.

3. For $g \in \mathbf{g}$ of the form $g = \mathbf{x}^\alpha - \sum_{i=1}^r \nu_{\beta_i, \alpha} \mathbf{x}^{\beta_i}$ let

$$ \mathbf{N}(\mathbf{x}^{\alpha}) = [\nu_{\beta_i, \alpha}, i = 1, \dots, r] $$

4. Let $J := [\text{In}(g); g \in \mathbf{g}]$

5. For $\mathbf{x}^\alpha \in \partial \mathbf{b}$,

- find the greatest $\mathbf{x}^{\alpha'} \in J$ for $\prec$, which divides $\mathbf{x}^\alpha$ with $\mathbf{x}^\gamma = \frac{\mathbf{x}^\alpha}{\mathbf{x}^{\alpha'}}$;

- compute

$$ \mathbf{N}(\mathbf{x}^{\alpha}) := \sum_{i=1}^{r} \nu_{\beta_i, \alpha'} \mathbf{N}(\mathbf{x}^{\gamma+\beta_i}) $$

where $\mathbf{N}(\mathbf{x}^{\alpha'}) = [\nu_{\beta_i, \alpha'}, i = 1, \dots, r]$;

- add $\mathbf{x}^\alpha$ to $J$.

**Output:** $[\nu_{\beta_i, \alpha}]_{1 \le i \le r, \alpha \in \mathbf{b}^+}$.

This algorithm computes and stores incrementally the vectors $\mathbf{N}(\mathbf{x}^\alpha) \in \mathbb{K}^r$, starting with $\mathbf{x}^\alpha \in \mathbf{b} \cup \text{In}(\mathbf{g})$. The list $J$ is updated at each loop, so that $J \subset \text{In}(I)$ and $\mathbf{N}(\mathbf{x}^\alpha)$ is already computed if $\mathbf{x}^\alpha \in J$. Since $\partial \mathbf{b}$ is sorted by increasing order, one shows by induction that if $\mathbf{x}^\alpha$ is the smallest monomial of $\partial \mathbf{b} \setminus J$ for $\prec$, and $\mathbf{x}^{\alpha'} \in \partial \mathbf{b}$ with $\mathbf{x}^{\alpha'} \prec \mathbf{x}^\alpha$, then $\mathbf{x}^{\alpha'} \in J$. This implies in particular that $\mathbf{x}^\gamma$ is either 1 or a variable $x_{i_\alpha}$. Since $\mathbf{b}^t \mathbf{N}(\mathbf{x}^{\alpha'}) = \sum_{i=1}^r \nu_{\beta_i, \alpha'} \mathbf{x}^{\beta_i}$ with $\mathbf{x}^{\beta_i} \preceq \mathbf{x}^{\alpha'}$ when $\nu_{\beta_i, \alpha'} \neq 0$, we have

$$ \mathbf{N}(\mathbf{x}^{\alpha}) = \mathbf{N}(\mathbf{x}^{\alpha'+\gamma}) = \sum_{i=1}^{r} \nu_{\beta_i, \alpha'} \mathbf{N}(\mathbf{x}^{\beta_i+\gamma}), $$

with $\mathbf{x}^{\beta_i+\gamma} \in \mathbf{b}^+$ and $\mathbf{x}^{\beta_i+\gamma} \preceq \mathbf{x}^\alpha$, so that $\mathbf{x}^{\beta_i+\gamma} \in \mathbf{b} \cup J$. This implies that in the loops of step 5, $\mathbf{N}(\mathbf{x}^{\beta_i+\gamma})$ has been computed when $\nu_{\beta_i, \alpha'} \neq 0$.

**Proposition 3.4.** *The output $\mathbf{N} = [\nu_{\beta_i, \alpha}]_{1 \le i \le r, \alpha \in \mathbf{b}^+}$ of Algorithm 1 is a TNF for $I = (\mathbf{g})$ from $\langle \mathbf{b}^+ \rangle$ to $\mathbb{K}^r$.*

*Proof.* We have by construction that $\mathbf{N}(\mathbf{x}^{\beta_j}) = [\delta_{\beta_i, \delta_j}, i = 1, \dots, r]$ so that $\mathbf{N}: \langle \mathbf{b}^+ \rangle \to \mathbb{K}^r$ is surjective.

We verify by induction on $\mathbf{x}^\alpha \in \mathbf{b}^+$ that $\mathbf{b}^t \mathbf{N}(\mathbf{x}^\alpha) \equiv \mathbf{x}^\alpha \bmod I$. By construction, we have $\mathbf{b}^t \mathbf{N}(\mathbf{x}^{\beta_i}) = \mathbf{x}^{\beta_i}$ for $i = 1, \dots, r$.

From step 3, we have for all $g = \mathbf{x}^\alpha - \sum_{i=1}^r \nu_{\beta_i, \alpha} \mathbf{x}^{\beta_i} \in \mathbf{g}$ with $\text{In}(g) = \mathbf{x}^\alpha$,

$$ \mathbf{x}^{\alpha} - \mathbf{b}^t \mathbf{N}(\mathbf{x}^{\alpha}) = \mathbf{x}^{\alpha} - \sum_{i=1}^{r} \nu_{\beta_i, \alpha} \mathbf{x}^{\beta_i} = g \in I $$

Thus, the induction hypothesis is true for $\mathbf{x}^\alpha \in \mathbf{b} \cup \text{In}(\mathbf{g})$.
Assume it is true for $\mathbf{x}^{\alpha'}$ and $\mathbf{x}^{\beta_i+\gamma}$ in step 5. Then $\mathbf{b}^t\mathbf{N}(\mathbf{x}^{\alpha'}) = \sum_{i=1}^r \nu_{\beta_i, \alpha'} \mathbf{x}^{\beta_i} \equiv \mathbf{x}^{\alpha'}$ and $\mathbf{b}^t\mathbf{N}(\mathbf{x}^{\beta_i+\gamma}) \equiv \mathbf{x}^{\beta_i+\gamma} \mod I$. Thus we have

$$ \mathbf{b}^t\mathbf{N}(\mathbf{x}^{\alpha}) = \sum_{i=1}^{r} \nu_{\beta_i, \alpha'} \mathbf{b}^t\mathbf{N}(\mathbf{x}^{\beta_i+\gamma}) \equiv \sum_{i=1}^{r} \nu_{\beta_i, \alpha'} \mathbf{x}^{\beta_i+\gamma} \equiv \mathbf{x}^{\alpha'+\gamma} = \mathbf{x}^{\alpha} \mod I. $$

This shows the induction property.

We deduce that for $p \in \langle \mathbf{b}^+ \rangle$, $p - \mathbf{b}^t\mathbf{N}(p) \equiv 0 \mod I$ and $\mathbf{b}^t\mathbf{N}(p) = p$ for $p \in \langle \mathbf{b} \rangle$, so that

$$ K := \ker \mathbf{N} = \{p - \mathbf{b}^t\mathbf{N}(p), p \in \langle \mathbf{b}^+ \rangle\} \subset I. $$

with $\mathbf{g} \subset K$. Thus $I := (\mathbf{g}) \subset (K) \subset I$, $(K) = I$ and $(K) + \langle \mathbf{b}^+ \rangle \supset (I) + \langle \mathbf{b} \rangle = R$, since $\mathbf{b}$ is a basis of $\mathcal{A} = R/I$.

For $p = \sum_{\mathbf{x}^{\alpha} \in \mathbf{b}^+} p_{\alpha} \mathbf{x}^{\alpha} \in (K) \cap \langle \mathbf{b}^+ \rangle$. We show by contradiction that $p \in K$. If not, assume that $p$ is an element of $(K) \cap \langle \mathbf{b}^+ \rangle \setminus K$ with the smallest initial monomial $\mathbf{x}^{\alpha_0} := \mathrm{In}(p) \in \mathbf{b}^+ \setminus \mathbf{b} = \partial \mathbf{b}$. Let $\kappa_{\alpha_0} = \mathbf{x}^{\alpha_0} - \mathbf{b}^t\mathbf{N}(\mathbf{x}^{\alpha_0}) \in K$. Then $p' = p - p_{\alpha_0} \kappa_{\alpha_0} \in (K) \cap \langle \mathbf{b}^+ \rangle$ and $\mathrm{In}(p') < \mathrm{In}(p)$, which contradicts the assumption on $p$. Consequently $(K) \cap \langle \mathbf{b}^+ \rangle = K$ and $\mathbf{N}$ is a TNF for $I$.

**Example 3.5.** We consider the following polynomial of $R = \mathbb{Q}[\mathbf{x}]$

$$ f = 9 - 48y + 106y^2 - 12xy - 6x^2 - 114y^3 + 22xy^2 + 18x^2y + 10x^3 \\ +64y^4 - 12xy^3 - 24x^2y^2 - 12x^3y - 18y^5 + 2xy^4 + 12x^2y^3 + 4x^3y^2 + 6x^4y \\ -6x^5 + 2y^6 - 2x^2y^4 - 2x^4y^2 + 2x^6 $$

derived from Motzkin polynomial. It is a non-negative polynomial vanishing at some points, that we want to find.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Graph of the polynomial $f$ derived from Motzkin polynomial</figcaption></figure>

We consider the critical points of $f$, where $f = 0$, defined by

$$ f = 0, \partial_x(f) = 0, \partial_y(f) = 0. $$

We compute a Grobner basis of the ideal $I$ generated by these polynomials<fnref n="2" /> for the Graded Reverse Lexicographic Ordering, and round its coefficients to 64-bits floating point numbers:

$$ g = [0.75 - 0.5y - 1.5x + xy, 1.5 - 3.0y - x + y^2 + x^2, 0.375 - 0.25x - 1.5x^2 + x^3]. $$

<footnote n="2">² using the package `Groebner.jl`</footnote>
The basis of the quotient $\mathcal{A}$ is $\mathbf{b} = [1, y, x, y^2]$. We compute the Truncated Normal Form for $(\mathbf{g})$ from $\langle \mathbf{b}^+ \rangle$ to $\mathbb{R}^4$ by Algorithm 1:

$$ \mathbf{N} = \begin{array}{c} \mathbf{1} \\ \mathbf{y} \\ \mathbf{x} \\ \mathbf{y}^2 \end{array} \begin{bmatrix} 1.0 & 0.0 & 0.0 & 0.0 & -0.75 & -1.5 & 1.875 & -1.125 \\ 0.0 & 1.0 & 0.0 & 0.0 & 0.5 & 3.0 & -5.75 & 0.0 \\ 0.0 & 0.0 & 1.0 & 0.0 & 1.5 & 1.0 & 0.0 & 2.25 \\ 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & -1.0 & 4.5 & 0.5 \end{bmatrix} $$

and deduce the matrices of multiplication in the basis $\mathbf{b}$:

$$ M_x = \begin{bmatrix} 0.0 & -0.75 & -1.5 & -1.125 \\ 0.0 & 0.5 & 3.0 & 0.0 \\ 1.0 & 1.5 & 1.0 & 2.25 \\ 0.0 & 0.0 & -1.0 & 0.5 \end{bmatrix}, \quad M_y = \begin{bmatrix} 0.0 & 0.0 & -0.75 & 1.875 \\ 1.0 & 0.0 & 0.5 & -5.75 \\ 0.0 & 0.0 & 1.5 & 0.0 \\ 0.0 & 1.0 & 0.0 & 4.5 \end{bmatrix} $$

From their joint diagonalization, we deduce the 4 solutions:

$$ \Xi = \begin{bmatrix} 1.5 & 0.5 & 0.5 & -0.5 \\ 1.5 & 2.5 & 0.5 & 1.5 \end{bmatrix}, $$

which are the points where $f$ is minimal. These are the steps done in the function `solve_grobner` of the package `AlgebraicSolvers.jl` implementing Algorithm 1.

### 3.3 Border bases

Border bases are generators of an ideal, with a special form that allows to compute easily Truncated Normal Forms. They are defined as follows. Let $R = \mathbb{K}[\mathbf{x}]$ and let $\mathbf{b} = \{\mathbf{x}^{\beta}, \beta \in \beta\} \subset R$ be a set of monomials stably connected to 1. A family of polynomials

$$ f_{\alpha} = \mathbf{x}^{\alpha} - \sum_{\mathbf{x}^{\beta} \in \mathbf{b}} f_{\alpha, \beta} \mathbf{x}^{\beta}, \quad \mathbf{x}^{\alpha} \in \partial \mathbf{b} $$

is a border basis of $I = (f_{\alpha})_{\mathbf{x}^{\alpha} \in \partial \mathbf{b}}$ with respect to $\mathbf{b}$ if $\langle \mathbf{b} \rangle \oplus I = R$.

Characterizations of border bases in terms of commutation of multiplication operators have been presented in [Mou99] and used to develop efficient algorithm to compute border bases [MT05, MT08, MT12, MT14]. See also e.g. [KK05, KK06] for border bases restricted to cases where $\mathbf{b}$ is stable by monomial division (i.e. if $\mathbf{x}^{\beta'}$ divides $\mathbf{x}^{\beta} \in \mathbf{b}$ then $\mathbf{x}^{\beta'} \in \mathbf{b}$). From the border basis $\mathbf{f} = (f_{\alpha})$, we define the following map:

$$ \mathbf{N}_{\mathbf{f}} : \langle \mathbf{b}^{+} \rangle \rightarrow \langle \mathbf{b} \rangle \\ \mathbf{x}^{\alpha} \mapsto \begin{cases} \mathbf{x}^{\alpha} & \text{if } \mathbf{x}^{\alpha} \in \mathbf{b} \\ \sum_{\mathbf{x}^{\beta} \in \mathbf{b}} f_{\alpha, \beta} \mathbf{x}^{\beta} & \text{if } \mathbf{x}^{\alpha} \in \partial \mathbf{b} \end{cases} $$

and we have the following property:
**Proposition 3.6.** if (f) is a border basis with respect to **b** stably connected, then **N**<sub>f</sub> is a TNF for I = (f) from ⟨**b**<sup>+</sup>⟩ to ⟨**b**⟩.

*Proof.* We have that $K := \ker \mathbf{N}_f = \langle f_\alpha, \mathbf{x}^\alpha \in \partial \mathbf{b} \rangle$. As $\mathbf{f}$ is a border basis, we have $\langle \mathbf{b} \rangle \oplus (K) = R$ so that $\langle \mathbf{b}^+ \rangle \cap (K) = K$ and $\langle \mathbf{b}^+ \rangle + (K) = B + (K) = R$. this shows that $\mathbf{N}_f$ is a TNF for $I = (K) = (\mathbf{f})$.

A characterization of Border basis is given in the following theorem (see
[Mou99]:

**Theorem 3.7.** Let $M_i : b \in \langle B \rangle \mapsto \mathbf{N}_f(x_i b) \in \langle B \rangle$. If $B$ is stably connected and the operators $M_i$ commute then $\mathbf{N}_f$ is a TNF for $(\mathbf{f})$ and $(\mathbf{f})$ is a border basis of $(\mathbf{f})$ with respect to $B$.

*Proof.* Let $N := \mathbf{N}_f$. By construction, we have $N_0 := N|_B = \text{Id}$ and $K = \ker N = \langle f_\alpha, \mathbf{x}^\alpha \in \partial B \rangle$. Then $M_i = N_0^{-1} N|_{x_i B}$. If $B$ is stably connected to 1 and the operators $M_i$ commute, then by Theorem 2.16, $N$ is a TNF for $(K) = (\mathbf{f})$ from $\langle B^+ \rangle$ to $\langle B \rangle$.

Example 3.8. We consider $R = \mathbb{K}[x_1, x_2]$, $f_{2,0} = x_1^2 - 3x_1 + 2$, $f_{1,1} = x_1x_2 - x_2 + x_1 - 1$, $f_{0,2} = x_2^2 - 3x_2 - 6x_1 + 8$ and $B = \{1, x_1, x_2\}$ used in Example 1.3.
We have $\partial B = \{x_1^2, x_1x_2, x_2^2\}$. Let

$$
N = \begin{array}{c@{\quad}c}
 & \begin{array}{ccccc} 1 & x_1 & x_2 & x_1^2 & x_2^2 \end{array} \\
\begin{array}{c} 1 \\ x_1 \\ x_2 \end{array} & \left[ \begin{array}{ccccc} 1 & 0 & 0 & -2 & 1 \\ 0 & 1 & 0 & 3 & -1 \\ 0 & 0 & 1 & 0 & 1 \end{array} \right]
\end{array}
$$

We check that the matrices

$$
M_1 = N|_{x_1 B} = \begin{bmatrix} x_1 & x_1^2 & x_1 x_2 \\ x_1 & 0 & -2 \\ x_2 & 1 & 3 \\ x_2 & 0 & 0 \end{bmatrix}, \quad M_2 = N|_{x_2 B} = \begin{bmatrix} x_2 & x_1 x_2 & x_2^2 \\ x_1 & 0 & -8 \\ x_2 & 0 & -1 \\ x_2 & 1 & 3 \end{bmatrix}
$$

commute. Then by Theorem 3.7 {$f_{2,0}, f_{1,1}, f_{0,2}$} is a border basis of (f) with
respect to B. By a joint diagonalization of $M_1, M_2$, we recover the 3 solutions

$$
\Xi = \begin{bmatrix} 1.0 & 1.0 & 2.0 \\ 1.0 & 2.0 & -1.0 \end{bmatrix} .
$$

These are the same solutions as in Example 3.2, since **f** is the border basis computed from *f*₁, *f*₂.

**3.4 Moment matrices**

In many applications such as tensor decomposition [BCMT10] or polynomial
optimization [Las10,Lau09], we are not given polynomial equations but the re-
striction on a vector space V of a linear functional Λ ∈ R* vanishing on an ideal
$I$ defining points $\Xi = \{\xi_1, \dots, \xi_r\} \subset \mathbb{C}^n$. The problem consists in recovering the points $\Xi$ from $\Lambda|_V$. We recall here the approach based on Hankel operators or moment matrices (see [Mou17] for more details) and connect it with TNF.

Let $V \subset R$ and $\Lambda \in V^*$. For $c, c' \subset R$ stably connected such that $\langle c \rangle \cdot \langle c' \rangle \subset V$, we define the Hankel operator

$$H_{\Lambda}^{c',c} : \langle c \rangle \to \langle c' \rangle^* \\ p \mapsto (p \star \Lambda).$$

This map is well-defined since $\forall p \in \langle c \rangle, \forall q \in \langle c' \rangle, pq \in V$ and $p \star \Lambda(q) = \Lambda(pq)$. If $c$ (resp. $c'$) is a basis of $\langle c \rangle$ (resp. $\langle c' \rangle$) then the matrix of $H_{\Lambda}^{c',c}$ is the basis $c$ and the dual basis of $c'$ is

$$H_{\Lambda}^{c',c} = [\Lambda(c'c)]_{c' \in \mathcal{C}, c \in \mathcal{C}}.$$

In many of the applications, $V = \mathbb{K}[x]_{\le \ell}$ for some $\ell \in \mathbb{N}$ and $c$ (resp. $c'$) is the set of monomials of degree $\le d$ (resp. $\le d'$) with $d + d' \le \ell$. Such a matrix is also called the *moment matrix* of $\Lambda$ in degree $(d', d)$. This matrix is called *Catalecticant* of order $(d', d)$ in tensor decomposition problems.

In order to recover the points $\Xi$, we use the property of flat extension: For $b \subset c, b' \subset c'$, we say that $H_{\Lambda}^{c',c}$ is a flat extension of $H_{\Lambda}^{b',b}$ if rank $H_{\Lambda}^{c',c} = \text{rank } H_{\Lambda}^{b',b}$.

This property is used for instance in polynomial optimization, to recover the optimal points from moment matrices (see [CF96,CF98]). We will use a generalization to sparse sets $c, c'$ due to [LM09].

**Theorem 3.9.** Assume that $b \subset c, b' \subset c'$ are stably connected, $b^+ \subset c, b^+ \subset c'$, $H_{\Lambda}^{b',b}$ is invertible, $H_{\Lambda}^{c',c}$ is a flat extension of $H_{\Lambda}^{b',b}$. Then $H_{\Lambda}^{b',c}$ is a TNF for (ker $H_{\Lambda}^{c',c}$) from $\langle c \rangle$ to $\langle b' \rangle^*$.

*Proof.* As $H_0 = H_{\Lambda}^{b',b}$ is invertible, $x_i b \subset c$ and $H_{\Lambda}^{c',c}$ is a flat extension of $H_{\Lambda}^{b',b}$, by [LM09][Lemma 2.1] the operators $M_i = H_0^{-1} H_{\Lambda}^{b',x_i b}$ commute. By Theorem 2.16, $N = H_{\Lambda}^{b',c}$ is a TNF for $(\ker N|_{b^+}) = (\ker H_{\Lambda}^{c',c})$ (by [LM09][Lemma 2.2] and Corollary 2.17) from $\langle c \rangle$ to $\langle b' \rangle^*$.

*Example 3.10.* We consider the homogeneous polynomial or equivalently the symmetric tensor

$$F = -x_0^4 - 24 x_0^3 x_2 - 8 x_0^3 x_1 - 60 x_0^2 x_2^2 - 168 x_0^2 x_1 x_2 - 12 x_0^2 x_1^2 \\ -96 x_0 x_2^3 - 240 x_0 x_1 x_2^2 - 384 x_0 x_1^2 x_2 + 16 x_0 x_1^3 - 46 x_2^4 - 200 x_1 x_2^3, \\ -228 x_1^2 x_2^2 - 296 x_1^3 x_2 + 34 x_1^4$$

which graph $\{(u, uF(u)) \in \mathbb{R}^3 | u \in \mathbb{S}^2\}$ on the unit sphere $\mathbb{S}^2$ gives the surface in Figure 2. The form $F$ is obtained by expansion of

$$F = (x_0 + 3x_1 - x_2)^4 + (x_0 + x_1 + x_2)^4 - 3 (x_0 + 2x_1 + 2x_2)^4$$
<figure><img src="image_3.png" /><figcaption>Fig. 2. Graph of F on $\mathbb{S}^2$</figcaption></figure>

The symmetric tensor decomposition problem consists in recovering the linear terms $L_1 = x_0 + 3x_1 - x_2$, $L_2 = x_0 + x_1 + x_2$, $L_3 = x_0 + 2x_1 + 2x_2$ and the coefficients 1, 1, -3 of the non-expanded form. This a very complex problem, with many applications, and a very rich geometry. We refer for instance to [IK99,Lan11] for more details. The tensor decomposition problem may not have a unique solution (up to permutations of the terms). In the case where this number of terms is small, one may expect a unique decomposition (up to permutations of the terms). Then we say that the tensor is *identifiable*. The approach, based on TNF, that we are describing hereafter applies in this case. When the number of terms is higher, one can search for an extension of F and TNF on larger spaces (see e.g. [BCMT10,BBCM13,BBCM11])

Using the *apolar product* (also known as Bombieri-Weyl product [Lan11]) and setting $x_0 = 1$, we associated to F the linear functional $\Lambda \in \mathbb{C}[x_1, x_2]^*_{\le 4}$ such that for $\alpha \in \mathbb{N}^2$ with $|\alpha| \le 4$,

$$ \Lambda(\mathbf{x}^{\alpha}) = \frac{(4 - |\alpha|)!\alpha_1!\alpha_2!}{4!} \text{coefficient}(F(1, x_1, x_2), \mathbf{x}^{\alpha}), $$

where coefficient($f, \mathbf{x}^{\alpha}$) is the coefficient $f_{\alpha}$ of $\mathbf{x}^{\alpha}$ in $f = \sum_{\alpha} f_{\alpha} \mathbf{x}^{\alpha}$. By the properties of the apolar product, $\Lambda$ is the restriction to $\mathbb{C}[\mathbf{x}]_{\le 4}$ of $e_{(3,-1)} + e_{(1,1)} - 3e_{(2,2)} \in \mathbb{R}^*$ where $e_{(\xi_1, \xi_2)} : p \in \mathbb{R} \mapsto p(\xi_1, \xi_2) \in \mathbb{C}$ is the evaluation at $\xi = (\xi_1, \xi_2) \in \mathbb{C}^2$.

Choosing $\mathbf{c} = \mathbf{c}' = \{1, x_1, x_2, x_1^2, x_1x_2, x_2^2\}$ so that $\mathbf{c} \cdot \mathbf{c}' \subset \mathbb{C}[\mathbf{x}]_{\le 4}$, we get

$$ H_{\Lambda}^{\mathbf{c}, \mathbf{c}} := \begin{bmatrix} 1 & x_1 & x_2 & x_1^2 & x_1 x_2 & x_2^2 \\ x_1 & -1 & -2 & -6 & -2 & -14 & -10 \\ x_2 & -2 & -2 & -14 & 4 & -32 & -20 \\ x_1^2 & -6 & -14 & -10 & -32 & -20 & -24 \\ x_1 x_2 & -2 & 4 & -32 & 34 & -74 & -38 \\ x_2^2 & -14 & -32 & -20 & -74 & -38 & -50 \\ & -10 & -20 & -24 & -38 & -50 & -46 \end{bmatrix} $$
which is of rank 3. We check that $H_0 := H_{\Lambda}^{\mathbf{b},\mathbf{b}}$ is invertible, where $\mathbf{b} = \{1, x_1, x_2\}$ is such that $\mathbf{b}^+ \subset \mathbf{c}$. Thus $H_{\Lambda}^{\mathbf{c},\mathbf{c}}$ is a flat extension of $H_{\Lambda}^{\mathbf{b},\mathbf{b}}$. By Theorem 3.9,

$$H_{\Lambda}^{\mathbf{b},\mathbf{c}} := \begin{array}{c} \mathbf{1} \\ x_1 \\ x_2 \end{array} \begin{bmatrix} -1 & -2 & -6 & -2 & -14 & -10 \\ -2 & -2 & -14 & 4 & -32 & -20 \\ -6 & -14 & -10 & -32 & -20 & -24 \end{bmatrix}$$

is a TNF for $I = (\ker H_{\Lambda}^{\mathbf{c},\mathbf{c}})$ from $\langle \mathbf{c} \rangle$ to $\langle \mathbf{b} \rangle^* \equiv \mathbb{C}^3$. Since $\Lambda$ is the restriction of $\mathbf{e}_{(3,-1)} + \mathbf{e}_{(1,1)} - 3\mathbf{e}_{(2,2)}$ to $\mathbb{C}[\mathbf{x}]_{\le 4}$, $I$ is the ideal $I(\Xi)$ of polynomials vanishing at $\Xi = [(3, -1), (1, 1), (2, 2)]$. Let

$$H_1 := H_{\Lambda}^{\mathbf{b},x_1\mathbf{b}} = \begin{array}{c} \mathbf{1} \\ x_1 \\ x_2 \end{array} \begin{bmatrix} x_1 & x_1^2 & x_1x_2 \\ -2 & -2 & -14 \\ -2 & 4 & -32 \\ -14 & -32 & -20 \end{bmatrix}, \quad H_2 := H_{\Lambda}^{\mathbf{b},x_2\mathbf{b}} := \begin{array}{c} \mathbf{1} \\ x_1 \\ x_2 \end{array} \begin{bmatrix} x_2 & x_1x_2 & x_1^2 \\ -6 & -14 & -10 \\ -14 & -32 & -20 \\ -10 & -20 & -24 \end{bmatrix}$$

Then the join diagonalization of matrices $M_i = H_0^{-1}H_i$, $i = 1, 2$ yields the points:

$$\Xi = \begin{bmatrix} \operatorname{eigen}(M_1) \\ \operatorname{eigen}(M_2) \end{bmatrix} = \begin{bmatrix} 3.0 & 1.0 & 2.0 \\ -1.0 & 1.0 & 2.0 \end{bmatrix},$$

that is, the solutions $\Xi = \mathcal{V}(I)$, which are the coefficients of $x_1, x_2$ in $L_1, L_2, L_3$. The coefficients $[1, 1, -3]$ can then be recovered by solving the linear system

$$\omega_1 L_1^4 + \omega_2 L_2^4 + \omega_3 L_3^4 = F$$

For more details on this tensor decomposition method, based on TNF, see [BCMT10].

# 4 Parametric Normal Forms

In this section, we consider an ideal $I \subset R = \mathbb{K}[\mathbf{x}]$ generated by the polynomials $h_1, \dots, h_s \in R$ such that $I$ is zero-dimensional of degree $r \in \mathbb{N}$. We denote by $\mathcal{A} = \mathbb{K}[\mathbf{x}]/I$ the quotient algebra of $R$ by the ideal $I$, which is a $\mathbb{K}$-vector space of dimension $r$.

Let $\mathbf{N}: W \to V$ be a TNF such that $\dim(W) = l < \infty$, $\dim(V) = r$ and there exist $B \subset W$ with $B^+ \subset W$ and $\mathbf{N}_{|B}: B \to V$ bijective. Let $\mathbf{N}^* = (\mathbf{N}_{|B})^{-1} \circ \mathbf{N}: W \to B$ be a TNF equivalent to $\mathbf{N}$.

Let $\mathbf{b} = \{b_1, \dots, b_r\}$ be a basis of $\mathbf{b}$ and $\mathbf{b}' = \{b'_{r+1}, \dots, b'_l\} \subset W$ such that $\mathbf{b} \sqcup \mathbf{b}'$ is a basis of $W$. The matrix of $\mathbf{N}^*$ in these basis is of the form

$$\mathbf{N}^* = [\mathrm{Id}_r | \boldsymbol{\nu}]$$

where $\boldsymbol{\nu} = (\nu_{i,j})_{1 \le i \le r, r+1 \le j \le l} \in \mathbb{K}^{r \times (l-r)}$. We verify that $\ker \mathbf{N}^* =: K = \langle b'_j - \sum_{i=1}^r \nu_{i,j} b_i, j = r+1, \dots, l \rangle$.

We introduce now variables $y_{i,j}$ for the coefficients $\nu_{i,j}$ and consider the matrix $N_y = [\mathrm{Id}_r | \mathbf{y}]$ where $\mathbf{y} = (y_{i,j})_{1 \le i \le r, r+1 \le j \le l}$. This defines the so-called *Parametric Truncated Normal Form*:

$$\mathbf{N}_y : \langle \mathbf{b}' \rangle \otimes \mathbb{K}[\mathbf{y}] \to \langle \mathbf{b} \rangle \otimes \mathbb{K}[\mathbf{y}] \\ \mathbf{b}'_j \mapsto \sum_{i=1}^r y_{i,j} b_i$$
Similarly, the *Parametric Multiplication* by $x_k$ is $\mathbf{M}_{y,k} : b \in \langle \mathbf{b} \rangle_y \mapsto \mathbf{N}_y(x_k b) \in \langle \mathbf{b} \rangle_y$ where $\langle \mathbf{b} \rangle_y := \langle \mathbf{b} \rangle \otimes \mathbb{K}[y]$. Its matrix in the basis $\mathbf{b}$ is $M_{y,k} = N_y S_k$.

**Definition 4.1.** The commutator ideal of $N_y$ in $\mathbb{K}[y]$

$$C = ((M_{y,k}M_{y,k'} - M_{y,k'}M_{y,k})_{i,j}, 1 \le i, j \le r, 1 \le k < k' \le n) \subset \mathbb{K}[y]$$

The parametric vanishing ideal of $h_1, \dots, h_l$ is

$$\mathcal{E} = ((h_k(\mathbf{M}_y)(1))_i, 1 \le i \le r, 1 \le k \le s) \subset \mathbb{K}[y].$$

where $p(\mathbf{M}_y)$ is the operator obtained by replacing the variable $x_i$ by $M_{y,i}$ in the polynomial $p \in \mathbb{K}[\mathbf{x}]$.

**Definition 4.2.** Let $\mathbb{Y} = \mathbb{K}[y]/(\mathcal{E} + \mathcal{C})$, $\mathbb{K}[\mathbf{x}]_\mathbb{Y} := \mathbb{K}[\mathbf{x}] \otimes \mathbb{Y} = \mathbb{K}[\mathbf{x}, \mathbb{y}]/(\mathcal{E} + \mathcal{C})$ and $\langle \mathbf{b} \rangle_\mathbb{Y} = \langle \mathbf{b} \rangle \otimes \mathbb{Y}$. The Parametric Normal Form associated to $\mathbf{N}_y$ is

$$\mathcal{N}_{\mathbb{Y}} : \mathbb{K}[\mathbf{x}]_{\mathbb{Y}} \to \langle \mathbf{b} \rangle_{\mathbb{Y}} \\ p(\mathbf{x}) \mapsto p(\mathbf{M}_{\mathbb{Y}})(1)$$

Its kernel is denoted $\mathcal{K}_{\mathbb{Y}} \subset \mathbb{K}[\mathbf{x}]_{\mathbb{Y}}$.

**Lemma 4.3.** $\mathcal{K}_{\mathbb{Y}} = \ker \mathcal{N}_{\mathbb{Y}}$ is an ideal of $\mathbb{K}[\mathbf{x}]_{\mathbb{Y}}$ such that $I_{\mathbb{Y}} := I \otimes \mathbb{Y} \subset \mathcal{K}_{\mathbb{Y}}$.

*Proof.* Since the operators $\mathbf{M}_{y,k} \in \mathrm{End}_{\mathbb{Y}}(\langle \mathbf{b} \rangle_{\mathbb{Y}})$ are commuting, we prove as in the proof of Proposition 2.15 that $\mathcal{K}_{\mathbb{Y}}$ is an ideal of $\mathbb{K}[\mathbf{x}]_{\mathbb{Y}}$.

By definition of $\mathcal{E}$, we have $h_k(\mathbf{M}_y)(1) = \mathcal{N}_{\mathbb{Y}}(h_k) = 0 \mod (\mathcal{E} + \mathcal{C})$, i.e. $h_k \in \mathcal{K}_{\mathbb{Y}}$ for $k = 1, \dots, s$. Thus $I_{\mathbb{Y}} \subset \mathcal{K}_{\mathbb{Y}}$.

**Lemma 4.4.** $\mathcal{N}_{\mathbb{Y}}$ coincides with $\mathbf{N}_{\mathbb{Y}}$ on $\langle \mathbf{b}' \rangle_{\mathbb{Y}}$ and $\mathcal{N}_{\mathbb{Y}} \circ \mathcal{N}_{\mathbb{Y}} = \mathcal{N}_{\mathbb{Y}}$.

*Proof.* We prove by induction that $\mathcal{N}_{\mathbb{Y}}(b) = \mathbf{N}_{\mathbb{Y}}(b)$ for $b \in \mathbf{b}'$ numbered so that $b_1 = 1$ and if $b = x_{i_b} \underline{b} \in \mathbf{b}$ then $\underline{b}$ has a lower index than $b$.

For $b_1 = 1$, we have $\mathbf{N}_{\mathbb{Y}}(1) = 1 = (\mathbf{M}_{\mathbb{Y}})^0(1) = \mathbf{N}_{\mathbb{Y}}(1)$. For $b \in \mathbf{b}$ with $b \neq 1$, $b = x_{i_b} \underline{b}$ with $1 \le i_b \le n$ and $\underline{b} \in \mathbf{b}$ of lower index. By induction hypothesis, $\mathcal{N}_{\mathbb{Y}}(\underline{b}) = \mathbf{N}_{\mathbb{Y}}(\underline{b}) = \underline{b}$. As $b \in \mathbf{b}$, we have $\mathbf{N}_{\mathbb{Y}}(b) = b$ and

$$\mathcal{N}_{\mathbb{Y}}(b) = \mathbf{M}_{y,i_b}(\mathbf{N}_{\mathbb{Y}}(\underline{b})) = \mathbf{M}_{y,i_b}(\underline{b}) = \mathbf{N}_{\mathbb{Y}}(x_{i_b} \underline{b}) = \mathbf{N}_{\mathbb{Y}}(b) = b.$$

For the elements $b'_j \in \mathbf{b}'$, $j = r + 1, \dots, l$, we have $b'_j = x_{i_j} b$ with $b \in \mathbf{b}$ and

$$\mathcal{N}_{\mathbb{Y}}(b'_j) = \mathbf{M}_{y,i_j}(\mathcal{N}_{\mathbb{Y}}(b)) = \mathbf{M}_{y,i_j}(b) = \mathbf{N}_{\mathbb{Y}}(x_{i_j}b)\mathbf{N}_{\mathbb{Y}}(b_j).$$

This proves that $\mathcal{N}_{\mathbb{Y}}(b') = \mathbf{N}_{\mathbb{Y}}(b')$ for all $b' \in \langle \mathbf{b}' \rangle_{\mathbb{Y}}$. In particular, since $\mathcal{N}_{\mathbb{Y}}(b) = \mathbf{N}_{\mathbb{Y}}(b) = b$ for $b \in \langle \mathbf{b} \rangle_{\mathbb{Y}}$, we have $\mathcal{N}_{\mathbb{Y}} \circ \mathcal{N}_{\mathbb{Y}} = \mathcal{N}_{\mathbb{Y}}$.

**Theorem 4.5.** We have

$$\mathcal{E} + \mathcal{C} = \mathbf{m}_{\nu}$$

where $\mathbf{m}_{\nu} = (y_{i,j} - \nu_{i,j}, 1 \le i \le r, r + 1 \le j \le l)$ is the maximal ideal of $\mathbb{K}[y]$ defining $\nu$.
Proof. For $f \in \mathbb{K}[\mathbf{x}]$, we have $f - \mathbf{N}_{\nu}(f) \subset I \subset \mathbf{K}$ with $\mathbf{N}_{\nu}(f) \in \langle \mathbf{b} \rangle$. Thus, we have

$$ \mathbf{N}_{\mathbb{Y}}(f) = \mathcal{N}_{\mathbb{Y}}(\mathbf{N}_{\nu}(f)) = \mathbf{N}_{\nu}(f) \text{ in } \langle \mathbf{b} \rangle_{\mathbb{Y}} $$

since $\mathbf{N}_{\nu}(f) \in \langle \mathbf{b} \rangle$ and by Lemma 4.4, $\mathcal{N}_{\mathbb{Y}}$ coincides with $\mathrm{Id}_{\langle \mathbf{b} \rangle}$ on $\langle \mathbf{b} \rangle$.

Taking $f = b'_j$ for $j = r+1, \dots, l$ and identifying the coefficients in the basis $\mathbf{b}$, we deduce that $\mathbf{y} \equiv \nu \mod (\mathcal{E} + \mathcal{C})$ and that $\mathbf{m}_{\nu} \subset (\mathcal{E} + \mathcal{C}) \subset \mathbb{K}[\mathbf{y}]$. Therefore, $\mathcal{E} + \mathcal{C} = \mathbf{m}_{\nu}$.

These equations are closely related to the equations defining the so-called Hilbert scheme $\mathrm{Hilb}_r(\mathbb{K}^n)$ of $r$ points, parametrizing the family of zero-ideal $I$ of $\mathbb{K}[\mathbf{x}]$ defining $r$ points (counted with multiplicity) [Gro95]. The points of the Hilbert scheme $\mathrm{Hilb}_r(\mathbb{K}^n)$ are the $r$-dimensional vector spaces of linear functionals $I^{\perp}$ restricted to a vector space $W$. They are points of the Grassmannian $\mathrm{Gr}_r(W^*)$, represented by the class of equivalence of a TNF $\mathbf{N}: W \to \mathbb{K}^r$. The Plücker coordinates are the $r \times r$ minors of $\mathbf{N}$. We verify that $\nu_{i,j}$ are the ratio of a $r \times r$ minor of $\mathbf{N}$ by the $r \times r$ minor of the identidy block of $\mathbf{N}$ (see also [Mou24]). It is shown in [ABM10], that the commutation relations $\mathcal{C}$ and relations deduced from $\mathcal{N}$ are defining equations of $\mathrm{Hilb}_r(\mathbb{K})$ (See also [BLMR14,HJ18]).

# 5 Conclusion

In this overview of methods for computing the solutions of zero-dimension ideals, our objective was to show that Truncated Normal Forms are present and useful in many algebraic solvers. TNFs provide a unified way to analyse these different tools. Their characterization is independent of the representation of the polynomials and applies for any finitely generated commutative $\mathbb{K}$-algebra $R$. We have seen that the commutation equations and parametric normal form equations define uniquely a TNF, opening the door for numerical iterative solvers for the computation of approximate TNF. We hope that this approach will launch new perspectives for the development of algebraic solvers.

# References

[ABM10] Mariemi Alonso, Jérôme Brachat, and Bernard Mourrain. The Hilbert scheme of points and its link with border basis. working paper or preprint, 2010.

[AS88] W. Auzinger and H. J. Stetter. *An Elimination Algorithm for the Computation of All Zeros of a System of Multivariate Polynomial Equations*, page 11–30. Birkhäuser Basel, 1988.

[BBCM11] Alessandra Bernardi, Jérôme Brachat, Pierre Comon, and Bernard Mourrain. Multihomogeneous Polynomial Decomposition using Moment Matrices. In A. Leykin, editor, *36th international symposium on Symbolic and algebraic computation (ISSAC 11)*, pages 35–42, San Jose, United States, 2011. ACM Press.
[BBCM13] Alessandra Bernardi, Jerome Brachat, Pierre Comon, and Bernard Mourrain. General Tensor Decomposition, Moment Matrices and Applications. *Journal of Symbolic Computation*, 52(May):51–71, 2013.

[BCMT10] Jerome Brachat, Pierre Comon, Bernard Mourrain, and Elias Tsigaridas. Symmetric tensor decomposition. *Linear Algebra and its Applications*, 433(11–12):1851–1872, 2010.

[Ber79] D. N. Bernshtein. The number of roots of a system of equations. *Functional Analysis and Its Applications*, 9(3):183–185, 1979.

[BLMR14] Jerome Brachat, Paolo Lella, Bernard Mourrain, and Margherita Roggero. Extensors and the Hilbert scheme. *Annali della Scuola Normale Superiore di Pisa, Classe di Scienze*, page pp. 23, 2014.

[BT22] Matías Bender and Simon Telen. Toric eigenvalue methods for solving sparse polynomial systems. *Mathematics of Computation*, 91(337):2397–2429, 2022.

[CE93] John Canny and Ioannis Emiris. *An efficient algorithm for the sparse mixed resultant*, page 89–104. Springer Berlin Heidelberg, 1993.

[CE24] Carles Checa and Ioannis Z. Emiris. Mixed subdivisions suitable for the greedy canny–emiris formula. *Mathematics in Computer Science*, 18(1), 2024.

[CF96] Raúl E. Curto and Lawrence A. Fialkow. *Solution of the Truncated Complex Moment Problem for Flat Data*. Number 568 in Memoirs of the American Mathematical Society. American Mathematical Society, 1996.

[CF98] Raúl E. Curto and Lawrence A. Fialkow. Flat extensions of positive moment matrices: recursively generated relations. *Memoirs of the American Mathematical Society*, 136(648):0–0, 1998.

[CLO92] David A. Cox, John Little, and Donal O’Shea. *Ideals, Varieties, and Algorithms*. Undergraduate Texts in Mathematics. Springer, 1992.

[Cox20] David A. Cox. *Applications of Polynomial Systems*, volume 134 of *Regional conference series in mathematics*. American Mathematical Society, Providence, Rhode Island, 2020. With contributions by Carlos D’Andrea, Alicia Dickenstein, Jonathan Hauenstein, Hal Schenck, Jessica Sidman.

[DB04] Carl De Boor. Ideal interpolation. *Approximation Theory XI: Gatlinburg*, pages 59–91, 2004.

[Ded15] Jean-Pierre Dedieu. *Newton-Raphson Method*. Springer Berlin Heidelberg, 2015.

[DS15] Carlos D’Andrea and Martín Sombra. A poisson formula for the sparse resultant. *Proceedings of the London Mathematical Society*, 110(4):932–964, 2015.

[Dum17] Bogdan Dumitrescu. *Positive Trigonometric Polynomials and Signal Processing Applications*. Springer International Publishing, 2017.

[EF17] Christian Eder and Jean-Charles Faugère. A survey on signature-based algorithms for computing gröbner bases. *Journal of Symbolic Computation*, 80:719–784, 2017.

[EM99] Ioannis Z. Emiris† and Bernard Mourrain‡. Matrices in elimination theory. *Journal of Symbolic Computation*, 28(1–2):3–44, 1999.

[EM07] Mohamed Elkadi and Bernard Mourrain. *Introduction à la résolution des systèmes polynomiaux*. Springer Berlin Heidelberg, 2007.

[ER94] Ioannis Z. Emiris and Ashutosh Rege. Monomial bases and polynomial system solving (extended abstract). In *Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94*, ISSAC '94, page 114–122. ACM Press, 1994.
[GKZ94] Israel M. Gelfand, Mikhail M. Kapranov, and Andrei V. Zelevinsky. *Dis-criminants, Resultants, and Multidimensional Determinants*. Birkhäuser Boston, 1994.

[Gro95] Alexander Grothendieck. Techniques de construction et théorèmes d'existence en géométrie algébrique. iv. les schémas de hilbert. In *Séminaire Bourbaki, Vol. 6*, pages 249–276. Soc. Math. France, Paris, 1995.

[HJ18] Abdelmoubine A. Henni and Marcos Jardim. Commuting matrices and the Hilbert scheme of points on affine spaces. *Advances in Geometry*, 18(4):467–482, 2018.

[HMS16] Jonathan D. Hauenstein, Bernard Mourrain, and Agnes Szanto. On deflation and multiplicity structure. *Journal of Symbolic Computation*, 83:228–253, 2016.

[IK99] Anthony Iarrobino and Vassil Kanev. *Power Sums, Gorenstein Algebras, and Determinantal Loci*. Springer Berlin Heidelberg, 1999.

[KK05] Achim Kehrein and Martin Kreuzer. Characterizations of border bases. *Journal of Pure and Applied Algebra*, 196(2-3):251–270, 2005.

[KK06] Achim Kehrein and Martin Kreuzer. Computing border bases. *Journal of Pure and Applied Algebra*, 205(2):279–295, 2006.

[Kus75] A. G. Kushnirenko. A newton polyhedron and the number of solutions of a system of k equations in k unknowns. *Usp. Matem. Nauk*, 30, 1975.

[Lan11] J. Landsberg. *Tensors: Geometry and Applications*. American Mathematical Society, 2011.

[Las09] Jean Bernard Lasserre. *Moments, Positive Polynomials and Their Applications*. Imerial College Press, 2009.

[Las10] Jean-Bernard Lasserre. *Moments, positive polynomials and their applications*. Number v. 1 in Imperial College Press optimization series. Imperial College Press; Distributed by World Scientific Publishing Co, London: Signapore; Hackensack, NJ, 2010.

[Lau09] Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In *Emerging applications of algebraic geometry*, volume 149 of *IMA Volumes in Mathematics and Its Applications*, pages 157–270. Springer, 2009.

[LM09] Monique Laurent and Bernard Mourrain. A generalized flat extension theorem for moment matrices. *Archiv der Mathematik*, 93(1):87–98, 2009.

[Mac02] F.S. Macaulay. Some formulae in elimination. *Proc. London Math. Soc.*, 1(33):3–27, 1902.

[Mas16] César Massri. Solving a sparse system using linear algebra. *Journal of Symbolic Computation*, 73:157–174, 2016.

[MMS20] Angelos Mantzaflaris, Bernard Mourrain, and Agnes Szanto. Punctual Hilbert Schemes and Certified Approximate Singularities. In *ISSAC 2020 - International Symposium on Symbolic and Algebraic Computation*, Kalamata, Greece, 2020.

[MMS22] Angelos Mantzaflaris, Bernard Mourrain, and Agnes Szanto. A certified iterative method for isolated singular roots. *Journal of Symbolic Computation*, 115:223–247, 2022.

[Mou98] B. Mourrain. Computing the isolated roots by matrix methods. *Journal of Symbolic Computation*, 26(6):715–738, 1998.

[Mou99] B. Mourrain. *A New Criterion for Normal Form Algorithms*, page 430–442. Springer Berlin Heidelberg, 1999.

[Mou17] Bernard Mourrain. Polynomial-exponential decomposition from moments. *Foundations of Computational Mathematics*, 18(6):1435–1492, 2017.
[Mou24] Bernard Mourrain. Isolated singularities, inverse systems and the punctual Hilbert scheme. In Anthony Iarrobino, Pedro Macias Marques, Maria Evelina Rossi, and Jean Vallès, editors, *Deformation of Artinian Algebras and Jordan Type*, volume 805 of *Contemporary Mathematics*, pages 205–224. American Mathematical Society, 2024.

[MT05] Bernard Mourrain and Philippe Trebuchet. Generalized normal forms and polynomial system solving. In *Proceedings of the 2005 international symposium on Symbolic and algebraic computation*, ISSAC05, page 253–260. ACM, 2005.

[MT08] Bernard Mourrain and Philippe Trébuchet. Stable normal forms for polynomial system solving. *Theoretical Computer Science*, 409(2):229–240, 2008.

[MT12] Bernard Mourrain and Philippe Trébuchet. Border basis representation of a general quotient algebra. In *Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation*, ISSAC’12, page 265–272. ACM, 2012.

[MT14] Bernard Mourrain and Philippe Trébuchet. Toric border basis. In *Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation*, ISSAC ’14, page 343–350. ACM, 2014.

[MTVB21] Bernard Mourrain, Simon Telen, and Marc Van Barel. Truncated normal forms for solving polynomial systems: Generalized and efficient algorithms. *Journal of Symbolic Computation*, 102:63–85, 2021.

[PS96] P. Pedersen and B. Sturmfels. *Mixed monomial bases*, page 307–316. Birkhäuser Basel, 1996.

[SW05] Andrew J Sommese and Charles W Wampler. *The Numerical Solution of Systems of Polynomials Arising in Engineering and Science*. WORLD SCIENTIFIC, 2005.

[TMB18] Simon Telen, Bernard Mourrain, and Marc Van Barel. Solving polynomial systems via truncated normal forms. *SIAM Journal on Matrix Analysis and Applications*, 39(3):1421–1447, 2018.