Algoritmi per l’Algebra e la Geometriaottenute si dicono funzioni polinomiali. Le funzioni...

Margherita Roggero

Algoritmi

per

l’Algebra e la Geometria

Laurea Magistrale in Matematica

A.A. 2006/2007

Indice

Capitolo 1 - Anelli di polinomi 4Prerequisiti di algebra commutativa . . . . . . . . . . . . . . . . . . . . . 4Ideali di k[x1, . . . , xn] e varieta algebriche di kn. . . . . . . . . . . . . . . . 6Ideali omogenei e varieta proiettive . . . . . . . . . . . . . . . . . . . . . . 9

Capitolo 2 - Algoritmo di divisione 11Divisione in k[x]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Ordinamento di monomi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Ideali monomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Ideali iniziali e basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . 19L’algoritmo di divisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21L’algoritmo di Buchberger . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Capitolo 3 - Applicazioni algebriche e geometriche 28Eliminazione di variabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Varieta parametriche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Numeri algebrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Somma di ideali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Intersezione di ideali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31Radicale di un ideale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Quoziente di due ideali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Radicale di ideali zero-dimensionali . . . . . . . . . . . . . . . . . . . . . . 34

Capitolo 4 - La matrice compagna 38Il caso di una variabile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Il caso generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39La base speciale BK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Capitolo 5 - Ricerca di soluzioni reali 44Autovalori reali delle matrici compagne . . . . . . . . . . . . . . . . . . . 44La forma bilineare Φf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Localizzazione degli zeri reali . . . . . . . . . . . . . . . . . . . . . . . . . 47

2

INDICE 3

Il metodo delle potenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Soluzioni reali di equazioni polinomiali . . . . . . . . . . . . . . . . . . . . 49

Algoritmi per l’Algebra e la Geometria (15 maggio 2007)

Capitolo 1

Anelli di polinomi

§ Prerequisiti di algebra commutativa

Sia A un anello commutativo con identita (nel seguito semplicemente anello). Ri-cordiamo che un ideale I di A e un sottogruppo additivo di A chiuso rispetto allamoltiplicazione per elementi di A ossia tale che :

a ∈ A, b ∈ I =⇒ ab ∈ I.

Se I e un ideale di A, al relazione in A data da a ∼ b se a− b ∈ I e una relazione diequivalenza e il quoziente A/I e dotato di una struttura di anello indotta da quelladi A:

(a+ I) + (b+ I) = a+ b+ I , (a+ I) · (b+ I) = ab+ I.

Parleremo allora di anello quoziente A/I di A modulo I.Un dominio (o dominio di integrita) e un anello A in cui vale la legge di

annullamento del prodotto, ossia:

a, b ∈ A , ab = 0 =⇒ a = 0 oppure b = 0.

I campi sono domini.L’anello di polinomi A[x1, . . . , xn] a coefficienti in un anello A nelle variabili

x1, . . . , xn e l’insieme di tutte le somme formali di un numero finito di termini deltipo axr1

1 . . . xrnn con a ∈ A ed esponenti ri ∈ N e le operazioni di somma e prodotto

definite in modo usuale. Se A e un dominio, anche A[x1, . . . , xn] lo e.

Lemma 1.1. Sia A un anello. Le due condizioni seguenti sono equivalenti:

i. Ogni ideale di A e finitamente generato.

ii. Ogni catena ascendente di ideali di A e stazionaria.

Dim: “⇒” Supponiamo che valga 1. e consideriamo una famiglia ai di ideali di A,dove i varia in un insieme totalmente ordinato I e ai ⊆ aj per ogni coppia di indicii, j ∈ I tali che i < j. L’unione a di tutti gli ai risulta essere un ideale (poiche gli ai

4

Anelli di polinomi 5

formano una catena); per ipotesi esiste un numero finito di elementi a1, . . . , ar ∈ Ache generano a. Scegliamo quindi degli indici i1, . . . , ir ∈ I tali che an ∈ ain e sia i0il loro massimo. Allora a1, . . . , ar ∈ ai0 e quindi ai0 = a e la catena da quel puntoin poi e stazionaria.

“⇐” Supponiamo esista un ideale a di A che non e finitamente generato;consideriamo una successione an, con n ∈ N, di elementi di a tali che an+1 /∈an = (a1, . . . , an): una tale successione esiste certamente perche in caso contrarioa1, . . . , an sarebbero generatori di a. Abbiamo cosı ottenuto una catena strettamentecrescente di ideali di A.

Definizione 1.2. Un anello A si dice noetheriano se soddisfa le due condizioniequivalenti del lemma precedente.

Teorema 1.3. (Teorema della base di Hilbert) Se A e un anello noetherianoallora anche l’anello dei polinomi A[x] lo e.

Definizione 1.4. Si dice che un dominio A e un dominio a fattorizzazione unica(in breve: e fattoriale o UFD) se ogni elemento non nullo e non invertibile di Asi decompone nel prodotto di elementi irriducibili e tale decomposizione e unica(a meno dell’ordine dei fattori e di unita ossia della moltiplicazione dei fattori perelementi invertibili).

Teorema 1.5. (Teorema di Gauss) Se A e UFD allora anche A[x] lo e.

Corollario 1.6. L’anello dei polinomi k[x1, . . . , xn] a coefficienti in un campo e undominio noetheriano fattoriale.

Se A = k e un campo, possiamo anche pensare k[x1, . . . , xn] come k-spaziovettoriale; una base privilegiata e l’insieme infinito T dei monomi, ossia dei terminicon coefficiente a = 1:

T := {xr11 · · ·x

rnn / ri ∈ N per i = 1, . . . , n } .

Il grado di un monomio xr11 · · ·xrn

n e il numero intero non negativo r1 + · · ·+rn; ilgrado di un polinomio f , che indicheremo con ∂f e il massimo grado di monomiche compaiono in f , dove con questa espressione intenderemo i monomi che di fcon coefficiente non nullo.

Esempio 1.7. Possiamo uniformare le scritture dei due polinomi f = x2 − 3 eg = 2x + 4 di R[x] scrivendo f = x2 + 0x − 3 e g = 0x2 + 2x + 4. Comunqueil monomio x non compare in f e il monomio x2 non compare in g; quest’ultimoha grado 1, anche se formalmente puo essere scritto facendo comparire anche x2 (omonomi di ogni altro grado superiore).


6 Capitolo 1

§ Ideali di k[x1, . . . , xn] e varieta algebriche di kn.

La valutazione di un polinomio f(x) ∈ k[x] in un elemento α di k si ottienesostituendo all’indeterminata x l’elemento α nell’espressione formale di f(x) = a0 +a1x+ · · ·+ anx

n, ossia la valutazione di f(x) in α e data da

f(α) = a0 + a1α+ · · ·+ anαn.

La valutazione del polinomio nullo in ogni α ∈ k e 0. D’altra parte puo capitareche un polinomio non nullo abbia valutazione 0 in ogni elemento α ∈ k. Per esempiose k ha solo un numero finito di elementi, k = {α1, . . . , αn}, allora il polinomio nonnullo f(x) = (x− α1) · · · (x− αn) ha valutazione 0 in ogni αi ∈ k.

Mediante la valutazione possiamo associare ad ogni polinomio f ∈ k[x] unafunzione f : k → k che associa ad ogni a ∈ k la valutazione f(a). Le funzioni cosıottenute si dicono funzioni polinomiali.

Le funzioni polinomiali con le usuali operazioni di somma e prodotto “punto perpunto” formano un anello che indichiamo con Fk[x]. L’applicazione canonica cheassocia ad ogni polinomio di k[x] la corrispondente funzione e, per costruzione, unomomorfismo suriettivo di anelli, ma, come mostra l’esempio precedente, non sempree anche iniettivo. Se pero k e un campo infinito, allora l’anello dei polinomi e l’anellodelle funzioni polinomiali sono canonicamente isomorfi e potremo considerare comeconcetti equivalenti polinomi e funzioni polinomiali (Principio di identita deipolinomi).

Piu in generale se f ∈ k[x1, . . . , xn], possiamo considerare la valutazione di fin un punto P = (a1, . . . , an) ∈ kn che denoteremo con f(a1, . . . , an) o con f(P ).Sef(a1, . . . , an) = 0 diremio che (a1, . . . , an) e una soluzione dell’equazione f = 0ovvero che (a1, . . . , an) e uno zero del polinomio f .

Dati i polinomi f1, . . . , fr di k[x1, . . . , xn] indichiamo con V = V (f1, . . . , fr) ilsottoinsieme di di kn degli zeri comuni ai polinomi fi. Un punto P = (a1, . . . , an)di kn appartiene a V se f1(a1, . . . an) = · · · = fr(a1, . . . an) = 0, ossia se e soluzionedel sistema di equazioni:

f1(x1, . . . , xn) = 0f2(x1, . . . , xn) = 0

. . . . . .fr(x1, . . . , xn) = 0

Piu in generale, dato un qualsiasi sottoinsieme B di k[x1, . . . , xn], possiamo con-siderare il sottoinsieme V = V (B) degli zeri comuni a tutti i polinomi f ∈ B,ossia:

V (B) = {P ∈ kn | f(P ) = 0 , ∀ f ∈ B}.

Ogni sottoinsieme V di kn del tipo V = V (B) per un qualche B ⊆ k[x1, . . . , xn]si dice insieme algebrico o varieta algebrica affine.

M. Roggero


Possiamo notare che le relazioni di inclusione tra sottoinsiemi di k[x1, . . . , xn]corrispondono a inclusioni di verso rovesciato tra i corrispondenti insiemi algebrici,ossia:

B1 ⊆ B2 =⇒ V (B1) ⊇ V (B2).

Inoltre uno stesso insieme algebrico V ⊆ kn puo essere ottenuto a partire da moltisottoinsiemi diversi di k[x1, . . . , xn]; a seconda dei casi potremmo preferire un insiemedi equazioni di V che sia “piu piccolo possibile” oppure “piu grande possibile”. Ledue richieste sono pero strettamente correlate, come mostra il seguente risultato.

Lemma 1.8. Sia V = V (B) un insieme algebrico di kn.

a. Se I e l’ideale generato da B (ossia l’insieme di tutte le combinazioni linearifinite di elementi di B a coefficienti in k[x1, . . . , xn]), allora V = V (I).

b. L’insieme I (V ) := {f ∈ k[x1, . . . , xn] | f(P ) = 0 per ogni P ∈ V } che contie-ne tutte i polinomi nulli su V e un ideale.

c. Esiste un insieme finito B′ ⊆ k[x1, . . . , xn] tale che V = V (B′).

Dim: Poiche B ⊆ I, si ha intanto V = V (B) ⊇ V (I) . D’altra parte, se P ∈ V (B),allora si ha anche P ∈ V (B); infatti per ogni f ∈ I se e solo se e del tipo f = g1f1 +· · ·+ grfr con f1, . . . , fr ∈ B e quindi f(P ) = g1(P )f1(P ) + · · ·+ gr(P )fr(P ) = 0.

Considerazioni analoghe alle precedenti permettono di verificare che I (V ) e unideale.

Infine un insieme finito di equazioni per V e ad esempio un insieme finito digeneratori di I (oppure di I (V )), che esiste per la noetherianita di k[x1, . . . , xn]. Inparticolare e possibile scegliere un insieme finito B′ ⊆ B.

Potremo allora definire un qualsiasi insieme algebrico V usando soltanto un nu-mero finito di polinomi f1, . . . , fr: V e quindi l’insieme delle soluzioni comuni a unnumero finito di equazioni polinomiali fi = 0.

Se B = {f1, . . . , fr}, indicheremo con (f1, . . . , fr) l’ideale I generato da B. Sinoti che I e I (V ) non sempre coincidono, ma si ha soltanto I ⊆ I (V ).

Esempio 1.9. Siano f ∈ k[X1, . . . , Xn] un polinomio non nullo di grado positivo,B = {f2} e V = V (B). L’ideale generato da B e l’ideale principale (f2), mal’insieme algebrico V puo essere ottenuto anche come V ((f)), con (f2) ( (f) equindi (f2) 6= I (V ), poiche f /∈ (f2), mentre f ∈ I (V ).

Definizione 1.10. Il radicale di un ideale I e:√I = {g ∈ k[X1, . . . , Xn] | gh ∈ I per qualche h ∈ N}.


8 Capitolo 1

Si puo facilmente verificare che√I e un ideale e vale inoltre il risultato seguente

che generalizza l’esempio.

Lemma 1.11. Se I e un ideale di R = k[X1, . . . , Xn] e V = V (I), allora si haanche V = V (

√I).

Dim: Osserviamo intanto che I ⊆√I e quindi (rovesciando le uguaglianze) si ha

V (I) ⊇ V (√I). D’altra parte, se P ∈ V (I) e f ∈

√I, allora fh ∈ I per un qualche

esponente h e quindi f(P ) = 0 poiche (f(P ))h = fh(P ) = 0 e k e un campo.

A partire da un ideale I possiamo quindi costruire due ideali, in genere piu grandidi I, che definiscono lo stesso insieme algebrico, ossia I (V (I)) e

√I. Uno dei piu

importanti risultati dell’algebra commutativa e della geometria algebrica stabilisceuno stretto legame tra questi due ideali.

Teorema 1.12 (Nullstellensatz o Teorema degli zeri di Hilbert). Si consideri uncampo k algebricamente chiuso. Se I e un ideale proprio di k[x1, . . . , xn] ,allora:

Forma debole: V (I) 6= ∅

Forma forte: I (V (I)) =√I.

Senza l’ipotesi che il campo k sia algebricamente chiuso, non sempre√I e il piu

grande ideale che definisce V (I), come mostra il seguente esempio.

Esempio 1.13. In R[x] l’ideale I = (x3+x) individua la varieta V (I) = V (x3+x) ={0} ed e un ideale radicale, ossia I =

√I. Pero vi sono anche polinomi che sono

nulli su V (I), ma che non appartengono a I, come ad esempio x. Piu precisamentesi ha I (V (I)) = (x) )

√I.

La corrispondenza biunivoca tra ideali radicali e ideali di varieta ha quindi bisognodell’ipotesi relativa alla chiusura algebrica del campo. Tuttavia il risultato continuaa valere, piu generalmente, per l’anello dei polinomi k[x1, . . . , xn] a coefficienti in uncampo k qualsiasi purche si considerino gli zeri a coordinate in un campo K este-sione algebricamente chiusa di k (e quindi le varieta associate siano sottoinsiemi diKn). Possiamo ad esempio applicare il Teorema degli zeri agli ideali di R[x1, . . . , xn]considerano le corrispondenti varieta in Cn.

Definizione 1.14. Si dice che un insieme algebrico V e irriducibile se non el’unione di due insiemi algebrici strettamente contenuti in V ossia se:

V = V1 ∪ V2 con V1 e V2 algebrici =⇒ V = V1 oppure V = V2.

M. Roggero


V si dice riducibile se non e irriducibile, ossia se e l’unione di due insiemi algebriciciascuno strettamente contenuto in V . Si dice dimensione di un insieme algebricoV la massima lunghezza r delle catene:

V0 ( V1 ( · · · ( Vr ⊆ V

dove le Vi sono varieta irriducibili.

Si puo dimostrare che un insieme algebrico non vuoto V di kn e irriducibile see soltanto se I (V ) e un ideale primo (ossia se fg ∈ I (V ) ⇒ f ∈ I (V ) oppureg ∈ I (V )). Si puo dimostrare, inoltre, per mezzo della teoria della decomposizio-ne primaria degli ideali, che ogni insieme algebrico di kn puo essere decompostonell’unione di un numero finito di varieta irriducibili.

Sia V un sottoinsieme algebrico di kn e sia I = I (V ) l’ideale associato. Ognipolinomio f ∈ k[x1, . . . , xn] definisce una funzione polinomiale:

f : V → k data da P 7→ f(P ).

Definizione 1.15. L’anello k[V ] delle funzioni polinomiali su V , dotato delle opera-zioni di somma e prodotto punto per punto, si dice anello delle coordinate di V .Due polinomi f e g definiscono la stessa funzione polinomiale in k[V ] se e soltantose la loro differenza f − g definisce la funzione nulla, ossia se f − g ∈ I. Allora k[V ]e canonicamente isomorfo a k[x1, . . . , xn]/I (V ).

§ Ideali omogenei e varieta proiettive

Un polinomio costituito da monomi tutti dello stesso grado si dice omogeneo ri-spetto alla graduzione standard. Ogni polinomio puo essere scritto in modo unicocome somma di polinomi omogenei di gradi distinti: le sue componenti graduate.

Una caratterizzazione importante dei polinomi omogenei e la seguente:

f ∈ k[x1, . . . , xn] e omogeneo di grado r ⇔ f(tx1, . . . , txn) = trf(x1, . . . , xn).

L’insieme delle radici di un polinomio omogeneo e allora un cono di kn con verticenell’origine.

Un ideale si dice omogeneo se contiene le componenti graduate dei suoi elementi;si verifica che un ideale e omogeneo se e soltanto se ammette un insieme di generatoricostituito da polinomi omogenei.

Se I e un ideale omogeneo, V (I) e quindi a sua volta un cono con vertice nel-l’origine; tali varieta corrispondono biunivocamente alle varieta proiettive dellospazio proiettivo Pn−1 di dimensione n− 1 sul campo k.

Viceversa, se un polinomio si annulla sui punti di un cono W , allora anche cia-scuna sua componente omogenea vi si annulla e quindi I (W ) e un ideale omogeneo.


10 Capitolo 1

Per lo studio delle varieta proiettive sono quindi particolarmente interessanti gliideali omogenei.

D’altra parte gli ideali omogenei hanno anche proprieta che in molte situazioni lirendono preferibili a quelli che non lo sono. Si puo allora ricorrere al procedimentodi omogenizzazione che trasforma un qualsiasi ideale I di k[x1, . . . , xn] in un idealeomogeneo di k[x0, x1, . . . , xn] mediante l’aggiunta di una nuova variabile.

Possiamo generalizzare il concetto di polinomio e ideale omogeneo introducentouna funzione “peso” che associa ad ogni variabile xi un numero intero di (di = 1 nelcaso standard); si definisce quindi il grado pesato di un monomio xa1

1 · · ·xann come

la somma a1d1 + · · ·+ andn.

M. Roggero

Capitolo 2

Algoritmo di divisione

§ Divisione in k[x].

Ricordiamo che l’anello dei polinomi in una variabile k[x] e un dominio euclideocon la valutazione data dal grado; quindi k[x] e un dominio a ideali principali e inesso vale la fattorizzazione unica.

Gli ideali di k[x] sono allora tutti principali ossia del tipo (f) con f ∈ k[x]. Dueideali (f) e (g) coincidono se e solo se f e g sono associati tra loro. Quindi:

Ideal(A) 1−1←→ k[x]/ ∼

dove ∼ e data da:f ∼ g ⇐⇒ f = ag con a ∈ k∗

poiche gli elementi non nulli di k sono gli unici elementi invertibili in k[x].La valutazione data dal grado e la conseguente struttura di dominio euclideo

non forniscono solo informazioni di tipo generale sulle proprieta di k[x], ma ancheun metodo effettivo di calcolo.

Ad esempio, dati due ideali (f) e (g) di k[x] si ha:

i) (f)+(g) = (h) dove h = MCD(f, g). Piu in generale, se I = (f1, . . . , fr), allorasi ha anche I = (f) con f = MCD(f1, . . . , fr).

ii) (f) ∩ (g) = (l) dove l = mcm(f, g);

iii) (f) ⊆ (g) ⇐⇒ g ∈ (f) ⇐⇒ g/f ossia se esiste q ∈ k[x] tale che f = gq.

iv) se I = (f), allora√I = (g) dove g = f

MCD(f,f ′) e f ′ e la derivata formale di f .

In tutti questi casi l’unico generatore dei vari ideali puo essere esplicitamente calco-lato mediante l’algoritmo di divisione euclidea, che permette di trovare il MCDdi due polinomi in una variabile. Inoltre:

11

12 Capitolo 2

v) Nell’anello quoziente k[x]/(f) due classi g1 e g2 coincidono se e solo se i restidella divisione di g1 per f e di g2 per f coincidono. Quindi la divisione fornisceanche un metodo per lavorare nei quozienti di k[x]. Il resto della divisione di gper f e un rappresentante privilegiato di g poiche in ogni classe vi e uno eun solo rappresentante di questo tipo. Quindi se d = ∂f , ogni classe e del tipoa0 + a1x+ . . . , ad−1xd−1.

vi) L’anello quoziente k[x]/(f) ha dimensione d come k-spazio vettoriale, poiche{xr | r = 0, . . . , ∂f − 1} e una sua base.

Esempio 2.1. Consideriamo un polinomio f ∈ R[x] e sia V la varieta definita daf in C. Se MCD(f, f ′) = 1, allora V e costituito da esattamente d = ∂f punti.Come osservato in vi), d e anche la dimensione di R[x]/(f) come R-spazio vettoriale.Vedremo in seguito come questa uguaglianza valga piu in generale per ogni varieta0-dimensionale, ossia costituita da un numero finito di punti, V in Rn (e anche inkn) e come essa fornisca un metodo effettivo per calcolare appunto la cardinalita diV .

Per eseguire materialmente la divisione tra due polinomi f e g per prima cosa liriordiniamo scrivendo i loro termini in ordine decrescente di grado:

f = anxn + an−1xn− 1 + · · ·+ a1x+ a0 , g = bmx

m + bm−1xm−1 + · · ·+ b1x+ b0;

quindi iniziamo a confrontare tra loro i termini di grado massimo anxn e bmxm: il

quoziente tra f e g ha come termine di grado massimo il quoziente anbm−1xn−m.

Si ottiene cosı il resto provvisorio f1 = f − anbm−1xn−mg e si procede nella

divisione ripetendo la stessa procedura a partire da f1.Anche l’anello k[x1, . . . , xn] e un dominio a fattorizzazione unica (Lemma di

Gauss), ma per n ≥ 2 non e un dominio a ideali principali (l’ideale (x1, x2) non eprincipale); quindi non puo essere neppure un dominio euclideo e non puo possedereuna divisione con resto come quella del caso di una sola variabile.

Cio nonostante, nei prossimi paragrafi vedremo come si puo costruire un or-dinamento dei monomi e una specie di divisione con resto che permetteranno digeneralizzare anche al caso di piu variabili alcune delle precedenti procedure. Saraad esempio possibile:

i. (Ideal membership) dati un ideale a e un elemento f di k[x1, . . . , xn],stabilire se f ∈ a;

ii. stabilire se due ideali di k[x1, . . . , xn] assegnati mediante insiemi di generatorisono uguali;

iii. stabilire se un polinomio f appartiene a√

a a partire da un insieme di gene-ratori di a;

M. Roggero

Algoritmo di divisione 13

iv. determinare√

a a partire da un insieme di generatori di a;

v. trovare una base di k[x1, . . . , xn]/a come k-spazio vettoriale;

vi. trovare in ogni classe di k[x1, . . . , xn]/a un rappresentante speciale;

vii. stabilire se due classi f e g di k[x1, . . . , xn]/a sono uguali.

viii. determinare la tabella delle operazioni in k[x1, . . . , xn]/a.

Molte altre procedure saranno poi esaminate nei capitoli successivi.

§ Ordinamento di monomi

Nel seguito denoteremo con Tn il sottoinsieme di k[x] = k[x1, . . . , xn] di tutti imonomi, ossia:

Tn = {xa11 x

a22 . . . xan

n = xa | a = (a1, . . . , an) ∈ Nn} .

L’usuale prodotto e una operazione interna a Tn (associativa e commutativa): pos-siamo allora parlare del monoide Tn.

Vogliamo ora definire relazioni d’ordine totale in Tn compatibili con tale strutturaalgebrica

L’applicazione log : xa 7→ a e un isomorfismo di monoidi tra Tn con l’operazionedi prodotto e Nn con l’operazione di somma componente per componente (ossiaall’usuale somma di vettori se pensiamo Nn come sottoinsieme di Rn). Le relazionid’ordine in Tn compatibili col prodotto corrispondono allora alle relazioni d’ordinein Nn compatibili con la somma.

Le relazioni d’ordine a cui siamo interessati dovranno soddisfare alcune propieta:

Definizione 2.2. Diciamo term order ogni ordinamento � su Tn che:

i) e un ordine totale ossia ∀xα, xβ ∈ Tn si ha:

xα � xβ oppure xβ � xα

ii) rispetta l’operazione di prodotto tra monomi ossia ∀xα, xβ, xγ ∈ Tn si ha:

xα � xβ =⇒ xαxγ � xβxγ .

iii) 1 � xα per ogni xα ∈ Tn

Nel seguito oltre a � useremo i simboli ≺, � e � col significato usuale.


14 Capitolo 2

Osservazione 2.3. Sia � un ordinamento totale in Tn che rispetta il prodotto.Allora vale la cancellazione ossia ∀xα, xβ , xγ ∈ Tn si ha

xαxγ ≺ xβxγ ⇐⇒ xα ≺ xβ.

Se infatti si avesse xα � xβ allora per ii) si avrebbe anche xαxγ � xβxγ .

La condizione iii) nella definizione di term order puo essere sostituita da altre,che, a seconda dei casi, possono risultare piu convenienti.

Proposizione 2.4. Sia � ordinamento totale in Tn che rispetta il prodotto. Sonoallora equivalenti:

iii1) 1 � xα per ogni xα ∈ Tn;

iii2) 1 ≺ xi per ogni indeterminata xi.

iii3) se xα divide xβ, allora xα � xβ.

iii4) � e un buon ordinamento.

Dim: La proprieta di cancellazione permette di vedere immediatamente l’equi-valenza tra iii1) e iii3); e inoltre immediata l’implicazione iii1)⇒ iii2). Per provarel’implicazione inversa iii2) ⇒ iii1) possiamo procedere per induzione sul grado deimonomi xα. Se il grado e 1, non c’e nulla da provare. Se si ha 1 � xα per tutti imonomi di un dato grado s, allora si ha anche 1 � xα � xixα e quindi la proprietavale anche per i monomi di grado s+ 1.

Proviamo ora che le prime condizioni sono equivalenti a iii4). Supponiamo che� sia un ordinamento totale che rispetta il prodotto ma tale che 1 � xi per unaqualche indeterminata. Allora

1 � xi � x2i � · · · � xn

i � . . .

e una catena decrescente infinita e quindi � non e un buon ordinamento.Supponiamo infine che valga iii3), ma che � non sia un buon ordine, ossia

supponiamo che esista una catena infinita strettamente decrescente

· · · � xαi � xαi+1 � . . .

Possiamo costruire una catena di ideali di k[x1, . . . , xn]:

· · · ⊆ ai = (xα1 , . . .xαi) ⊆ ai+1 = (xα1 , . . .xαi+1) ⊆ . . .

Notiamo che ad ogni passo otteniamo un ideale strettamente piu grande del prece-dente; infatti xαk+1 e piu piccolo di ogni xαi con i ≤ k e quindi per iii3) non puoessere un suo multiplo. Allora xαk+1 ∈ ak+1, ma non appartiene all’ideale ak da cui

M. Roggero


ak ( ak+1. Otteniamo cosı un assurdo, poiche una catena strettamente crescenteinfinita di ideali e in contrasto con la noetherianita di k[x1, . . . , xn].

Notiamo che ogni term order definisce in particolare un ordinamento totalesull’insieme delle variabili. A meno di un cambiamento di nome potremo sempresupporre che si abbia:

x1 � x2 � · · · � xn � 1.

Esempio 2.5. L’ordinamento piu naturale in Zn e quello lessicografico che indiche-remo con ≤Lex o semplicemente con ≤.

Per ogni coppia di elementi (α1, . . . , αn), (β1, . . . , βn) di Zn si ha (α1, . . . , αn) ≤(β1, . . . , βn) se vale una delle condizioni equivalenti:

i. (α1, . . . , αn) = (β1, . . . , βn) oppure αi = βi per ogni i < r e αr < βr;

ii. (α1− β1, . . . , αn− βn) e la n-upla nulla (0, . . . 0) oppure il suo primo elementonon nullo e negativo.

Ovviamente tale ordinamento in Zn induce un ordinamento anche sul sottoinsie-me Nn e quindi anche su Tn: chiameremo entrambi ordinamento lessicografico. Siverifica facilmente che Lex e un term order.

Due classi molto vaste di ordinamenti su Tn, che comprendono essenzialmentetutti i term orders che useremo, sono date dai risultati seguenti.

Proposizione 2.6. Sia A una matrice n×n a entrate intere di rango massimo. Larelazione �A in Nn data da:

(α1, . . . αn) �A (β1, . . . , βn) ⇐⇒ At(α1, . . . αn) ≤Lex At(β1, . . . , βn)

e una relazione d’ordine totale.Inoltre �A e un term order se e solo se il primo elemento non nullo in ogni

colonna di A e positivo.

Dim: Lasciamo al lettore la verifica che si tratta di un ordinamento totale; osser-viamo soltanto che la proprieta antisimmetrica discende dal fatto che la matrice harango massimo. Per provare la caratterizzazione dei term orders, ricordiamo la Pro-posizione 2.4. Grazie a tale risultato abbiamo che �A e un term order se e solo perogni j = 1, . . . , n si ha 1 �A xj e quindi se e solo se At(0, . . . , 1, 0, . . . , 0) ha il primoelemento non nullo positivo. Ma il primo elemento non nullo di At(0, . . . , 1, 0, . . . , 0)e proprio il primo elemento non nullo della colonna j-esima di A.


16 Capitolo 2

Proposizione 2.7. Sia w = (w1, . . . , wn) un vettore “generico”di Rn ossia tale chenessun wi sia combinazione lineare dei rimanenti a coefficienti interi.

Allora la relazione in Nn data da:

(α1, . . . αn) �w (β1, . . . , βn) ⇐⇒ w · (α1, . . . αn) ≤ w · (β1, . . . , βn)

e una relazione d’ordine totale.Inoltre �w e un term order se e solo wi > 0 per ogni i = 1, . . . , n.

Dim: Lasciamo al lettore la verifica che si tratta di un ordinamento totale; osservia-mo soltanto che la proprieta antisimmetrica discende dal fatto che per la genericitadelle coordinate di w si ha w ·α 6= 0 per ogni stringa non nulla α ∈ Zn. La caratte-rizzazione dei term orders discende poi immediatamente dal Lemma 2.4.

In alcuni caasi e utile considerare term orders definiti mediante vettori w nongenerici, ad esempio a componenti intere; in tal caso per avere un effettivo termorder e necessario introdurre un term order di sostegno che interviene ogni volta cheil vettore non e sufficiente ad assicurare la proprieta antisimmetria.

Esempio 2.8. L’unico term order su T1 (ossia sui monomi di k[x]) e quello dato dalgrado. Si ha infatti 1 < x e quindi, moltiplicando per xn, xn < xn+1. L’applicazionelog costituisce quindi una applicazione biunivoca che conserva l’ordine tra T1 e N.

Esempio 2.9. L’ordinamento lessicografico ≤Lex in Tn, per ogni n ≥ 2, si puo pen-sare come il term order ≤A scegliendo come A la matrice identita. Anche se Tn e uninsieme numerabile, tuttavia ≤Lex e molto diverso dall’ordinamento ≤ in N nel sensoche non vi e nessuna applicazione biunivoca tra N e Tn che conserva l’ordinamento.Infatti tra due numeri naturali qualsiasi si trovano sempre un numero finito di altrinumeri, mentre tra due monomi si possono trovare anche infiniti monomi:

1 < x2 < x22 < x3

2 < · · · < xk2 < · · · < x1.

L’esempio precedente mostra anche come vi siano sottoinsiemi di Tn (nel no-stro caso {x2, x

22, . . . , x

i2, . . . }) che non ammettono massimo rispetto a ≤Lex, pur

essendo superiormente limitati. Per questo motivo si preferisce talvolta un altroordinamento, strettamente legato a ≤Lex, ma in cui situazioni “spiacevoli” di questotipo non si verificano.

Esempio 2.10. Consideriamo la matrice:

A =

1 1 . . . . . . 1 11 0 . . . . . . 0 00 1 . . . . . . 0 0. . . . . . . . . . . . . . . . . .0 0 . . . . . . 1 0

M. Roggero


Il term order≤A ad essa associato confronta innanzi tutto il grado totale dei monomi:il monomio piu grande tra due e quello di grado maggiore; a parita di grado siconfrontano poi gli esponenti a partire da quelli delle indeterminate maggiori, comein Lex. Percio questo term order si chiama lessicografico graduato e si denota≤DegLex. In simboli:

xα ≤DegLex xβ se ∂(xα) < ∂(xβ) oppure ∂(xα) = ∂(xβ) e xα ≤Lex xβ

Poiche in ogni grado vi sono soltanto un numero finito di monomi, tra due monomise ne trovano solo un numero finito di altri. Si tratta quindi di un ordinamentomolto simile a quello di N.

Esempio 2.11. Vogliamo determinare tutti i term orders graduati su T2, ossia suimonomi di k[x, y], supponendo y ≺ x. Se moltiplichiamo questa relazione per ognimonomio di grado r− 1, otteniamo un unico possibile ordinamento tra i monomi digrado r:

yr ≺ xyr−1 ≺ · · · ≺ xr−iyi ≺ xr−i+1yi−1 ≺ · · · ≺ xr.

Quindi vi sono solo due possibili ordinamenti graduati, questo e quello ottenutoponendo x ≺ y. Tutte le matrici invertibili del tipo

(1 1a b

)individuano l’uno o l’altro

a seconda del segno di a− b.

Esempio 2.12. Vogliamo determinare tutti i term orders graduati su T3, ossia suimonomi di k[x, y, z], supponendo z ≺ y ≺ x. Se moltiplichiamo questa relazione perogni monomio di grado 1, otteniamo una serie di relazioni tra i monomi di secondogrado, ossia:

z2 ≺ yz ≺ xz ≺ xy ≺ x2 e anche z2 ≺ yz ≺ y2 ≺ xy ≺ x2

ma non otteniamo alcuna indicazione su quale sia il minore tra xz e y2. Porrey2 ≺ xz porta all’unico ordinamento ≤DegLex, ma vi e anche un term order per ilquale xz ≺ y2, ed e quello associato alla matrice:

A =

1 1 10 0 −10 −1 0

Esempio 2.13. Generalizzando l’esempio precedente, consideriamo la matrice:

A =

1 1 . . . . . . 1 10 0 . . . . . . 0 −10 0 . . . . . . −1 0. . . . . . . . . . . . . . . . . .0 −1 . . . . . . 0 0


18 Capitolo 2

Il term order ≤A su Tn ad essa associato, detto lessicografico inverso graduatoe denotato abitualmente con ≤RevDegLex, e un term order graduato, ossia confrontainnanzi tutto il grado totale dei monomi; nel caso in cui ∂(xα) = ∂(xβ), allora:

xα <RevDegLex xβ se ∃r (1 ≤ r ≤ n) tale che αi = βi per ogni i > r e αr > βr.

Nota bene: Il DegRevLex non e un ordinamento DegLex con una diversagerarchia delle variabili poiche in entrambi i casi abbiamo fissato xn ≺ · · · ≺ x1.

Esempio 2.14. Siano x1, . . . xn e y1, . . . , ym due insiemi di indeterminate e siaI = (f1, . . . , fr) un ideale di k[x,y]. Eliminare le variabili x da I vuol dire de-terminare tutti gli elementi di I (cioe tutte le combinazioni lineari di f1, . . . fr concoefficienti in k[x,y]), in cui compaiono solo le variabili y. In termini algebrici sitratta di determinare un insieme di generatori per l’ideale J = I ∩ k[y] dell’anellok[y]. Un ordinamento di eliminazione delle x e un term order rispetto al qualeun monomio in cui compaia anche una xi e maggiore di ogni monomio nelle solevariabili y. Rispetto a un ordinamento siffatto per ogni polinomio f ∈ k[x,y]:

il massimo dei monomi di f e yβ ⇐⇒ f ∈ k[y].

E un ordinamento di eliminazione delle x ad esempio il Lex in cui le variabili sonoordinate in modo che le xi siano piu grandi delle yj .

Piu in generale possiamo considerare due qualsiasi term orders �x e �y suimonomi nelle sole variabili x e y rispettivamente. Otteniamo un ordinamento dieliminazione delle variabili x nel modo seguente:

xαyβ � xα′yβ′ ⇐⇒ xα ≺x xα′ oppure xα = xα′ e yβ �y yβ′ .

§ Ideali monomiali

Lemma 2.15. Sia I un ideale di k[x1, . . . , xn] = k[x]. Le seguenti condizioni sonoequivalenti:

i. se f appartiene a I, allora ogni monomio di f appartiene a I;

ii. I e generato dall’insieme dei suoi monomi;

iii. I = (xα1 , . . . ,xαr).

Lasciamo al lettore la facile verifica dell’equivalenza delle tre condizioni; notiamosoltanto che la prova dell’implicazione 2. ⇒ 3. segue immediatamente dal Teoremadella Base di Hilbert. Si potrebbe anche dimostrare direttamente tale implicazione,nota come Lemma di Dickson e da essa dedurre poi il Teorema della Base.

M. Roggero


Definizione 2.16. Un ideale I di k[x1, . . . , xn] = k[x] che soddisfa le condizioniequivalenti del Lemma 2.15 si dice ideale monomiale. Si dice base di un idealemonomiale I ogni insieme di generatori monomiali di I che sia minimale, ossia taleche nessun suo sottoinsieme proprio genera I.

Proposizione 2.17. Un ideale monomiale I possiede un’unica base {xα1 , . . . ,xαr}.

Dim: Possiamo ottenere un insieme di generatori minimale a partire da un qualsiasiinsieme (finito) di generatori monomiali, cancellando ogni monomio che sia multiplodi un altro.

Se poi {xα1 , . . . ,xαr} e {xβ1 , . . . ,xβs} sono due basi di I, allora per ogni i ≤ ril monomio xαi dovrebbe dividere un monomio xβj , il quale a sua volta dovrebbedividere un monomio xαi′ . Per la proprieta transitiva, xαi dovrebbe dividere xαi′ .Poiche per costruzione nessun monomio di una base puo dividerne un altro, alloraxαi = xαi′ e quindi xαi = xβj .

Segue immediatamente dalla definizione che un ideale monomiale e un idea-le omogeneo rispetto ad una qualsiasi graduazione, standard o pesata, anche noncompatibile col term order fissato.

Se I = (xα1 , . . . ,xαr) e un ideale monomiale, e molto semplice trovare dellestrategie operative per rispondere ai problemi posti all’inizio di questo capitolo. Persapere se un polinomio f appartiene a I, basta controllare se ogni termine di f emultiplo di uno dei monomi xαi . Una base di k[x1, . . . , xn]/I come k-spazio vettorialee costituita dalle classi dei monomi che non appartengono a I, ossia che non sonomultipli di alcun xαi ; quindi per determinare un rappresentante speciale (unico) inogni classe g di k[x1, . . . , xn]/I basta cancellare da g ogni termine che e multiplo diuno degli xαi .

Vedremo ora come un term order permetta di trovare strategie analoghe a queste,ma applicabili anche nel caso di un ideale qualsiasi.

§ Ideali iniziali e basi di Grobner

Introduciamo alcune notazioni. Sia f un polinomio non nullo di k[x1, . . . , xn].Supponiamo fissato un term order in Tn.

Definizione 2.18. Consideriamo l’unica scrittura f =∑s

j=1 ajxγj con 0 6= aj ∈ kper ogni j = 1, . . . , s. Si dice:

• monomio iniziale (in inglese leading monomial) di f , denotato Lm(f) ilmassimo (rispetto a �) degli xγj ;


20 Capitolo 2

• termine iniziale (in inglese leading term) di f , denotato Lt(f) il termineajxγj , dove xγj = Lm(f);

• coefficiente iniziale o coefficiente direttivo (in inglese leading coeffi-cient) di f , denotato Lc(f) il coefficiente aj in f di xγj = Lm(f).

Valgono le ovvie relazioni per ogni coppia di polinomi non nulli:

i. Lt(f) = Lc(f)Lm(f);

ii. Lm(fg) = Lm(f)Lm(g) , Lc(fg) = Lc(f)Lc(g) , Lt(fg) = Lt(f)Lt(g);

iii. Lm(f + g) � max{Lm(f) , Lm(g)} e vale “=”ogni volta che Lm(f) 6= Lm(g).

Definizione 2.19. Se I e un ideale di k[x1, . . . , xn], si dice ideale iniziale di I(rispetto a �) l’ideale monomiale In(I) generato da

{xγ ∈ Tn | xγ = Lm(f) per qualche f ∈ I}

Proposizione 2.20. Sia I un ideale di k[x1, . . . , xn]. Consideriamo un insieme digeneratori monomiali {xα1 , . . . ,xαr} di In(I) e per ogni i , (1 ≤ i ≤ r) sia fi ∈ Itale che Lm(fi) = xαi.

Allora I = (f1, . . . , fn).

Dim: Supponiamo per assurdo che ci siano polinomi di I che non si possono scriverecome combinazione lineare a coefficienti in k[x1, . . . , xn] degli fi; nell’insieme di talipolinomi, ve ne e (almeno) uno il cui monomio iniziale e minimo rispetto al prefissatoterm order: sia f un polinomio siffatto.

Per costruzione si ha Lm(f) = xβ ∈ In(I) = (xα1 , . . . ,xαr) e quindi vi sono unindice s ≤ r e un monomio xγ tali che xβ = xγ · xαs . Il polinomio f −Lc(f) · xγ · fs

appartiene quindi ad I, non e combinazione degli fj (altrimenti anche f lo sarebbe)e ha monomio iniziale minore di f , contro l’ipotesi.

Le proprieta sopra provate per gli ideali monomiali e le basi monomiali nonvalgono per ideali qualsiasi o per insiemi qualsiasi di generatori di un ideale, comemostra l’esempio seguente.

Esempio 2.21. Consideriamo l’ideale I = (x, y) di k[x, y]. Si tratta di un idealemonomiale e {x, y} e la sua base. Per ogni intero r ≥ 1, l’ideale I possiede an-che l’insieme minimale di generatori Br = {x , y − y2 , y2 − y3 , . . . , yr−1 − yr , yr}costituito da r + 1 polinomi.

Se fissiamo ad esempio l’ordinamento DegLex e l’intero r = 2, l’insieme deimonomi iniziali di B2 e {x = Lm(x) , y2 = Lm(y − y2) = Lm(y2)} = {x, y2} chenon costituisce un insieme di generatori per In(I) = I.

M. Roggero


Esempio 2.22. Consideriamo come prima l’ordinamento DegLex e sia I l’ideale dik[x, y, z] generato da {f1 = xy − y + 1 , f2 = y2z − x}.

Il polinomio g = x2 + yz − x appartiene ad I, poiche g = yz · f1 − (x − 1) · f2;pero x2 = Lm(g) /∈ (xy = Lm(f1) , y2z = Lm(f2)).

Definizione 2.23. Chiamiamo base di Grobner o base standard (in breve G-base) di un ideale I di k[x1, . . . , xn] (rispetto a un fissato term order) un insieme dipolinomi {f1, . . . , fr} ⊂ I tali che (Lm(f1), . . . , Lm(fr)) = In(I).

Un base di Grobner si dice ridotta se per ogni i ≤ r si ha Lc(fi) = 1 e Lm(fi)non divide alcun monomio che compare in fj se j 6= i.

Proposizione 2.24. Ogni ideale I ha una sola base di Grobner ridotta.

Dim: Possiamo intanto osservare che due G-basi ridotte hanno lo stesso numero dielementi (tanti quanti ne ha l’insieme minimale di generatori monomiali di In(I)).Se B1 = {f1, . . . , fr} e B2 = {g1, . . . , gr} sono due basi di Grobner ridotte, possiamosupporre, riordinando eventualmente gli indici, che Lm(fi) = Lm(gi) per ogni i ≤ r.Allora il polinomio fi−gi deve essere nullo, perche altrimenti il suo monomio iniziale,che compare in fi oppure in gi, dovrebbe essere multiplo di un monomio inizialeLm(fj) = Lm(gj), contro l’ipotesi.

In virtu della Proposizione 2.20, una G-base di I e anche un insieme (non neces-sariamente minimale) di generatori di I. Quando diremo che un insieme di polinomiB e una base di Grobner senza specificare qual e l’ideale, l’ideale sottinteso saraquello generato da B.

§ L’algoritmo di divisione

In questo paragrafo supporremo fissato un term order � in k[x1, . . . , xn] con la solitaconvenzione sull’ordine delle indeterminate.

Vogliamo estendere all’anello k[x1, . . . , xn] l’algoritmo di divisione che in k[x]porta a determinare il quoziente e il resto tra due polinomi.

Sia B = {f1, . . . , fr} un insieme finito di polinomi e sia I l’ideale da essi generato.Preso un qualsiasi polinomio g possiamo considerare la sua scrittura g =

∑si=1 cjx

αj

con cj 6= 0 e xαj � xαj−1 . Cerchiamo un monomio di g che sia multiplo di uno deimonomi Lm(fi): se non ce ne sono diciamo che g non e riducibile mediante B; incaso contrario operiamo un passo di riduzione di g mediante B nel modo seguente.

Sia xαh il maggiore dei monomi di g divisibile per qualche monomio iniziale deipolinomi in B: sia ad esempio

xαh = xβ · Lm(fi).


22 Capitolo 2

Costruiamo il nuovo polinomio g1 = Lt(fi)g− chxβ ·fi; indicheremo la relazione cosıottenuta col simbolo:

gB−→ g1.

In g1 compaiono gli stessi monomi di g maggiori di xαh , ma non copare xαh . Pos-siamo poi ripetere il procedimento a partire da g1 fino a che e possibile, ossia fino ache non otteniamo un polinomio non ulteriormente riducibile.

Ad ogni passo si prende in considerazione un monomio piu piccolo di quelloesaminato al passo precedente; tali monomi formano una successione decrescenteche e quindi finita, grazie al fatto che un term order e un buon ordine.

Useremo il simbolog

B−→+ g′

per dire che con un tale procedimento possiamo passare dal polinomio g a g′.

Osservazione 2.25. Fissati un term order � in Tn e un insieme di polinomi B ⊂k[x], la costruzione precedente individua su k[x] una relazione d’ordine (non totale)data da g1 � g2 se g1 = g2 oppure g1

B−→+ g2.Analogamente possiamo costruire un grafo orientato G (B) i cui vertici sono i

polinomi e i cui spigoli sono le relazioni g B−→ g′. In particolare fissato un polinomiog possiamo considerare il sottografo orientato Gg(B) il cui insieme dei vertici e

{g′ ∈ k[x] | g B−→+ g′} ∪ {g} che risulta essere un grafo finito.In caso contrario, potremmo considerare, nell’insieme dei polinomi g per cui

Gg(B) e infinito, un polinomio g0 che ha monomio iniziale minimo. Se al primo passodi riduzione di g0 non si prende in considerazione Lm(g0), il polinomio g0 − Lt(g0)ha la stessa proprieta di g0 ma monomio iniziale piu piccolo, contro l’ipotesi diminimalita di Lm(g0). Quando, d’altra parte, si prende in considerazione Lm(g0),il primo passo di riduzione puo essere effettuato al piu in r = card(B) modi diversi;quindi almeno uno dei polinomi ottenuti dopo un primo passo di riduzione soddisfala stessa proprieta e ha monomio iniziale minore, di nuovo contro l’ipotesi.

Di conseguenza, in ciascun insieme Gg(B) vi sono solo un numero finito dipossibili polinomi non ulteriormente riducibili.

Il procedimento di riduzione prima definito risulta in generale insoddisfacente,in quanto non porta a determinare un unico resto e non risolve il problema dell’idealmembership.

Esempio 2.26. Consideriamo l’ordinamento DegLex in k[x, y] e l’insieme di poli-nomi B = {f1 = 2xy2 + 4y2 + 3x, f2 = y2 − 2y − 2}.

Il polinomio g = 2x3y3 + 4y2 si puo ridurre ai due polinomi (entrambi nonulteriormente riducibili)

g1 = −3x3y − 24x2y − 16x2 + 8y + 8

M. Roggero


con la procedura g1 = (((g − x2yf1) + 4x2yf2) + 8x2f2)− 4f2, ma anche a

g2 = 12x3y + 8x3 + 8y + 8

con la procedura g2 = ((g − 2x3yf2)− 4x3f2)− 4f2.Il polinomio f = f1 − (2x + 4)f2 = 4xy + 7x + 8y + 8 appartiene ovviamente

all’ideale I generato da B; pero, se non conoscessimo gia la sua scrittura come com-binazione di f1 e f2, il procedimento di riduzione non ci permetterebbe di ricavarla,poiche anzi f non e riducibile mediante B.

Teorema 2.27. Siano � un term order in Tn e B = {f1, . . . , fr) un sottoinsiemefinito di un ideale I di k[x1, . . . , xn]. Le seguenti affermazioni sono equivalenti:

i. B e una base di Grobner di I;

ii. ∀ g ∈ I, g 6= 0, ∃fi ∈ B tale che Lm(fi) divide Lm(g);

iii. ∀ g ∈ I, g 6= 0, si ha g B−→+ 0;

iv. ∀ g ∈ I, g 6= 0, si ha g =∑r

i=1 hifi con Lm(g) = maxi{Lm(hifi)}.

Dim: 4. =⇒ 1. e 1. =⇒ 2. seguono immediatamente dalla definizione di base diGrobner.

“2. =⇒ 3.”Supponiamo valga 2.; allora ogni polinomio non nullo di I puo essereridotto mediante B.

Come abbiamo gia visto, ogni catena di riduzioni e finita. Quindi se g ∈ I, esisteg′ non ulteriormente riducibile tale che g B−→+ g′; per costruzione g′ = g−

∑hifi e

quindi anche g′ appartiene a I. Allora g′ = 0.“3. =⇒ 4.”Per come e stato definito l’algoritmo di riduzione, se g B−→+ 0, al-

lora g =∑t

j=1 hjfij dove al crescere di i i monomi Lm(hjfij ) sono strettamentedecrescenti. In particolare Lm(g) = Lm(h1fi1) = maxj{Lm(hjfij ) }. Raccogliendoi coefficienti di ciascun fi otteniamo l’asserto.

Corollario 2.28. Fissato un term order in Tn, siano I un ideale di k[x1, . . . , xn] eB una base di Grobner di I.

Allora per ogni polinomio g ∈ k[x1, . . . , xn], esiste un unico polinomio nonulteriormente riducibile g′ tale che g B−→+ g′.

Inoltre tale polinomio g′ e invariante nella classe g + I.

Dim: Supponiamo che si abbia gB−→+ g′ e h B−→+ h′ con g − h ∈ I. Per come

e stato definito l’algoritmo di riduzione si ha g′ = g −∑lifi e quindi g − g′ ∈ I;

analogamente anche h− h′ ∈ I e quindi g′ − h′ ∈ I.


24 Capitolo 2

In virtu del risultato precedente, g′−h′ B−→+ 0. Se g′ e h′ non sono ulteriormenteriducibili, allora nessun monomio che compare in essi e multiplo di uno dei Lm(fi)e anche g′ − h′ non e ulteriormente riducibile. Quindi g′ − h′ = 0.

Definizione 2.29. L’unico polinomio non ulteriormente riducibile modulo B nellaclasse g+ I si dice resto (per analogia col caso di una sola indeterminata) o formanormale di g modulo B.

I risultati precedenti mostrano che le basi di Grobner sono la risposta ai problemiposti all’inizio di questo capitolo. Tramite una G-base possiamo infatti sapere dopoun numero finito di passi di riduzione se un dato polinomio appartiene o meno a Ie possiamo anche trovare un rappresentante speciale in ogni classe di equivalenza ink[x1, . . . , xn]/I

Proposizione 2.30. Siano I un ideale di k[x1, . . . , xn] e J il suo ideale inizialerispetto a un prefissato un term order �.

1) Le classi in k[x1, . . . , xn]/I dei monomi di Tn \ J sono tutte distinte e costi-tuiscono una base di k[x1, . . . , xn]/I come k-spazio vettoriale.

2) k[x1, . . . , xn]/I e k[x1, . . . , xn]/J sono isomorfi e quindi hanno la stessa di-mensione come k-spazi vettoriali. Un isomorfismo di k-spazi vettoriali (maNON di anelli!) e dato da f + I 7→ f ′ + J , dove f ′ e la forma normale di f .

Dim: Per 1) basta osservare che in ogni classe f + I vi e uno e un solo rappre-sentante f ′ (la forma normale di f) i cui monomi appartengono tutti a Tn \ J ; 2)segue immediatamente osservando che tale mappa e k-lineare e trasforma la basemonomiale di k[x1, . . . , xn]/I presentata al punto precedente nella base monomialedi k[x1, . . . , xn]/J .

Vediamo ora una importantissima conseguenza applicativa del risultato prece-dente, che riprenderemo e preciseremo nei capitoli successivi.

Corollario 2.31. Siano V una varieta algebrica e I = I (V ) l’ideale corrispondente.Supponaimo per semplicita V ⊆ kn e I ⊆ k[x] con k campo algebricamente chiuso.

Allora V e un insieme finito di punti se e soltanto se k[x]/I ha dimensione finitacome k-spazio vettoriale.

In tal caso si ha card(V ) = dimk(k[x]/I).

Dim: Se V e infinita vi sara almeno una variabile xi tale che le i-esime coordinatedei punti di V assumono infiniti valori diversi: sia xn. In tal caso le classi in k[x]/Idi 1, xn, xn

2, . . . xnm, . . . sono linerarmente indipendenti (in caso contrario, se vi

fosse una relazione∑t

j=0 cjxjn = 0 allora

∑tj=0 cjx

jn ∈ I = I (V ) e quindi tutti i

M. Roggero


punti di V avrebbero n-esima coordinata scelta tra le t soluzioni di∑t

j=0 cjxjn = 0,

contro l’ipotesi.

Supponaimo ora che V sia finito e costituito da r punti {P1, . . . , Pr}. A meno diun cambio di coordinate possiamo supporre che le n-esime coordinate dei punti Pj

siano tutte distinte. Proviamo che dimk(k[x]/I) = r e che una base di k[x]/I comek-spazio vettoriale e costituita dalle classi di 1, xn, . . . , x

r−1n . Fissiamo il term order

Lex con il solito ordinamento delle variabili 1 ≺ xn ≺ · · · ≺ x1 e procediamo perinduzione su r.

Se r = 1, allora V = {P (a1, . . . , an)} e quindi I (P ) = (x1 − a1, . . . , xn − an) eIn(I) = (x1, . . . , xn). L’insieme differenza Tn \ In(I) contiene soltanto 1 e da ciosegue l’asserto grazie alla Proposizione 2.30.

Supponiamo l’asserto vero per r−1 punti e proviamo che vale anche per r punti.Siano V1 = {P1, . . . , Pr−1} e I1 = I (V1) in modo che V = V1 ∪ {Pr(a1, . . . , an)} e Ie costituito dai polinomi di I1 che si annullano anche in Pr.

Grazie all’ipotesi induttiva, sappiamo che ogni monomio xα /∈ {1, xn, . . . , xr−2n }

e il monomio iniziale di un qualche polinomio g ∈ I1. Se xβ /∈ {1, xn, . . . , xr−1n },

allora si puo sicuramente scrivere xβ = xα ·xi con xα /∈ {1, xn, . . . , xr−2n }. Preso un

g ∈ I1 tale che Lm(g) = xα, allora f = g(xi − ai) ∈ I, poiche f si annulla in tuttii punti di V ; infatti f(Pj) = g(Pj)(aji − ai) = 0 se j ≤ r − 1 perche g(Pj) = 0 ed’altra parte f(Pr) = g(Pr)(ai − ai) = 0.

Si ha quindi xβ = Lm(g)Lm(xi − ai) = Lm(f) ∈ In(I) ossia Tn \ In(I) ⊆{1, xn, · · · , xr−1

n }. D’altra parte le classi di 1, xn, · · · , xr−1n sono linearmente indi-

pendenti in k[x]/I, poiche in caso contrario dovrebbe esservi in I un polinomio deltipo h(xn) =

∑r−1i=0 cix

in (di grado < r) avente tra le sue radici le r distinte n-esime

coordinate dei punti di V .

Come osservazione finale, notiamo che avremmo potuto utilizzare un term orderqualsiasi oppure un’altra delle indeterminate al posto di xn; pero con il Lex e lavariabile “piu piccola ” xn, la base di k[x]/I trovata e costituita da monomi chesono tutti in forma normale rispetto a I. Utilizzando tale base, ogni classe di k[x]/Isi scrive in modo unico come la classe di un polinomio del tipo

∑r−1i=0 bix

in con bi ∈ k,

dove tale polinomio e proprio l’unico in forma normale rispetto a Lex nella classe.

§ L’algoritmo di Buchberger

Vediamo ora come e possibile calcolare espressamente una base di Grobner di unideale di cui sia noto un inseme di generatori.


26 Capitolo 2

Definizione 2.32. Sia � un term order in k[x1, . . . , xn] = k[x] e siano g1, g2 ∈ k[x].Si dice S-polinomio di g1 e g2 la loro combinazione lineare

S(g1, g2) = axαg1 − bxβg2

con coefficienti i termini axα = Lt(g2)MCD(Lm(g1),Lm(g2)) e bxβ = Lt(g1)

MCD(Lm(g1),Lm(g2)) .Quindi a = Lc(g2), b = Lc(g1) e Lt(xαg1) = Lt(xβg2) = MCM(Lt(g1), Lt(g2)).

Teorema 2.33 (Buchberger). Si consideri fissato un term order in k[x]. Siano Iun ideale di k[x] e B = {g1, . . . , gr} un insieme di generatori di I.

Allora B e una base di Grobner per I se e soltanto se per ogni coppia di elementigi, gj di B si ha S(gi, gj)

B−→+ 0.

Dim: La condizione e ovviamente necessaria, poiche S-polinomi di elementi di Istanno in I e quindi, se B e una G-base, si riducono a 0.

Proviamo allora che e anche una condizione sufficiente. Sia f un elemento nonnullo di I. Poiche il numero di possibili passi di riduzione a partire da f e finito, cibastera provare che si puo eseguire almeno un passo di riduzione su f . Per ipotesi sipuo scrivere f come

∑higi in molti modi diversi: scegliamone una in cui il monomio

m, massimo tra i Lm(higi) compare il minor numero di volte. Affermiamo che intale scrittura m compare una sola volta. In caso contrario, sia m = Lm(h1g1) =Lm(h2g2); quindi m e un multiplo di MCM(Lt(g1), Lt(g2)) ossia h1 e un multiplodel coefficiente di g1 in S(g1, g2). Allora nella scrittura di f come combinazione dei gi

il prodotto Lt(h1)g1 puo essere sostituito con una espressione del tipo m′(Lm(h2)g2+∑h′igi) dove

∑h′igi e la riduzione a 0 di S(g1, g2) e quindi ogni monomio m′Lm(h′igi)

e strettamente piu piccolo di m. In questo modo otterremo un’altra scrittura di fin cui m compare meno che nella precedente, contro l’ipotesi.

Se allora m compare una sola volta, allora coincide con Lm(f): sia Lm(f) =Lm(hr)Lm(gr). Possiamo percio eseguire il primo passo di riduzione f B−→ f −Lt(hr)gr.

Algoritmo di Buchberger per determinare una G-base di un ideale a partireda un insieme di generatori B = {f1, . . . , fn}. Fissato un qualche ordine tra lecoppie (fi, fj) si calcola l’S-polinomio S(fi, fj) e quindi una sua riuzione completa gij

rispetto a B. Se gij = 0, si passa a considerare la coppia successiva. In caso contrariosi considera l’insieme di generatori B′ = B ∪ {gij}. L’algoritmo termina perchead ogni passo i monomi iniziali degli elementi degli insiemi B via via consideratigenerano ideali monomiali sempre piu grandi.

Lasciamo come esercizio al lettore la dimostrazione del seguente risultato, che cisara utile in seguito.

Proposizione 2.34. Si consideri fissato un term order e siano I e J ideali di k[x].Allora:

M. Roggero


i) I = J ⇐⇒ I e J hanno la stessa G-base ridotta.

ii) Supponiamo I ⊆ J . Allora: I = J ⇐⇒ In(I) = In(J).

Infine, qualche parola relativamente al caso graduato. E intanto evidente chegli ideali monomiali (e quindi in particolare, gli ideali iniziali) sono ideali omogeneirispetto ad ogni possibile graduazione. Vale inoltre:

Proposizione 2.35. Se I e un ideale di k[x] omogeneo rispetto ad una graduazioneδ, allora la G-base ridotta di I rispetto ad un qualsiasi term order e costituita dapolinomi omogenei rispetto a δ.

Dim: Possiamo costruire la G-base ridotta mediante l’algoritmo di Buchbergerconsiderando inizialmente un insieme di generatori omogenei di I. Notiamo poi chel’S-polinomio di due polinomi omogenei e omogeneo. Piu in generale, ogni passo diriduzione utilizzato dall’algoritmo di Buchberger trasforma un insieme di generatoriomogenei in un altro insieme di generatori omogenei.


Capitolo 3

Applicazioni algebriche e geometriche

§ Eliminazione di variabili

Sia I un ideale di k[x,y]. Eliminare le variabili y da I vuol dire determinare l’idealeJ = I ∩ k[x] di k[x]. Spesso le variabili da eliminare sono chiamate parametri. Perdeterminare J possiamo procedere nel modo indicato dal seguente risultato.

Proposizione 3.1. Si consideri fissato un term order di eliminazione delle y.Allora:

1) Per ogni f ∈ k[x,y] si ha: f ∈ k[x] ⇐⇒ Lm(f) ∈ k[x].

2) Per ogni ideale I di k[x,y] una G-base di I ∩ k[x] e data dai polinomi di unaG-base di I in cui non compaiono le y.

Dim: Della prima affermazione proviamo soltanto l’implicazione non banale. SeIn(f) = xα, allora per ogni monomio xα′yβ′ che compare in f si ha xα � xα′yβ′ equindi β′ = (0, . . . , 0), come volevasi.

Per la seconda affermazione poi basta ricordare che ogni polinomio g ∈ I ∩ k[x],in quanto elemento di I si riduce a 0 mediante una G-base di I; nel procedimentodi riduzione pero possono intervenire effettivamente solo elementi della G-base il cuitermine iniziale non contiene le variabili y. Grazie al punto precedente, g si riduceusando solo quegli elementi della G-base in cui le y non compaiono.

Per eliminare le variabili y dall’ideale I basta allora calcolare una G-base B di Irispetto ad un ordinamento di eliminazione delle y; quindi I∩k[x] e l’ideale generatoda B ∩ k[x].

§ Varieta parametriche

Consideriamo dei polinomi f1(y), . . . , fn(y) di k[y] = k[y1, . . . , ym]. Mediante le fj

possiamo costruire le seguenti due applicazioni. Un omomorfismo di k-algebre:

φ : k[x1, . . . , xn]→ k[y1, . . . , ym] dato da φ(xi) = fi(y).

28

Applicazioni algebriche e geometriche 29

Notiamo che φ, in quanto omomorfismo di anelli e di k-spazi vettoriali, e univoca-mente e ben definito per ogni possibile scelta delle fi.

Il nucleo di φ e l’ideale di tutti i polinomi g(x1, . . . , xn) tali che g(f1(y), . . . , fn(y))e il polinomio nullo.

Abbiamo poi una mappa:

ψ : km → kn data da ψ((a1, . . . , am)) = (f1(a1, . . . , am), . . . , fn(a1, . . . , am)).

L’immagine di ψ e la varieta algebrica definita dalle equazioni parametriche:x1 = f1(y)x2 = f2(y)...xn = fn(y)

Si tratta proprio della varieta il cui ideale e Ker(φ). Per determinare tale idealepossiamo allora eliminare le variabili y dall’ideale di k[x,y] generato da xi − fi(y)(utilizzando quindi un ordinamento di eliminazione).

Osserviamo che vi sono molte equazioni parametriche diverse che definisconouna stessa varieta: un esempio banale (ma ve ne sono anche di meno ovvi) si puoottenere moltiplicando tutte le fi per uno stesso fattore costante.

Un caso particolarmente importante e quello in cui i polinomi fi sono dei monomi,ossia fi = yαi . In tal caso la G-base ridotta dell’ideale I = Ker(φ) rispetto adun qualsiasi term order e costituita da binomi ossia da differenze di due monomixu − xv.

Definizione 3.2. Un ideale I di k[x] generato da binomi si dice ideale torico; unavarieta il cui ideale e torico si dice varieta torica affine.

Il fatto che una varieta parametrizzata mediante monomi sia torica e conseguenzadel risultato seguente.

Proposizione 3.3. Sia I un ideale di k[x] generato da binomi, ossia:

I = (xα1 − xβ1 , . . . ,xαr − xβr).

Allora la G-base ridotta di I rispetto ad un qualsiasi term order e costituita dabinomi.

Quindi anche ogni ideale di eliminazione di variabili da I e ancora generato dabinomi.

Dim: La costruzione della G-base ridotta (e di conseguenza l’eliminazione di varia-bili) puo essere ottenuta a partire da un insieme B di generatori monomiali mediantedue sole operazioni:


30 Capitolo 3

i) la costruzione di S-polinomi di elementi di B;

ii) passi di riduzione a partire da un binomio f ∈ B usando gli elementi di B\{f}.

Proviamo che in entrambi i casi, si ottengono ancora binomi.Se f1 = xα1−xβ1 , f2 = xα2−xβ2 ∈ B (dove il primo monomio e maggiore del se-

condo), il loro S-polinomio e xγ1f1−xγ2f2 dove xγ1xα1 = xγ2xα2 = mcm(xα1 ,xα2).Allora S(f1, f2) = xγ2xβ2 − xγ1xβ1 e ancora un binomio.

Se f = xγ − xδ ∈ B e uno dei suoi monomi e multiplo del monomio di testa dif1 = xα1 − xβ1 ∈ B (f1 6= f), sia xδ = xα1xδ′ , il primo passo riduzione e f − xδ′f1

che e ancora un binomio.

§ Numeri algebrici

Accenniamo brevemente ad una applicazione dei metodi computazionali, in partico-lare dell’eliminazione delle variabili, all’aritmetica.

Siano α e β due numeri complessi algebrici si Q. E noto che i numeri algebriciformano un campo. Sono numeri algebrici anche tutti quelli che si possono ottenereda α e β mediante le operazioni, ad esempio α+β e α ·β. Vediamo quale puo essereun metodo veloce per ottenere un polinomio in Q[x] di cui α+ β oppure α · β sianoradici.

Consideriamo i polinomi p(x), q(x) ∈ Q[x] tali che p(α) = 0 e q(β) = 0. Introdu-ciamo due altre variabili y, z; vogliamo determinare un polinomio h(z) ∈ Q[z] taleche h(α+ β) = 0. Un polinomio siffatto puo essere ottenuto eliminando le variabilix e y dall’ideale I = (p(x), q(y), z− x− y). Poiche V (I) ha solo un numero finito dipunti (al piu ∂(p) · ∂(q) punti), allora I ∩ k[z] non e ridotto al solo ideale nullo.

Per il prodotto α · β si procede allo stesso modo eliminando x e y dall’ideale(p(x), q(y), z − xy).

§ Somma di ideali

Siano I e J due ideali di k[x]. L’ideale somma I + J e il minimo ideale che contieneI ∪ J . In generale I ∪ J non e un ideale (piu precisamente non lo e a meno che unodei due ideali sia contenuto nell’altro): l’ideale somma e allora l’ideale generato daI ∪ J .

Si verifica facilmente che:

I + J = {f + g | f ∈ I, g ∈ J}.

M. Roggero


Se I = (f1, . . . , fr) e J = (g1, . . . , gs) sono assegnati mediante degli insiemi digeneratori, l’ideale somma e

I + J = (f1, . . . , fr, g1, . . . , gs).

Notiamo che se anche i due insiemi di generatori di I e J assegnati sono loroG-basi (rispetto ad un prefissato term order), non e detto in generale che la lorounione sia una G-base per l’ideale somma.

Lemma 3.4. Siano I, J ideali di k[x] e V , W varieta di Kn. Allora:

1) V (I + J) = V (I) ∩ V (J).

2) I (V ∩W ) ⊇ I (V ) + I (W ).

Dim: 1) Se P ∈ V (I) ∩ V (J), allora per ogni elemento f + g ∈ I + J con f ∈ I eg ∈ J , si ha f(P )+g(P ) = 0 e quindi P ∈ V (I+J). D’altra parte, V (I+J) ⊆ V (I)poiche I + J ⊇ I (e analogamente V (I + J) ⊆ V (J) poiche I + J ⊇ J).

2) Se f ∈ I (V ) e g ∈ I (W ), ossia se f si annulla in tutti i punti di V e g siannulla in tutti i punti di W , allora entrambi si annullano nei punti dell’intersezionee quindi f + g si annulla su V ∩W .

Notiamo infine che non sempre si ha I (V ∩ W ) = I (V ) + I (W ). Se K ealgebricamente chiuso, si puo provare, grazie al Nullstellensatz, che per ottenereI (V ∩W ) e necessario (e sufficiente) passare al radicale, ossia:

I (V ∩W ) =√

I (V ) + I (W ).

§ Intersezione di ideali

Siano I e J ideali di k[x]. L’intersezione insiemistica di I e J e ancora un ideale dik[x] che possiamo quindi denotare semplicemente con I ∩ J . L’intersezioni di idealiha un importante significato geometrico.

Lemma 3.5. Siano I, J ideali di k[x] e V , W varieta di Kn (K estensione di k).Allora:

1) V (I ∩ J) = V (I) ∪ V (J).

2) I (V ∪W ) = I (V ) ∩I (W ).


32 Capitolo 3

Dim: Per il primo punto proviamo soltanto l’inclusione non banale. Sia P un puntodi V (I ∩ J) e supponiamo che P /∈ V (I). Esiste allora un polinomio f ∈ I tale chef(P ) 6= 0. Per ogni g ∈ V (J) si ha fg ∈ I ∩ J e quindi (fg)(P ) = 0. Ne seguequindi g(P ) = 0, poiche k un campo, e quindi P ∈ V (J), come volevasi.

Il secondo punto segue poi immediatamente dal primo.

Per determinare l’ideale intersezione I ∩J , introduciamo una variabile ausiliaria.

Proposizione 3.6. Siano I e J ideali di k[x] e sia a l’ideale di k[x, w] generato datutti i prodotti wf con f ∈ I e (1− w)g con g ∈ J . Allora:

I ∩ J = a ∩ k[x].

Dim: Osserviamo intanto che se I = (f1, . . . , fr) e J = (g1, . . . , gs), allora:

a = (wf1, . . . , wfr, (1− w)g1, . . . , (1− w)gs).

Quindi e immediato scrivere esplicitamente un insieme di generatori per a, noti degliinsiemi di generatori per I e per J .

Se f ∈ I ∩ J , allora f appartiene anche all’ideale (wI + (1 − w)J) di k[x, w]poiche si ha f = wf + (1− w)f .

Per provare l’altra inclusione, osserviamo che ogni elemento f ∈ a e del tipof =

∑wfi(x)pi(x, w) +

∑(1− w)gj(x)qj(x, w). Se in particolare f ∈ k[x], allora il

secondo membro rimarra invariato sostituendo in esso un qualsiasi elemento λ ∈ ka w. In particolare per w = 1 si ha f =

∑fi(x)pi(x, 1) =

∑fi(x)p′i(x) e quindi

f ∈ I. Analogamente per w = 0 si ha f =∑gj(x)qj(x, 0) =

∑gj(x)q′j(x) da cui

f ∈ J .

Per determinare I ∩ J a partire da un inseme di generatori {f1, . . . , fr} di I euno {g1, . . . , gr} di J , basta allora trovare una G-base di a a partire dall’insiemedi generatori {wf1, . . . , wfr, (1 − w)g1, . . . , (1 − w)gr} rispetto ad un term order dieliminazione per w.

In particolare se V = V (f) e W = V (g), allora V ∪ W = V ((f) ∩ (g)) =V (m.c.m.(f, g)): la tecnica per determinare l’ideale intersezione permette quindi ditrovare anche il minimo multiplo comune a due polinomi.

Questa procedura, che fornisce un insieme di generatori per l’ideale intersezionea partire da generatori dei due ideali, permette quindi di determinare un insiemedi equazioni per l’unione V ∪W di due varieta di cui siano note singolarmente leequazioni.

Anche l’insieme dei prodotti di ciascun elemento di un insieme di generatori diI (V ) per uno di un insieme di generatori di I (W ) e un insieme di equazioni perla varieta unione, ma in generale l’ideale da esse generato, detto ideale prodotto epiu piccolo di I (V ∪W ).

M. Roggero


Definizione 3.7. Si dice prodotto di due ideali I e J l’ideale generato da tuttii prodotti fg con ∈ I e g ∈ J . Si noti che l’insieme dei prodotti di questo tipo ingenere non e un ideale perche non e chiuso rispetto alla somma, ma si ha:

I · J = {f1g1 + · · ·+ frgr | fi ∈ I, gi ∈ J, r ∈ N}.

Per determinare I (V ∪W ) a partire da I (V ) e da I (W ), potremmo alloracalcolare il radicale dell’ideale I (V ) ·I (W ). Purtroppo, anche se e facile scrivereun insieme di generatori di I · J , il calcolo del suo radicale non lo e affatto.

§ Radicale di un ideale

Sia I un ideale di k[x] e sia V la varieta degli zeri di I a coordinate in una estensionealgebricamente chiusa K di k. Per sapere se un certo polinomio f si annulli o menosu V possiamo ricorrere al Teorema degli zeri: f si annulla su V se e soltanto se fappartiene all’ideale radicale

√I. Un metodo operativo per eseguire questo controllo

e quello suggerito dal risultato seguente.

Proposizione 3.8. Siano I un ideale e f un polinomio di k[x] e sia J l’ideale dik[x, w] generato da I e da 1− fw. Allora:

f ∈√I ⇐⇒ J = (1).

Dim: Per provare che si tratta di una condizione sufficiente, basta osservare che perogni r ≥ 1 il polinomio 1− wrf r e multiplo di 1− wf .

Supponiamo viceversa f /∈√I. Per il Nullstellensatz esiste allora un punto P ∈

Kn tale che P = (λ1, . . . , λn) ∈ V (I), ma f(P ) 6= 0. Allora (λ1, . . . , λn, f(P )−1) ∈Kn+1 e un punto della varieta V (J) e quindi (ancora per il Nullstellensatz) J 6= (1).

Il risultato precedente permette cosı di risolvere il Radicalmembership, piusemplice del calcolo effettivo dell’ideale radicale. Vedremo nel prossimo capitolocome si puo determinare esplicitamente un insieme di generatori del radicale di unideale I a partire da un insieme di generatori di I, in particolare quando V (I) e uninsieme finito di punti.

§ Quoziente di due ideali

Il quoziente di due ideali I e J di k[x] si definisce nel modo seguente:

I : J = {f ∈ k[x] | fJ ⊆ I}


34 Capitolo 3

E facile verificare che si tratta di un ideale di k[x] che contiene I. Se I = I (V )e J = I (W ) sono gli ideali di due varieta algebriche, l’ideale quoziente I : J el’ideale di V \W (o meglio della minima varieta che contiene l’insieme differenza,che potrebbe non essere una varieta). Per calcolare l’ideale quoziente utilizziamo imetodi introdotti mei paragrafi precedenti e il lemma seguente.

Lemma 3.9. Siano I e J ideali e f un elemento di k[x]. Allora:

i. I ∩ (f) = f(I : (f))

ii. I : J =⋂r

i=1(I : (fi)) dove J = (f1, . . . fr).

Dim: 1. Se g ∈ I ∩ (f), allora g = fh ∈ I e quindi h ∈ I : (f) e fh ∈ f(I : (f)).Viceversa se h ∈ I : (f), allora fh ∈ I ∩ (f).

2. L’asserto si ottiene immediatamente osservando che fJ ⊆ I se e soltanto sefgi ∈ I per ogni i = 1, . . . , r.

Per calcolare il quoziente I : J bastera allora calcolare gli ideali come I ∩ (gi)mediante il metodo visto nel paragrafo precedente e dividere quindi ogni elementodi un insieme di generatori per gi stesso. Grazie al lemma precedente sappiamo chetali generatori saranno multipli esatti di gi e il calcolo del quoziente potra essere ef-fettuato in modo operativo mediante riduzione rispetto al B = {gi} e ad un qualsiasiterm order. Ottenuti cosı gli ideali I : (gi), l’algoritmo per il calcolo dell’intersezionepermette poi di determinare I : J .

§ Radicale di ideali zero-dimensionali

Da ora in poi chiameremo ideali 0-dimensionali gli ideali di k[x] = k[x1, . . . , xn]che definiscono varieta costituite da un numero finito di punti in Kn, dove K e uncampo algebricamente chiuso.

Abbiamo gia provato (cfr. Proposizione 2.30) che le dimensioni dei k-spazi vet-toriali k [x] /I e k [x] /In(I) (dove In(I) e calcolato rispetto ad un qualsiasi termorder) coincidono. Inoltre (cfr. Corollario 2.31) se I e un ideale 0-dimensionaleradicale, allora tale dimensione coincide col numero di punti in V (I).

In realta la proprieta di avere anello quoziente A = k [x] /I di dimensione finitavale piu in generale per ogni ideale 0-dimensionale. Infatti grazie ai risultati sopracitati possiamo vedere che per un m � 0 tutti i monomi di grado ≥ m stanno inIn(√I ). Se B e una G-base per

√I con s elementi e se r e un intero tale che f r

i ∈ Iper ogni fi ∈ B, allora ogni monomio di grado ≥ rsm sta in In(I).

Viceversa, se V (I) non e finito, allora k [x] /√I ha dimensione infinita e quindi,

a maggior ragione ce l’ha k [x] /I.

M. Roggero


In conclusione:

I e un ideale 0-dimensionale ⇐⇒ dimkk [x] /I <∞.

Vogliamo ora trovare un algoritmo che permetta di calcolare il radicale di ogniideale 0-dimensionale.

Definizione 3.10. Diremo che un polinomio f e privo di potenze (in inglesesquare-free) se nella sua decomposizione in fattori irriducibili in k[x] non vi sonofattori ripetuti; per estensione la parte senza potenze (square free part) di unpolinomio f e il prodotto dei fattori irriducibili distinti di f ciascuno con molteplicita1 ossia un generatore di

√(f).

Vediamo intanto come si puo procedere nel caso di 1 variabile. Ricordiamo chein k[x] tutti gli ideali sono principali ossia del tipo (f).

Lemma 3.11. Sia k un campo perfetto. Se f ′ e la derivata di f , allora:√(f) = (f) : (f ′) =

(f

MCD(f, f ′)

).

Dim: Se f =∏f ri

i , con fi irriducibili e distinti, allora

f ′ =∑

i

rif

fif ′i =

∏f ri−1

i

∑i

f ′i ∏j 6=i

fj

.

Poiche il campo k e perfetto, fi e f ′i non hanno fattori in comune e quindiMCD(f, f ′) =∏f ri−1

i .

Teorema 3.12. Sia k un campo perfetto e I un ideale di k [x] tale che V (I) e uninsieme finito di punti. Per ogni i = 1, . . . , n sia poi fi(xi) un generatore di I∩k [xi]e sia gi la parte senza potenze di fi ossia (gi) =

√I ∩ k[xi]. Allora:

√I = I + (g1, . . . , gn) .

Dim: Per semplicita supponiamo k = K algebricamente chiuso.Indichiamo con I l’ideale I + (g1, . . . , gn), che e ovviamente contenuto in

√I.

Proviamo l’inclusione non banale, procedendo per induzione sul numero r dei puntidi V (I). Osserviamo intanto che i polinomi gi non sono altro che i prodotti deifattori xi −αij al variare di αij tra le i-esime coordinate (non ripetute) dei punti diV (I): a meno di un cambio di coordinate possiamo supporre che tra tali punti cisia l’origine O e che nessun punto di V (I) \ {O} abbia coordinate nulle.

Se r = 1, allora gi = xi ∈ I e quindi I = (x1, . . . , xn) = I ({O}) =√I.


36 Capitolo 3

Supponiamo l’asserto vero per r punti e proviamolo per r + 1.Sia J = I : (x1, . . . , xn). Osserviamo che V (J) = V (I) \ {O}. Infatti V (J) ⊆ V (I)poiche J ⊇ I ⊇ I; d’altra parte se gi = hixi e h = h1 · · ·hn, allora hxi ∈ I e quindih ∈ J , ma h(O) 6= 0.

Definiamo J in modo analogo a I e proviamo che J = J . Intanto hi e proprioil generatore di

√J ∩ k[xi] e quindi J = J + (h1, . . . , hn). Dobbiamo allora provare

che hi ∈ J . Poiche J ⊆√J , allora hs

i ∈ J per un qualche s; inoltre hixi ∈ I ⊆ J .Allora si ha anche hi = MCD(hs

i , hixi) ∈ J ∩ k[xi] ⊆ J , come volevasi.

Per ipotesi induttiva si ha quindi J = J =√J .

Se f ∈√I, allora f si annulla su V (I) ⊂ V (J) e quindi f ∈

√J = J ; allora

ad esempio x1f ∈ I. Ripetendo il ragionamento relativamente ad un diverso puntoP di V (I) con prima coordinata α1 6= 0, otteniamo che f · (x1 − α1) ∈ I e quindif ∈ I, come volevasi.

Ricordiamo inoltre che polinomi fi come richiesto nell’enunciato esistono certa-mente: ciascuno di essi puo essere determinato operativamente come l’ultimo ele-mento della G-base ridotta di I calcolata rispetto ad un ordinamento di eliminazionein cui xi e la variabile piu piccola. Anche i gi possono poi essere determinati colmetodo proposto nel lemma precedente.

Corollario 3.13 (Shape lemma). Se I e un ideale 0-dimensionale radicale dik[x] = k[x1, . . . , xn] e i punti di V (I) hanno n-esime coordinate diverse, allorarispetto ad un ordinamento di eliminazione di xn la G-base ridotta di I e del tipo:

B = {x1 − p1(xn) , x2 − p2(xn) , . . . , xn−1 − pn−1(xn) , gn(xn)}.

Dim: L’ultimo polinomio della G-base e gn(xn) = Πi(xn − ain) dove aij indicala j-esima coordinata del punto Pi di V (I). Poiche queste coordinate sono peripotesi distinte, gn ha grado esattamente r = #(V (I)) = dimkk[x]/I e le classi di1, xn, . . . , x

r−1n formano una base di k[x]/I come k-spazio vettoriale.

Per ogni i < n, la classe di xi in k[x]/I si puo quindi scrivere come classe di unacombinazione lineare di tali monomi, ossia della forma

pi(xn) = 1 · a0 + a1xn + · · ·+ ar−1xr−1n .

poiche la differenza xi − pi(xn) di rappresentanti di una stessa classe modulo Iappartiene a I, si ha B ⊂ I. Inoltre mediante B (e un ordinamento di eliminazionedi xn) e possibile ridurre ogni polinomio fino ad ottenere un resto nella sola xn digrado minore di r. Poiche I non contiene elementi di questo tipo, a parte 0, ognielemento di I si riduce a 0 mediante B e quindi B e una G-base di I (chiaramenteridotta).

M. Roggero


Esercizio 3.14. Provare teoricamente che (a meno di un cambiamento lienare dicoordiante) e possibile far sı che i punti di V (I) abbiano j-esime coordinate tuttedistinte tra di loro per ogni j = 1, . . . , n. Trovare poi una procedura che permettadi determinare un cambio di variabili in modo che le n-esime coordinate dei puntidi V (I) (noto l’ideale radicale I mediante dei generatori, ma non note le coordinatedei punti di V (I)!!!) per metta di fare in modo che i punti di V (I) abbiano n-esimecoordinate distinte.

Dal risultato precedente seguono subito alcune interessanti proprieta (per nullaovvie a priori):

Corollario 3.15. Ogni ideale 0-dimensionale, radicale I di k[x] = k[x1, . . . , xn] egenerabile mediante n polinomi.

Osserviamo che in k[x] ci sono ideali il cui numero minimo di generatori e grandea piacere.

Esercizio 3.16. Provare che per ogni m ∈ N, l’ideale 0-dimensionale

(x, y)m = (xm, xm−1y, . . . , xm−iyi, . . . , ym)

di R[x, y] non puo essere ottenute mediante meno di n+ 1 generatori.

Invece gli ideali radicali che definiscono un insieme finito di punti sono interse-zione completa. Tale locuzione deriva dal significato geometrico: nel piano R2 uninsieme finito di punti puo sempre essere ottenuto come intersezione di due curveopportune; nello spazio R3 come intersezione di 3 superfici opportune, ecc.

Il Corollario 3.13 precisa anzi che in R2 si puo scegliere una di tali curve comeunione di rette “verticali ” ossia del tipo x = c (purche gli zeri di I abbiano ascissetutte distinte) e l’altra del tipo y = f(x) ossia data dal grafico di una funzionepolinomiale e che inoltre tutte le altre curve che passano per quei punti si ottengonoa partire dalle due particolari. Analogamente in R3 una delle 3 superfici e unionedi piani perpendicolari ad esempio all’asse x e le altre sono cilindri con generatriciparallale rispettivamente agli assi y e z.

Volendo calcolare in modo approssimato gli zeri di un ideale 0-dimensionale I,la G-base data dal Corollario 3.13 risulta particolarmente conveniente. Infatti, unavolta trovato un valore approssimato c per una delle soluzioni c di gn(xn) = 0, l’unicopunto P di V (I) che ha n-esima coordinata c si ottiene in modo approssimato comeP (p1(c), . . . , pn−1(c), c) calcolando le singole coordinate indipendente l’una dall’al-tra, senza propagare eccessivamente gli errori. Ottenere quella G-base ridotta peropuo richiedere un numero molto alto di calcoli in quanto e necessario usare un termorder di eliminazione, in genere abbastanza pesante da gestire.


Capitolo 4

La matrice compagna

In questo capitolo vedremo come la ricerca delle soluzioni di una equazione o,piu generalmente, di un sistema di equazioni polinomiali possa essere ricondotto adun problema di algebra lineare.

Abbiamo imparato nei corsi di algebra lineare che gli autovalori di una matricesono le radici del suo polinomio caratteristico e quindi siamo abituati a pensare cheper determinare gli autovalori si deve risolvere una equazione polinomiale. In realtarisolvere in modo esatto una equazione polinomiale e in genere impossibile e moltimetodi di approssimazione delle radici di un polinomio sono computazionalmentepoco convenienti. Ci sono invece metodi alternativi per approssimare gli autovaloridi una matrice che non passano attraverso il polinomio caratteristico e che sonodecisamente piu veloci.

Rovesciando il procedimento usuale, associeremo ad un dato polinomio P (x)una matrice, detta matrice compagna, che ha P (x) come polinomio carateristico.Generalizzeremo poi il procedimento al caso di un sistema di equazioni polinomialicon un numero finito di soluzioni, per ricondurre la ricerca approssimata di talisoluzioni alla ricerca degli autovalori di una opportuna matrice.

§ Il caso di una variabile

Consideriamo un campo k e una sua estensione K algebricamente chiusa. Introdu-ciamo innanzi tutto la nozione classica di matrice compagna che riguarda il caso diun polinomio (non costante) in una variabile:

P (x) = xn + an−1xn−1 + ...+ a0 ∈ k [x].

Ad esso associamo la matrice n× n data da:

CP =

0 1 0 . . . 0 00 0 1 . . . 0 0...

......

......

0 0 0 . . . 0 1−a0 −a1 −a2 . . . −an−2 −an−1

38

La matrice compagna 39

che si dice appunto matrice compagna del polinomio P .E facile verificare direttamente (ad esempio per induzione su n) che il polinomio

caratteristico di CP e (−1)nP . Di conseguenza le radici di P coincidono con gli au-tovalori di CP . Noi preferiamo pero dare una diversa dimostrazione di quest’ultimofatto mediante una interpretazione di CP che sara quella che generalizzeremo al casodegli ideali di k[x].

Possiamo notare che il quoziente A = k[x]/(P ) e uno k-spazio vettoriale didimensione n con base B =

{1, x, x2, ..., xn−1

}e che CP non e altro che la matrice

associata rispetto alla base B all’endomorfismo lineare

φx : A→ A

dato dalla moltiplicazione per x. Un modo equivalente per ottenere la matrice CP

e quello di considerare l’anello A′ = K[x]/(P ) che e un K-spazio vettoriale (dellastessa dimensione n di cui B e ancora una base) e la corrispondente applicazionelineare

ψx : A′ → A′.

Proposizione 4.1. Gli autovalori di CP sono le radici di P (x) e un autovettorecorrispondente all’autovalore λ si ottiene dividendo F per x− λ.

Dim: Se λ e una delle radici di P , allora per il Teorema di Ruffini si ha

P (x) = (x− λ)Q(x)

che possiamo riscrivere in A′ (ossia nel quoziente modulo P ) come:

x q = λ q.

La classe q di Q e allora un elemento non nullo di A′ per il quale la moltiplicazioneper x coincide con la moltiplicazione per la costante λ; allora λ e un autovalore diψx con autovettore Q(x). Utilizzando la base B avremo Q(x) =

∑n−1i=0 bix

i e λ saraun autovalore della matrrice CF con autovettore (b0, . . . , bn−1).

§ Il caso generale

Introduciamo ora una nozione piu generale di matrice compagna.Ricordiamo che un ideale I di k [x1, ..., xn] = k[x] si dice ideale zero-dimensionale

quando la varieta V = V (I) in Kn e un insieme finito e che in tal caso k [x1, ..., xn] /Ie uno spazio vettoriale di dimensione finita; se I e radicale, la dimensione d di Acome k-spazio vettoriale e proprio la cardinalita di V . Indichiamo con I l’ideale diK[x] generato dagli elementi di I: osserviamo che I e I definiscono la stessa varieta


40 Capitolo 4

V in Kn. Indichiamo poi con A′ il quoziente K [x] /I, di cui utilizzeremo la strutturadi anello e di K-spazio vettoriale (ma ad esempio non quella di k-spazio vettorialeche pure ha).

Nel seguito indicheremo con lettere maiuscole i polinomi di k[x] e di K[x] e conle corrispondenti lettere minuscole le loro classi in A o in A′. Si noti che se F ∈ k[x]le classi di F in A ed in A′ sono oggetti diversi (sono F + I e F + I rispettivamente);nel nostro caso tuttavia questo abuso di notazione non causera errori. Notiamoanche che in generale non ha senso valutare una classe f in un punto qualsiasi diKn, mentre non ci sono ambiguita nella scrittura f(P ) quando P ∈ V poiche F (P )e invariante nella classe di F .

Sia F ∈ k [x] un polinomio; in analogia a quanto fatto prima definiamo permoltiplicazione la funzione :

φF : A→ A data da φF (g) = fg.

Lasciamo per esercizio al lettore la verifica del risultato seguente.

Proposizione 4.2. Siano F, G ∈ k [x1, ..., xn]. Allora:

a) φF e una applicazione lineare da A in A

b) φF = φG ⇐⇒ F −G ∈ I

Dunque due polinomi danno la stessa applicazione lineare se e solo stanno nellastessa classe nel quoziente A ed in particolare φF e l’applicazione lineare nulla se esoltanto se F ∈ I. Potremo allora scrivere indifferentemente φF oppure φf .

Ogni polinomio F definisce per moltiplicazione anche l’applicazione lineare diK-spazi vettoriali:

ψF : A′ −→ A′ data da ψF (g) = fg

che, come prima, dipende solo dalla classe di F e quindi potremo denotare anchecon ψf .

Se fissiamo una base B di A come k-spazio vettoriale, B e anche una base di A′

come K-spazio vettoriale. La matrice associata a φf e quella associata a ψf rispettoalla base B coincidono: indicheremo tale matrice con Tf (B) (o brevemente con Tf

quando non c’e ambiguita riguardo alla base B).

Definizione 4.3. Se F = xi, la matrice Ti := Txi e detta i-esima matrice compa-gna di I.

Una base B particolarmente utile e quella che si ottiene fissando un term orderin Tn e considerando i monomi di Tn \ In(I).

M. Roggero


Esempio 4.4. Consideriamo l’ideale I di R[x, y] generato da

G ={x2 +

32xy +

12y2 − 3

2x− 3

2y , xy2 − x , y3 − y

}.

Rispetto al term order degrevlex con x > y, G e la base di Grobner ridotta di I.L’ideale iniziale e In (I) =

(x2, xy2, y3

). I monomi che non compaiono in In(I) for-

mano la base monomiale B ={1, x, y, xy, y2

}di R[x, y]/I come R-spazio vettoriale

(ed anche di C[x, y]/I come C-spazio vettoriale). Costruiamo la tabella di molti-plicazione tra gli elementi di B indicando ciascun prodotto mediante la sua formanormale rsipetto a G:

· 1 x y xy y2

1 1 x y xy y2

x x α xy β xy y xy y2 x yxy xy β x α xyy2 y2 x y xy y2

dove α = −32xy −

12y

2 + 32x+ 3

2y e β = 32xy + 3

2y2 − 3

2x−12y.

L’effetto sugli elementi di B della moltiplicazione per x e dato dalla seconda rigadi questa tabella di moltiplicazione. Possiamo allora costruire Tx che sara la matrice5× 5 le cui colonne sono formate dai coefficienti rispetto alla base B degli elementiche compaiono in tale riga.

Tx =

0 0 0 0 01 3/2 0 −3/2 10 3/2 0 −1/2 00 3/2 1 3/2 00 −1/2 0 3/2 0

Analogamente le righe successive della tabella corrisponderanno alla moltiplicazioneper y, xy ecc. Per ottenere la matrice associata alla moltiplicazione per un generi-co elemento F potremo costruire direttamente la tabella di moltiplicazione per Foppure ricorrere al risultato seguente.

Proposizione 4.5. Si ha:

Tf + Tg = Tf+g ed anche Tf · Tg = Tfg

Dunque il prodotto di matrici del tipo Tf e commutativo. Una importanteconseguenza e che tutte le matrici Tf possono essere ottenute come somme e prodottidi matrici compagne oppure delle matrici associate agli elementi di una fissata baseB.


42 Capitolo 4

Corollario 4.6. Sia f(x) =∑

cαxα11 · · ·x

αnn ed anche f =

∑aigi con gi ∈ B.

Allora:Tf =

∑cα(T1)α1 · · · (Tn)αn =

∑aiTgi .

L’importante risultato seguente generalizza la Porposizione 4.1

Teorema 4.7. Gli autovalori in K di TF sono i valori F (P ) assunti da F nei puntidi P ∈ V . L’autospazio in A′ corrispondente all’autovalore λ = F (P ) e la proiezionein A′ dell’ideale

(I : I (P )

)di K[x] (dipendente da P , ma non dipendente da F ).

Dim: Supponiamo che λ sia un autovalore e g ∈ A′ sia un relativo autovettorenon nullo; allora fg = λg ed esiste un punto P ∈ V tale che g(P ) 6= 0. Allora da(f − λ)g = 0 segue che f(P ) = λ.

Viceversa, se P sta in V , l’ideale(I : I (P )

)e strettamente piu grande di I;

preso allora un polinomio G ∈(I : I (P )

)\ I, la sua classe g in A′ e non nulla.

Inoltre si ha (F − λ)G ∈ I poiche tale polinomio si annulla in tutti i punti di V equindi (f − λ) g = 0 in A′. Allora g e proprio un autovettore dell’autovalore λ.

Corollario 4.8. Se I e radicale, allora per ogni F ∈ K[x] le matrici Tf (e quindiin particolare le matrici compagne Ti) sono contemporaneamente diagonalizzabili suK (ma non necessariamente su k!).

Dim: Per quanto visto e sufficiente provare la tesi per le matrici compagne; possiamoanzi considerare un generico cambiamento lineare di variabili rispetto al quale i puntidi V = abbiano tutti i-esime coordinate distinte, per ogni i = 1, . . . , n.

In tal caso A′ ha dimsnione d pari al numero di punti di V e quindi ogni matriceTi ha rango d e d autovalori distinti in K: Ti e quindi diagonalizzabile.

Si puo poi dedurre che le Tf sono contemporaneamente diagonalizzabili sia dallacommutativita del prodotto sia dal fatto che hanno tutte gli stessi autospazi.

Corollario 4.9. Gli autovalori di Ti in K coincidono con le i-esime coordinatedei punti di V . Inoltre, se H e il polinomio minimo di Ti, H(xi) e un generatoredell’ideale di eliminazione I ∩ k [xi].

§ La base speciale BK

Da ora in poi supporremo sempre che I sia radicale. Grazie a questa ipotesi perprovare che un elemento f in A o in A′ e nullo bastera mostrare che f(P ) = 0 perogni P ∈ V .

M. Roggero


Costruiamo esplicitamente una base B per A′ rispetto alla quale le matrici Tf

sono diagonali. Si e visto nella dimostrazione del Teorema 4.7 che per ogni puntoP ∈ V esiste un elemento wP di A′ tale che che wP (P ) 6= 0 e wP (Q) = 0 per ogniQ ∈ V , Q 6= P . Possiamo normalizzare in modo che si abbia wP (P ) = 1. Notiamoche per questi elementi valgono le relazioni in A′:

wPwQ = 0 se P 6= Q e w2P = wP ; (1)

infatti wPwQ e w2P − wP si annullano in tutti i punti di V . Poniamo allora

BK = {wP / P ∈ V } .

Corollario 4.10. La matrice TwP (BK) e tutta nulla tranne nell’unico posto corri-spondente alla riga e alla colonna associata a wP .

Dunque per ogni f la matrice Tf (BK) e diagonale e gli elementi della diagonalesono proprio le valutazioni f(P ) di f nei punti P di V .

Dim: La prima affermazione segue immediatamente dalle (1), cosı come le scritture:

f =∑P∈V

f(P )wP e quindi Tf (BK) =∑P∈V

f(P )TwP (BK)

Notiamo che la base BK e unica poiche per ogni P ∈ V vi e un unico elementowP ∈ A′ tale che, come richiesto:

wP (P ) = 1 e wP (P ′) = 0 per ogni P ′ ∈ V, P ′ 6= P. (2)

Due elementi siffatti avrebbero infatti differenza che si annulla su tutti i punti di V .

Se P e un punto a coordinate in k, allora wP sta in A; se invece P non hacoordinate in k, allora fanno parte di V anche i coniugati di P ; in tal caso la baserispetto a cui le matrici compagne sono in forma diagonale non e definita su k. Sipuo comunque trovare una base su k rispetto alla quale le matrici compagne abbianouna forma particolarmente semplice, anche se non diagonale.

In ogni caso, il rango e la traccia di Tf non dipendono dalla base scelta e quindi,rispetto ad una base qualsiasi, il rango e il numero di punti di V che non apparten-gono alla ipersuperficie F = 0 e la traccia e la somma dei valori assunti da f suipunti di V .

Tratteremo in dettaglio queste due ultime questioni nel prossimo capitolo, limi-tandoci al caso dei campi k = R e K = C.


Capitolo 5

Ricerca di soluzioni reali

Nel capitolo precedente abbiamo visto come ricondurre il calcolo di zeri di unideale a quello di autovalori di matrici compagne. Vediamo piu precisamente questorisultato in relazione al problema di discriminare nel caso del campo reale gli zerireali di una varieta da quelli comlessi (non reali).

Manteniamo tutte le notazioni introdotte nel precedente capitolo, ma k sarasempre R e K sara C.

§ Autovalori reali delle matrici compagne

Consideriamo la base complessa BC = {wP / P ∈ V } costruita nel capitolo prece-dente; per ogni punto reale P ∈ V si ha wP ∈ A, mentre seQ ∈ V non e reale neppurewQ lo e, poiche se lo fosse si avrebbe wQ(Q) = wQ(Q) (dove la sopralineatura indicail coniugato), mentre per ipotesi wQ(Q) = 0 e wQ(Q) = 1.

Fissiamo per ogni coppia di punti complessi coniugati di V uno dei due cheindichiamo con Q (e quindi l’altro sara Q) e poniamo wQ = xQ +iyQ, dove xQ, yQ ∈A ossia sono reali. Avremo allora:

wQ(Q) = xQ(Q)− i yQ(Q) = xQ(Q)− i yQ(Q) = wQ(Q) = 1 = 1

ed anche

wQ(P ) = xQ(P )− iyQ(P ) = wQ(P ) = 0 = 0 se P ∈ V, P 6= Q.

Allora wQ = wQ = xQ − iyQ.

Otteniamo in tal modo la base di A su R (ed anche di A′ su C):

BR ={wP / P ∈ V ∩ Rn }∪{xQ, yQ / Q, Q ∈ V \ Rn

}.

Per costruzione si ha:

1 = wQ(Q) = xQ(Q) + iyQ(Q) e 0 = wQ(Q) = xQ(Q)− iyQ(Q)

44

Ricerca di soluzioni reali 45

da cui xQ(Q) = 12 e yQ(Q) = −1

2 i e inoltre

xQwP = yQwP = 0 se P 6= Q,Q , x2Q =

12xQ , xQyQ =

12yQ, y

2Q = −1

2xQ (3)

Teorema 5.1. Per ogni F ∈ R[x], la matrice di Tf (BR) e diagonale a blocchi:

- un blocco 1× 1 costituito da f(P ) per ogni punto reale P di V ;

- un blocco 2× 2 (aQ bQ−bQ aQ

)

dove f(Q) = aQ + ibQ per ogni coppia di punti complessi coniugati Q e Q di V .

Dim: Rispetto alla base BR ogni elemento f ∈ A ha la scrittura

f =∑

f(P )wP + 2∑

aQxQ − 2∑

bQyQ

dove la prima somma riguarda tutti i punti reali di V , mentre le altre due corrispon-dono ai punti non reali (uno per ogni coppia). La tesi segue allora immediatamentedalle relazioni date in (3).

Corollario 5.2. Gli autovalori reali di Ti(B) per ogni base reale B di A sono lei-esime coordinate dei punti reali di V .

Piu in generale per ogni F ∈ R[x] gli autovalori reali di Tf (B) sono i valoriassunti da F nei punti reali di V .

Il problema che si incontra quando si prova ad applicare concretamente questirisultati teorici al fine di determinare il numero degli zeri reali e la loro posizio-ne, sia pur in modo approssimato, nasce essenzialmente dalla difficolta di costruireesplicitamente la base BR. Infatti per ottenere la base BR e necessario aver cal-colato precedentemente le radici del polinomio caratteristico, problema di difficoltaequivalente a quello che stiamo cercando di risolvere. Non ci sono invece particolaridifficolta a costruire le matrici TF (B) utilizzando una base B qualsiasi. Dobbiamoquindi cercare le informazioni che ci interessano in proprieta delle matrici, quali ilrango e la segnatura, che sono invarianti per cambio di base e non richiedono lasoluzione di equazioni polinomiali. Nel caso delle matrici Tf pero rango e segnaturadipendono sia dai punti reali di V sia da quelli non reali. Abbiamo quindi bisognodi una nuova costruzione.


46 Capitolo 5

§ La forma bilineare Φf

Per ogni polinomio F di R[x] consideriamo la forma bilineare su A data da

ΦF : A×A −→ R

ΦF (g, h) = traccia(φfgh).

Poiche come prima ΦF e invariante nella classe di F potremo anche indicarla conΦf . Sia poi Mf (B) la matrice associata a Φf rispetto ad una fissata base B.

Teorema 5.3. La matrice MF (BR) e simmetrica e diagonale a blocchi:

- un blocco 1× 1 costituito da f(P ) per ogni punto reale P di V

- un blocco 2× 212

(aQ bQbQ −aQ

)per ogni coppia di punti complessi coniugati Q e Q di V . Tali blocchi hanno traccianulla e hanno determinante negativo se f(Q) 6= 0 o nullo se f(Q) = 0.

Dim: Grazie alle (1) e (3) possiamo vedere come presi due elementi g, h ∈ BR siottengano endomorfismi φfgh nulli (e quindi con traccia nulla) in tutti i casi trannenei seguenti:

i) per le coppie (g, h) = (wP , wP ) dove P e un punto reale di V ; in tal caso fgh =fwP = f(P )wP e la traccia e f(P ) (cfr. Corollario 4.10);

ii) per le coppie (xQ, xQ), (yQ, yQ) e (xQ, yQ) = (yQ, xQ) dove Q e Q sono unacoppia di punti complessi coniugati di V ; in tali casi la traccia di φfgh coinciderispettivamente con la traccia delle matrici:

14

(aP bP−bP aP

),

14

(−aP −bPbP −aP

),

14

(bP −aP

aP bP

)In corrispondenza nella matrice Mf (BR) si ottiene un blocco 2× 2 come nell’enun-ciato.

La struttura delle matrici Mf (BR) permette di visualizzare molto facilmente leproprieta di rango e segnatura che sono pero caretteristiche della forma bilineareindipendenti dalla base utilizzata per costruire la matrice.

Corollario 5.4. Per ogni F ∈ R [x], il rango ρ(Φf ) e la segnatura σ(Φf ) della formabilineare Φf soddisfano:

ρ(Φf ) = ] {P ∈ V : f(P ) 6= 0}σ(Φf ) = ] {P ∈ V ∩ Rn : f(P ) > 0} − ] {P ∈ V ∩ Rn : f(P ) < 0}

M. Roggero


In paratica ogni punto reale P contribuisce alla segnatura col segno di f(P ),mentre le coppie di punti complessi coniugati non danno contributo alla segnatura;inoltre ogni punto di V che e anche zero di f abbassa di uno il rango della matrice.

Potremo concretamente costruire la matrice associata alla forma bilineare uti-lizzando una base qualsiasi e calcolarne rango e segnatura per dedurne numero eposizione degli zeri reali del sistema. Il paragrafo successivo e dedicato appuntoall’applicazione concreta di tale metodo.

§ Localizzazione degli zeri reali

Sia F e un polinomio (non nullo) di R[x]; possiamo decomporre Rn nell’unionedisgiunta:

Rn = H+F ∪H

−F ∪ VR(F )

dove H+F = {P ∈ Rn : F (P ) > 0} e analogamente per H−

F .

Se ad esempio F e di primo grado VR(F ) e un iperpiano e H+F e H−

F sono i duesemispazi individuati dall’iperpiano stesso; se F e una costante positiva V (F ) e H−

F

sono vuoti e Rn = H+F .

Se I e V sono definiti come nei precedenti paragrafi, localizzare gli zeri reali diV significa determinare la distribuzione dei punti di VR tra H+

F ,H−F e VR(F ) per un

insieme opportuno di polinomi F .

Come abbiamo visto la segnatura di ΦF fornisce la differenza tra il numero dipunti reali di V che cadono in H+

F e quello dei punti che cadono in H−F .

Possiamo allora determinare il numero r dei punti reali di V prendendo il poli-nomio costante F = 1: infatti r = σ(Φ1).

Scegliamo poi un polinomio F che assuma in Rn sia valori positivi sia valorinegativi, ossia tale che H+

F e H−F sono entrambe non vuote: possiamo ad esempio

considerare dei polinomi di primo grado. Il polinomio F 2 definisce la stessa iper-superficie V (F ) = V (F 2), ma H+

F 2 = H+F ∪ H

−F e H−

F 2 = ∅. Il confronto tra lasegnatura di Φ1 e quelle di ΦF e di ΦF 2 ci fornisce il numero r0 di punti reali di Vin cui F si annulla:

r0 = σ(Φ1)− σ(ΦF 2)

e il numero r1 dei punti in cui F e positivo:

r1 =12

(σ(ΦF ) + σ(ΦF 2))

Con calcoli di questo tipo relativi a polinomi xi − aik per opportuni valori reali diaik si puo giungere ad una “quadrettatura ” dello spazio Rn con cubi n-dimensionalisufficientemente piccoli e stabilire in quale di essi si trovi ciascuno zero reale di I.


48 Capitolo 5

Il lato piu interessante di questo metodo e che permette di portare a termine ilcalcolo effettivo e completo in modo puramente simbolico, cosı che non sia necessarioricorrere ad approssimazioni numeriche.

Nei capitoli iniziali abbiamo visto che teoricamente si possono determinare ipunti di V ottenendo per ciascuna variabile xi un generatore dell’ideale I ∩ k[xi]mediante la base di Grobner rispetto ad un oridinamento di eliminazione e calcolando(necessariamente in modo approssimato) le sue radici che sono le i-esime coordinatedei punti di V ; ci si trova cosı a risolvere in modo numerico equazioni in una variabiledi grado alto per cui non sempre e facile distinguere tra radici reali e radici non realicon parte immaginaria piccola. Inoltre computazionalmente il calcolo di basi diGrobner rispetto ad ordinamenti di eliminazione e particolarmente pesante.

Il metodo illustrato in questo capitolo utilizza le basi di Grobner per determinareuna base B, ma a questo scopo ogni term order va bene; si puo scegliere quindi unterm order tra quelli che forniscono algoritmi piu veloci. La differenza non e da pocoe puo esser addirittura quella tra riuscire e non riuscire a concludere il calcolo.

terminiamo con qualche accenno ad un metodo per calcolare gli autovalori diuna matrice reale che non passa attraverso il polinomio caratteristico e ad alcuniclassici criteri per valutare il numero di radici reali di un polinomio.

§ Il metodo delle potenze

Sia M una matrice reale che ha un unico autovalore dominante, cioe un autovaloreλ che soddisfa |λ| > |µ| per ogni altro autovalore µ di M . Partendo da una sceltacasuale di un vettore v0, formiamo la successione di vettori:

vk+1 = versore parallelo a Mvk.

Si dimostra che la successione vk (in genere) tende ad un autovettore di λ. il cuivalore sara approssimato per k � 0 da:

‖Mvk‖ .

Una variante consiste nel cercare l’autovalore di M piu vicino ad un certo s (sceltoa caso) applicando il metodo delle potenze alla matrice M ′ = (M −sI)−1. Per quasitutte le scelte di s ci sara un unico autovalore dominante di M ′. Inoltre, se λ′ e

l’autovalore dominante di M ′, allora1λ′

+ s e l’autovalore di M piu vicino ad s.

M. Roggero


§ Soluzioni reali di equazioni polinomiali

Sia F (x) = anxn + . . . ,+a1x+ a0 un polinomio di R[x].

Regola di Cartesio Il numero di soluzioni reali positive dell’equazione F (x) = 0e al massimo pari al numero di cambiamenti di segno della sequenza dei coefficientinon nulli di F (x).Dim: Indichiamo con ν(G) il numero di cambi di segno nella sequenza dei coefficientidi un polinomio G ∈ R [x].

Possiamo supporre a0 = 1 (dividendo per la massima potenza di x che divide Fe moltiplicando per l’inverso del termine noto, operazioni che non modificano ne ilnumero di radici reali positive di F ne il numero di cambi di segno nella sequenzadei coefficienti). Sia r il minimo indice ≥ 1 tale che ar 6= 0.

Se F = 1, la tesi e banalmente vera. Supponiamo allora che l’asserto sia sod-disfatto per tutti i polinomi di grado < n: in particolare vale quindi per il poli-nomio derivato F ′(x). Possiamo osservare che ν(F ′) = ν(F ) se ar > 0, mentreν(F ′) = ν(F )− 1 se ar < 0.

Ricordando lo studio di funzione di una variabile, si vede facilmente che tra dueradici consecutive di F c’e sempre almeno una radice di F ′ e inoltre che, se ar > 0,almeno una radice di F ′ si trova tra 0 e la prima radice positiva di F . Allora:

se ar > 0 si ha ](V (F ) ∩ R+) ≤ ](V (F ′) ∩ R+) ≤ ν(F ′) = ν(F )se ar < 0 siha ](V (F ) ∩ R+) ≤ ](V (F ′) ∩ R+) + 1 ≤ ν(F ′) + 1 = ν(F ).

Piu precisamente si puo verificare che la differenza tra il numero di cambi di segnoe il numero di radici positive e un numero pari ≥ 0.

Applicando la regola di Cartesio ai polinomi F (x) e F (−x) si determina unamaggiorazione del numero totale di radici reali 6= 0 di F .

Se F ha esattamente ∂F radici reali 6= 0, allora il numero di quelle positivecoincide esattamente col numero di cambi di segno nella sequenza dei coefficienti diF (x) e il numero di quelle negative coincide col numero di cambi di segno in F (−x),poiche il numero complessivo di cambi di segno in F (x) e F (−x) e al massimo ∂F .Infatti si devono esaminare le coppie di coefficienti non nulli consecutivi (ai, aj) inF : se i = j + 1 in (ai, aj) e ((−1)iai, (−1)jaj) c’e esattamente un cambio di segno,mentre se i > j + 1 vi possono essere due cambi di segno, ma in tal caso vi e unacoppia di coefficienti non nulli consecutivi in meno.

Se in F compaiono esattamente m monomi con coefficiente non nullo, alloraν(F (x)) ≤ m− 1 e anche ν(F (−x)) ≤ m− 1 da cui

](V (F ) ∩ R∗) ≤ 2m− 2.


50 Capitolo 5

Questo valore puo risultare notevolmente piu basso del grado di F , nel caso deipolinomi sparsi, ossia dei polinomi di grado alto, ma con pochi monomi.

Analogo al precedente, ma piu preciso, e il risultato seguente, che permette dideterminare quante sono le radici reali di un polinomio che sono contenute in unprefissato intervallo.

Dato un polinomio F (x), consideriamo i polinomi Fi definiti ricorsivamente da:

F0 = F

F1 = F ′(x)

Fi = resto della divisione di Fi−2 per Fi−1, per i ≥ 2.

Chiaramente i polinomi Fi hanno grado strettamente decrescente e quindi la succes-sione termina dopo al massimo ∂F passi.

Teorema di Sturm Se F (a) 6= 0 e F (b) 6= 0, il numero di radici di F (x) compresenell’intervallo [a, b] e dato dalla differenza tra il numero di cambi di segno nellasequenza F0(a), F1(a), . . . , Fm(a) e il numero di cambi di segno nella sequenzaF0(b), F1(b), . . . , Fm(b).

M. Roggero

Algoritmi per l’Algebra e la Geometriaottenute si dicono funzioni polinomiali. Le funzioni...

Documents

Transcript of Algoritmi per l’Algebra e la Geometriaottenute si dicono funzioni polinomiali. Le funzioni...