Zero-Dimensional Ideals

or

The inestimable Value of Estimable Terms

Lorenzo Robbiano ^{∗}

It’s like switching your point of view. Things sometimes look complicated

from one angle, but simple from another.

(Achilles to the Tortoise, in Gödel, Escher, Bach

(Douglas R. Hofstadter)

Abstract This survey describes several aspects of the theory of zero-dimensional ideals. It is organised according to the following themes:

1 - Introduction

2 - Zero-Dimensional Ideals and Commuting Endomorphisms 3 - Zero-Dimensional Ideals and Rewrite Rules

1 Introduction

There are many ways of looking at zero-dimensional ideals. These algebraic objects correspond to systems of polynomial equations whose set of solutions is finite. Of course the above sentence is vague, since we do not mention where we are looking for solutions, or, to put it in more challenging way, we do not specify what we mean by solutions. In any event, it is possible to make a solid foundation for a theoretical approach to algebraic systems of polynomial equations, and I refer the interested reader to Section 3.7 of [KR00] for a thorough discussion of the topic.

Consider the polynomial ring P = K[x, y] and the ideal I = (y). The quotient ring P/J is isomorphic to K[x], an infinite dimensional K -vector space. Instead, if we pick the ideal I = (x^{2}, y), then the quotient ring P/I has \{1, \overline{x}\} as a basis. The last is an example of a zero-dimensional ideal. Let I be a zero-dimensional ideal in P = K[x_{1}, …, x_{n}]. We may look at it from the inside by describing a set of generators, or from the outside by describing a set of polynomials whose residue classes in P/I form a basis of P/I as a K -vector space.

∗Address: Dipartimento di Matematica, Via Dodecaneso 35, 16146 Genova, Italy e-mail: robbiano@dima.unige.it URL: http://www.dima.unige.it/STAFF/ROBBIANO

Let us see how these points of view behave in the case of a univariate polynomial ring P = K[x]. In this case every ideal I is principal, hence the description “from the inside” can be given by specifying the unique monic generator of I. Suppose that I is an ideal generated by f = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{d−1}x^{d−1} + x^{d}. It is clear that {f} is also a Gröbner basis of I and that O = (1, x, …, x^{d−1}) maps to a basis of P/I. However O does not capture all the information about I, and so we need something more. We consider the endomorphism of P/I given by “multiplication by x” and represent it via the matrix associated to \overline{O}. This is the well-known companion matrix of f, from which the polynomial f can be reconstructed (see Remarks 2.19 and 2.20).

The main reason why we are interested in stepping aside from the theory of Gröbner bases is that there are bases of P/I which cannot be obtained with a Gröbner basis computation (see Example 3.5). Besides, many bases of this type are very interesting both from a theoretical and a computational point of view (see for instance [Mo99]).

In Section 2 we build up the theoretical background for a description of zero-dimensional ideals “from the outside”, i.e. via multiplication endomorphisms which have the important property of being pairwise commuting. In general, given a finite dimensional vector space V and a finite set of pairwise commuting endomorphisms Φ_{1}, …, Φ_{n} of V , one van ask: do they come from multiplication endomorphisms of a vector space of the type P/I, where I is a zero-dimensional ideal? To answer this question, we use a P -module structure on V given by f(x_{1}, …, x_{n})v = f(Φ_{1}, …, Φ_{n})(v), and show that the answer is affirmative if and only if V is cyclic (see Proposition 2.10). Then we describe an algorithm which checks whether V is cyclic (see Proposition 2.17). Several examples at the end of the section illustrate this piece of theory.

In Section 3 we switch our point of view a little and introduce rewrite rules. It is wellknown that the confluence of rewrite rules associated to polynomials is guaranteed if and only if the marking of the polynomial is coherent, i.e. induced by a term ordering (see Theorem 3.8 taken from [RS93]). So we must focus our attention on a different way of rewriting. We introduce a normal remainder function from the non-commutative polynomial ring to V (see Definition 3.14), and we study its properties. Then we introduce border bases (see Definition 3.18) and matrices associated to them (see Definition 3.20). The final Theorem 3.23 and its Corollary 3.24 make the desired connection between commuting matrices, border bases, and the representation of a zero-dimensional ideal “from the outside”.

This paper was largely inspired by [Mo99] which started the algorithmic, as well as the theoretical, investigation of these special bases related to zero-dimensional ideals. Our contribution should be considered as an introduction to a piece of mathematics which will certainly play an important role in the near future. The ideas developed here have been already used in [CR01] to solve an important problem in statistics.

Conventions

Throughout the entire paper we adopt the conventions and terminology used in the recent book [KR00]. In particular P denotes the multivariate polynomial ring K[x_{1}, …, x_{n}] over a field K, and 𝕋^{n} the monoid of terms (power products) in the indeterminates x_{1}, …, x_{n}.

An important convention that we are using consistently is the following. Tuples of elements are denoted with calligraphic letters, while their underlying set is denoted with the corresponding roman character. For instance when G = (g_{1}, … g_{r}), then automatically G denotes {g_{1}, … g_{r}}. What about matrices? Let V be a finitely generated K -vector space, F a tuple of vectors in V , and E a basis of V . We denote by M_{F}^{E} the matrix whose columns are the E -coordinates of the vectors in F. For Φ ∈ End_{K}(V), the matrix M_{Φ(E)}^{E} will be simply denoted by M_{Φ}^{E}.

2 Zero-Dimensional Ideals and Commuting Endomorphisms

We remind the reader that the theory of term orderings can be found in Section 1.4 of [KR00], and start by recalling the following fundamental result (see [KR00] Proposition 3.7.1) which characterizes zero-dimensional ideals.

Proposition 2.1 Let I be an ideal in P, let \overline{K} be the algebraic closure of K, and let \overline{P} = \overline{K}[x_{1}, …, x_{n}]. The following conditions are equivalent.

a) The ideal I\overline{P} is contained in only finitely maximal ideals of \overline{P}.

b) For i = 1, …, n, we have I ∩ K[x_{i}] ≠ (0).

c) The K -vector space P/I is finite-dimensional. Let σ be a term ordering on 𝕋^{n}. Then the above conditions are equivalent to the following ones

d) The set 𝕋^{n} \ LT_{σ}{I} is finite.

e) For every i ∈ {1, …, n}, there exists a number α_{i} ≥ 0 such that we have x_{i}^{α_{i}} ∈ LT_{σ}(I).

Definition 2.2 An ideal I = (f_{1}, …, f_{s}) in P is called zero-dimensional if it satisfies the equivalent conditions of Proposition 2.1. The number dim_{K}(P/I), finite by the above proposition, is usually called the multiplicity of P/I, and is denoted by mult(P/I).

This is our starting point and we shall find condition c) especially useful. Our next goal is to relate zero-dimensional ideals to finite sets of pairwise commuting endomorphisms.

Definition 2.3 Let V be a finite dimensional K -vector space, and let End_{K}(V) be the (non-commutative) K -algebra whose elements are the K -linear endomorphisms of V . The multiplication in End_{K}(V) is given by composition. Suppose that Φ_{1}, …, Φ_{n} ∈ End_{K}(V) are such that Φ_{i}Φ_{j} = Φ_{j}Φ_{i} for i, j ∈ {1, …, n}. We say that Φ_{1}, …, Φ_{n} are pairwise commuting endomorphisms.

Given pairwise commuting endomorphisms, we may define several algebraic structures attached to them.

Proposition 2.4 Let V be a finite dimensional K -vector space, and Φ_{1}, …, Φ_{n} ∈ End_{K}(V) pairwise commuting endomorphisms.

a) There exists a unique K -algebra homomorphism Θ : P ⟶ End_{K}(V) which is defined by Θ(1) = Id, the identity isomorphism of V , and Θ(x_{i}) = Φ_{i} for i = 1, …, n. We have Θ(f(x_{1}, …, x_{n})) = f(Φ_{1}, …, Φ_{n}). b) There exists a P -module structure on V defined by f(x_{1}, …, x_{n})v = f(Φ_{1}, …, Φ_{n})(v).

We say that V is a P -module via Φ_{1}, …, Φ_{n}.

c) For every w ∈ V , the K -linear map α_{w} : End_{K}(V) ⟶ V which is defined by the rule α_{w}(Φ) = Φ(w), induces the map Θ_{w} = α_{w} ∘ Θ : P ⟶ V which is therefore defined by Θ_{w}(f) = f(Φ_{1}, …, Φ_{n})(w) = f(x_{1}, …, x_{n})w, and is a P -module homomorphism.

d) Given a tuple W = (w_{1}, …, w_{r}), a P -module homomorphism Θ_{W} : P^{r} ⟶ V is defined by Θ_{W}(f_{1}, …, f_{r}) = ∑_{i=1}^{r} Θ_{w_{i}}(f).

Proof. All the proofs are easy and left to the reader. □

Proposition 2.5 Let V be a finite dimensional K -vector space, let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms, and let w ∈ V . The map Θ_{w} is characterized by the following three properties

i) Θ_{w}(1) = w,

ii) Θ_{w} is K -linear,

iii) Θ_{w}(x_{i}f) = Φ_{i}(Θ_{w}(f)) for all f ∈ P.

Proof. It follows from the definition that Θ_{w} satisfies the above properties. Now, let φ : P ⟶ V be a map with the three properties above. We want to show that φ = Θ_{w}. By ii) it suffices to show that φ and Θ_{w} coincide on terms and by i) we can make induction on the degree. So let t be a term of degree d and assume that φ and Θ_{w} coincide on terms of degree at most d − 1. We write t = x_{i}t′ with deg(t′) = d − 1. Property iii) implies that φ(t) = Φ_{i}(φ(t′)) = Φ_{i}(Θ_{w}(t′)) = Θ_{w}(t), and we are done. □

Lemma 2.6 Let V be a finite dimensional K -vector space and let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms.

a) The map Θ induces a K -algebra isomorphism P/ Ker(Θ) ≅ K[Φ_{1}, …, Φ_{n}].

b) Ker(Θ) is a zero-dimensional ideal.

c) Ker(Θ) = Ann_{P} (V).

d) For w ∈ V we have Ker(Θ_{w}) ⊇ Ker(Θ), hence Ker(Θ_{w}) is a zero-dimensional ideal, and Θ_{w} defines a K -linear map \overline{Θ}_{w} : P/ Ker(Θ) to V .

Proof. The proof of a) follows immediately from the definitions. To prove b) it suffices to say that for every i = 1, …, n the characteristic polynomial of Φ_{i} vanishes at Φ_{i}, hence the claim follows from Proposition 2.1.b. To prove c) we observe that f(x_{1}, …, x_{n}) annihilates V if and only if f(Φ_{1}, …, Φ_{n}) is the zero endomorphism, and this happens if and only if f(x_{1}, …, x_{n}) ∈ Ker(Θ). Claim d) is clear. □

Let us consider a fundamental case of commuting endomorphisms.

Proposition 2.7 Let I be a zero-dimensional ideal in P, let Φ_{x_{1}}, …, Φ_{x_{n}} ∈ End_{K}(P) be the endomorphisms defined by the multiplications by x_{1}, …, x_{n} respectively.

a) The maps Φ_{x_{1}}, …, Φ_{x_{n}} induce maps in End_{K}(P/I), still denoted by Φ_{x_{1}}, …, Φ_{x_{n}}. b) The K -algebra homomorphism Θ : P ⟶ End_{K}(P/I) defined by Θ(x_{i}) = Φ_{x_{i}} for

i = 1, …, n is such that Ker(Θ) = I.

c) The map Θ induces a K -algebra isomorphism P/I ≅ K[Φ_{x_{1}}, …, Φ_{x_{n}}].

Proof. First of all, to prove that the maps Φ_{x_{i}} pass to the quotient we need to show that Φ_{x_{i}}(I) ⊆ I. This is clear since Φ_{x_{i}} is multiplication by x_{i}. To show the inclusion I ⊆ Ker(Θ) we first observe that Θ(f(x_{1}, …, x_{n})) = f(Φ_{x_{1}}, …, Φ_{x_{n}}). Now it suffices to show that f ∈ I implies that f(Φ_{x_{1}}, …, Φ_{x_{n}}) is the zero map. In other words it suffices to show that f(Φ_{x_{1}}, …, Φ_{x_{n}})(h) ∈ I for every h ∈ P, and this follows from the fact that f(Φ_{x_{1}}, …, Φ_{x_{n}})(h) = fh. To prove that Ker(Θ) ⊆ I, let f ∈ Ker(Θ). Then f(Φ_{x_{1}}, …, Φ_{x_{n}}) is the zero map, which implies that f(Φ_{x_{1}}, …, Φ_{x_{n}})(1) = f ∈ I.

Finally we observe that the proof of c) follows from b) and Lemma 2.6.a. □

Remark 2.8 Following Propositions 2.4 and 2.7, we can say that the K -vector space P/I is a cyclic P -module via Φ_{x_{1}}, …, Φ_{x_{n}}, generated by 1, and Θ_{1} coincides with the canonical homomorphism P ⟶ P/I.

Definition 2.9 The endomorphisms Φ_{x_{1}}, …, Φ_{x_{n}} ∈ End_{K}(P/I) described above are called the multiplication endomorphisms of P/I. Let \overline{O} = (\overline{f}_{1}, …, \overline{f}_{μ}) be a basis of P/I as a K -vector space. Then the matrices M\overline{O} ; Φ_{x_{1}} , …, M\overline{O} ; Φ_{xn} associated to Φ_{x_{1}}, …, Φ_{x_{n}} with respect to \overline{O} are called the multiplication matrices associated to \overline{O}, and simply denoted

by M\overline{O} ; x_{1}, …, M\overline{O} ; x_{n}

Let us go back to the general situation. We are going to study the conditions under which the map Θ_{w} is surjective.

Proposition 2.10 Let V be a finite dimensional K -vector space, let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms, let J = Ker(Θ) = Ann_{P} (V), and let w ∈ V . The following conditions are equivalent

a) There exists a tuple (h_{1}, …, h_{μ}) of polynomials whose classes form a basis of P/J as a K -vector space, such that the corresponding tuple (Θ_{w}(h_{1}), …, Θ_{w}(h_{μ})) is a basis of V as a K -vector space.

b) For every tuple (h_{1}, …, h_{μ}) of polynomials whose classes form a basis of P/J as a K -vector space, the corresponding tuple (Θ_{w}(h_{1}), …, Θ_{w}(h_{μ})) is a basis of V as a K -vector space.

c) We have V = ⟨w⟩, i.e. V is a cyclic P -module via Φ_{1}, …, Φ_{n} generated by w.

d) The map Θ_{w} : P ⟶ V is surjective.

e) The map \overline{Θ}_{w} : P/J ⟶ V is an isomorphism of K -vector spaces. Moreover, these conditions imply that J = Ker(Θ_{w}).

Proof. The implications a) ⇒ e), e) ⇒ d), and b) ⇒ a) are clear, so let us prove that d) ⇒ c). For every v ∈ V we have v = Θ_{w}(f) for a suitable f ∈ P, so that v = Θ_{w}(f) = f(x_{1}, …, x_{n})w.

Now we prove that c) ⇒ b). For every v ∈ V there exists f ∈ P such that v = f(x_{1}, …, x_{n})w. The class of f modulo J is uniquely represented as ∑_{i=1}^{μ} a_{i}h_{i}, hence v = f(x_{1}, …, x_{n})w = (∑_{i=1}^{μ} a_{i}h_{i}(x_{1}, …, x_{n}))(w) = ∑_{i=1}^{μ} a_{i}h_{i}(Φ_{1}, …, Φ_{n})(w). This implies that (h_{1}(Φ_{1}, …, Φ_{n})(w), …, h_{μ}(Φ_{1}, …, Φ_{n})(w)) = (Θ_{w}(h_{1}), …, Θ_{w}(h_{μ})) is a tuple of generators. Suppose now that ∑_{i=1}^{μ} a_{i}Θ_{w}(h_{i}) = ∑_{i=1}^{μ} a_{i}h_{i}(Φ_{1}, …, Φ_{n})(w) = 0. Then ∑_{i=1}^{μ} a_{i}h_{i}(Φ_{1}, …, Φ_{n}) vanishes on V , hence ∑_{i=1}^{μ} a_{i}h_{i}(x_{1}, …, x_{n}) ∈ J, hence a_{i} = 0 for i = 1, …, μ, and the proof of the equivalence is complete.

The last claim follows from e). □

The next result shows that every K -linear surjective map from P to V can be interpreted as a particular Θ_{w}.

Proposition 2.11 Let V be a finite dimensional K -vector space whose dimension is denoted by μ, let φ : P ⟶ V be a K -linear surjective map whose kernel is an ideal, and let w = φ(1). Then the formula Φ_{i}(φ(f)) = φ(Φ_{x_{i}}(f)) defines pairwise commuting endomorphisms Φ_{i} ∈ End_{K}(V) for i = 1, …, n, so that φ = Θ_{w} with respect to Φ_{1}, …, Φ_{n}, i.e. so that φ(f) = f(Φ_{1}, …, Φ_{n})(w).

Proof. Clearly φ induces an isomorphism \overline{φ} : P/I ⟶ V and the conclusion follows easily from Remark 2.8. □

Proposition 2.12 Let V be a finite dimensional K -vector space, let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms, and let w ∈ V be such that V = ⟨w⟩ as a P -module via Φ_{1}, …, Φ_{n}. Then the equality

Φ_{i} = \overline{Θ}_{w} Φ_{x_{i}} (\overline{Θ}_{w})^{−1}

holds for every i = 1, …, n.

Proof. We observe that \overline{Θ}_{w} is an isomorphism by Proposition 2.10.e. Now, for every v ∈ V there exists f(x_{1}, …, x_{n}) ∈ P such that v = f(x_{1}, …, x_{n})w. Then \overline{Θ}_{w}Φ_{x_{i}}(\overline{Θ}_{w})^{−1}(v) = \overline{Θ}_{w}Φ_{x_{i}}(f(x_{1}, …, x_{n})) = \overline{Θ}_{w}(x_{i}f(x_{1}, …, x_{n})) = Φ_{i}f(Φ_{1}, …, Φ_{n})(w) = Φ_{i}(f(x_{1}, …, x_{n})w) = Φ_{i}(v). □

We are ready to make the transition from endomorphisms to matrices. The following lemma collects some elementary facts, whose proofs are left to the reader.

Lemma 2.13 Let V be a finite dimensional K -vector space, and let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms. Let E, F be bases of V , and let M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}, M_{Φ_{1}}^{F}, …, M_{Φ_{n}}^{F} be the corresponding matrices.

a) M_{Φ_{i}}^{E} = M_{F}^{E} M_{Φ_{i}}^{F} (M_{F}^{E})^{−1} , for every i = 1, …, n, and hence M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E} are simultaneously similar to M_{Φ_{1}}^{F}, …, M_{Φ_{n}}^{F}.

b) The K -algebras K[Φ_{1}, …, Φ_{n}] and K[M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}] are naturally isomorphic.

c) The conditions f(M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}) = 0 and f(M_{Φ_{1}}^{F}, …, M_{Φ_{n}}^{F}) = 0 are equivalent for every polynomial f(x_{1}, …, x_{n}) ∈ P.

Theorem 2.14 Let V be a finite dimensional K -vector space, let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms, assume that there exists w ∈ V such that V = ⟨w⟩ as a P -module via Φ_{1}, …, Φ_{n}, and let J = Ker(Θ) = Ann_{P} (V). Let E be a basis of V , let \overline{O} be a basis of P/J, let M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E} be the matrices of Φ_{1}, …, Φ_{n} associated to E, and let M\overline{O} ; x_{1}, …, M\overline{O} ; x_{n} be the multiplication matrices associated to \overline{O}. Then \overline{Θ}_{w}(\overline{O}) is a basis of V and we have

a) M_{Φ_{i}}^{\overline{Θ}_{w}(\overline{O})} = M\overline{O} ; x_{i} for every i = 1, …, n.

b) M_{Φ_{i}}^{E} = M_{\overline{Θ}_{w}(\overline{O})}^{E} M\overline{O} ; x_{i} (M_{\overline{Θ}_{w}(\overline{O})}^{E})^{−1} , for every i = 1, …, n, and hence M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}

are simultaneously similar to M\overline{O} ; x_{1}, …, M\overline{O} ; x_{n}.

Proof. We put B = \overline{Θ}_{w}(\overline{O}) and start the proof with the observation that B is a basis of V as a K -vector space by Proposition 2.10, so that a) follows from Proposition 2.12. To prove b), we combine a) with the relation M_{Φ_{i}}^{E} = M_{B}^{E} M_{Φ_{i}}^{B} (M_{B}^{E})^{−1} (see Lemma 2.13.a) and deduce M_{Φ_{i}}^{E} = M_{B}^{E} M\overline{O} ; x_{i} (M_{B}^{E})^{−1} which concludes the proof. □

At this point we illustrate the theory with some applications, remarks and examples. In general, if we want to compute Ann_{P} (V) we can use the criteria explained in the next remark.

Remark 2.15 Let V be a finite dimensional K -vector space, let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms, and let J = Ker(Θ) = Ann_{P} (V). Then a Gröbner basis of J can be computed in the following way. We choose a basis E of V and consider the homomorphism Θ′ : P ⟶ K[M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}], defined by Θ′(1) = I_{μ}, the identity matrix, and Θ′(x_{i}) = M_{Φ_{i}}^{E} for i = 1, …, n. From the above lemma we know that J = Ker(Θ′).

Let t = x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} be a power product. Then Θ′(t) = (M_{Φ_{1}}^{E})^{a_{1}}(M_{Φ_{2}}^{E})^{a_{2}} ⋯ (M_{Φ_{n}}^{E})^{a_{n}}. Of course a matrix can be represented as a tuple and the linear dependence among matrices can be checked. Therefore a variant of the Buchberger-Möller Algorithm (see [ABKR99] and [AKR01]) computes J.

Remark 2.16 Let E = (e_{1}, …, e_{μ}) be a basis of V as a K -vector space. Then E generates V as a P -module. Consequently the map Θ_{E} : P^{μ} ⟶ V is a surjective map of P -modules. If M denotes its kernel we get an isomorphism of P -modules P^{μ}/N ≅ V . How do we compute N? One can see that a variant of Buchberger-Möller Algorithm (see the above remark) applied to modules does the job.

Suppose we want to check whether V is cyclic. We can proceed using the algorithm described below.

Proposition 2.17 Let V be a finite dimensional K -vector space, let Φ_{1}, …, Φ_{n} ∈ End_{K}(V) be pairwise commuting endomorphisms, and let J = Ker(Θ) = Ann_{P} (V). Consider the following sequence of instructions.

1) Compute a Gröbner basis of J, and hence a tuple of terms O = (t_{1}, …, t_{μ}), whose residue classes are a basis of P/J as a K -vector space. This step can be performed using the above Remark 2.15.

2) If dim(V) ≠ μ return “ V is not a cyclic P -module via Φ_{1}, …, Φ_{n}”.

3) Choose a basis E of V and compute M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}.

4) Let u_{1}, …, u_{μ} be independent indeterminates and define a generic vector u by putting M_{u}^{E} = (u_{1}, …, u_{μ})^{tr} . Then compute det(A_{u}) where

A_{u} = (t_{1}(M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}) · M_{u}^{E}, …, t_{μ}(M_{Φ_{1}}^{E}, …, M_{Φ_{n}}^{E}) · M_{u}^{E})

5) If det(A_{u}) ≠ 0 has no solutions in K, in particular if det(A_{u}) = 0, return “ V is not a cyclic P -module via Φ_{1}, …, Φ_{n}”.

6) Choose a tuple (a_{1}, …, a_{μ}) on which det(A_{u}) does not vanish, let w be defined by

M_{w}^{E} = (a_{1}, …, a_{μ})^{tr} . Return V = ⟨w⟩. This is an algorithm which verifies whether V is a cyclic P -module via Φ_{1}, …, Φ_{n}, and in the affirmative case computes a generator.

Proof. There is no problem of termination and the correctness follows from Proposition 2.10.c. □

We illustrate the preceding facts with a specific example.

Example 2.18 Let Φ_{1}, Φ_{2} be the endomorphisms of ℚ^{3} defined by the following two matrices in Mat_{3}(ℚ)

M_{1} = M_{Φ_{1}}^{E} = ( \begin{matrix}0 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix} ) and M_{2} = M_{Φ_{2}}^{E} = ( \begin{matrix}0 & 1 & 1 \\ 0 & 2 & 1 \\ 0 & 1 & 1 \end{matrix} )

with respect to the canonical basis E = (e_{1}, e_{2}, e_{3}). We want to find the representation P/J ≅ ℚ[Φ_{1}, Φ_{2}], where P = ℚ[x, y], as explained in Lemma 2.6. In other words we want to compute generators of J.

We pick a degree compatible term ordering, and we follow the scheme of computation suggested in Remark 2.15. It turns out that it suffices to compute M_{1}^{2} , M_{1}M_{2} , M_{1}^{2} to get the relations M_{1}^{2} − M_{2} , M_{1}M_{2} − M_{1} − M_{2} , M_{1}^{2} − M_{1} − 2M_{2} , and check that the set {x^{2} − y, xy − x − y, y^{2} − x − 2y} is a Gröbner basis, hence a set of generators of J.

The next goal is to check whether ℚ^{3} is a cyclic P -module via Φ_{1}, Φ_{2} . We follow the suggestion of Proposition 2.17. The triple O = (1, x, y) is such that the residue classes of its components form a basis of P/J as a ℚ-vector space. Then we pick a generic vector u, and compute (1(M_{1}, M_{2}) u, x(M_{1}, M_{2}) u, y(M_{1}, M_{2}) u) = (Id u, M_{1} u, M_{2} u). We let u = (u_{1}, u_{2}, u_{3}), and construct the matrix which represents these three vectors with respect to E. We get

M_{u} = ( \begin{matrix}u_{1} & u_{2} & u_{2} + u_{3} \\ u_{2} & u_{2} + u_{3} & 2u_{2} + u_{3} \\ u_{3} & u_{2} & u_{2} + u_{3} \end{matrix} )

We observe that det(M_{w}) = (u_{2}^{2} − u_{2}u_{3} − u_{3}^{2})(u_{1} − u_{3}), and hence every rational vector (a_{1}, a_{2}, a_{3}) such that a_{1} ≠ a_{3} is a generator of ℚ^{3} as a P -module. For instance we may pick w = 1e_{1} + 1e_{2} + 0e_{3} = (1, 1, 0). The three vectors w, Φ_{1}(w), Φ_{2}(w) form a basis of ℚ^{3} , and hence ℚ^{3} is a cyclic P -module via Φ_{1}, Φ_{2} . Therefore Θ_{w}(O) is defined by

M_{Θ_{w}(O)}^{E} = ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 2 \\ 0 & 1 & 1 \end{matrix} ) whose inverse is (M_{Θ_{w}(O)}^{E})^{−1} = ( \begin{matrix}1 & 0 & −1 \\ 1 & −1 & 1 \\ 0 & 1 & 1 \end{matrix} )

Finally we use Theorem 2.14 to conclude that

M_{Φ_{1}}^{Θ_{w}(O)} = M_{x}^{O} = ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} ) and M_{Φ_{2}}^{Θ_{w}(O)} = M_{y}^{O} = ( \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{matrix} )

and that M_{Φ_{1}}^{E}, M_{Φ_{2}}^{E} are simultaneously similar to M_{x}^{O}, M_{y}^{O},via the matrix M_{Θ_{w}(O)}^{E}. In other words

( \begin{matrix}0 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix} ) = ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 2 \\ 0 & 1 & 1 \end{matrix} ) ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} ) ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 2 \\ 0 & 1 & 1 \end{matrix} )^{−1}

and

( \begin{matrix}0 & 1 & 1 \\ 0 & 2 & 1 \\ 0 & 1 & 1 \end{matrix} ) = ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 2 \\ 0 & 1 & 1 \end{matrix} ) ( \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{matrix} ) ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 2 \\ 0 & 1 & 1 \end{matrix} )^{−1}

What happens if we choose as w a vector which annihilates det(M_{w})? Let us choose w = (1, 2, 1). In this case we may compute Ker(Θ_{w}) again by using a B-M scheme of computation. We get Ker(Θ_{w}) = (x − y − 1, y^{2} − 3y + 1), hence Ker(Θ_{w}) ⊃ Ker(Θ) (see Lemma 2.6.d), and Θ_{w} is not an isomorphism.

Remark 2.19 Let Φ ∈ End_{K}(V). Then we have K[x]/(m(Φ)) ≅ K[Φ], where m(Φ) is the minimal polynomial of Φ. Let m(Φ) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{d−1}x^{d−1} + x^{d}. We may choose (1, x, …, x^{d−1}) so that \overline{O} = (1, \overline{x}, …, \overline{x}^{d−1}) is a basis of K[x]/(m(Φ)), and it is clear that

M\overline{O} ; x = ( \begin{matrix}0 & 0 & 0 & … & 0 & −a_{0} \\ 1 & 0 & 0 & … & 0 & −a_{1} \\ 0 & 1 & 0 & … & 0 & −a_{2} \\ … & … & … & … & … & … \\ 0 & 0 & 0 & … & 0 & −a_{d−2} \\ 0 & 0 & 0 & … & 1 & −a_{d−1} \end{matrix} )

This is the companion matrix or Frobenius companion matrix of m(Φ).

Remark 2.20 In the case of a single endomorphism, the conditions of Proposition 2.10 are equivalent to the condition dim_{K}(V) = d. Namely, if condition a) is satisfied then dim_{K}(V) = dim_{K}(P/(m(Φ)) = d. Conversely, if dim_{K}(V) = d then m(Φ) coincides with the characteristic polynomial of Φ, so that there is only one invariant polynomial and V is cyclic.

Example 2.21 Consider the following matrix

M = ( \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} )

and the corresponding endomorphism Φ of K^{4} defined by M_{Φ}^{E} = M. The minimal polynomial of Φ is x^{2} , while the characteristic polynomial is x^{4} . Then 4 = dim(K^{4}) > deg(m(Φ)), and K^{4} is not a cyclic K[x]-module via Φ.

Example 2.22 Let Φ_{1}, Φ_{2} be the endomorphisms of ℚ^{3} defined by the following two matrices in Mat_{3}(ℚ)

M_{1} = M_{Φ_{1}}^{E} = ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) and M_{2} = M_{Φ_{2}}^{E} = ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} )

with respect to the canonical basis E = (e_{1}, e_{2}, e_{3}). It is easy to check that they commute, M_{1}^{2} = M_{1}M_{2} = M_{2}^{2} = 0, and there is no linear dependence relating Id, M_{1} , M_{2} . Therefore we obtain P/J ≅ ℚ[Φ_{1}, Φ_{2}], where J = (x^{2}, xy, y^{2}). In this case dim(P/J) = dim(V), but, unlike the univariate case (see Remark 2.20), V is not a cyclic P -module via Φ_{1} , Φ_{2} . To verify this claim we apply Proposition 2.17 and compute the matrix A_{u} which turns out to be

A_{u} = ( \begin{matrix}u_{1} & 0 & 0 \\ u_{2} & u_{1} & u_{1} \\ u_{3} & 0 & 0 \end{matrix} )

hence det(A_{u}) = 0.

3 Zero-Dimensional Ideals and Rewrite Rules

Suppose that we are given a zero-dimensional proper ideal I in P. We let ϱ : P ⟶ P/I be the canonical surjective map and μ = mult_{K}(P/I), which is finite by Proposition 2.1. Let V be a finitely generated K -vector subspace of P, and let φ : P ⟶ V be a surjective K -linear map such that φ_{|_{V}} = id_{V} and such that Ker(φ) = I. We observe that P is the direct sum of the two vector subspaces I and V , and that V is isomorphic to P/I. Therefore the map φ is uniquely defined by the given data, and V is a cyclic P -module generated by φ(1) and the theory developed in the previous section applies. In particular we use Proposition 2.11 to obtain endomorphisms of V induced by the multiplication endomorphisms on P and P/I (see Definition 2.9) which we still denote by Φ_{x_{1}}, …, Φ_{x_{n}}. For a basis O of V , we denote by M_{x_{1}}^{O}, …, M_{x_{n}}^{O} the corresponding matrices. We are going to use this setting in the following case.

Definition 3.1 We let O = (h_{1}, …, h_{μ}) be a tuple of polynomials such that \overline{O} = (\overline{h}_{1}, …, \overline{h}_{μ}) is a basis of P/I as a K -vector space. We denote by V (O) the K -vector subspace of P generated by the elements of O. The linear map φ : P ⟶ V (O) is called NF_{O,I}. It turns out to be defined by NF_{O,I}(f) = ∑_{i=1}^{μ} a_{i}h_{i}, where the elements a_{1}, …, a_{μ} are given by ϱ(f) = ∑_{i=1}^{μ} a_{i}\overline{h}_{i}.

a) The polynomial NF_{O,I}(f) is called the normal form of f with respect to (O, I), and the linear map NF_{O,I} is called the normal form map with respect to (O, I).

b) The matrices M_{x_{i}}^{O} are called the multiplication matrices of NF_{O,I}.

c) If there exists an algorithm which computes NF_{O,I}(f) for every f ∈ P, we say that NF_{O,I} is explicit.

Remark 3.2 From the above definitions we get the following properties. a) f − NF_{O,I}(f) ∈ I for every f ∈ P.

b) NF_{O,I}(NF_{O,I}(f)) = NF_{O,I}(f) for every f ∈ P.

c) NF_{O,I}(fg) = NF_{O,I}(NF_{O,I}(f) NF_{O,I}(g)) for every f, g ∈ P.

d) V (O) is a cyclic P -module generated by NF_{O,I}(1).

For instance we may consider the zero-dimensional ideal I = (x^{2}, y) in P = K[x, y], and choose O = (1, x). For f ∈ P we may uniquely write f = a_{1} + a_{2}x mod I. Then NF_{O,I}(f) = a_{1} + a_{2}x.

Corollary 3.3 Let I be a zero-dimensional proper ideal in P, let O = (t_{1}, …, t_{μ}) be a tuple of polynomials such that \overline{O} = (\overline{t}_{1}, …, \overline{t}_{μ}) is a basis of P/I as a K -vector space, let w = NF_{O,I}(1), and let M_{x_{1}}^{O}, …, M_{x_{n}}^{O} be the multiplication matrices of NF_{O,I}. For f ∈ P we have

NF_{O,I}(f) = O · f(M_{x_{1}}^{O}, …, M_{x_{n}}^{O}) · M_{w}^{O}

hence NF_{O,I} is an explicit normal form map with respect to (O, I).

Proof. The claim is a direct consequence of Proposition 2.11 applied to NF_{O,I}. □

Gröbner basis theory tells us that a typical example of O is given by O = 𝕋^{n} \ LT_{σ}{I}, where I is a zero-dimensional proper ideal in P. In that case O has the important property defined below.

Definition 3.4 Let O be a non-empty set of power products such that whenever t′|t for some t ∈ O then t′ ∈ O. Then O is called an order ideal of monomials or a standard set of power products or a complete set of estimable terms. In particular, 1 ∈ O.

However, there are complete sets of estimable terms which form a basis modulo an ideal I, but they are not the complement of LT_{σ}(I), no matter what term ordering σ is chosen. To illustrate this remark we recall the following example from [Ro98].

Example 3.5 Consider the following set {(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)} of five points in 𝔸_{ℚ}^{2}, denote by I ⊂ P = ℚ[x, y] the vanishing ideal of this set, and let O = (1, x, y, x^{2}, y^{2}). The evaluation matrix of the elements of O at the points has determinant −4, hence (\overline{1}, \overline{x}, \overline{y}, \overline{x}^{2}, \overline{y}^{2}) is a ℚ-basis of P/I. Consequently, there is a K -linear surjective map P ⟶ V (O) which sends every polynomial f to the uniquely defined element a_{1} + a_{2}x + a_{3}y + a_{4}x^{2} + a_{5}y^{2} of V (O) such that the residue class of f in P/I is a_{1} + a_{2}\overline{x} + a_{3}\overline{y} + a_{4}\overline{x}^{2} + a_{5}\overline{y}^{2} . However, this map is not induced by a map of the type NF_{σ,I}, since {1, x, y, x^{2}, y^{2}} is not of the form 𝕋^{2} \ LT_{σ}(I) for some term ordering σ.

To prove this fact, consider f = x^{2} + xy − x − \frac{1}{2}y^{2} − \frac{1}{2}y. It is in I, since it vanishes at the five points. For any term ordering σ, we have x^{2} >_{σ} x and y^{2} >_{σ} y. If x >_{σ} y, then x^{2} >_{σ} xy >_{σ} y^{2} . If y >_{σ} x, then y^{2} >_{σ} xy >_{σ} x^{2} . This means that there are only two possibilities for the leading term of f: either it is x^{2} or y^{2} . In both cases we get that LT_{σ}(f) is an element of O but by definition LT_{σ}(f) ∈ LT_{σ}(I).

We compute M_{x}^{O} and M_{y}^{O}. It turns out that

M_{x}^{O} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 1 & −1 & 0 & −1 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \end{matrix} ) M_{y}^{O} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & \frac{1}{2} & 0 & \frac{1}{2} & 1 \\ 0 & −1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 1 & \frac{1}{2} & 0 \end{matrix} )

while w = (1, 0, 0, 0, 0)^{tr} . One can check that M_{x}^{O}M_{y}^{O} = M_{y}^{O}M_{x}^{O}. Let us compute NF_{O,I}(x^{6}y^{2}). We may use the formula of Corollary 3.3, and get

NF_{O,I}(x^{6}y^{2}) = O · (M_{x}^{O})^{6}(M_{y}^{O})^{2} · w = \frac{1}{2}y + \frac{1}{2}y^{2}

At this point we are going to switch our point of view. We begin with the following definition borrowed from [RS93].

Definition 3.6 A pair (g, t) is said to be a marked polynomial if g is a non-zero polynomial and t ∈ Supp(g) with the coefficient of t in g being 1. We also say that g is marked by t. Let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials, T = (t_{1}, …, t_{ν}) a tuple of power products. If (g_{1}, t_{1}), …, (g_{ν}, t_{ν}) are marked polynomials, we say that G is marked by T . The tuple G is said to be marked coherently by T if there exists a term ordering σ with the property that t_{i} = LT_{σ}(g_{i}) for every i = 1, …, ν.

Definition 3.7 Let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials marked by T = (t_{1}, …, t_{ν}). Let g, g′ ∈ P, and suppose there exist a constant c ∈ K, a term t ∈ 𝕋^{n}, and an index i ∈ {1, …, ν} such that g′ = g − c tg_{i} and t · t_{i} ∉ Supp(g′). Then we say that g reduces to g′ in one step using the rewrite rule defined by the marked polynomial (g_{i}, t_{i}). The passage from g to g′ is also called a reduction step and we write g ⟶^{g_{i}} g′.

Gröbner basis theory shows that when a tuple of polynomials G is marked coherently, the associated rewriting system has the property that every chain f_{1} ⟶^{g_{i_{1}}} f_{2} ⟶^{g_{i_{2}}} ⋯ becomes eventually stationary (see [KR00], Proposition 2.2.2.c). The fundamental result of [RS93] shows that this is the only case.

Theorem 3.8 A tuple G of marked polynomials is marked coherently if and only if every sequence of reduction steps associated to G terminates.

Let us illustrate this fact with simple examples.

Example 3.9 Let P = K[x, y], G = (xy − x^{2} − y^{2}) marked by xy. Then the sequence x^{2}y ⟶^{g} x^{3} + xy^{2} ⟶^{g} x^{3} + x^{2}y + y^{3} can be prolonged indefinitely.

Example 3.10 Let P = K[x, y], G = (g_{1}, g_{2}, g_{3}, g_{4}, g_{5}), where g_{1} = x^{3} , g_{2} = y^{3} , g_{3} = xy − x^{2} − y^{2} marked by xy, g_{4} = x^{2}y, g_{5} = xy^{2} . The ideal generated by G is zerodimensional, nevertheless the sequence

x^{2}y ⟶^{g_{3}} x^{3} + xy^{2} ⟶^{g_{1}} xy^{2} ⟶^{g_{3}} x^{2}y + y^{3} ⟶^{g_{2}} x^{2}y

can be prolonged indefinitely, while of course x^{2}y ⟶^{g_{4}} 0 terminates in one step, and the sequence x^{2}y ⟶^{g_{3}} x^{3} + xy^{2} ⟶^{g_{1}} xy^{2} ⟶^{g_{5}} 0 terminates in a finite number of steps.

The examples show that in order to get termination we need something more.

Definition 3.11 Let O = {t_{1}, …, t_{μ}} be a complete set of estimable terms. In this case we define O^{+} = {t ∈ 𝕋^{n} \ O | ∃ i ∈ {1, …, n}, t′ ∈ O with x_{i}t′ = t}, and we call it the border of O (see also [MMM93]).

Remark 3.12 We make a couple of easy remarks about O^{+} .

a) If O is a complete set of estimable terms, every term t is either in O or a multiple of an element of O^{+} .

b) Suppose that t = x_{i}t′ ∈ O ∪ O^{+} . Then also t′ ∈ O ∪ O^{+} .

Definition 3.13 We let P = K⟨x_{1}, …, x_{n}⟩ be the ring of non-commutative polynomials in the indeterminates x_{1}, …, x_{n} and let π : P ⟶ P be the canonical surjective K -linear homomorphism of rings. We let x_{1}, …, x_{n} be ordered so that x_{1} > x_{2} > ⋯ > x_{n}. Then every commutative term t is canonically represented as t = x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}}, and with this convention we define a K -linear map λ : P ⟶ P which associates to t the non-commutative term x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}}. Clearly π∘λ = id_{P}. In the following, we shall omit λ and identify f ∈ P with λ(f) ∈ P.

Definition 3.14 Let O be a tuple of terms in P such that O is a complete set of estimable terms, let O^{+} = (b_{1}, …, b_{ν}) be such that its underlying set is O^{+} , and let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials marked by O^{+} and such that Supp(b_{j} − g_{j}) ⊆ O for i = 1, …, ν. Then we define a K -linear function P ⟶ V (O) called NR_{O,G}, or simply NR by the following rules

a) NR(τ) = π(τ) if π(τ) ∈ O,

b) NR(x_{i}τ) = b_{j} − g_{j} if π(x_{i}τ) = b_{j} ∈ O^{+} and π(τ) ∈ O.

c) NR(x_{i}τ) = NR(x_{i} NR(τ)) if neither a) nor b) applies. It is easy to check that NR_{O,G} is defined. It is called the normal remainder function with respect to (O, G). We say that f is irreducible with respect to (O, G) if Supp(π(f)) ⊆ O, and hence the equality NR_{O,G}(f) = π(f) holds true.

Proposition 3.15 Let O be a tuple of terms in P such that O is a complete set of estimable terms, let O^{+} = (b_{1}, …, b_{ν}) be such that its underlying set is O^{+} , and let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials marked by O^{+} and such that Supp(b_{j} − g_{j}) ⊆ O for i = 1, …, ν. Let I be the ideal generated by G and let f ∈ P. Then

a) π(f) − NR_{O,G}(f) ∈ I for every f ∈ P.

b) NR_{O,G}(x_{i}f) − NR_{O,G}(fx_{i}) ∈ I for every f ∈ P and every i = 1, … n.

Proof. Claim b) follows from claim a) since π(x_{i}f) = π(fx_{i}), hence NR(x_{i}f)−NR(fx_{i}) = NR(x_{i}f) − π(x_{i}f) + π(fx_{i}) − NR(fx_{i}). So let us prove a). We may assume that f is a noncommutative term. If it is a base case, then the conclusion follows from the definition. Otherwise we may write f = x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s}}τ, where π(τ) ∈ O and π(x_{i_{s}}τ) ∈ O^{+} . We call σ(f) this number s.

We have π(f) = x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s}}π(τ), hence π(f) − NR_{O,G}(f) = f_{1} + f_{2} where

f_{1} = x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s−1}}(x_{i_{s}}π(τ) − NR(x_{i_{s}}τ))
f_{2} = x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s−1}} NR(x_{i_{s}}τ) − NR_{O,G}(f)

hence

f_{2} = x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s−1}} NR(x_{i_{s}}τ) − NR(x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s−1}} NR(x_{i_{s}}τ))

we observe that σ(x_{i_{s}}π(τ)) = 1 and σ(x_{i_{1}} · x_{i_{2}} ⋯ x_{i_{s−1}} NR(x_{i_{s}}τ)) = s − 1. An easy inductive argument on σ concludes the proof. □

In the next example we make clear that the function NR_{O,G} : P ⟶ V (O) may take different values on non-commutative power products which have the same projection to P.

Example 3.16 Consider O = (1, x, y, x^{2}, y^{2}) which is a complete set of estimable terms such that O^{+} = {xy, x^{3}, y^{3}, x^{2}y, xy^{2}}. Consider the tuple of polynomials G = (xy − x^{2} − y^{2}, x^{3} − x^{2}, y^{3} − y^{2}, x^{2}y − x^{2}, xy^{2} − y^{2}) marked by O^{+} . Then

NR(yx^{2}) = x^{2} while NR(x^{2}y) = NR(x NR(xy)) = NR(x(x^{2} + y^{2})) = x^{2} + y^{2}

Consequently, we obtain that y^{2} = (x^{2} + y^{2}) − x^{2} ∈ I.

The next important investigation is about the possibility of having particular situations where NR_{O,G} does not depend on the representation of the power products. We need the following result.

Proposition 3.17 Let I be a zero-dimensional proper ideal in P, let O = {t_{1}, …, t_{μ}} be a complete set of estimable terms such that \overline{O} = \{\overline{t}_{1}, …, \overline{t}_{μ}\} is a basis of P/I as a K -vector space, and let O^{+} = {b_{1}, …, b_{ν}}.

a) For each j = 1, …, ν there exists a unique linear combination ∑_{k=1}^{μ} a_{kj}t_{k} with a_{kj} ∈ K for k ∈ {1, …, μ}, j ∈ {1, …, ν}, and g_{j} = b_{j} − ∑_{k=1}^{μ} a_{kj}t_{k} ∈ I.

b) The ideal I is generated by {g_{1}, …, g_{ν}}.

Proof. Clearly P = V (O)⊕I, hence a) follows immediately. Let J be the ideal generated by {g_{1}, …, g_{ν}}. To complete the proof we need to show that J = I. Since J ⊆ I it suffices to show that P = V (O) + J, hence it suffices to show that t ∈ V (O) + J for every term t. We know that 1 ∈ V (O), since O is a complete set of estimable terms, so we make induction on deg(t), and assume that the claim is proved up to degree d − 1. Let t be a term of degree d > 0. There exists i such that t = x_{i}t′ for a suitable term t′ of degree d − 1. Then t′ = ∑_{i=1}^{μ} a_{i}t_{i} + g with a_{i} ∈ K for i = 1, …, μ and g ∈ J. Therefore t = ∑_{i=1}^{μ} a_{i}x_{i}t_{i} + x_{i}g. Now, either x_{i}t_{i} ∈ O or x_{i}t_{i} ∈ O^{+} . In the first case there is nothing to prove. If x_{i}t_{i} ∈ O^{+} , then x_{i}t_{i} belongs to V (O) + J by assumption, and the proof is complete. □

Definition 3.18 Following Proposition 3.17, we let O^{+} = (b_{1}, …, b_{ν}) be such that its underlying set is O^{+} , call G the tuple (g_{1}, …, g_{ν}) and let G be marked by O^{+} . Then the pair (G, O^{+}) is called the border basis of I with respect to O. We observe that in the case where O = 𝕋^{n} \ LT_{σ}(I) border bases were discussed in [MMM93].

Example 3.19 We continue the study of the running Example 3.5. In that case we have O = {1, x, y, x^{2}, y^{2}}. We get O^{+} = {xy, x^{3}, y^{3}, x^{2}y, xy^{2}} and we know already that f_{xy} = xy−x− \frac{1}{2}y+x^{2}− \frac{1}{2}y^{2} , f_{x^{3}} = x^{3}−x, f_{y^{3}} = y^{3}−y. It is easy to check that f_{x^{2}y} = x^{2}y− \frac{1}{2}y− \frac{1}{2}y^{2} and f_{xy^{2}} = xy^{2} − x − \frac{1}{2}y + x^{2} − \frac{1}{2}y^{2} . In conclusion, the set F = \{f_{xy}, f_{x^{3}}, f_{y^{3}}, f_{x^{2}y}, f_{xy^{2}}\} with f_{xy} marked by xy, f_{x^{3}} by x^{3} , f_{y^{3}} by y^{3} , f_{x^{2}y} by x^{2}y, f_{xy^{2}} by xy^{2} , is the border basis of I with respect to O.

Definition 3.20 Let O = (t_{1}, …, t_{μ}) be such that O is a complete set of estimable terms and let O^{+} = (b_{1}, …, b_{ν}) be such that its underlying set is O^{+} . Let G = {g_{1}, …, g_{ν}} be a tuple of polynomials marked by O^{+} and such that Supp(g_{k} − b_{k}) ⊆ O for k = 1, …, ν. We construct matrices M_{1}, …, M_{n} ∈ Mat_{μ}(K) in the following way. If x_{k}t_{j} ∈ O, then the j^{th} - column of M_{k} is (0, …, 0, 1, 0, …, 0)^{tr} , with 1 in the position corresponding to the power product x_{k}t_{j}. If x_{k}t_{j} ∈ O^{+} there exists i ∈ {1, …, ν} such that x_{k}t_{j} = b_{i}, and in this case the j^{th} -column of M_{k} contains the coefficients of (t_{1}, …, t_{μ}) in the representation of the polynomial g_{i} − b_{i} as a linear combination of the elements in O. The matrices M_{1}, …, M_{n} are called the matrices associated to (O^{+}, G).

We now make an interesting connection between NR_{O,G} and the matrices associated to (O^{+}, G).

Proposition 3.21 Let O = (t_{1}, t_{2}, …, t_{μ}) be a tuple such that O is a complete set of estimable terms, let t_{1} = 1, let O^{+} = (b_{1}, …, b_{ν}) be such that its underlying set is O^{+} , and let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials marked by O^{+} and such that Supp(b_{j} − g_{j}) ⊆ O for i = 1, …, ν. Finally let M_{1}, …, M_{n} ∈ Mat_{μ}(K) be the matrices associated to (O^{+}, G). Then

NR_{O,G}(x_{i_{1}}x_{i_{2}} ⋯ x_{i_{s}}) = O · M_{i_{1}}M_{i_{2}} ⋯ M_{i_{s}} · M_{t_{1}}^{O}

for every non-commutative power product x_{i_{1}}x_{i_{2}} ⋯ x_{i_{s}}.

Proof. The assumption t_{1} = 1 implies NR(1) = O · M_{t_{1}}^{O} = 1, hence the proposition is proved for the term 1, and we can make induction on the degree. Let τ = x_{i_{1}}x_{i_{2}} ⋯ x_{i_{s}} and use the inductive assumption to say that NR(x_{i_{2}} ⋯ x_{i_{s}}) = O · M_{i_{2}} ⋯ M_{i_{s}} · M_{t_{1}}^{O}. Then NR(τ) = NR(x_{i_{1}} NR(x_{i_{2}} ⋯ x_{i_{s}})) = NR(x_{i_{1}}O · M_{i_{2}} ⋯ M_{i_{s}} · M_{t_{1}}^{O}). We call v the column matrix M_{i_{2}} ⋯ M_{i_{s}} · M_{t_{1}}^{O} so that NR(τ) = NR(x_{i_{1}}O · v). Therefore it suffices to prove that NR(x_{i_{1}}O · v) = O · M_{i_{1}} · v for every column matrix v. We use the linearity of NR and reduce the problem to prove that NR(x_{i_{1}}O · M_{t_{j}}^{O}) = O · M_{i_{1}} · M_{t_{j}}^{O} for j = 1, …, μ. By definition NR(x_{i_{1}}O · M_{t_{j}}^{O}) = NR(x_{i_{1}}t_{j}), and again by definition NR(x_{i_{1}}t_{j}) is the linear combination of the components in O with coefficients the j^{th} column of M_{i_{1}} . In other words NR(x_{i_{1}}t_{j}) = O · M_{i_{1}} · M_{t_{j}}^{O}, and the proof is complete. □

Example 3.22 Consider Example 3.16. We construct the matrices associated to (O^{+}, G) and get

M_{x} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix} ) M_{y} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \end{matrix} )

We compute M_{x}^{2}M_{y} − M_{y}M_{x}^{2} and get

M = M_{x}^{2}M_{y} − M_{y}M_{x}^{2} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & −1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{matrix} )

Using Proposition 3.21 we see that NR_{O,G}(x^{2}y−yx^{2}) = (1, x, y, x^{2}, y^{2})·M·M_{t_{1}}^{O} = y^{2} . Again we check that y^{2} ∈ I, as we did in Example 3.16.

The following result makes the connection between quotient bases and associated matrices, and is the main result in this section.

Theorem 3.23 Let O = (t_{1}, …, t_{μ}) be such that O is a complete set of estimable terms, and assume that O^{+} = (b_{1}, …, b_{ν}) is such that O^{+} = {b_{1}, …, b_{ν}}. Let G = (g_{1}, …, g_{ν}) be a tuple of non-zero polynomials marked by O^{+} and such that Supp(b_{j} − g_{j}) ⊆ O for i = 1, …, ν, and let I be the ideal generated by G. The following conditions are equivalent.

a) The set \overline{O} = (\overline{t}_{1}, …, \overline{t}_{μ}) is a basis of P/I as a K -vector space.

b) The pair (G, O^{+}) is the border basis of I with respect to O.

c) The matrices M_{1}, …, M_{n} associated to (G, O^{+}) are pairwise commuting.

Proof. We start the proof by showing that a) ⇒ b). The assumption implies that the ideal I is zero-dimensional, hence we may use Proposition 3.17.a to say that for each j = 1, …, ν there exists a unique linear combination ∑_{k=1}^{μ} a_{kj}t_{k} with a_{kj} ∈ K for k ∈ {1, …, μ}, j ∈ {1, …, ν}, and g′_{j} = b_{j} − ∑_{k=1}^{μ} a_{kj}t_{k} ∈ I. The uniqueness implies that g′_{i} = g_{i} for i = 1, …, μ, so that (G, O^{+}) is the border basis of I with respect to O.

Now we prove that b) ⇒ c). If the pair (G, O^{+}) is the border basis of I with respect to O, then \overline{O} is a basis of P/I, hence we may define NF_{O,I} : P ⟶ V (O). We use the uniqueness of NF_{O,I}, Corollary 3.3, and Proposition 3.21 to deduce that M_{k} = M_{x_{k}}^{O} for every k = 1, …, n. Since the matrices M_{x_{k}}^{O} are pairwise commuting, we are done.

Finally we prove that c) ⇒ a). We use Proposition 3.21 which allows to get a K -linear map NR_{O,G} : P ⟶ V (O). The assumption implies that this map factorizes through P, hence we get a map φ : P ⟶ V (O), and now we prove that φ is surjective. It suffices to show that φ(t_{i}) = t_{i} for i = 1, …, μ. This is true for i = 1 by construction, and we make induction on the degree. So let t_{i} ≠ 1. It is possible to write t_{i} = x_{k}t_{j} for a suitable k and a term t_{j} ∈ O. Then φ(t_{i}) = O · M_{k} · t_{j}(M_{1}, …, M_{n}) · M_{t_{1}}^{O} = O · M_{k} · M_{t_{j}}^{O}. But M_{k} · M_{t_{j}}^{O} is the j^{th} column of M_{k}, which is (0, …, 0, 1, 0, … 0)^{tr} with 1 in the i^{th} position, by the very definition of M_{k}. Therefore we have proved that φ is surjective, and hence \overline{O} is a basis of P/ Ker(φ). It is easy to see that Ker(φ) is an ideal, and we use Proposition 3.17 applied to Ker(φ) to conclude that Ker(φ) = (g_{1}, …, g_{ν}) = I. Now the proof is complete. □

Corollary 3.24 If the equivalent conditions of the theorem are satisfied we have a) The ideal I is zero-dimensional, and dim_{K}(P/I) = μ.

b) The matrices M_{1}, …, M_{n} associated to (O^{+}, G) are the multiplication matrices of NF_{O,I}.

c) The normal remainder function NR_{O,G} induces a map P ⟶ V (O), which is NF_{O,I}.

Proof. The proof of a) follows immediately from Claim a) of the theorem. The proof of b) is already included in the proof of b) ⇒ c) of the theorem. The proof of c) is included in the proof of c) ⇒ a) of the theorem. □

Example 3.25 We go back to Example 3.5 and compute NF_{O,I}(x^{6}y^{2}) again, but now we use the border basis F computed in Example 3.19. We proceed as follows. We write x^{6}y^{2} = x^{3}y^{2} · x^{3} , we use the marked polynomial f_{x^{3}} to make a reduction step and get x^{4}y^{2} which we write x^{4}y^{2} = xy^{2} · x^{3} . We use f_{x^{3}} again and get x^{2}y^{2} = xy · xy. We use f_{xy} and get

xy(x + \frac{1}{2}y − x^{2} + \frac{1}{2}y^{2}) = x^{2}y + \frac{1}{2}xy^{2} − x^{3}y + \frac{1}{2}xy^{3}

We use f_{x^{3}} and then f_{y^{3}} and get

x^{2}y + \frac{1}{2}xy^{2} − xy + \frac{1}{2}xy = −\frac{1}{2}xy + x^{2}y + \frac{1}{2}xy^{2}

Finally we use f_{xy}, f_{x^{2}y}, f_{xy^{2}} and get

−\frac{1}{2}(−x^{2} + \frac{1}{2}y^{2} + x + \frac{1}{2}y) + \frac{1}{2}y^{2} + \frac{1}{2}y + \frac{1}{2}(x^{2} + \frac{1}{2}y^{2} + x + \frac{1}{2}y) = \frac{1}{2}y + \frac{1}{2}y^{2}

Therefore NF_{O,I}(x^{6}y^{2}) = \frac{1}{2}y + \frac{1}{2}y^{2} , which agrees with the value computed in Example 3.5.

We can follow different paths, but Corollary 3.24.c) implies that we always arrive at the same conclusion.

References

[ABKR99] J. Abbott, A. Bigatti, M. Kreuzer, L. Robbiano, Computing Ideals of Points, J. Symb. Comput. 30, 341–356 (1999)

[AKR01] J. Abbott, M. Kreuzer, L. Robbiano, Computing Zero-Dimensional Schemes, Preprint (2001)

[AS88] W. Auzinger, H.J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Numerical Mathematics, Proc. Int. Conf. Singapore 1988, Volume 86 of Int. Ser. Numer. Math., 11–30 (1988)

[Bu65] B. Buchberger, On finding a Vector Space Basis of the Residue Class Ring modulo a zero dimensional Polynomial Ideal (in German), PhD Thesis, Universität Innsbruck, Innsbruck (1965)

[CR97] M. Caboara, L. Robbiano, Families of ideal in Statistics, Proceedings of the ISSAC-97 Conference (Maui, Hawaii, July 1997) Küchlin ed., 404-409 (1997)

[CR01] M. Caboara, L. Robbiano, Families of Estimable Terms, Preprint

[CNR98] A. Capani, G. Niesi, L. Robbiano, CoCoA, a system for doing Computations in Commutative Algebra , Available via anonymous ftp from cocoa.dima.unige.it, Version 4.0 (1998)

[KR00] M. Kreuzer, L. Robbiano, Computational Commutative Algebra 1, Springer-Verlag (2000)

[MMM93] M.G Marinari, H.M. Möller, T. Mora Gröbner Bases of Ideals Defined by Functionals with an Application to Ideals of Projective Points, Applicable Algebra in Engineering, Communications and Computing, 4 No. 2, 103 – 145 (1993)

[Mo99] B. Mourrain, Criterion for Normal Form Algorithms, Proceedings of the 13^{th} International Symposium, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS 1719, 430–443 (1999)

[PRW00] G. Pistone, E. Riccomagno, H.P. Wynn, Computational Commutative Algebra In Statistics, Monographs on Statistics and Applied Probability 89 Chapman&Hall/CRC (2000)

[PW96] G. Pistone, H.P. Wynn, Generalised confounding and Gröbner bases, Biometrika 83-3, 653–666 (1996)

[RS93] A. Reeves, B. Sturmfels, A Note on Polynomial Reduction, J. Symb. Comput. 16, 273–277 (1993)

[Ro98] L. Robbiano, Gröbner Bases and Statistics, In B. Buchberger, F. Winkler, editors, Gröbner Bases and Applications (Proc. of the Conf. 33 years of Gröbner Bases), London Mathematical Society Lecture Notes Series, 251, 179–204, Cambridge University Press (1998)

[T99] R. Tenberg, Duale Basen nulldimensionaler Ideale und Anwendungen, Dissertation Universität Dortmund, September 1999, Shaker Verlag (2000)