Un algoritmo de Gauss para polinomios simétricos
Nuestro gran maestro Gauss nos ha dejado varios algoritmos muy importantes, que seguimos usando y enseñando al día de hoy. Entre ellos: la escalerizacion gaussiana y el metodo de Gauss-Seidel; ambos destinados a buscar soluciones de sistemas de ecuaciones lineales.
Otro algoritmo debido a Gauss, aunque mucho menos conocido, es el que comento en esta entrada. Este algoritmo permite expresar cualquier “polinomio simétrico” en funcion de los denominados “polinomios simétricos elementales”.
Carl Gauss vivió en lo que hoy es Alemania, entre 1777 y 1855, mayormente en la ciudad de Göttingen. Su trabajo más conocido es “Disquisitiones Arithmeticae” (Investigaciones en Aritmetica), publicado en 1801, al inicio de su carrera, y que trata mayormente sobre lo que hoy es la “teoría de números”.
Su carrera académica se extiende por 50 años más, con diversos aportes en distintas áreas del conocimiento, particularmente de la astronomía, la física y la matemática. Entre sus discípulos se cuentan Richard Dedekind, Bernhard Riemann y Sophie Germain
Polinomios simétricos y su Teorema Fundamental
Un polinomio simétrico es algo de la siguiente forma: $p(x,y) = x^2 y + x y^2$. Decimos que es simétrico porque, si intercambiamos las variables $x$ e $y$, el polinomio no cambia: $$ p(y,x) = y^2 x + y x^2 = x^2 y + x y^2 = p(x,y) .$$
Un ejemplo de polinomio no simétrico es $p(x,y) = x^2 y + x y$. En este caso, si intercambiamos las variables, se obtienen polinomios distintos: $$p(y,x) = y^2 x + y x \neq p(x,y) .$$
Existen dos polinomios simétricos que son particularmente importantes. Estos son los polinomios simétricos elementales, dados por: $$ e_1(x,y) = x+y, \quad e_2(x,y) = xy .$$
La importancia de estos, está dada por el “Teorema fundamental de los polinomios simétricos”. Este resultado dice que podemos expresar cualquier polinomio simétrico usando solamente los polinomios simétricos elementales.
Como ejemplo, consideremos el polinomio simétrico $ p(x,y) = x^2 y + x y^2 $. Tomando factor común $xy$, podemos escribir $p$ en términos de los polinomios simétricos elementales: $$ p(x,y) = x^2 y + x y^2 = x y ( x + y ) = e_1(x,y) e_2(x,y) .$$
Por lo tanto, el Teorema Fundamental permite “codificar” todos los polinomios simétricos, que son infinitos, con una cantidad finita de polinomios: los polinomios simétricos elementales $e_1$ y $e_2$.
Sin embargo, el enunciado del Teorema no nos dice cómo podemos “codificar” un polinomio simétrico cualquiera $p(x,y)$, en términos de los polinomios simétricos elementales. Por suerte para nosotros, Gauss introdujo un algoritmo para resolver este último problema.
Orden lexicográfico
Para ver cómo funciona el algoritmo de Gauss, necesitamos definir un orden en los sumandos de un polinomio. Estos sumandos son de la forma: $C x^a y^b$, donde $a$ y $b$ son exponentes no negativos, y $C$ es un número cualquiera.
Vamos a decir que $C_1 x^{a_1} y^{b_1} > C_2 x^{a_2} y^{b_2}$, si se cumple: $$ a_1 > a_2, \quad \text{o} \quad a_1 = a_2 \ \text{y} \ b_1 > b_2 .$$ Es decir: primero comparamos los exponentes de la variable $x$, y solamente si estos son iguales, pasamos a comparar los exponentes de la variable $y$. Notar que el coeficiente $C$ de cada sumando es irrelevante al definir el orden.
Por ejemplo:
- $-10 x^4 y^2 > 7 x^3 y^5$, porque $4>3$ (en este caso el exponente de $y$ es irrelevante).
- $7 x^3 y^5 > 8 x^3 y^2$, porque $3=3$ y $5>2$.
Este orden entre los sumandos de un polinomio, se denomina “orden lexicográfico”. Al parecer fue Gauss quien introdujo este orden en la literatura científica, y lo hizo justamente para describir el algoritmo del que trata esta entrada.
Algoritmo de Gauss
Consideremos el siguiente polinomio simétrico $$ p(x,y) = 2 x^3 y - 3 x^2 y^2 + 6 x^2 y + 2 x y^3 + 6 x y^2 .$$ Vamos a utilizar el algoritmo de Gauss para expresarlo en términos de los polinomios simétricos elementales. Para esto procedemos de la siguiente forma.
-
Identificamos el mayor sumando del polinomio $p$, en relación al orden lexicográfico. Este se denomina “término líder” del polinomio, y se denota LT (“Leading Term”). En el ejemplo el término líder es: $$ LT(p) = 2 x^3 y = 2 x^3 y^1 $$
-
Los exponentes de las variables del término líder son $3$ y $1$. Teniendo en cuenta esto, a este término líder le vamos a asociar el siguiente polinomio: $$ 2 e_1(x,y)^{3-1} e_2(x,y)^1 = 2 (x+y)^2 x y = 2 x^3 y + 2 y^3 x + 4 x^2 y^2 .$$
-
Al polinomio inicial $p$, le restamos el polinomio anterior, y obtenemos: $$ p_1(x,y) = p(x,y) - 2 e_1(x,y)^2 e_2(x,y)^1 = - 7 x^2 y^2 + 6 x^2 y + 6 x y^2 .$$
-
Repetimos el paso inicial, pero aplicado al nuevo polinomio $p_1$. Su término líder es: $$ LT(p_1) = -7 x^2 y^2 .$$ Los exponentes de sus variables son: $2$ y $2$. Por lo tanto, le asociamos el siguiente polinomio: $$ -7 e_1(x,y)^{2-2} e_2(x,y)^2 = -7 (x+y)^0 (x y)^2 = -7 x^2 y^2 .$$ Al polinomio $p_1$, le restamos el polinomio anterior, y obtenemos: $$ p_2(x,y) = p_1(x,y) - ( -7 e_2(x,y)^2 ) = p_1(x,y) + 7 x^2 y^2 = 6 x^2 y + 6 x y^2 .$$
-
Repetimos el paso inicial, pero aplicado al nuevo polinomio $p_2$. Su término líder es: $$ LT(p_2) = 6 x^2 y = 6 x^2 y^1 .$$ Los exponentes de sus variables son: $2$ y $1$. Por lo tanto, le asociamos el siguiente polinomio: $$ 6 e_1(x,y)^{2-1} e_2(x,y)^1 = 6 (x+y)^1 (x y)^1 = 6 x^2 y + 6 x y^2 .$$ Al polinomio $p_2$, le restamos el polinomio anterior, y obtenemos: $$ p_3(x,y) = p_2(x,y) - 6 e_1(x,y) e_2(x,y) = p_2(x,y) - (6 x^2 y + 6 x y^2) = 0 .$$
-
Llegamos a un polinomio nulo, por lo que dejamos de iterar.
En este proceso obtuvimos las siguientes igualdades:
$$ p_1(x,y) = p(x,y) - 2 e_1(x,y)^2 e_2(x,y) ,$$ $$ p_2(x,y) = p_1(x,y) + 7 e_2(x,y)^2 = 6 x^2 y + 6 x y^2 ,$$ $$ p_3(x,y) = p_2(x,y) - 6 e_1(x,y) e_2(x,y) = 0 .$$
Reemplazando desde la última ecuación hacia la primera, obtenemos la expresión buscada:
$$ p_2(x,y) = 0 + 6 e_1(x,y) e_2(x,y) .$$ $$ p_1(x,y) = p_2(x,y) - 7 e_2(x,y)^2 = 6 e_1(x,y) e_2(x,y) - 7 e_2(x,y)^2 .$$ $$ p(x,y) = p_1(x,y) + e_1(x,y)^2 e_2(x,y) = $$ $$ = 6 e_1(x,y) e_2(x,y) - 7 e_2(x,y)^2 + 2 e_1(x,y)^2 e_2(x,y) .$$
Notar que si definimos el polinomio $q(z,w) = 6 z w - 7 w^2 + 2 z^2 w$, podemos escribir: $$ p(x,y) = q(e_1(x,y), e_2(x,y)) .$$ Podemos pensar que el algoritmo de Gauss calcula este polinomio $q$, que al evaluarlo en los polinomios simétricos elementales, nos da el polinomio simétrico $p$ inicial.
Pseudocódigo
El algoritmo de Gauss es muy sencillo de implementar con un bucle “while”. Para esto iniciamos con:
-
$p_0(x,y) = p(x,y)$, con $p$ polinomio simétrico,
-
$i=0$.
Luego, mientras $p_i$ sea no nulo o no constante, iteramos de la siguiente forma:
-
Determinar el término líder de $p_i$: $LT(p_i) = C_i x^{a_i} y^{b_i}$.
-
Definir el polinomio $p_{i+1}(x,y) = p_i(x,y) - C_i e_1(x,y)^{a_i - b_i} e_2(x,y)^{b_i}$.
-
Incrementar el contador $i = i + 1$.
Si el valor final de $i$ es $N$, entonces:
$$ p(x,y) = p_N + \sum \limits_{k=0}^{N} C_k e_1(x,y)^{a_k - b_k} e_2(x,y)^{b_k} ;$$ siendo $p_N$ el polinomio nulo, o un polinomio constante conocido. El correspondiente polinomio $q$, de variables $z$ y $w$ es: $$ q(z,w) = p_N + \sum \limits_{k=0}^{N} C_k z^{a_k - b_k} w^{b_k} .$$
La implementación requiere de un algoritmo secundario para determinar el término líder de un polinomio. Para simplificar este proceso, se puede implementar el algoritmo en Macaulay2, que cuenta con un comando para determinar el término líder. En este enlace pueden encontrar una implementación en Macaulay2.
Más de dos variables
El algoritmo de Gauss se puede generalizar fácilmente al caso de más de dos variables. Por ejemplo, para tres variables $x$, $y$ y $z$, solamente hay que tener en cuenta lo siguiente para adaptar el método:
-
el orden lexicográfico compara primero los exponentes de las $x$, luego los de las $y$ (en caso de ser necesario), y finalmente los de $z$ (en caso de ser necesario). Por ejemplo: $$ x^2 y^3 z^0 > x^2 y^2 z^5 .$$
-
Los polinomios simetricos elementales son tres (igual que la cantidad de variables): $$ e_1(x,y,z) = x+y+z, \quad e_2(x,y,z) = xy + xz + yz, \quad e_3(x,y,z) = x y z .$$
-
A un término líder de la forma $C x^a y^b z^c$, se le asocia el polinomio: $$ C e_1(x,y,z)^{a-b} e_2(x,y,z)^{b-c} e_3(x,y,z)^c .$$