Sistemas polinomiales (Elementos b´asicos)

ALBERTO VIGNERON TENORIO Dpto. de Matem´aticas

Universidad de C´adiz

´Indice general 1. Introducci´ on

2

2. Generalidades sobre polinomios

5

2.1. Orden monomial . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2. Algoritmo de divisi´ on . . . . . . . . . . . . . . . . . . . . . .

7

2.3. S−polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.4. Bases de Gr¨ obner . . . . . . . . . . . . . . . . . . . . . . . . .

9

3. Generalizando Gauss a sistemas polinomiales

11

4. Ejemplo

12

1

Cap´ıtulo 1

Introducci´ on Los sistemas polinomiales son una pieza importante dentro de la modelizaci´ on de problemas reales. El estudio y c´alculo de sus soluciones exactas constituyen todo un campo de trabajo con aplicaciones directas en la econom´ıa, la ingenier´ıa, inform´ atica, telecomunicaciones, etc. Estos problemas se estudian dentro de diversas ramas de las Matem´aticas. La aproximaci´on ´ que vamos a realizar la abordaremos desde el punto de vista del Algebra Computacional. Las preguntas a las que vamos tratar de dar respuesta son: ¿Cu´ ando tiene soluci´ on un sistema polinomial? ¿Cu´ ando tiene una cantidad finita de soluciones un sistema polinomial? ¿C´ omo podemos calcular dichas soluciones? Si nos encontramos frente a un sistema de ecuaciones lineales, aplicamos el m´etodo de eliminaci´ on de Gauss. Por ejemplo, dado el sistema de ecuaciones (pi es la ecuaci´ on i)    p1 ≡ x +2y     p ≡ +3x −y

−z

6x

=0

+t −u −6 = 0

2

 p3 ≡      p4 ≡

+t +u

+t +u −1 = 0

+y

x −2y +2z −2t

(1.1)

+5 = 0

el primer paso ser´ıa fijar un elemento sobre el que pivotar, en este ejemplo escogemos el monomio en x de la primera ecuaci´on, el segundo reducir las 2

´ CAP´ITULO 1. INTRODUCCION ecuaciones pivotando sobre el elemento     x +2y    p − 3p → p   2 1 2   −7y p3 − 6p1 → p3 ⇒   −11y    p −p   → p4 4 1   −4y

3 elegido, −z

+t

+u

=0

+3z −2t −4u −6 = 0 +6z −5t −5u −1 = 0 +3z −3t

(1.2)

−u +5 = 0

Esta reducci´ on tiene como consecuencia que en todas las ecuaciones, salvo la primera, hemos eliminado la variable x. Adem´as, sus soluciones son las mismas que las del sistema (1.1). La anterior operaci´ on p2 − 3p1 → p2 es equivalente a sustituir p2 por una combinaci´ on de p1 y p2 obtenidas a partir del m´ınimo com´ un m´ ultiplo de los coeficientes de x, dividido por el coeficiente de cada ecuaci´on. Las otras dos se obtienen a partir del m´ınimo com´ un m´ ultiplo de los coeficientes de x de la primera ecuaci´ on, y la tercera y cuarta respectivamente. An´ alogamente, si pivotamos ahora sobre −7y en la segunda ecuaci´on para continuar con la reducci´on,     x +2y −z +t +u =0    7p − 11p → p   3 2 3   −7y +3z −2t −4u −6 = 0 ⇒   9z −13t +9u +59 = 0    7p − 4p   → p4 4 2   9z −13t +9u +59 = 0 De nuevo, la operaci´ on 7p3 −11p2 → p3 se obtiene a partir del m´ınimo com´ un m´ ultiplo de los coeficientes de y en la segunda y tercera ecuaci´on, divididos por los correspondientes coeficientes de y en cada una de las ecuaciones: mcm(7, 11) mcm(7, 11) p3 − p2 , 11 7

7p3 − 11p2 = y 7p4 − 4p2 → p4 de 7p4 − 4p2 =

mcm(7, 4) mcm(7, 4) p3 − p2 . 4 7

La u ´ltima operaci´ on de la reducci´on, p4 − p3 → p4 , la obtendremos de p4 − p3 =

mcm(9, 9) mcm(9, 9) p4 − p3 , 9 9

´ CAP´ITULO 1. INTRODUCCION

4

quedando el sistema:    x +2y −z +t +u =0     −7y +3z −2t −4u −6 = 0  9z −13t +9u +59 = 0      0 =0 Al final de este proceso, hemos re-escrito el sistema inicial en una expresi´ on agradable. Las nuevas ecuaciones tienen las mismas soluciones que en el sistema inicial (1.1). Mediante este procedimiento obtenemos, para ecuaciones lineales, respuestas a las preguntas anteriores: ¿Cu´ ando tiene soluci´ on un sistema lineal? El sistema es compatible porque no hemos obtenido ninguna ecuaci´on incompatible, es decir, del tipo 1 = 0. ¿Cu´ ando tiene una cantidad finita de soluciones un sistema lineal? El sistema tiene infinitas soluciones porque, por ejemplo, la variable u puede tomar cualquier valor. ¿C´ omo podemos calcular dichas soluciones? Podemos calcular todas las soluciones despejando z en funci´on de t y u de la u ´ltima ecuaci´on (no nula), despu´es y en funci´on de z, t y u de la pen´ ultima, y x en funci´ on del resto de la primera ecuaci´on. ¿Podemos encontrar un proceso equivalente cuando tratamos con sistemas de ecuaciones polin´ omicas? ¿Podemos encontrar esa expresi´ on agradable con un sistema polinomial? Las respuestas a estas preguntas son afirmativas, y se basan, al igual que la reducci´on de Gauss en: encontrar elementos sobre los que pivotar, reducir las ecuaciones obteniendo nuevos sistemas (con una expresi´ on agradable) que tengan las mismas soluciones que los de partida. Para ello vamos a utilizar las llamadas bases de Gr¨obner, dando un procedimiento de reducci´ on de polinomios en varias variables similar al que hemos aplicado sobre el ejemplo anterior.

Cap´ıtulo 2

Generalidades sobre polinomios Consideremos ahora un conjunto de polinomios, F = {f1 , . . . , ft }, en las variables x1 , . . . , xn . En general, vamos a denotar por C[x1 , . . . , xn ] al conjunto de todos los polinomios en las variables x1 , . . . , xn , con coeficientes en C (conocido como anillo de polinomios). Dado un monomio xa11 xa22 · · · xann , llamaremos exponente de xa11 xa22 · · · xann al vector (a1 , a2 , . . . , an ) ∈ Nn . N´otese que cada monomio tiene asociado un u ´nico exponente y viceversa. Definici´ on 1. Dado un conjunto de polinomios I ⊂ C[x1 , . . . , xn ], diremos que I es un ideal si verifica: 0 ∈ I. Si f, g ∈ I, entonces f + g ∈ I. Si f ∈ I y h ∈ C[x1 , . . . , xn ], entonces hf ∈ I. Lema 1. Dados los polinomios iniciales F = {f1 , . . . , ft }, el conjunto {h1 f1 + · · · + ht ft | h1 , . . . , ht ∈ C[x1 , . . . , xn ]} es un ideal de C[x1 , . . . , xn ], al que llamaremos ideal generado por F, y denotaremos por < f1 , . . . , ft > .

5

CAP´ITULO 2. GENERALIDADES SOBRE POLINOMIOS

6

N´ otese que las soluciones del sistema polinomial f1 = 0, . . . , ft = 0, que nos ocupa, son las mismas que las de cualquier sistema de generadores del ideal < f1 , . . . , ft > . Por lo tanto, encontrar esa expresi´ on agradable a la que nos referimos en la introducci´on pasa por encontrar sistemas de generadores especiales del ideal. En lo que sigue, vamos a plantear los elementos necesarios para ello.

2.1.

Orden monomial

La elecci´ on del pivote en una generalizaci´on de la reducci´on de Gauss, va a suponer, en primer lugar, escoger una ecuaci´on y un monomio en ella. Para ello se utilizan los llamados ´ordenes monomiales. Dado que hemos relacionado de manera u ´nica un monomio con su exponente, xa11 xa22 · · · xann ! (a1 , a2 , . . . , an ) ∈ Nn , podemos ordenar los monomios mediante esos exponentes. En particular, y para el problema que nos ocupa, vamos a considerar el conocido como orden lexicogr´ afico, aunque, como es comprensible, existen gran cantidad de ´ordenes con distintas utilidades. Definici´ on 2. Diremos que a = (a1 , . . . , an ) ∈ Nn es menor (respecto al orden lexicogr´ afico) que b = (b1 , b2 , . . . , bn ) ∈ Nn , y lo denotaremos por a ∩C[xi ] mediante bases de Gr¨ obner (teorema 2). ¿C´ omo podemos calcular dichas soluciones? Teorema 5. Dado el sistema polinomial f1 = 0, . . . , ft = 0, la expresi´ on agradable que buscamos viene dada por una base de Gr¨ obner (reducida) del ideal < f1 , . . . , ft > respecto del orden lexicogr´ afico.

11

Cap´ıtulo 4

Ejemplo Consideremos el sistema polinomial ( f = xy 2 − 2 x − y 2 + 2 = 0 g =

x2 y − x2 + y − 1

= 0

(4.1)

donde hemos subrayado los monomios l´ıderes de cada polinomio. Para hallar la expresi´ on agradable del sistema, aplicamos el algoritmo 1 considerando fijado el orden lexicogr´ afico con x > y. En primer lugar calculamos el S−polinomio de f y g : S(f, g) = x2 y − 2 x2 − xy 2 + 2 x − y 2 + y, y lo dividimos por el conjunto F = {f, g}, S(f, g) = −f + g + (−x2 − 2 y 2 + 3). Como el resto es no nulo, a˜ nadimos dicho resto, que denotaremos por r1 , al conjunto F. Ahora realizamos el S−polinomio de f y r1 : S(f, r1 ) = 2 x2 + xy 2 − 2 x + 2 y 4 − 3 y 2 , y lo dividimos por el conjunto F = {f, g, r1 }, S(f, r1 ) = −f − 2r1 + (2 y 4 − 6 y 2 + 4). Como el resto es no nulo, a˜ nadimos dicho resto, que denotaremos por r2 , al conjunto F. 12

CAP´ITULO 4. EJEMPLO

13

Continuando ese procedimiento, llegamos a que una base de Gr¨obner de F = {f, g} respecto del orden lexicogr´afico es: {f, g, x2 + 2 y 2 − 3, y 4 − 3 y 2 + 2, y 3 − y 2 − 2 y + 2}, por lo tanto, el sistema tiene soluci´on porque dicha base no es {1}. El sistema inicial (4.1) tiene una expresi´ on agradable   xy 2 − 2 x − y 2 + 2     2 2    x y−x +y−1 x2 + 2 y 2 − 3     y4 − 3 y2 + 2     3 y − y2 − 2 y + 2

= 0 = 0 = 0 = 0 = 0

De las dos u ´ltimas ecuaciones, obtenemos que los posibles valores de y √ son ± 2 y 1. Fijados estos valores, calculamos los de x : Para y = 1, x = 1. Para y =

√

√ 2, x = ± −1 = ±i.

√ √ Para y = − 2, x = ± −1 = ±i. Al final, hemos calculado las 4 soluciones del sistema, aunque s´olo una de ellas, el par (1, 1), es real. De haber calculado una base de Gr¨obner de F = {f, g} respecto al orden lexicogr´ afico y > x, habr´ıamos obtenido que el polinomio x3 − 1 − x2 + x estar´ıa en ella. Como en la base que hemos calculado antes considerando x > y tenemos polinomios s´ olo en la variable y, concluir´ıamos, aplicando el teorema 4, que el sistema ten´ıa una cantidad finita de soluciones. En cualquier caso, en este ejemplo hemos calculado primero las soluciones y hemos visto que hay una cantidad finita de ellas.

Bibliograf´ıa [1] D. COX, J. LITTLE, D. O’SHEA. Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra. Springer (2007).

14