Varias perspectivas sobre las bases de Gröbner : forma normal de Smith, algoritmo de Berlekamp y álgebras de Leibniz

Memoria realizada en el Departamento de Algebra de la Facultad de Matemáticas, bajo la dirección del profesor Manuel Ladra Gónzalez, para obtener el Grado de DOCTOR en Ciencias Matemáticas por la Universidad de Santiago de Compostela. Santiago de Compostela 2003 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Departamento de Álxebra Santiago de Compostela 2003 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Departamento de Álxebra (Co)HOMOLOGêA DE MîDULOS PRECRUZADOS (Co)HOMOLOGêA DE MîDULOS PRECRUZADOS Departamento de çlxebra Daniel Arias Mosquera UNIVERSIDADE DE SANTIAGO DE COMPOSTELA (Co)HOMOLOGêA DE MîDULOS PRECRUZADOS Departamento de Álxebra 2005 Manuel Avelino Insua Hermo UNIVERSIDADE DE SANTIAGO DE COMPOSTELA VARIAS PERSPECTIVAS SOBRE LAS BASES DE GRÖBNER: FORMA NORMAL DE SMITH, ALGORITMO DE BERLEKAMP Y ÁLGEBRAS DE LEIBNIZ Memoria realizada en el Departamento de Algebra de la Facultad de Matemáticas, bajo la dirección del profesor Manuel Ladra Gónzalez, para obtener el Grado de DOCTOR en Ciencias Matemáticas por la Universidad de Santiago de Compostela. Santiago de Compostela 2003 Varias perspectivas sobre las Bases de Gr¨obner: Forma Normal de Smith, Algoritmo de Berlekamp y ´ Algebras de Leibniz Manuel Avelino Insua Hermo Universidad de Santiago de Compostela Departamento de ´ Alxebra Santiago de Compostela, 7 de Abril de 2005 Varias perspectivas sobre las Bases de Gr¨obner: Forma Normal de Smith, Algoritmo de Berlekamp y ´ Algebras de Leibniz Fdo.: Manuel Avelino Insua Hermo Memoria para optar al grado de Doctor realizada en el Departamento de ´ Alxebra de la Universidad de Santiago de Compostela bajo la direcci´on del Profesor D. Manuel Ladra Gonz´alez. Santiago de Compostela, a 7 de Abril de 2005. Fdo.: Prof. Dr. Manuel Ladra Gonz´alez A mi Padre Avelino, mi Madre Marit´e, mi Abuela Juana, mi hermano Juanjo, mi mujer Amalia y mi hija Cristina Ma, con todo mi cari˜no. Agradecimientos Llegado este momento se impone la necesidad, m´as que la simple obligaci´on cort´es, de expresar mi m´as sincero agradecimiento a aquellas personas que han contribuido, en una u otra forma a este trabajo. En primer lugar, sin duda, debo agradecer a mi director de tesis D. Manuel Ladra Gonz´alez, el apoyo tanto acad´emico como personal que me ha prestado; as´ı mismo quiero agradecerle desde aqu´ı la confianza que ha mantenido en m´ı a lo largo de estos a˜nos. Sin saberlo Manolo, una simple llamada tuya para interesarte c´omo me iba y darme ´animos, me ha servido para mantener la confianza en m´ı mismo, bien cuando ve´ıa que no daba avanzado o bien cuando al estar trabajando las ganas de continuar flaquean; por todo ello te estoy muy agradecido, muchas gracias Manolo. As´ı mismo quiero hacer extensivo mi agradecimiento a todos los profesores del Departamento de ´ Alxebra, por el apoyo recibido. Ya en el terreno m´as personal quiero desde aqu´ı, agradecer a mis padres Avelino y Marit´e todo el cari˜no, apoyo incondicional y confianza en mis posibilidades que siempre me han mostrado, siempre hab´eis estado conmigo en los buenos y malos momentos; siempre hab´eis sabido darme el consejo adecuado; hora es ya de que retorne algo de lo que he recibido (por peque˜na que sea esta satisfacci´on). Por todo ello, y seguramente mucho m´as que se me olvida, quiero expresar mi reconocimiento y mi cari˜no m´as sincero. Continuando en orden cronol´ogico, quiero desde aqu´ı agradecer a mi mujer Amalia todo el apoyo y comprensi´on recibidos. Gracias por entender la importancia que esta tesis tiene para m´ı. como algoritmos deterministas), surge un nuevo tipo de algoritmos, los algoritmos probabil´ısticos. Este tipo de procedimientos, que son muy utilizados en los test de primalidad y en la factorizaci´on de polinomios en una o varias variables, est´an basados en utilizar m´etodos probabil´ısticos para obtener el resultado deseado. Hoy en d´ıa, no cabe la menor duda de que en matem´aticas las palabras algoritmo y computadora van ´ıntimamente ligadas, pues son las computadoras los instrumentos con los que poner en pr´actica los algoritmos desarrollados sobre el papel. El rol que han desempe˜nado y todav´ıa desempe˜nan las computadoras no se qued´o aqu´ı, pues a su vez, el hecho de poder mediante una computadora, aplicar un algoritmo para resolver un problema determinado, ha servido como est´ımulo para el desarrollo de nuevos algoritmos; e incluso se puede decir m´as, el uso de las computadoras en matem´aticas impuls´o e impulsa la ”parte constructivista”, por llamarla as´ı, de sus distintas ramas, de hecho, por ejemplo en ´ Algebra en la actualidad se habla de la disciplina de ´ Algebra Computacional. Las aportaciones de las computadoras no se quedaron aqu´ı, pues hubo quien intuy´o una nueva funcionalidad: el c´alculo simb´olico. La idea de hacer c´alculo simb´olico con un ordenador es relativamente reciente. Desde 1960 hasta nuestros d´ıas se han realizado numerosos lenguajes de computaci´on simb´olica, desde el pionero Lisp, pasando por Alpak, Camal, Formac, Saint, en la d´ecada de los a˜nos sesenta, hasta los m´as actuales como Axiom, Bergman, Cayley, Cocoa, Gap, Magma, Maple, Mathematica, Reduce y Singular. Al igual que la idea de hacer c´alculo simb´olico con un ordenador, la construcci´on de algoritmos en el campo del ´algebra conmutativa y geometr´ıa algebraica es tambi´en relativamente reciente. Hermann [Her26] fue una de los primeros matem´aticos que se interes´o en la construcci´on de algoritmos, en el campo de la teor´ıa de ideales del anillo de polinomios en nvariables sobre un cuerpo K(n≥1). Descubri´o un algoritmo que calculaba la desii composici´on primaria de un ideal y otro que serv´ıa para comprobar si un polinomio pertenec´ıa a un ideal dado; ´este ´ultimo algoritmo reduc´ıa el problema a resolver un sistema de ecuaciones lineales. M´as tarde Seidenberg [Sei74] publicar´ıa una revisi´on de ambos m´etodos dados por Hermann. El avance m´as significativo en la construcci´on de algoritmos para ´algebra conmutativa y geometr´ıa algebraica, surge de la teor´ıa y t´ecnicas que desarroll´o Bruno Buchberger en su tesis doctoral [Buc65]. La teor´ıa de Buchberger o Bases de Gr¨obner, permite manipular polinomios en varias variables casi de la misma forma, que uno manipula polinomios en una variable. El algoritmo de Buchberger, piedra angular de la teor´ıa de las Bases de Gr¨obner, es una generalizaci´on del Algoritmo de Euclides al caso multivariable, si se ve desde el punto de vista de la teor´ıa de ideales sobre K[x1, ..., xn] (Kcuerpo), debido a la unicidad del resto de la divisi´on de un polinomio por una Base de Gr¨obner. Tambi´en se puede considerar como una generalizaci´on del algoritmo de eliminaci´on de Gauss al caso no lineal, si se ve desde el punto de vista de la teor´ıa de variedades, pues, en el caso lineal, los polinomios que definen una variedad lineal en el sistema final, tras haber aplicado Gauss, forman una Base de Gr¨obner respecto al orden monomial lexicogr´afico. Incluso se puede considerar como una generalizaci´on de la resultante de Sylvester para el c´alculo del polinomio m´ınimo de dos polinomios en una variable. Buscando las primeras ”huellas” de lo que posteriormente ser´ıan las bases de Gr¨obner, es necesario retroceder hasta finales del siglo XIX, y situarse, con cierta sorpresa, en el contexto de la Teor´ıa de Invariantes, m´as concretamente en el ”tira y afloja” que mantuvieron dos matem´aticos de prestigio de la ´epoca, ´estos son Hilbert y Gordan. En 1890 Hilbert dio a conocer su primera prueba del teorema de Finitud [H1890], que establece que el anillo de invariantes asociado a un grupo finito est´a finitamente generado. Aunque de gran inter´es te´orico, su demostraci´on no ten´ıa por si misma gran inter´es pr´actico, pues la prueba dada por Hilbert es no constructiva; fue precisamente esta no constructividad de la demostraci´on iii dada por Hilbert el hecho que critic´o Gordan, y es justo en este contexto al revisar la demostraci´on dada por Hilbert, cuando Gordan pronunci´o la ya famosa frase: ”esto es teolog´ıa y no matem´aticas”. Posteriormente, el propio Gordan en cierta forma se retract´o de lo dicho afirmando que: ”la teolog´ıa tambi´en tiene sus ventajas”, al publicar ´el mismo [G1899] una nueva prueba del teorema de la Base de Hilbert (responsable de la no constructividad de la prueba de 1890); en el citado art´ıculo utiliza por primera vez ideas similares a las bases de Gr¨obner, que ´el llama ”le systeme irr´eductible N”, y la generaci´on finita de los ideales monomiales para deducir el teorema de la Base de Hilbert. Con el transcurso del tiempo se ha podido comprobar que la demostraci´on de 1890 no era en el fondo tan no constructiva, como en un principio se pens´o, pues bas´andose en ella Derksen [Der99] ha construido un algoritmo de computaci´on de los invariantes fundamentales de un grupo lineal reductivo, utilizando las bases de Gr¨obner como herramienta de c´alculo. Motivado por las cr´ıticas recibidas, Hilbert da tres a˜nos m´as tarde una nueva prueba, esta vez constructiva, del teorema de Finitud utilizando sistemas homog´eneos de par´ametros [H1893]. El uso de un concepto m´as o menos aproximado de lo que es una base de Gr¨obner no se qued´o aqu´ı; Macaulay [M1916] introdujo el concepto de H-base de un ideal en K[x1, ..., xn]. Una H-base es un subconjunto finito F de K[x1, ..., xn] tal que a cada 0 6=g∈<F > tiene una H-representaci´on, esto es, una representaci´on de la forma: g=X f∈F hf·f con max{grado(hf·f)/f ∈F} ≤ grado(g). Bajo un orden monomial adecuado, se puede probar que toda base de Gr¨obner es una H-base, aunque el rec´ıproco no es cierto en general. Macaulay prob´o la existencia de una H-base para un ideal dado de forma no constructiva, como una simple aplicaci´on del teorema de la Base de Hilbert. iv Tambi´en se debe a Macaulay la introducci´on de ´ordenes totales en el conjunto de los monomios de un anillo de polinomios [M1927], ´ordenes que utiliz´o para caracterizar las posibles funciones de Hilbert de ideales graduados, compar´andolas con ideales monomiales. M´as tarde, Gr¨obner [Gr¨o39] public´o aplicaciones de la idea de Macaulay de ordenar los monomios y de encontrar expl´ıcitamente una base del K- espacio vectorial K[x1,...,xn] I, siendo Iun ideal de dimensi´on cero, aunque s´olo resolvi´o parcialmente este problema. En 1964, Gr¨obner propuso a su estudiante Bruno Buchberger el c´alculo de tales bases como tema para su tesis doctoral. La intenci´on de ambos era resolver el problema del c´alculo de una K-base de K[x1,...,xn] Isiendo Iun ideal de dimensi´on cero. Para su sorpresa, consiguieron desarrollar un algoritmo que era v´alido para cualquier ideal I. Incomprensiblemente los resultados obtenidos por Buchberger recibieron escasa atenci´on hasta principios de los a˜nos setenta, fue entonces cuando Buchberger acu˜n´o el t´ermino base de Gr¨obner. En el terreno cient´ıfico sucede muchas veces que las nuevas teor´ıas suelen ser obtenidas casi simult´anea e independientemente por distintos investigadores, de hecho as´ı fue en este caso pues a la vez que se desarrollaba la teor´ıa de las bases de Gr¨obner, Hironaka [Hir64] introduce, aunque de modo no constructivo, las bases est´andar (”standard bases”) para ideales en el anillo de series de potencias; estas bases han resultado ser an´alogas de las bases de Gr¨obner. El trabajo de Hironaka fue independiente del de Buchberger, y no fue hasta los a˜nos setenta cuando la analog´ıa fue sacada a la luz. Knuth y Bendix [KnB70] desarrollaron la idea de la compleci´on del par cr´ıtico, estructura que recuerda al algoritmo de Buchberger, para la completa reescritura de sistemas de ecuaciones (”term-rewriting systems”). Incluso antes que el correspondiente concepto en ´algebras asociativas conmutativas libres, las bases de Gr¨obner para ideales en ´algebras de Lie libres fueron introducidas por Shirshov [Shi62]. v Desde su creaci´on, la teor´ıa de las Bases de Gr¨obner ha experimentado un notable crecimiento. Si se restringe a sus aplicaciones, se ve que estas aparecen por doquier, en ´areas tan diversas de las matem´aticas como la integraci´on indefinida de funciones racionales, la teor´ıa de c´odigos, la estad´ıstica, las ecuaciones en derivadas parciales, la teor´ıa de grafos, programaci´on entera, funciones hipergeom´etricas, an´alisis num´erico, dise˜no geom´etrico asistido por ordenador, teor´ıa de homotop´ıa combinatoria, etc (v´ease [BuW98]). En el caso particular del ´algebra conmutativa y geometr´ıa algebraica, proporciona m´etodos para el c´alculo de inversas de aplicaciones racionales, la resoluci´on de sistemas de ecuaciones polin´omicas, la inversi´on de matrices, el c´alculo del m´aximo com´un divisor de varios polinomios, la pertenencia de un polinomio a un ideal del anillo de polinomios en nvariables, el c´alculo de las ecuaciones impl´ıcitas de una variedad a partir de sus ecuaciones param´etricas, etc (v´ease [CLO92, BeW93]). El trabajo que a continuaci´on se presenta consta de dos partes claramente diferenciadas. En la primera, se utilizan bases de Gr¨obner para calcular la Forma Normal de Smith (primer cap´ıtulo) y para calcular la factorizaci´on de un polinomio libre de cuadrados en una variable, con coeficientes en un cuerpo finito (segundo cap´ıtulo). En la segunda parte (tercer cap´ıtulo) se aborda un tema m´as arduo, la definici´on del concepto de base de Gr¨obner en el ´algebra envolvente universal de un ´algebra de Leibniz. Como en todo trabajo de investigaci´on, se plantean al principio del mismo los objetivos que se pretenden alcanzar, en este caso, el director de esta tesis propuso un doble objetivo, por una parte la obtenci´on de la forma can´onica de Jordan de una matriz dada, utilizando las Bases de Gr¨obner como herramienta de c´alculo, y por otra, la definici´on de bases de Gr¨obner en el ´algebra envolvente universal de un ´algebra de Leibniz gde dimensi´on finita. El c´alculo, utilizando bases de Gr¨obner, de la forma can´onica de Jordan era un procedimiento que no se conoc´ıa, pero se ten´ıa el convencimiento de vi que tal procedimiento exist´ıa, de que hab´ıa una conexi´on entre las bases de Gr¨obner y el c´alculo de la forma can´onica de Jordan. Puesto que las formas can´onicas de las matrices (la forma can´onica de Jordan, la forma can´onica de Frobenius, la segunda forma can´onica y la forma can´onica de Jacobson [Ser02, Jea99]) se pueden obtener a partir de la Forma Normal de Smith, se cambi´o el objetivo inicial por uno m´as ambicioso, el c´alculo de la Forma Normal de Smith con bases de Gr¨obner. El primer paso que se dio para lograr calcular la Forma Normal de Smith utilizando las bases de Gr¨obner, fue el an´alisis del algoritmo cl´asico de obtenci´on de dicha forma can´onica [Jac74]. Un an´alisis con detalle muestra que es posible una reformulaci´on de dicho algoritmo, las ideas b´asicas son ahora diagonalizaci´on y reordenaci´on de los divisores elementales. Se llega de esta forma a un algoritmo nuevo de c´alculo de la Forma Normal de Smith, la traducci´on de este algoritmo al contexto de bases de Gr¨obner proporcionar´a el procedimiento buscado. Sea A∈Matm×n(D) una matriz con coeficientes en un DIP y el ideal IA de D[x1, ..., xn] generado por las filas de la matriz A·(x1, ..., xn)T. El c´alculo de la base de Gr¨obner del ideal IAno es otra cosa que aplicar el algoritmo de eliminaci´on de Gauss a la matriz A. Teniendo en cuenta que al aplicar Gauss a una matriz se est´an haciendo s´olo operaciones en filas, y que para obtener la Forma Normal de Smith es necesario hacer, por norma general, operaciones en filas y columnas, ¿c´omo es posible obtener la Forma Normal de Smith si no se est´a operando en columnas? Esta dificultad que se presenta es f´acilmente salvable, sin m´as que tener en cuenta que operar en columnas no es m´as que operar en filas en la traspuesta. De esta forma surge la idea de aplicar Gauss a una matriz (operaciones en filas), trasponer el resultado, volver a aplicar el algoritmo de Gauss (operaciones en columnas en la matriz original), trasponer el resultado y volver a empezar el proceso. Inmediatamente surge la pregunta de si esta sucesi´on de bases de Gr¨obner conduce a la Forma Normal de Smith. La respuesta, como a vii continuaci´on se ver´a es que no, este proceso conduce siempre hacia una matriz diagonal equivalente a la matriz inicial (diagonalizaci´on). No obstante, una vez aqu´ı, la obtenci´on de la Forma Normal de Smith se consigue sin mayor dificultad sin m´as que reordenar los divisores elementales (reordenaci´on). Obtenido el algoritmo se plantean otros dos desaf´ıos no menos interesantes. El primero es la obtenci´on de las matrices de paso y, como consecuencia, de las formas can´onicas m´as conocidas: la forma can´onica racional o de Frobenius, la segunda forma can´onica, las formas can´onicas de Jacobson y Jordan (objetivo inicial) pues todas ellas se pueden obtener a partir de la Forma Normal de Smith. Un trabajo sobre un tema de ´algebra computacional no se puede entender actualmente sin la programaci´on de los algoritmos obtenidos, pues bien, este punto constituye el segundo desaf´ıo. El planteamiento que se ha hecho, desde un principio, del c´alculo de la Forma Normal de Smith ha sido tomar como base un DIP cualquiera, por coherencia con esta forma de proceder, se ha desarrollado un paquete en lenguaje Mathematica, el paquete SmithGroebner, que es capaz de operar en cualquier DIP que el usuario desee. Esta capacidad que posee el paquete SmithGroebner de manejar cualquier DIP, que es muy interesante desde un punto de vista matem´atico, parad´ojicamente es tambi´en su principal desventaja, pues al tener que programar en un DIP cualquiera, se est´a obligado ”a priori” a utilizar rutinas lo m´as generales posibles, no contempladas en Mathematica y por lo tanto no compiladas, que ya de partida van a hacer m´as lento su funcionamiento. A´un as´ı, no hay actualmente disponible ning´un programa de computaci´on simb´olica que ofrezca unas prestaciones y una flexibilidad a la hora de escoger el DIP de trabajo, comparables a las que proporciona el paquete SmithGroebner, t´engase en cuenta que se est´a hablando de un paquete en el que tiene cabida cualquier DIP. viii Fermat es un lenguaje de computaci´on simb´olica que permite calcular la Forma Normal de Smith de matrices con coeficientes en Q,ZoFq, posibilidad cubierta tambi´en por el paquete SmithGroebner. Magma permite calcular la Forma Normal de Smith de matrices con coeficientes en un dominio eucl´ıdeo, posibilidad cubierta y ampliada por el paquete SmithGroebner, pues ´este da la ocasi´on a mayores de trabajar en un DIP que no sea dominio euclideo, por ejemplo el anillo Z[1+√−19 2] [Cam88, Gre97]. Reduce [Hea95] posee el paquete normform para calcular la Forma Normal de Smith de matrices con coeficientes en Z,Q[x] o en anillos de la forma Q(y1, ..., yn)[x]. Tambi´en calcula la forma can´onica de Frobenius, la forma can´onica de Jacobson y la forma can´onica de Jordan. Este paquete que posee Reduce es quiz´as el que m´as se acerca a las prestaciones que ofrece SmithGroebner. Mathematica posee los paquetes IntegerSmithNormalForm.m yPolynomialSmithNormalForm.m que calculan la Forma Normal de Smith de matrices con coeficientes en ZyQ[x] respectivamente. El paquete SmithGroebner que aqu´ı se presenta, se puede considerar como una extensi´on de estos dos paquetes. Maple proporciona rutinas para calcular la Forma Normal de Smith de matrices con coeficientes en ZoF[x], siendo Fun cuerpo, posibilidad cubierta por el paquete SmithGroebner. Los DIPs que por defecto maneja el paquete SmithGroebner, aunque como se ha dicho es posible a˜nadir cualquier otro que desee el usuario, son:1 Z Z[i]Q R C Zp FqZ[1+√−19 2]Q[x]R[x]C[x]Zp[x] Fq[x] 1Fq: Cuerpo finito de q elementos ix El paquete SmithGroebner es capaz de: Calcular la Forma Normal de Smith y las matrices de paso de una matriz con coeficientes en cualquier DIP de los anteriores. Calcular la inversa de una matriz con coeficientes en cualquier DIP de los anteriores. Calcular la forma can´onica de Frobenius, la segunda forma can´onica y las formas can´onicas de Jacobson y Jordan, as´ı como sus respectivas matrices de paso, de una matriz con coeficientes en uno de los cuerpos anteriormente citados. Calcular los generadores zide los c´ıclicos en los que descompone un K[x]-m´odulo finitamente generado (Kcuerpo) y los generadores de sus ideales aniquiladores (0 : zi); los cuales se obtienen como tesis en el Teorema de Estructura de M´odulos finitamente generados definidos sobre un DIP. Paralelamente al desarrollo del paquete SmithGroebner, se ha ido escribiendo un notebook en Mathematica en el que se explican los DIPs disponibles y el modo de funcionamiento de los comandos al servicio del usuario, que proporciona el paquete SmithGroebner. Dicha ayuda, una vez instalada, puede ser consultada dentro de la ayuda del propio Mathematica en la secci´on Addons, subsecci´on bases de Gr¨obner La ´ultima secci´on de este primer cap´ıtulo, est´a dedicada a la utilizaci´on del paquete SmithGroebner para mostrar algunas aplicaciones del c´alculo de la Forma Normal de Smith, en tres campos bien distintos: La identificaci´on de grupos abelianos finitamente generados. La resoluci´on de sistemas de ecuaciones diferenciales lineales. La resoluci´on de sistemas de ecuaciones diof´anticas. x Durante el desarrollo del paquete SmithGroebner surgi´o la necesidad de factorizar polinomios en una variable sobre un cuerpo finito, para poder implementar los algoritmos de c´alculo de las distintas formas can´onicas que manejan los divisores elementales. Como Mathematica no tiene, hasta donde el que suscribe sabe, un comando espec´ıfico, ni un paquete, de c´alculo de dicha factorizaci´on, surgi´o la necesidad de programar el algoritmo de Berlekamp [Ber67] para obtenerla. El algoritmo de Berlekamp proporciona una forma r´apida y elegante de factorizar polinomios sobre cuerpos finitos de orden peque˜no q. La idea clave en la que se basa este algoritmo es la de sacar partido de las soluciones de la ecuaci´on: g(x)q−g(x) = 0 mod f(x) siendo f(x) el polinomio m´onico de grado na factorizar. Para a continuaci´on resolver un cierto sistema de ecuaciones lineales de orden n, y con cada elemento h(x) de una base del espacio soluci´on, ir desgranando los factores irreducibles del polinomio f(x) al utilizar la f´ormula: f(x) = Y c∈Fq GCD(f(x), h(x)−c) Este algoritmo tambi´en proporciona una forma de factorizar polinomios sobre Z, pues basta con factorizar sobre Znsiendo n un entero lo suficientemente grande [Ber72]. La pista que proporcion´o la traducci´on del algoritmo de Berlekamp a un contexto con bases de Gr¨obner, y con ello el embri´on de lo que ser´ıa el segundo cap´ıtulo, fueron los art´ıculos de Lazard [Laz85] y Czichowski [Czi95]. En el ´ultimo de estos art´ıculos el autor, bas´andose en el trabajo de Lazard, calcula la integral de una funci´on racional P(x) Q(x), siendo P(x), Q(x)∈K[x] (Kcuerpo de caracter´ıstica cero) y Q(x) un polinomio m´onico y libre de cuadrados. Para ello, da precisamente el m´etodo de calcular los m´aximos comunes dixi 4 1 Bases de Gr¨obner y la Forma Normal de Smith con d1|d2|cij ∀i, j. Tras min(m, n) etapas como mucho, el proceso termina con la obtenci´on de la Forma Normal de Smith:             d10 ... dp 0 ... 0 0             con d1|d2|...|dp. Computacionalmente hablando, como posteriormente se comprobar´a, es un c´alculo pesado, pedir que en la etapa i-´esima didivida a todos los elementos de la matriz que est´an por debajo de ´el. Surge de modo natural entonces la pregunta ¿qu´e sucede si se quita s´olo esta condici´on de divisibilidad? La respuesta es casi inmediata pues, se tendr´ıa un nuevo algoritmo que en un n´umero finito de etapas, conducir´ıa a una matriz diagonal que tiene la misma Forma Normal de Smith que la matriz de partida. Una vez aqu´ı, el paso a la Forma Normal de Smith es relativamente f´acil, pues basta con reordenar los factores irreducibles en los que se descomponen los elementos de la diagonal principal [Mal72]. Se llega de este modo a un nuevo algoritmo de c´alculo de la Forma Normal de Smith, las ideas b´asicas son ahora: - Diagonalizaci´on - Reordenaci´on La traducci´on a un contexto con bases de Gr¨obner del proceso de diagonalizaci´on, es la clave para la obtenci´on del algoritmo buscado. Para dicha traducci´on se procede del siguiente modo. Es conocido, que para obtener la Forma Normal de Smith de una matriz, es necesario por norma general, hacer operaciones elementales en filas y columnas. Al aplicar el algoritmo de eliminaci´on de Gauss a una matriz, se est´an haciendo s´olo operaciones en 1.1 Introducci´on 5 filas; se puede pensar entonces que no existe tal conexi´on entre las bases de Gr¨obner y el c´alculo de la Forma Normal de Smith, pues no se act´ua sobre las columnas de la matriz. Esta dificultad que se presenta es f´acilmente salvable, sin m´as que tener en cuenta que operar en columnas no es m´as que operar en filas en la traspuesta. Surge entonces de modo natural, la idea de aplicar el algoritmo de eliminaci´on de Gauss a una matriz dada (=operaciones elementales en filas), trasponer el resultado y volver a aplicar el algoritmo de eliminaci´on de gaussiana a esta nueva matriz (=operaciones elementales en columnas en la matriz original), trasponer el resultado y volver a empezar el proceso. Inmediatamente surge la pregunta de si esta ”sucesi´on de bases de Gr¨obner” conduce o no a la Forma Normal de Smith, la respuesta a esta cuesti´on es que no, pues en general este proceso conduce a la obtenci´on de una matriz diagonal que tiene la misma Forma Normal de Smith que la de partida. Como posteriormente se comprobar´a, es precisamente esta forma de actuar, la traducci´on a un contexto con bases de Gr¨obner del proceso de diagonalizaci´on citado anteriormente, pues aunque en principio no lo parezca, un an´alisis m´as en profundidad mostrar´a que se est´a haciendo lo mismo en ambos casos. Obtenido el algoritmo de c´alculo de la Forma Normal de Smith, se plantean otros dos desaf´ıos no menos interesantes. El primero de ellos es la obtenci´on de las matrices de paso y, como consecuencia, de las formas can´onicas m´as conocidas: la forma can´onica Racional o de Frobenius, la segunda forma can´onica, las formas can´onicas de Jacobson y Jordan. El punto clave para lograr calcular las matrices de paso, es darse cuenta que la Reordenaci´on se puede lograr aplicando el algoritmo de Diagonalizaci´on a una matriz adecuada. Si a una matriz A= (aij) de mfilas y ncolumnas le aplicamos el algoritmo de diagonalizaci´on esbozado anteriormente, obtendremos una matriz diagonal D=diag(d1, ..., dp,0, ..., 0) que posee la misma Forma Normal de Smith que 6 1 Bases de Gr¨obner y la Forma Normal de Smith la matriz inicial. Para conseguir la Forma Normal de Smith se proceder´a del siguiente modo, en primer lugar se construye la matriz: D1=             d10. . . . . . . . . . . . . . . 0 . . ..... . .. . . dr. . . dr . . . 0 0 . . . . . ..... . . 0. . . . . . . . . . . . 0... 0             D1posee la misma Forma Normal de Smith que las matrices AyD. Si se aplica a D1el algoritmo de diagonalizaci´on se obtiene una matriz de la forma: D2=               mcd(d1, ..., dr) 0 d0 2... d0 r 0 ... 0 0               por la propia mec´anica heredada del algoritmo cl´asico de c´alculo de la Forma Normal de Smith, para matrices que sean de la misma forma que D1. Aplicando de nuevo el proceso a la submatriz de D2obtenida al eliminar la primera fila y columna y as´ı sucesivamente, se conseguir´a en un n´umero finito de etapas, obtener una matriz de la forma:             e10 ... er 0 ... 0 0             1.2 Planteamiento Inicial 7 con e1|e2|...|er, esto es, habremos calculado la Forma Normal de Smith de la matriz A. Llegados a este punto, es posible concluir que el proceso de diagonalizaci´on es la clave para obtener la Forma Normal de Smith, a su vez, el algoritmo de eliminaci´on de Gauss aplicado de forma reiterada, es el n´ucleo del algoritmo de Diagonalizaci´on. Dada una matriz Ade mfilas y ncolumnas, las matrices de paso se van a ir construyendo de la siguiente forma, en primer lugar se aplica el algoritmo de eliminaci´on de Gauss a la matriz (A|Im), siendo Imla matriz identidad de orden m, de esta forma se obtiene una matriz (B|P), y se consigue no s´olo hacer operaciones en las filas de la matriz A, sino que adem´as, en las posiciones de Imse ”guarda memoria” de lo hecho, esto es, B=PA. A continuaci´on se repite el mismo proceso anterior pero para la traspuesta de By la matriz In, con lo cual se obtendr´a una matriz (C|Q) verificando C=QBT, se puede concluir entonces que la matriz traspuesta de C (= CT) es la matriz Adespu´es de haber realizado operaciones elementales en las filas y en las columnas, as´ı pues CT=PAQT. Aplicando el algoritmo de diagonalizaci´on de este modo, dentro del algoritmo de c´alculo de la Forma Normal de Smith, es posible ir construyendo las matrices de paso. La aproximaci´on que en este cap´ıtulo se presenta, al c´alculo de la Forma can´onica Racional o de Frobenius es mediante un algoritmo determinista. Se han hecho tambi´en aproximaciones a este c´alculo mediante algoritmos probabil´ısticos [GiS02]. En lo que sigue, D denota a un dominio de ideales principales (esto es, D es un anillo unitario y conmutativo tal que todo ideal est´a generado por uno de los elementos del propio ideal), m, n y r son n´umeros naturales. 1.2. Planteamiento Inicial En esta segunda secci´on, se va a exponer el algoritmo de c´alculo de la Forma Normal de Smith, v´ease [Jac74], que servir´a como base a partir de 8 1 Bases de Gr¨obner y la Forma Normal de Smith la cual, se construir´a un nuevo algoritmo de obtenci´on de la Forma Normal de Smith, que utiliza las bases de Gr¨obner como herramienta de c´alculo. Para ello es necesario establecer, previamente, las siguientes definiciones y resultados. Definici´on 1.2.1 Dado d∈D, se denomina longitud de d, brevemente l(d), al n´umero de elementos primos de su factorizaci´on. Ejemplo 1.2.2 Sea D=Z l(8) = l(2 ·2·2) = 3 l(6) = l(2 ·3) = 2 l(−1) = 0 Proposici´on 1.2.3 Si u∈Des unidad, entonces l(u) = 0. Definici´on 1.2.4 Sobre el conjunto Matm×n(D)se define la siguiente relaci´on binaria: A, B ∈Matm×n(D)se dicen equivalentes , brevemente A≃B, si existen P∈ Matm×m(D)yR∈Matn×n(D)ambas inversibles, tales que B=PAR. Proposici´on 1.2.5 ≃es una relaci´on de equivalencia. Definici´on 1.2.6 Las matrices P y Q se denominan matices de paso. Definici´on 1.2.7 Se denomina matriz elemental , a una matriz que es de alguna de estas tres formas: Dado b∈D,i, j, n ∈Ntales que i6=j, i ≤n, j ≤n. Tij(b)es una matriz cuadrada de orden n, con un uno en cada posici´on de su diagonal principal, b en la posici´on (i,j) y cero en el resto. Dado u∈Dunidad, i, n ∈Ntales que i≤n. Di(u)es una matriz cuadrada de orden n y diagonal, con u en el lugar (i,i) y un uno en las dem´as posiciones de su diagonal principal. 1.2 Planteamiento Inicial 9 Dados i, j, n ∈N, tales que i, j ≤n. Pij es la matriz que se obtiene a partir de la matriz identidad de orden n, intercambiando las filas i y j. Definici´on 1.2.8 Dada A∈Matm×n(D), son operaciones elementales en A, la multiplicaci´on por la izquierda o por la derecha, por matrices elementales. Las operaciones elementales son pues: 1. Tij(b)·A−→ Matriz obtenida a partir de A, sum´andole a la fila i la fila j multiplicada por b. 2. A·Tij(b)−→ Matriz obtenida a partir de A, sum´andole a la columna j la columna i multiplicada por b 3. Di(u)·A−→ Matriz obtenida a partir de A, multiplicando la fila i por u. 4. A·Di(u)−→ Matriz obtenida a partir de A, multiplicando la columna i por u. 5. Pij ·A−→ Matriz obtenida a partir de A, intercambiando las filas i y j. 6. A·Pij −→ Matriz obtenida a partir de A, intercambiando las columnas i y j. Observaciones: Multiplicar por la izquierda por una matriz elemental, conlleva una transformaci´on en filas Multiplicar por la derecha por una matriz elemental, conlleva una transformaci´on en columnas. 10 1 Bases de Gr¨obner y la Forma Normal de Smith Al realizar una operaci´on elemental sobre una matriz, se obtiene una matriz equivalente a la inicial. Teorema 1.2.9 [Jac74] Cualquier matriz de m filas por n columnas con coeficientes en D, es equivalente a una matriz diagonal, cuyos elementos no nulos, d1, ..., dr,verifican que d1divide a d2, d2divide a d3,..., dr−1divide a dr. Adem´as, esta matriz diagonal es ´unica, salvo multiplicaci´on de los elementos diagonales no nulos por unidades de D, y se denomina Forma Normal de Smith. Definici´on 1.2.10 Sea A∈Matm×n(D)yS=diag(d1, ..., dr,0, ..., 0) su Forma Normal de Smith (d1, ..., drno nulos). Entonces: d1, ..., drse denominan factores invariantes de A. Consid´erense las factorizaciones en irreducibles de los factores invariantes: di=pei1 i1·... ·peirj irj, pij 6=pis si j6=s, i = 1, ..., r Entonces cada peij ij se denomina divisor elemental sobre D de A. La propia demostraci´on del teorema anterior constituye un algoritmo de c´alculo de la Forma Normal de Smith. Es precisamente este algoritmo el punto de partida; una reformulaci´on del mismo m´as la traducci´on de esta reformulaci´on al contexto de bases de Gr¨obner son los pasos que se seguir´an para lograr el objetivo de este cap´ıtulo. A continuaci´on se presenta la citada demostraci´on en formato de algoritmo de c´alculo de la Forma Normal de Smith; debido a su extensi´on y para facilitar su comprensi´on, se presenta troceado en dos rutinas, el algoritmo Smith (la rutina principal) y el algoritmo Divisible (una subrutina de la rutina principal). Algoritmo 1.2.11 Smith Entrada: A∈Matm×n(D)tal que A es no nula. Salida: La Forma Normal de Smith de A. 1.2 Planteamiento Inicial 11 1. Se coloca, mediante transformaciones elementales (cambios de filas y columnas), un elemento no nulo y con longitud m´ınima, en la posici´on (1,1). Esta matriz as´ı obtenida, es equivalente a la inicial y pasa a ser A. 2. A=Divisible(A) 3. Todos los elementos no nulos de la primera fila y columna son divisibles por a11, a diferencia de lo que ocurre con el resto de los elementos de la matriz que no tienen por qu´e serlo. Mediante operaciones elementales sobre filas y columnas de la matriz A, se llega a una matriz de la forma:       a11 0... 0 0b22 ... b2n . . .. . ..... . . 0bm2... bmn       4. Mientras a11 no divida a todos los elementos de la matriz. a) Se escoge un bij que no sea divisible por a11. b)A=T1i(1) ·A(se le suma a la primera fila de A, la i-´esima) c)A=Divisible(A) d) Todos los elementos no nulos de la primera fila y columna, son divisibles por a11, a diferencia de lo que ocurre con el resto de los elementos de la matriz que no tienen porque serlo. Mediante operaciones elementales sobre las filas y columnas de la matriz A, se llega a una matriz de la forma:       a11 0... 0 0b22 ... b2n . . .. . ..... . . 0bm2... bmn       12 1 Bases de Gr¨obner y la Forma Normal de Smith 5. A es de la forma:       d11 0... 0 0c22 ... c2n . . .. . ..... . . 0cm2... cmn       verificando que d11 divide a cij,i∈ {2, ..., m}, j ∈ {2, ..., n} 6. Se aplica este algoritmo de nuevo, a la submatriz:     c22 ... c2n . . ..... . . cm2... cmn     7. Fin. Algoritmo 1.2.12 Divisible Enrada: A∈Matm×n(D)tal que A es no nula Salida: Una matriz equivalente a la matriz de entrada, que verifica que todo elemento no nulo de la primera fila y primera columna, es divisible por el elemento que ocupa la posici´on (1,1). 1. Mientras todo elemento no nulo de la primera fila y columna no sea divisible por a11. a) ¿Existe en la primera fila un elemento no nulo que no sea divisible por a11? 1) S´ı i) Se lleva este elemento hasta la posici´on (1,2) mediante un intercambio de columnas. A es ahora de la forma: 1.2 Planteamiento Inicial 13     a b a13 a1n . . .. . .. . ..... . . am1am2am3amn     ii) Se calculan d,α, β,s,t∈Dtales que: d=mcd(a, b) α·a+β·b=d a=s·d b=t·d iii) A=       a b a13 . . . a1n a21 a22 . . .. . .. . . . . .. . .. . ..... . . am1am2. . . . . . amn        ·          α−t0... 0 β s 0... 0 0 0 1 ... 0 . . .. . .. . ..... . . 0 0 0 ... 1          =       d0a13 . . . a1n α·a21 +β·a22 −t·a21 +s·a22 a23 . . . a2n . . .. . .. . ..... . . α·am1+β·am2−t·am1+s·am2am3. . . amn       [Nota: l(a)> l(d). La longitud del elemento que ocupa la posici´on (1,1) disminuye.] b) ¿Existe en la primera columna un elemento no nulo que no sea divisible por a11? 1) S´ı i) Se lleva ese elemento hasta la posici´on (2,1), mediante un intercambio de filas. A es de la forma: 20 1 Bases de Gr¨obner y la Forma Normal de Smith E=             f10. . . 0. . . 0 0e10. . . . . .. . .... . . .er. . . er . . .. . . ... 0 0 0 . . . 0             Si se vuelve a aplicar el algoritmo Diagonaliza a esta nueva matriz se obtendr´a otra diagonal que tiene en su posici´on (2,2), el primer factor invariante de la submatriz diag(e1, ..., er)∈Mat(m−1)×(n−1)(D) que es, el segundo factor invariante de la matriz E. Es importante destacar que la primera fila y la primera columna no influyen a la hora de aplicar el algoritmo Diagonaliza a la matriz E, es m´as, no sufren ninguna modificaci´on. Si se continua este proceso (el bucle del algoritmo SmithR), se obtendr´a al final la Forma Normal de Smith. A la vista del algoritmo SmithR, se puede observar que, la base sobre la que se apoya la reformulaci´on del algoritmo de c´alculo de la Forma Normal de Smith, es el proceso de diagonalizaci´on. De hecho, una traducci´on de este algoritmo de diagonalizaci´on al contexto de bases de Gr¨obner, proporcionar´ıa de modo inmediato un algoritmo de c´alculo de la Forma Normal de Smith. Este es, precisamente el objetivo de la pr´oxima secci´on. 1.4. Una soluci´on con Bases de Gr¨obner Antes de exponer el teorema central, pilar b´asico como se ver´a, del algoritmo de computaci´on de la Forma Normal de Smith, es necesario establecer previamente unos conceptos. Definici´on 1.4.1 Dada A= (aij)∈Matm×n(D), se llamar´a ideal asociado a A, brevemente IA,al ideal de D[x1, ..., xn]generado por: 1.4 Una soluci´on con Bases de Gr¨obner 21 f1=a11x1+... +a1nxn . . . fm=am1x1+... +amnxn Definici´on 1.4.2 Dadas A= (aij)∈Matm×n(D)yB∈Mat(m+r)×n(D), se dir´a que B es igual a A salvo un n´umero finito de filas nulas, brevemente B=0A, si: B=             a11 . . . a1n . . ..... . . am1. . . amn 0. . . 0 . . ..... . . 0. . . 0             Proposici´on 1.4.3 Dadas A∈Matm×n(D)yB∈Mat(m+r)×n(D), se verifica: Si B=0A, entonces A y B tienen el mismo rango y los mismos factores invariantes. Definici´on 1.4.4 MatN×n(D) := t m∈NMatm×n(D) Definici´on 1.4.5 Sean A, B ∈MatN×n(D). B es equivalente a A salvo un n´umero finito de filas nulas, brevemente B ≃0A, si la Forma Normal de Smith de B es igual, salvo un n´umero finito de filas nulas, a la Forma Normal de Smith de A. Proposici´on 1.4.6 ≃0es transitiva. Proposici´on 1.4.7 Dadas A, B ∈MatN×n(D), se verifica: Si B≃0A, entonces A y B tienen el mismo rango y los mismos factores invariantes. 22 1 Bases de Gr¨obner y la Forma Normal de Smith Fijado un orden monomial cualquiera en D[x1, x2, ..., xn] con x1> x2> ... > xn, se establece: Definici´on 1.4.8 Dados f, g ∈D[x1, x2, ..., xn] 1. lp(f) denota la potencia principal de f. 2. lc(f) denota el coeficiente principal de f. 3. lt(f) denota al producto de lc(f) por lp(f). 4. La sicigia de f y g es: S(f, g) = mcm(lc(f),lc(g)) lc(f)·mcm(lp(f),lp(g)) lp(f)f−mcm(lc(f),lc(g)) lc(g)·mcm(lp(f),lp(g)) lp(g)g El teorema que sigue, es la base del algoritmo de c´alculo que en este cap´ıtulo se presenta. Dada A∈MatN×n(D), se demuestra que cualquier base de Gr¨obner Fuerte de IA[AdL94], proporciona una matriz equivalente aA. Teorema 1.4.9 Sea A= (aij)∈Matm×n(D)una matriz no nula. Se verifica: 1. Cualquier base de Gr¨obner Fuerte de IAes de la forma: {g1=a1 1x1+a1 2x2+...+a1 nxn, g2=a2 2x2+...+a2 nxn, ..., gn=an nxn}∪B siendo B, o el conjunto vac´ıo, o un conjunto formado por polinomios homog´eneos en x1, ..., xn, de grado mayor o igual que 2. 2. La matriz Lad(A) :=             a1 1. . . a1 n .... . . an n 0... 0 . . .. . . 0... 0             ∈Matm×n(D) 1.4 Una soluci´on con Bases de Gr¨obner 23 que se obtiene a partir de la base de Gr¨obner Fuerte de apartado anterior, es equivalente a A. 3. Existe P∈Matm×m(D)inversible, tal que Lad(A) = P·A Demostraci´on: Sea A= (aij)∈Matm×n(D),tal que A es no nula. Se supondr´a que las filas de A est´an ordenadas de la siguiente forma:                       0 . . . 0 0 0 . . .. . . 0 0 . . .                       Esto es, en primer lugar las filas cuya primera columna es no nula, luego, a continuaci´on, las filas cuya primera columna es nula y la segunda columna es no nula, y as´ı sucesivamente. Esta ordenaci´on no es restrictiva, esto es, no hay que reordenar la matriz antes de calcular la base de Gr¨obner. Es simplemente una cuesti´on de resaltar que se va a considerar cada bloque de filas por separado, y para simplificar notaci´on. Se tiene entonces una partici´on de {1, ..., m}. Se define: I1={1, ..., p1}, ´ındices correspondientes a las filas de A cuya primera columna es no nula. I2={p1+ 1, ..., p2}, ´ındices correspondientes a las filas de A cuya primera columna es nula y la segunda es no nula. 24 1 Bases de Gr¨obner y la Forma Normal de Smith ... In={pn−1+ 1, ..., m}, ´ındices correspondientes a las filas de A cuya primera columna no nula es la columna n. I1tI2t... tIn={1, ..., m}. Cabe la posibilidad de que uno o varios Iisean el conjunto vac´ıo. Sea {f1, ..., fm}el conjunto de generadores de IA. De aqu´ı en adelante, se utilizar´a la palabra bloque, para designar el conjunto de todos los polinomios cuyos sub´ındices est´an en un mismo Ii. {f1, ..., fm}es un conjunto de polinomios homog´eneos de grado 1. El car´acter homog´eneo de los polinomios iniciales es heredado por las sicigias y sus reducidos m´odulo un determinado conjunto de polinomios tambi´en homog´eneos. Esto es, todos los polinomios no nulos que aparecen al aplicar el algoritmo de c´alculo de una base de Gr¨obner, son homog´eneos de grado mayor o igual que 1. Adem´as, s´olo al hacer la sicigia de dos polinomios cuyos sub´ındices est´an en el mismo Ik, se puede obtener un polinomio homog´eneo de grado uno. Esto es as´ı, por el car´acter homog´eneo de grado 1, de los polinomios iniciales. A continuaci´on se procede a aplicar el algoritmo de c´alculo de una base de Gr¨obner a IA. Se empieza por calcular las sicigias y sus reducidos, al llegar al c´alculo de una sicigia de dos polinomios cuyos sub´ındices est´an en el mismo Ik, se razona de la siguiente forma: Se supone que f1yf2est´an en el primer bloque, esto es {1,2} ⊆ I1, y se quiere calcular S(f1, f2). f1=a11x1+... +a1nxn;a11 6= 0 f2=a21x1+... +a2nxn;a21 6= 0 S(f1, f2) = mcm(a11,a21) a11 f1−mcm(a11,a21) a21 f2=a21 mcd(a11,a21)f1−a11 mcd(a11,a21)f2= 1.4 Una soluci´on con Bases de Gr¨obner 25 =a21 mcd(a11,a21)(a11x1+... +a1nxn)−a11 mcd(a11,a21)(a21x1+... +a2nxn) = =a21a12−a11a22 mcd(a11,a21)x2+... +a21a1n−a11a2n mcd(a11,a21)xn Se comprueba que este polinomio se puede obtener, multiplicando por una matriz inversible. Se define: B=      a11 . . . a1n . . ..... . . am1. . . amn 0. . . 0       ;B=0A          1 0 . . . 0 0 1 0 . . .. . ..... . . .... . . a21 mcd(a11,a21)−a11 mcd(a11,a21)0... 0 1          ·      a11 . . . a1n . . ..... . . am1. . . amn 0. . . 0       =       a11 a12 . . . a1n . . .. . . am1am2. . . amn 0a21a12−a11a22 mcd(a11,a21)... a21a1n−a11a2n mcd(a11,a21)       =C La ´ultima fila de C contiene los coeficientes de S(f1, f2).Queda por calcular S(f1, f2){f1,...,fm}. S(f1, f2)f1. . . fm fsq1... qm 26 1 Bases de Gr¨obner y la Forma Normal de Smith s es el ´ındice que le corresponde al nuevo polinomio, hay que tener en cuenta que es posible que se hayan a˜nadido otros polinomios antes de calcular esta sicigia. S(f1, f2) = m P i=1 qifi+fs=⇒fs=S(f1, f2)− m P i=1 qifi Esto es lo mismo que hacer:          1 0 0 0 1 . . .. . .... 0 0 ...0 −q1−q2. . . −qm1          | {z } Inversible       a11 a12 . . . a1n . . .. . . am1am2. . . amn 0a21a12−a11a22 mcd(a11,a21). . . a21a1n−a11a2n mcd(a11,a21)       =D La ´ultima fila de D contiene los coeficientes de fs. Adem´as se verifica: D≃C≃B=0A entonces, D≃0A y por lo tanto A y D tienen los mismos factores invariantes. Si fs6= 0 entonces lp(fs) = xkpara alg´un k∈ {1, ..., n}y se a˜nade el ´ındice de este nuevo polinomio, s, a Ik. Es muy importante ir a˜nadiendo cada ´ındice nuevo al bloque al que pertenezca a medida que se van obteniendo los polinomios lineales, pues esta demostraci´on se basa en los n´umeros que aparecen en cada Ik. As´ı mismo, se lleva cuenta de las matrices por las que se va multiplicando (para al final obtener P); para ello se define: 1.4 Una soluci´on con Bases de Gr¨obner 27 P1=          1 0 0 0 1 0 . . .. . ..... . . 0 0 ...0 −q1−q2. . . −qm1          ·          1 0 0 0 1 0 . . .. . ..... . . .... . . a21 mcd(a11,a21)−a11 mcd(a11,a21)0... 0 1          P1·A0=Dsiendo A0la matriz A m´as una fila de ceros. Se prosigue con los c´alculos de las sicigias y sus reducidos, hasta que se llega a otra sicigia de dos polinomios cuyos ´ındices vuelven a estar los dos en el mismo Ik. Razonando igual que antes, se define E como la matriz D m´as una fila de ceros. Calcular el polinomio reducido de la sicigia, no es m´as que multiplicar E por una determinada matriz inversible H; sea Fel resultado. Por ser F≃E=0Dse deduce que F≃0D, como adem´as D≃0A, entonces se sigue que F≃0A Para seguir llevando cuenta de las matrices por las que se multiplica, se define: P2=H·      p11 . . . p1m+1 0 . . ..... . .. . . pm+11 . . . pm+1m+1 0 0. . . 0 1       siendo P1=    p11 . . . p1m+1 . . ..... . . pm+11 . . . pm+1m+1     P2·A0=Fsiendo A0la matriz A m´as dos filas de ceros. Siguiendo esta estrategia de c´alculo, se llegar´ıa, al finalizar la computaci´on de la base de Gr¨obner de IA, a una matriz ∆,de r filas y n columnas, que contendr´ıa a todos los polinomios de grado 1 de la base de Gr¨obner, y a una matriz Ω cuadrada e inversible de orden r, tales que Ω ·A0= ∆ (siendo A0la matriz A m´as r-m filas nulas). Adem´as, por construcci´on, ∆ ≃0A. 28 1 Bases de Gr¨obner y la Forma Normal de Smith ∆ se puede volver a pensar, para simplificar notaci´on, que es de la forma:             #I1elementos 0 #I2elementos . . . 0 . . .. . .. . .. . . 0 #In             Una vez obtenida una base de Gr¨obner de IA, hay que calcular una base de Gr¨obner Fuerte para IA. I1, ..., Inson conjuntos saturados [AdL94]. De cualquier otro conjunto saturado J, al calcular fJse va a obtener un polinomio homog´eneo de grado mayor o igual que dos. S´olo al calcular fIk, con Ikno vac´ıo, se obtendr´a un polinomio homog´eneo de grado 1. As´ı, cada bloque Ikno vac´ıo, contribuye con un polinomio fIk. Se ilustra este c´alculo para I1, para los dem´as casos es similar. El primer paso es calcular {aj}j∈I1tales que: X j∈I1 aj·lc(fj) = mcd({lc(fj)/j ∈I1}) (1.1) Por definici´on: fI1=P j∈I1 aj·fj De nuevo, este polinomio tambi´en se puede obtener multiplicando por la izquierda por una matriz inversible. Se define γcomo la matriz ∆ m´as una fila de ceros (γ=0∆). 1.4 Una soluci´on con Bases de Gr¨obner 29             1 ... 1 ... ... a1. . . a#I10. . . 1             | {z } Inversible ·               #I1elementos 0 #I2elementos . . . 0 . . .. . .. . .. . . 0 #In 0 . . . 0               =Σ La ´ultima fila de Σ est´a formada por los coeficientes de fI1en x1, ..., xn. De nuevo Σ ≃γ=0∆, y por lo tanto Σ ≃0∆, como adem´as ∆ ≃0A, se verifica entonces que Σ ≃0A. No hay que olvidar que tambi´en se est´a llevando cuenta de las matrices por las que se multiplica. Se define: Ψ =                1 ... ... 1 ... ... a1. . . a#I10... 0 1                ·              Ω11 Ω1r0 Ωr1Ωrr 0 0 0 1              , con Ω =     Ω11 . . . Ω1r . . ..... . . Ωr1. . . Ωrr     Razonando de igual modo con el resto de los bloques Ikno vac´ıos, se obtendr´ıan PFinal ∈Matu×n(D)yΨFinal ∈Matu×u(D) tales que: 36 1 Bases de Gr¨obner y la Forma Normal de Smith Falta por calcular una base de Gr¨obner Fuerte. Cada bloque Ikno vac´ıo, contribuye con un polinomio. Primer Bloque. I1={1,3}, fI1=f1              1000000 0100000 0010000 0001000 0000100 0000010 1000001              ·              1−1 0 0−5 6 2 3 7 0 3 2 0 0 −13 0 0 28 0 0 0              =                    1−1 0 0−5 6 2 3 7 0 3 2 0 0 −13 0 0 28 1−1 0 | {z } fI1                    =E Se define: P3=              1000000 0100000 0010000 0001000 0000100 0000010 1000001              ·              1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 2−1−1 0 1 0 0 0 3 0 5 0 1 0 0 0 0 0 0 0 1              = =              1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 2−1−10100 0 3 0 5 0 1 0 1 0 0 0 0 0 1              1.4 Una soluci´on con Bases de Gr¨obner 37 Se verifica que E=P3·A3 El segundo bloque est´a formado por dos polinomios (I2={2,4}); el m´aximo com´un divisor de sus coeficientes principales (mcd(−5,3)) es 1. Teniendo en cuenta que 1 = 1·(−5)+2·3se define fI2= 1·(−5y+6z)+2·(3y+2z) = y+ 10z. F=                 10000000 01000000 00100000 00010000 00001000 00000100 00000010 01020001                 ·                 1−1 0 0−5 6 2 3 7 0 3 2 0 0 −13 0 0 −28 1−1 0 0 0 0                 = =                      1−1 0 0−5 6 2 3 7 0 3 2 0 0 −13 0 0 −28 1−1 0 0 1 10 | {z } fI2                      =F Se define: 38 1 Bases de Gr¨obner y la Forma Normal de Smith P4=                 10000000 01000000 00100000 00010000 00001000 00000100 00000010 01020001                 ·                 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 2−1−1 0 1 0 0 0 0 3 0 5 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1                 = =                 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 2−1−101000 0 3 0 5 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 2 0 0 0 1                 Se verifica que F=P4·A4 El tercer bloque est´a formado por dos polinomios (I3={5,6}); el m´aximo com´un divisor de sus coeficientes principales (mcd(−13,28)) es 1. Teniendo en cuenta que 1 = (−13) ·(−13) −6·28 se define fI3=z. G=                   1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0000−13 −6 0 0 1                   ·                    1−1 0 0−5 6 2 3 7 0 3 2 0 0 −13 0 0 28 1−1 0 0 1 10 0 0 0                    = 1.4 Una soluci´on con Bases de Gr¨obner 39 =                        1−1 0 0−5 6 2 3 7 0 3 2 0 0 −13 0 0 28 1−1 0 0 1 10 0 0 1 | {z } Q                        =G P5=                   1000 0 0 000 0100 0 0 000 0010 0 0 000 0001 0 0 000 0000 1 0 000 0000 0 1 000 0000 0 0 100 0000 0 0 010 0000−13 −6001                   ·                    1 0 0 000000 0 1 0 000000 0 0 1 000000 0 0 0 100000 2−1−1010000 0 3 0 501000 1 0 0 000100 0 1 0 200010 0 0 0 000001                    = 40 1 Bases de Gr¨obner y la Forma Normal de Smith =                   1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2−1−1 0 1 0 0 0 0 0 3 0 5 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 2 0 0 0 1 0 −26 −5 13 −30 −13 −6 0 0 1                   Se verifica que G=P5·A5. Adem´as s´olo queda hacer operaciones elementales en G, para obtener la matriz buscada. f1=x−y= 1 ·(x−y)+0·(y+ 10z)+0·z f2=−5y+ 6z= 0 ·(x−y)+(−5) ·(y+ 10z) + 56 ·z f3= 2x+ 3y+ 7z= 2 ·(x−y)+5·(y+ 10z)+(−43) ·z f4= 3y+ 2z= 0 ·(x−y)+3·(y+ 10z)+(−28) ·z f5=−13z= 0 ·(x−y)+0·(y+ 10z)+(−13) ·z f6= 28z= 0 ·(x−y)+0·(y+ 10z) + 28 ·z Por lo tanto: T17(−1) −→ hace cero la primera fila de G T29(−56) ·T28(5) −→ hace cero la segunda fila de G T39(43) ·T38(−5) ·T37(−2) −→ hace cero la tercera fila de G T49(28) ·T48(−3) −→ hace cero la cuarta fila de G T59(13) −→ hace cero la quinta fila de G T69(−28) −→ hace cero la sexta fila de G De este modo, si se define Ψde modo que Ψ := T17(−1)·T29(−56)·T28(5)· T39(43) ·T38(−5) ·T37(−2) ·T49(28) ·T48(−3) ·T59(13) ·T69(−28) entonces se verifica que 1.4 Una soluci´on con Bases de Gr¨obner 41 Ψ·G=                   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 1 0 0 1 10 0 0 1                   si adem´as se intercambian las filas convenientemente, entonces P39 ·P28 ·P17 ·Ψ | {z } Φ ·G=                   −1 1 0 0 1 10 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0                   Φ·G= Φ ·P5·A5                   −1 1 0 0 1 10 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0                   42 1 Bases de Gr¨obner y la Forma Normal de Smith Ψ·P5=                   1 0 0 0 0 0 1 0 0 0 1 0 2 0 0 0 1 0 −26 −5 13 −30 −13 −6 0 0 1 −728 −143 364 −845 −364 −168 0 −3 28 −336 −66 168 −390 −168 −78 0 0 13 728 143 −364 845 364 169 0 0 −28 0 0 0 0 0 0 −1 0 0 1456 286 −728 1690 728 336 0 5 −56 −1120 −220 560 −1300 −559 −258 −2−5 43                   Lad(A) =       −1 1 0 0 1 10 0 0 1 0 0 0       P=      1 0 0 0 0 1 0 2 −26 −5 13 −30 −728 −143 364 −845       La matriz Pverifica que es invertible y que Lad(A) = P·A Para calcular, en general la Forma Normal de Smith de una matriz, es necesario hacer transformaciones en filas y columnas. Como se acaba de comprobar; mediante el c´alculo de una base de Gr¨obner Fuerte del ideal asociado a una matriz dada, se puede obtener una matriz equivalente en filas a la primera. Al calcular una base de Gr¨obner Fuerte, no se realizan operaciones en las columnas de la matriz, s´olo en las filas. Este hecho podr´ıa inducir a pensar que no hay un nexo claro entre la Teor´ıa de las bases de Gr¨obner y el c´alculo de la Forma Normal de Smith (falta operar en columnas). No 1.4 Una soluci´on con Bases de Gr¨obner 43 obstante, esta dificultad es f´acilmente salvable teniendo en cuenta que las operaciones en columnas no son m´as, que operaciones en filas en la traspuesta. Estos dos hechos, por una parte que una base de Gr¨obner Fuerte proporcione una matriz equivalente en filas, y por otra, saber que las operaciones en columnas no son m´as que operaciones en filas en la traspuesta, son el origen de un concepto que va a desempe˜nar un papel central, en el algoritmo de diagonalizaci´on, el concepto de par equivalente. Definici´on 1.4.11 Se llamar´a par equivalente de una matriz no nula A= (aij), brevemente e A, a un par de matrices (1A= (1aij),2A= (2aij)), tales que: 1A=Lad(A) 2A=Lad(1AT), siendo 1ATla matriz traspuesta de 1A. Lema 1.4.12 A≃1A≃2AT Lema 1.4.13 Sea i un n´umero natural tal que ai1es el primer elemento no nulo de la primera columna de una matriz no nula A= (aij). Se verifica: l(ai1)≥l(1a11)≥l(2a11). Demostraci´on: Trivial si se tiene en cuenta que 1a11 (2a11) es el m´aximo com´un divisor de un conjunto de elementos de D, entre los que est´a ai1(1a11). ¤ Lema 1.4.14 Sea iun n´umero natural tal que ai1es el primer elemento no nulo de la primera columna de una matriz no nula A= (aij). Si l(ai1)≥l(1a11) = l(2a11), entonces 2Aes de la forma:       1a11 0 0 0 R . . .... 0       44 1 Bases de Gr¨obner y la Forma Normal de Smith siendo R una matriz triangular superior. Demostraci´on: e A= (1A, 2A) con 1Ay2Atriangulares superiores. 2a11 es el m´aximo com´un divisor de los elementos no nulos de la primera columna de 1AT, entre ellos 1a11. l(1a11) = l(2a11) garantiza que 1a11 =u·2a11, con u unidad en D. Luego 1a11 es el m´aximo com´un divisor de los elementos no nulos de la primera columna de 1AT. Este hecho, unido a la restricci´on {C1}, garantiza que el polinomio que aporta el primer bloque es 1a11x1. Con lo cual la matriz 2Aes de la forma:       1a11 0 0 0 R . . .... 0       ¤ Definici´on 1.4.15 Se entender´a por ”c´alculo reiterado del par equivalente de una matriz A”, al proceso de construcci´on de la sucesi´on {e An}n∈N∪{0}, donde e A0=e A e A−→ (1A,2A)A1=2AT e A1−→ (1A1,2A1)A2=2AT 1 e A2−→ (1A2,2A2)A3=2AT 2 . . . 1.4 Una soluci´on con Bases de Gr¨obner 45 Lema 1.4.16 La sucesi´on {e An}n∈N∪{0}, est´a formada por matrices equivalentes todas entre s´ı. Demostraci´on: Trivial si se tiene en cuenta el Lema 1.4.12. ¤ Teorema 1.4.17 El c´alculo reiterado del par equivalente de una matriz no nula A, conduce a una matriz diagonal equivalente a A. Demostraci´on: Sea A= (aij)∈Matm×n(D) tal que Aes no nula, e A= ( 1A, 2A) con 1A= ( 1aij) y 2A= (2aij). Sea adem´as ai1el primer elemento no nulo de la primera columna. Por el Lema 1.4.13 se verifica que l(ai1)≥l(1a11)≥l(2a11). S´olo se pueden dar uno de estos cuatro casos: i)l(ai1)> l(1a11)> l(2a11) ii)l(ai1)> l(1a11) = l(2a11) iii)l(ai1) = l(1a11)> l(2a11) iv)l(ai1) = l(1a11) = l(2a11) Si se verifica ii) o iv), entonces 2A; por el Lema 1.4.14, va a ser de la forma:       1a11 0 0 0 R . . .... 0       con Runa matriz triangular superior. Cada vez que se calcula el par equivalente de una matriz, se presenta la casu´ıstica anterior. En el proceso de c´alculo reiterado del par equivalente, los casos i) y iii) no se pueden dar un n´umero infinito de veces, ya que este hecho implicar´ıa la existencia de una sucesi´on de n´umeros naturales estrictamente decreciente, acotada superiormente y con infinitos t´erminos, 52 1 Bases de Gr¨obner y la Forma Normal de Smith de la primera columna, se escoger´a 1a11x1como el polinomio que aporta el primer bloque, se impone la condici´on {C1}. A continuaci´on se expone un ejemplo en el que la no aplicaci´on de {C1}, conduce a un bucle infinito al aplicar el algoritmo DiagonalizaG. Ejemplo 1.4.20 Se Diagonal´ıza siguiendo los pasos del algoritmo DiagonalizaG, la siguiente matriz. A=Ã1 0 −1 1 ! C´alculo de e A. •C´alculo de 1A. -f1=x f2=−x+y=⇒I1={1,2} I2=∅ -S(f1, f2) = y=f3=⇒I2={3} -fI1=−x+y(No se aplica la condici´on {C1}y se escoge f2). -fI2=y -1A=Lad(A) = Ã−1 1 0 1 ! •C´alculo de 2A. •1AT=Ã−1 0 1 1 ! •f1=−x f2=x+y=⇒I1={1,2} I2=∅ •S(f1, f2) = y=f3=⇒I2={3} •fI1=x+y(No se aplica la condici´on {C1}y se escoge f2). •fI2=y 1.4 Una soluci´on con Bases de Gr¨obner 53 •2A=Lad(1AT) = Ã1 1 0 1 ! A=2AT=Ã1 0 1 1 ! C´alculo de e A. •C´alculo de 1A. -f1=x f2=x+y=⇒I1={1,2} I2=∅ -S(f1, f2) = −y=f3=⇒I2={3} -fI1=x+y(No se aplica la condici´on {C1}y se escoge f2). -fI2=−y -1A=Lad(A) = Ã1 1 0−1! •C´alculo de 2A. •1AT=Ã1 0 1−1! •f1=x f2=x−y=⇒I1={1,2} I2=∅ •S(f1, f2) = y=f3=⇒I2={3} •fI1=x−y •fI2=y •2A=Lad(1AT) = Ã1−1 0 1 ! A=2AT=Ã1 0 −1 1 ! Llegando de este modo a la matriz inicial, con lo que se podr´ıan repetir los c´alculos desde el principio una y otra vez. 54 1 Bases de Gr¨obner y la Forma Normal de Smith 1.5. Matrices de Paso Si bien es importante conocer la Forma Normal de Smith de una matriz, tambi´en es importante conocer sus matrices de paso; sobre todo de cara a la utilizaci´on de la Forma Normal de Smith para la resoluci´on de efectiva de problemas. 1.5.1. Construcci´on El punto de partida para la construcci´on de las matrices de paso, es tambi´en el punto de partida del algoritmo DiagonalizaG; ´este es el Teorema 1.4.9. Cada vez que se aplica este resultado, esto es, cada vez que se calcula para una matriz dada A,Lad(A), existe una matriz Pinversible tal que Lad(A) = P·A. Pues bien, simplemente llevando cuenta de las matrices P, por las que se va multiplicando, se obtendr´a al final tanto la Forma Normal de Smith, como sus matrices de paso. Teorema 1.5.1 Llevando cuenta de las matrices por las que se va multiplicando en el algoritmo SmithG, se obtienen las matrices de paso. Demostraci´on: Dada B∈Matm×n(D) no nula, se le aplica el algoritmo SmithG. A=B Paso 1: Aplicar DiagonalizaG a A. - Si A no es diagonal, se calcula e A. -1A=Lad(A) Por el Teorema 1.4.9, existe F1∈Matm×m(D) inversible, tal que 1A=Lad(A) = F1A. 1.5.1 Construcci´on 55 -2A=Lad(1AT) Por el Teorema 1.4.9, existe C1∈Matn×n(D) inversible, tal que 2A=Lad(1AT) = C1·1AT - 1A=F1A 2A=C1·1AT→2A=C1·1AT=C1·(F1B)T=C1·BT·FT 1 - Sea A=2AT=F1·B·CT 1 - Si A no es diagonal, se calcula e A. -1A=Lad(A) Por el Teorema 1.4.9, existe F2∈Matm×m(D) inversible, tal que 1A=Lad(A) = F2A. -2A=Lad(1AT) Por el Teorema 1.4.9, existe C2∈Matn×n(D) inversible, tal que 2A=Lad(1AT) = C2·1AT - 1A=F2A 2A=C2·1AT→2A=C2·1AT=C2·(F2A)T=C2·AT·FT 2 -A=2AT(= F2·F1·B·CT 1·CT 2=F2·F1·B·(C2·C1)T) - Si A no es diagonal, se calcula e A. - ... Este proceso termina tras un n´umero finito de pasos, con una matriz diagonal equivalente a la inicial y de la forma: A=2AT= (Fr·... ·F1) | {z } F ·B·(Cr·... ·C1)T | {z } C Paso 2: Reordenaci´on de los divisores elementales. - Bucle i= 1, ..., m´ın(m, n)−1 -i= 1 - Se construye la matriz P 56 1 Bases de Gr¨obner y la Forma Normal de Smith -A=A·P -C=C·P - Al aplicar DiagonalizaG a A se recogen las matrices D1, G1 por las que al multiplicar Ase obtiene una matriz Diagonal (v´ease paso 1) -A=D1·A·G1 -C=C·G1 -F=D1·F -i= 2 ... Como resultado de este bucle se llegar´a a dos matrices F y C inversibles tales que la Forma Normal de Smith de B es: F·B·C.¤ Para que el c´alculo de las matrices de paso sea completo, s´olo queda por explicar c´omo, dada una matriz A, se puede obtener una matriz inversible P, tal que Lad(A) = P·A. El m´etodo natural es el que se expone en la demostraci´on del Teorema 1.4.9; ir construyendo P, a medida que se avanza en el c´alculo de la base de Gr¨obner Fuerte de IA.No obstante, no es este el camino que aqu´ı se seguir´a, ya que supondr´ıa manejar matrices de tama˜no arbitrariamente grande (recu´erdese que el n´umero de filas, depende del n´umero de sicigias que se calculan para obtener una base de Gr¨obner Fuerte de IA). El proceso que se seguir´a para obtener P, es el siguiente: Dada A∈Matm×n(D), se construye la matriz (A|Im), esto es, a la matriz A se le a˜nade la matriz identidad de orden m. Se calcula una base de Gr¨obner Fuerte para I(A|Im)=<{f1(x1, ..., xn) + y1, ..., fm(x1, ..., xn) + ym}>con respecto a un orden monomial cualquiera con x1> ... > xn> y1> ... > ym. El conjunto de los polinomios de grado 1 de esta base de Gr¨obner Fuerte es de la forma: 1.5.1 Construcci´on 57 {g1(x1, ..., xn) + h1(y1, ..., ym), ..., gt(x1, ..., xn) + ht(y1, ..., ym), u1(y1, ..., ym), ..., us(y1, ..., ym)}. A la hora de calcular una base de Gr¨obner, es importante la elecci´on del par de polinomios del que se va a calcular su sicigia. Escoger uno u otro par, supondr´a al final, llegar seguramente a bases de Gr¨obner distintas. Si para calcular una base de Gr¨obner Fuerte de IA=<{f1, ..., fm}>, se siguen los mismos pasos que se siguieron en la construcci´on de la base de Gr¨obner Fuerte de I(A|Im)para obtener {g1(x1, ..., xn)+h1(y1, ..., ym), ..., gt(x1, ..., xn)+ ht(y1, ..., ym)}, al final, cuando se complete el c´alculo de la base de Gr¨obner Fuerte de IA, se tendr´a que el conjunto de polinomios de grado 1 para esa base de Gr¨obner Fuerte de IAes {g1(x1, ..., xn), ..., gt(x1, ..., xn)}; esto es as´ı, pues se han hecho las ”mismas cuentas” para IAque para I(A|Im), en lo que a c´alculo de polinomios de grado 1 en {x1, ..., xn}se refiere. La ´unica diferencia sustancial entre un c´alculo y el otro es que en el segundo se arrastran t´erminos adicionales (la parte que depende de {y1, ..., ym}) al hacer las cuentas, y en el primero no. Este hecho se expresa y ampl´ıa en el siguiente resultado. Teorema 1.5.2 Dada A∈Matm×n(D),Guna base de Gr¨obner Fuerte de I(A|Im)yLad(A|Im)la matriz que se obtiene a partir de G, entonces existe P∈Matm×m(D)inversible y existe una base de Gr¨obner Fuerte de IAtal que su correspondiente matriz Lad(A)verifica: Lad(A|Im) = (Lad(A)|P) Lad(A) = P·A Demostraci´on: Como se acaba de comprobar, es posible obtener los mismos polinomios de grado 1, salvo los sumandos que dependen de {y1, ..., ym}, tanto al calcular una Base de Gr¨obner Fuerte de IAcomo de IA|Im. Este hecho, garantiza que la submatriz de Lad(A|Im),formada por las primeras m filas y n columnas, es Lad(A). Por el Teorema 1.4.9 existe P∈Matm×m(D) inversible tal que: 58 1 Bases de Gr¨obner y la Forma Normal de Smith Lad(A|Im) = P·(A|Im) = (P·A |{z} Lad(A) |P) ¤ El papel que juega la matriz Imal a˜nadirse a A, es el de ”guardar memoria” de la matriz de paso P. Con este hecho en mente, es f´acil modificar los algoritmos DiagonalizaG y SmithG para obtener las matrices de paso. Algoritmo 1.5.3 DiagonalizaG Paso Entrada: A∈Matm×n(D)tal que Aes no nula. Salida: Este algoritmo devuelve tres matrices B, F, C tales que: -B∈Matm×n(D)es diagonal y equivalente a A. -F∈Matm×m(D)inversible. -C∈Matn×n(D)inversible. -B=F·A·C 1. F=Im;C=In(Ij: Matriz identidad de orden j) 2. Mientras Ano diagonal. - Se calcula Lad(A|Im)(= 1(A|Im)) /*Lad(A|Im) = (Lad(A)|P); Lad(A) = P·A*/ -1A=Lad(A) -F=P·F - Se calcula Lad(1AT|In) /*Lad(1AT|In) = (Lad(1AT)|Q); Lad(1AT) = Q·1AT*/ -2A=Lad(1AT) -C=Q·C/*Se traspone al final*/ -A=2AT 1.5.1 Construcci´on 59 3. C=CT;B=A 4. Devuelve B, F, C 5. Fin Algoritmo 1.5.4 SmithG Paso Entrada: A∈Matm×n(D)tal que Aes no nula. Salida: Este algoritmo devuelve tres matrices G,H,K tales que: -G∈Matm×n(D)es la Forma Normal de Smith de A. -H∈Matm×m(D)inversible. -K∈Matn×n(D)inversible. -G=H·A·K 1. (A, H, K) = DiagonalizaG Paso(A) 2. ¿Aes la Forma Normal de Smith? - No -P=In+B Ines la matriz identidad de orden n, Bes la matriz nula, salvo en las posiciones (j, i)min(m,n) j=j+ique contienen un uno. -A=A·P -K=K·P -(A, F, C) = DiagonalizaG Paso(A) -H=F·H -K=K·C - ¿Aes la Forma Normal de Smith? 60 1 Bases de Gr¨obner y la Forma Normal de Smith - S´ı, entonces salir del bucle. 3. G=A 4. Devuelve G,H,K 5. Fin La forma de proceder en el algoritmo SmithG Paso, es el modo m´as completo de calcular la Forma Normal de Smith, puesto que, a medida que se va avanzando en su c´alculo, se van construyendo las matrices de paso. Adem´as, todo este proceso se realiza utilizando las bases de Gr¨obner como herramienta de c´alculo. 1.5.2. C´alculo de la inversa de una matriz Seguramente llama la atenci´on, tratar a estas alturas de cap´ıtulo, el tema de decidir si una matriz es inversible o no, y en caso afirmativo calcular su inversa. No obstante, esto est´a plenamente justificado, pues en la subsecci´on siguiente de c´alculo de Formas Can´onicas, se necesitar´a calcular inversas de matrices. Dos son los algoritmos que se presentan, y aunque s´olo el primero de ellos es v´alido para su utilizaci´on en la siguiente subsecci´on, ambos ponen de manifiesto la relaci´on entre el c´alculo de la inversa de una matriz y el c´alculo de la Forma Normal de Smith. El primero se fundamenta en el c´alculo de las matrices de paso, y el segundo en la obtenci´on del polinomio m´ınimo. C´alculo de la Inversa y Matrices de Paso. Sea D, como hasta ahora, un dominio de ideales principales y A∈ Matn(D). Entonces, existen matrices S, P, Q de orden n, tales que: -Ses la Forma Normal de Smith de A. 1.5.2 C´alculo de la inversa de una matriz 61 -PyQson inversibles. -S=P·A·Q De la ´ultima igualdad se concluye que para que Asea inversible, todos los elementos que forman la diagonal principal de S, deben ser unidades de D. De ser cierto A−1=Q·S−1·P. Este razonamiento da pie al siguiente algoritmo: Algoritmo 1.5.5 Inversa Paso Entrada: A∈Matn(D)tal que Aes no nula. Salida: Si Aes inversible devuelve su inversa, de no serlo devuelve 0. 1. (S, P, Q) = SmithG Paso(A)/* S=P·A·Q*/ 2. ¿Todos los elementos de la diagonal principal de Sson unidades en D? - S´ı. -Inversa A =Q·S−1·P - No. -Inversa A = 0 3. Devuelve Inversa A 4. Fin C´alculo de la Inversa y el Polinomio M´ınimo. En esta subsecci´on se parte de un cuerpo conmutativo Ky de una matriz A∈Matn(K). Es conocido que el polinomio m´ınimo de A,m(x) = xm+ am−1xm−1+...+a0,es el factor invariante de mayor grado de la matriz xIn−A, donde Ines la matriz identidad de orden n[DuF99]. Que la matriz Asea inversible depende del t´ermino independiente de m(x), pues a0= 0 es condici´on necesaria y suficiente para que la matriz 68 1 Bases de Gr¨obner y la Forma Normal de Smith En la prueba del Teorema de Estructura se demuestra finalmente, que las im´agenes por Ψ de los ´ultimos svectores de la base C0={e0 1= n X i=1 1pi1ei, e0 2= n X i=1 1pi2ei, ..., e0 n= n X i=1 1pinei} (P−1= (1pij)), son las que determinan los elementos de Vcuyos c´ıclicos generan V. As´ı pues se verifica: z1= Ψ(e0 n−s+1), ..., zs= Ψ(e0 n) V=K[x]z1⊕... ⊕K[x]zs(1.2) Adem´as - (0 : zi) = (di) con di=xmi+ami−1xmi−1+... +a0i, i = 1, ..., s - (0 : z1)⊇(0 : z2)⊇... ⊇(0 : zs) Este hecho da pie al siguiente algoritmo. Algoritmo 1.5.13 Generadores Primera Descomposici´on. Entrada: -Kcuerpo y Vun K-espacio vectorial. -B={v1, ..., vn}una K-base de V. -A∈Matn×n(K)no nula, tal que Aes la matriz del endomorfismo de Ven la base B. Salida: z1, ..., zs∈Vyd1, ..., ds∈K[x]tales que -V=K[x]z1⊕... ⊕K[x]zs -(0 : zi) = (di), i = 1, ..., s 1.5.3 C´alculo de Formas Can´onicas 69 -(0 : z1)⊇(0 : z2)⊇... ⊇(0 : zs). -d1, ..., dsson polinomios m´onicos. 1. (S, P, Q) = SmithG Paso(xIn−A)/* S=diag(1, ..., 1, d1, ..., ds)*/ 2. s=n´umero de elementos distintos de 1 en la diagonal principal de S. 3. Inversa P =Inversa Paso(P)/* Ψ(ei) = vi, siendo {e1, ..., en}la base can´onica de K[x]n*/ 4. zi= Ψ(columna n−s+i-´esima de Inversa P), i= 1, ..., s 5. di=elemento de Sque ocupa la posici´on (n−s+i, n−s+i), i = 1, ..., s 6. Se hacen m´onicos d1, ..., ds 7. Devuelve {{z1, ..., zs},{d1, ..., ds}} 8. Fin Ejemplo 1.5.14 Se aplica el algoritmo Generadores Primera Descomposici´on a: -A=Ã2−1 0 1 !∈Mat2×2(Q) -B={v1= (−1,0,2), v2= (0,1,1)} V=< v1, v2>⊆Q3 70 1 Bases de Gr¨obner y la Forma Normal de Smith 1. (S, P, Q) = SmithG Paso(xI2−A) S=Ã1 0 0 (x−1)(x−2) ! P=Ã−1 0 1−x1! Q=Ã0 1 1 2 −x! 2. s= 1 3. Inversa P =Inversa Paso(P). Inversa P =Ã−1 0 1−x1! 4. z1= Ψ(0 ·e1+ 1 ·e2) = 0 ·v1+ 1 ·v2=v2= (0,1,1) 5. d1= (x−1) ·(x−2) = x2−3x+ 2 6. Devuelve {{(0,1,1)},{x2−3x+ 2}} 7. Fin Se puede afirmar entonces que: -V=< v1, v2>=K[x]·v2(Ves un K[x]-m´odulo c´ıclico). -(0 : v2) = (x2−3x+ 2) Definici´on 1.5.15 Dado un polinomio m´onico f=xn+an−1xn−1+... + a0∈K[x], se denomina matriz compa˜nera asociada a f, a la matriz C(f)∈ Matn×n(K)cuyo t´ermino (i, j)es: 1.5.3 C´alculo de Formas Can´onicas 71 1, si j+ 1 = i. −ai−1, si j=n. 0, en cualquier otro caso. Ejemplo 1.5.16 La matriz compa˜nera de x3−2x2+ 4 es: C(x3−2x2+ 4) =    0 0 −4 1 0 0 0 1 2    Teorema 1.5.17 [Bar96, Ser02] Dada una matriz Ade orden nsobre K, existe una matriz Pde orden ne inversible, tal que: (F=)P−1AP =diag(C(f1), ..., C(ft)),con f1|f2|...|ft. F se dice que es la Forma Can´onica Racional o de Frobenius de A. La Forma Can´onica Racional de A[Jac74], se obtiene a partir de la primera descomposici´on de V(1.2), que proporciona el Teorema de Estructura. Tomando como K-base para cada m´odulo c´ıclico K[x]zi[Jac74] {zi, x ·zi, ..., xmi−1·zi} se obtiene una K-base para Vde la forma B0={z1, x ·z1, ..., xm1−1·z1, z2, x ·z2, ..., xm2−1·z2, ..., zs, x ·zs, ..., xms−1·zs}. Si Pes la matriz que se obtiene al colocar en columnas las coordenadas de los vectores de B0, entonces se verifica que P−1AP es una matriz diagonal por bloques, formada por las matrices compa˜neras de los factores invariantes de la matriz caracter´ıstica de A, esto es, se obtiene la Forma Can´onica Racional de A. De este razonamiento se sigue el siguiente algoritmo: 72 1 Bases de Gr¨obner y la Forma Normal de Smith Algoritmo 1.5.18 Frobenius. Entrada: -Kcuerpo. -A∈Matn×n(K)no nula, la matriz del endomorfismo de Knen las bases can´onicas. Salida: - Una matriz Rtal que Res la Forma Can´onica Racional de A. - Una matriz inversible P, tal que P−1·A·P=R 1. {{z1, ..., zs},{d1, ..., ds}}=Generadores Primera Descomposici´on(A,C) /* Ces la base can´onica de Kn*/ 2. B0=∅;R=matriz nula de tama˜no n×n; indicador bloque=1 3. Bucle i= 1 hasta s/*Se construye B0*/ -m=grado(di) -B0=B0∪ {zi, x ·zi, ..., xm−1·zi} - Se sustituye el rect´angulo de Rde coordenadas -(indicador bloque, indicador bloque) /* Esquina superior izqda. */ -(indicador bloque +m−1, indicador bloque +m−1) /* Esquina inferior dcha. */ por la matriz compa˜nera de di -indicador bloque =indicador bloque +m 4. Pes la matriz que se obtiene al poner en columnas los vectores de B0 5. Devuelve R, P 1.5.3 C´alculo de Formas Can´onicas 73 6. Fin Ejemplo 1.5.19 Se calcular´a la Forma Can´onica Racional de: A=            0−1000 0 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 −2 0 0 0 0 0 3            ∈Mat6×6(Q) 1. {{z1, ...ds},{d1, ..., ds}}=Generadores Primera Descomposici´on(A, C) -z1= (−3,3,−1,0,−1,0);d1=x−1 -z2= (1,−1,0,0,−1,0);d2=x−1 -z3= (0,1 2,1 2,1,0,1 4);d2=x4−7x3+ 17x2−17x+ 6 2. B0=∅;R= matriz nula de orden 6; indicador bloque=1 3. Bucle i=1 hasta 3 -i= 1 -m= 1 -B0={z1} -(indicador bloque, indicador bloque) = (1,1) -(indicador bloque +m−1, indicador bloque +m−1) = (1,1) - Se sustituye el bloque de R de coordenadas (1,1)-(1,1) por la matriz compa˜nera de x−1. 74 1 Bases de Gr¨obner y la Forma Normal de Smith R=            100000 000000 000000 000000 000000 000000            -indicador bloque = 2 -i= 2 -m= 1 -B0={z1, z2} -(indicador bloque, indicador bloque) = (2,2) -(indicador bloque +m−1, indicador bloque +m−1) = (2,2) - Se sustituye el bloque de R de coordenadas (2,2)-(2,2) por la matriz compa˜nera de x−1. R=            100000 010000 000000 000000 000000 000000            -indicador bloque = 3 -i= 3 -m= 4 -B0={z1, z2}∪{z3, A ·z3= (−1 2,1,1 2,2,−1 4,3 4), A2·z3= (−1,3 2,1 2,4,−2,9 4), A3·z3= (−3 2,2,1 2,8,−13 2,27 4)} -(indicador bloque, indicador bloque) = (3,3) -(indicador bloque +m−1, indicador bloque +m−1) = (6,6) 1.5.3 C´alculo de Formas Can´onicas 75 - Se sustituye el bloque de R de coordenadas (3,3)-(6,6) por la matriz compa˜nera de x4−7x3+ 17x2−17x+ 6. R=            1 0 0 0 0 0 0 1 0 0 0 0 00000 −6 0 0 1 0 0 17 00010−17 0 0 0 0 1 7            -indicador bloque = 7 4. P=            −3 1 0 −1 2−1−3 2 3−11 213 22 −1 0 1 2 1 2 1 2 1 2 0 0 1 2 4 8 −1−1 0 −1 4−2−13 2 0 0 1 4 3 4 9 4 27 4            5. Devuelve R, P 6. Fin Teorema 1.5.20 [Jac74, DuF99, Coh74] Sea Mun K[x]-m´odulo, x∈M, d∈K[x]tal que (0 : x)=(d)yd=pe1 1·... ·pet t,pi6=pjsi i6=j, la descomposici´on de den primos. Entonces: -Dx =Dx1⊕... ⊕Dxtcon (0 : xi) = (pei i) -xi=pe1 1·... ·pei−1 i−1·pei+1 i+1 ·... ·pet t, i = 1, ..., t. Teniendo en cuenta este resultado, cada K[x]-m´odulo c´ıclico de la descomposici´on (1.2), se puede volver a descomponer en suma directa de K[x]- m´odulos c´ıclicos. Se obtiene as´ı, una segunda descomposici´on de V: V=K[x]·u1⊕... ⊕K[x]·ur(1.3) 76 1 Bases de Gr¨obner y la Forma Normal de Smith siendo (0 : ui)=(pi(x)ei), con pi(x) un polinomio m´onico e irreducible en K[x], i= 1, ..., r. Teorema 1.5.21 [Bar96, Ser02] Dada una matriz Ade orden nsobre K, existe una matriz Pde orden ne inversible, tal que: (F=)P−1AP =diag(C(qa1 1), ..., C(qat t)),q1, ..., qtirreducibles sobre K[x]. Fse dice que es la Segunda Forma Can´onica de A. Tomando de nuevo como K-base de cada m´odulo c´ıclico K[x]ui {ui, x ·ui, ..., xhi−1·ui} siendo hiel grado del polinomio pei i, se obtiene una K-base para Vde la forma B00 ={u1, x ·u1, ..., xh1−1·u1, ..., ur, x ·ur, ..., xhr−1·ur} Si Pes la matriz que se obtiene al colocar en columnas las coordenadas de los vectores de B00, entonces se verifica que P−1AP es una matriz diagonal por bloques, formada por las matrices compa˜neras de los divisores elementales de la matriz caracter´ıstica de A, esto es, se obtiene la Segunda Forma Can´onica de A. Esta forma de proceder da lugar a: Algoritmo 1.5.22 Segunda Forma Can´onica. Entrada: -Kcuerpo -A∈Matn×n(K)no nula, la matriz del endomorfismo de Knen las bases can´onicas. 1.5.3 C´alculo de Formas Can´onicas 77 Salida: - Una matriz Rtal que Res la Segunda Forma Can´onica de A - Una matriz inversible P, tal que P−1·A·P=R 1. {{z1, ..., zs},{d1, ..., ds}} =Generadores Primera Descomposici´on(A, C) /* Ces la base can´onica de Kn*/ 2. B00 =∅;Res la matriz nula de orden n; indicador bloque=1. 3. Bucle i= 1 hasta s - Se factoriza dien primos (sobre K[x]) -di=pei,1 i,1·... ·pei,t i,t ,pi,j 6=pi,k si j6=k. -t=n´umero de factores primos en la descomposici´on de di. - /* Se descompone K[x]zien suma directa de c´ıclicos */ - Bucle j= 1 hasta t -u=di pei,j i,j zi -m=grado(pi,j)·ei,j -B00 =B00 ∪ {u, x ·u, ..., xm−1u} - Se sustituye el rect´angulo de R: -(indicador bloque, indicador bloque) /* Esquina superior izquierda */ -(indicador bloque +m−1, indicador bloque +m−1) /* Esquina inferior derecha */ por la matriz compa˜nera de pei,j i,j . •indicador bloque =indicador bloque +m 4. Pes la matriz que se obtiene al poner en columnas los vectores de B00. 84 1 Bases de Gr¨obner y la Forma Normal de Smith 1. {{z1, ..., zs},{d1, ..., ds}} =Generadores Primera Descomposici´on(A, C) /* Ces la base can´onica de Kn*/ 2. B000 =∅;Res la matriz nula de orden n; indicador bloque=1. 3. Bucle i= 1 hasta s - Se factoriza dien primos (sobre K[x]) -di=pei,1 i,1·... ·pei,t i,t ,pi,j 6=pi,k si j6=k. -t=n´umero de factores primos en la descomposici´on de di. - /* Se descompone K[x]zien suma directa de c´ıclicos */ - Bucle j= 1 hasta t -u=di pei,j i,j zi -m=grado(pi,j)·ei,j;gradop =m·eij -B000 =B000 ∪ {u, x ·u, ..., xm−1·u, pi,j ·u, x ·pi,j ·u, ..., xm−1· pi,j ·u, ..., peij −1 i,j ·u, x ·peij −1 i,j ·u, ..., xm−1·peij −1 i,j ·u} - Se sustituye el rect´angulo de R: -(indicador bloque, indicador bloque) /* Esquina superior izquierda */ -(indicador bloque+gradop−1, indicador bloque+gradop− 1) /* Esquina inferior derecha */ por la matriz hipercompa˜nera de pei,j i,j . •indicador bloque =indicador bloque +gradop 4. Pes la matriz que se obtiene al poner en columnas los vectores de B000. 5. Devuelve R, P 6. Fin 1.5.3 C´alculo de Formas Can´onicas 85 Ejemplo 1.5.28 Se calcular´a la Forma Can´onica de Jacobson de la matriz: A=      000−4 1 0 0 0 010−4 0 0 1 0       ∈Mat4×4(Q) 1. {{z1, ..., zs},{d1, ..., ds}} =Generadores Primera Descomposici´on(A, C) z1= (0,0,1 4,0);d1=x4+ 4x2+ 4 2. B000 =∅;Rla matriz nula de orden 4; indicador bloque=1 3. Bucle i= 1 hasta 1 -i= 1 -d1= (x2+ 2)2 -t= 1 - Bucle j= 1 hasta 1 -u=z1 -m= 2; gradop = 4 -B000 ={z1, x ·z1= (0,0,0,1 4), (x2+ 2) ·z1= (−1,0,−1 2,0), x(x2+ 2) ·z1= (0,−1,0,−1 2)} -(indicador bloque, indicador bloque) = (1,1) -(indicador bloque+gradop−1, indicador bloque+gradop− 1) = (4,4) por la matriz hipercompa˜nera de (x2+ 2)2 R=      0−2 0 0 1 0 0 0 0 1 0 −2 0 0 1 0       86 1 Bases de Gr¨obner y la Forma Normal de Smith -indicador bloque = 5 4. P=      0 0 −1 0 0 0 0 −1 1 40−1 20 01 40−1 2       5. Devuelve R, P 6. Fin Queda, por ´ultimo, tratar el c´alculo de la Forma Can´onica de Jordan de una matriz. La Forma Can´onica de Jordan es la apariencia que toma la Forma Can´onica de Jacobson, cuando los divisores elementales de la matriz caracter´ıstica, son potencias de polinomios de grado 1 [Ser02]. El m´etodo natural para calcular entonces la Forma Can´onica de Jordan de una matriz, se reduce a comprobar que las ra´ıces del polinomio caracter´ıstico est´an todas en K, y, en caso afirmativo, aplicar el algoritmo de c´alculo de la Forma Can´onica de Jacobson. Ejemplo 1.5.29 Se calcular´a la Forma Can´onica de Jordan de la matriz A=            0−1000 0 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 −2 0 0 0 0 0 3            ∈Mat6×6(Q) Los factores invariantes no triviales son x−1, x −1, x4−7x3+ 17x2− 17x+ 6. Todos tienen sus ra´ıces en Q, por lo que si se aplica el algoritmo Jacobson se obtendr´a entonces la Forma Can´onica de Jordan de A. 1. {{z1, ..., zs},{d1, ..., ds}} =Generadores Primera Descomposici´on(A, C) 1.5.3 C´alculo de Formas Can´onicas 87 -z1= (−3,3,−1,0,−1,0);d1=x−1 -z2= (1,−1,0,0,−1,0);d2=x−1 -z3= (0,1 2,1 2,1,0,1 4);d3=x4−7x3+ 17x2−17x+ 6 2. B00 =∅;Res la matriz nula de orden 6; indicador bloque=1 3. Bucle i= 1 hasta 3 -i= 1 -d1=x−1 -t= 1 - Bucle j= 1 hasta 1 -u=z1 -m= 1;gradop = 1 -B000 ={z1} -(indicador bloque, indicador bloque) = (1,1) -(indicador bloque+gradop−1, indicador bloque+gradop− 1) = (1,1) - Se sustituye el rect´angulo de Rde coordenadas (1,1)-(1,1), por la matriz hipercompa˜nera de x−1. R=            100000 000000 000000 000000 000000 000000            - indicador bloque=2 -i= 2 -d2=x−1 88 1 Bases de Gr¨obner y la Forma Normal de Smith -t= 1 - Bucle j= 1 hasta 1 -u=z2 -m= 1;gradop = 1 -B000 ={z1, z2} -(indicador bloque, indicador bloque) = (2,2) -(indicador bloque +gradop −1, indicador bloque +gradop − 1) = (2,2) - Se sustituye el rect´angulo de Rde coordenadas (2,2)-(2,2), por la matriz hipercompa˜nera de x−1. R=            100000 010000 000000 000000 000000 000000            - indicador bloque=3 -i= 3 -d3= (x−1)2·(x−2) ·(x−3) -t= 3 - Bucle j= 1 hasta 3 -j= 1 -u= (x−2) ·(x−3) ·z3= (3 2,−1 2,1,0,1 2,0) -m= 1;gradop = 2 -B000 ={z1, z2}∪{u, (x−1)u= (−1,1,0,0,0,0)} -(indicador bloque, indicador bloque) = (3,3) 1.5.3 C´alculo de Formas Can´onicas 89 -(indicador bloque+gradop−1, indicador bloque+gradop− 1) = (4,4) - Se sustituye el rect´angulo de Rde coordenadas (3,3)-(4,4), por la matriz hipercompa˜nera de (x−1)2. R=            100000 010000 001000 001100 000000 000000            - indicador bloque=5 -j= 2 -u= (x−1)2·(x−3) ·z3= (0,0,0,−1,0,0) -m= 1;gradop = 1 -B000 ={z1, z2,(3 2,−1 2,1,0,1 2,0),(−1,1,0,0,0,0)}∪ {(0,0,0,−1,0,0)} -(indicador bloque, indicador bloque) = (5,5) -(indicador bloque+gradop−1, indicador bloque+gradop− 1) = (5,5) - Se sustituye el rect´angulo de Rde coordenadas (5,5)-(5,5), por la matriz hipercompa˜nera de x−2. R=            100000 010000 001000 001100 000020 000000            - indicador bloque=6 -j= 3 90 1 Bases de Gr¨obner y la Forma Normal de Smith -u= (x−1)2·(x−2) ·z3= (0,0,0,0,−1,1) -m= 1;gradop = 1 -B000 =B000 ∪ {(0,0,0,0,−1,1)} -(indicador bloque, indicador bloque) = (6,6) -(indicador bloque+gradop−1, indicador bloque+gradop− 1) = (6,6) - Se sustituye el rect´angulo de Rde coordenadas (6,6)-(6,6), por la matriz compa˜nera de x−3. R=            100000 010000 001000 001100 000020 000003            - indicador bloque=7 4. P=            −3 1 3 2−100 3−1−1 2100 −101000 0 0 0 0 −1 0 −1−11 20 0 −1 000001            5. Devuelve R, P 6. Fin Observaciones: Los algoritmos de c´alculo de la Segunda Forma Can´onica y de la Forma Can´onica de Jacobson, son casi id´enticos, las ´unicas diferencias radican 1.5.4 M´as Bases de Gr¨obner 91 a la hora de construir la K-base, y en el hecho de que en uno se mane- ja la matriz compa˜nera y en el otro la matriz hipercompa˜nera. Este comportamiento simplifica enormemente la programaci´on del c´alculo de ambas Formas Can´onicas. No siempre es posible, en la pr´actica, obtener la Segunda Forma Can´onica y la Forma Can´onica de Jacobson, pues para su c´alculo se debe conocer previamente la factorizaci´on en irreducibles de los factores invariantes (=divisores elementales), y esto no siempre es factible. En C, por ejemplo, aunque te´oricamente todo polinomio de grado mayor que uno con coeficientes complejos, se puede expresar como producto de polinomios de grado uno, en la pr´actica, no siempre se puede llegar a esta factorizaci´on. La Forma Can´onica de Jordan, no es m´as que la apariencia que adopta la Forma Can´onica de Jacobson, en el caso de que los divisores elementales sean potencias de polinomios lineales, o lo que es equivalente, cuando los factores invariantes tengan todas sus ra´ıces en el cuerpo K sobre el que se trabaja. 1.5.4. M´as Bases de Gr¨obner Una vez que se ha conseguido, utilizando la teor´ıa de bases de Gr¨obner, reformular los tres algoritmos cl´asicos de c´alculo de formas can´onicas, es dif´ıcil no caer en la tentaci´on de preguntarse, ¿ qu´e m´as pueden aportar las bases de Gr¨obner ?, esto es, ¿ ser´ıa posible utilizar bases de Gr¨obner para realizar alg´un c´alculo m´as ? Un examen detallado de los tres algoritmos de c´alculo de formas can´onicas (Frobenius, Segunda Forma Can´onica, Jacobson) muestra que tres son los c´alculos m´as importantes que se hacen, el primero es el de calcular los elementos {z1, ..., zs}y los factores invariantes, que ya se hace utilizando bases de Gr¨obner; el segundo es la factorizaci´on de los factores invariantes (en Segunda Forma Can´onica y Jacobson), y el tercero es el c´alculo 92 1 Bases de Gr¨obner y la Forma Normal de Smith de la acci´on de un polinomio f(x)∈K[x] sobre un vector v∈V. Este c´alculo es muy importante, pues se necesita para construir la K-base de Ven la cual el endomorfismo que define la matriz A, se expresa matricialmente mediante una de las cuatro formas can´onicas descritas anteriormente. La cuesti´on que subyace tras el c´alculo de la acci´on de un polinomio sobre un vector, es la evaluaci´on de un polinomio en una matriz (f(x)·v= f(A)·v) [Gie93]. Este c´alculo en principio puede parecer trivial, sin embargo, es un problema muy complicado de resolver, pues aunque la mec´anica es muy sencilla, en la pr´actica, el n´umero de operaciones a realizar se dispara a medida que crece el orden de la matriz y el grado del polinomio sobre el que act´ua. En esta subsecci´on se va a explicar c´omo calcular la acci´on de un polinomio f(x)∈K[x] sobre un vector v∈V, utilizando bases de Gr¨obner. El ´unico objetivo de esta subsecci´on es el de mostrar que este c´alculo se puede hacer utilizando la teor´ıa de bases de Gr¨obner, sin entrar a discutir en ning´un momento, la rapidez o lentitud del procedimiento que aqu´ı se expone. Se define, igual que en la subsecci´on anterior, el epimorfismo: Ψ : K[x]n³V Ψ es una presentaci´on libre del K[x]-m´odulo Vsiendo KerΨ su m´odulo de relaciones. Se puede afirmar entonces que se tiene un isomorfismo de K[x]- m´odulos entre K[x]n KerΨyV. En la mayor´ıa de los libros de ´algebra, se manejan siempre los elementos de R-m´odulo Rn(con Run anillo cualquiera), de la forma n P i=1 aiei, siendo {e1, ..., en}la base can´onica de Rnya1, ..., an∈R. Esto es, se piensan, por comodidad para su manipulaci´on, como polinomios en las variables e1, ..., en con coeficientes en R. Este modo de actuar define, de modo natural, un monomorfismo K[x]- lineal: 1.5.4 M´as Bases de Gr¨obner 93 θ:K[x]n½K[x, E1, ..., En] g= (g1(x), ..., gn(x)) Ãθ(g) = g1(x)·E1+... +gn(x)·En A partir de los morfismos de K[x]-m´odulos θy Ψ, y definiendo Icomo el K[x]-m´odulo θ(KerΨ), es posible construir de modo natural el siguiente diagrama conmutativo de K[x]-m´odulos: Ker Ψ//θ u // ²² ²² I ²² ²² K[x]n//θ// ²²²² K[x, E1, ..., En] ²²²² V∼ =K[x]n Ker Ψ ////K[x,E1,...,En] I La propiedad universal del con´ucleo garantiza la existencia de un ´unico morfismo inyectivo θ:V∼ =K[x]n KerΨ−−−−−→ K[x, E1, ..., En] I que hace el diagrama conmutativo. En lo tocante al K[x]-m´odulo I, es posible concretar un poco m´as y afirmar: Proposici´on 1.5.30 Iest´a generado como K[x]-m´odulo por {xE1− n P i=1 ai1Ei, ..., xEn− n P i=1 ainEi} Demostraci´on: Trivial teniendo en cuenta que n ∪ j=1{fj= n P i=1 xej−aijei}es una K[x]-base de KerΨ¤ 100 1 Bases de Gr¨obner y la Forma Normal de Smith De entre todos los DIPs que maneja el paquete escogidos inicialmente, llama seguramente la atenci´on el anillo Z[1+√−19 2], este anillo es el ´unico para el que no hay definido en Mathematica ning´un comando espec´ıfico; para todos los dem´as existen funciones definidas en mayor o menor medida. Z[1+√−19 2] constituye uno de los pocos ejemplos conocidos, de anillos que son DIPs y no son dominios eucl´ıdeos [Cam88, Gre97]. Es precisamente este motivo por el que se incluy´o este anillo en el paquete. Para m´as informaci´on, se recomienda instalar la ayuda del paquete y consultar en el HelpBrowser de Mathematica, la secci´on Add-ons, subsecci´on bases de Gr¨obner. 1.7. Aplicaciones Con el correr del tiempo, la Forma Normal de Smith se ha ido aplicando para resolver los m´as diversos problemas; ahora, una vez que ha quedado de manifiesto que se puede calcular la Forma Normal de Smith mediante un c´alculo sucesivo de bases de Gr¨obner; todas estas aplicaciones de la Forma Normal de Smith, pasan a ser problemas resolubles con t´ecnicas de la Teor´ıa de las bases de Gr¨obner. 1.7.1. Grupos Abelianos Finitamente Generados. Si bien era necesaria una secci´on de aplicaciones del c´alculo de la Forma Normal de Smith, donde trabajar con el paquete construido; no es menos cierto que, hablar del c´alculo de la Forma Normal de Smith, y no hablar en primera instancia de la identificaci´on de R-m´odulos finitamente generados sobre un dominio de ideales principales, en este caso R=Z, ser´ıa incomprensible. Pues las dos, el c´alculo de la Forma Normal de Smith y la identificaci´on de R-m´odulos finitamente generados sobre un dominio de ideales principales, van ´ıntimamente ligadas [Jac74, DuF99, F1879]. 1.7.1 Grupos Abelianos Finitamente Generados. 101 Todo grupo abeliano finitamente generado queda definido por un conjunto de generadores y uno de relaciones, y rec´ıprocamente. La Forma Normal de Smith de la matriz del conjunto de relaciones, es la que proporciona la informaci´on que se necesita, para identificar el grupo. Ejemplo 1.7.1 Se identificar´a el grupo abeliano Mgenerado por {a, b, c, d}, sujeto a las relaciones {a+b+d= 0,2a−b=c} La matriz de relaciones es Ã1 1 0 1 2−1−1 0 ! Se calcula la Forma Normal de Smith Smith[{{1,1,0,1},{2,−1,−1,0}}, Z] y se obtiene S=Ãd1= 1 0 0 0 0d2= 1 0 0 ! Entonces [DuF99] M∼ =Z d1Z⊕Z d2Z⊕Z⊕Z∼ =Z⊕Z Ejemplo 1.7.2 Se identificar´a el grupo abeliano Mgenerado por {a, b, c, d}, sujeto a las relaciones {2a−3b=c, a +d= 0,5d= 0} La matriz de relaciones es    2−3−1 0 1 0 0 1 0 0 0 5    102 1 Bases de Gr¨obner y la Forma Normal de Smith Se calcula la Forma Normal de Smith Smith[{{2,−3,−1,0},{1,0,0,1},{0,0,0,5}}, Z] y se obtiene S=   d1= 1 0 0 0 0d2= 1 0 0 0 0 d3= 5 0    Entonces [DuF99] M∼ =Z d1Z⊕Z d2Z⊕Z d2Z⊕Z∼ =Z5⊕Z 1.7.2. Ecuaciones Diferenciales Lineales Uno de los m´etodos de resoluci´on de un sistema de m ecuaciones diferenciales lineales de orden ncon coeficientes constantes, es el m´etodo de eliminaci´on [NaS92]. Este m´etodo se basa en manejar la matriz de operadores diferenciales lineales asociada al sistema de ecuaciones. Esta matriz de operadores, se puede considerar como una matriz de polinomios en una variable; surge entonces de modo natural, la idea de aplicar el c´alculo de la Forma Normal de Smith para su resoluci´on. Ejemplo 1.7.3 Se calcular´a la soluci´on general de: x00(t) + y0(t)−x(t) + y(t) = −1 x0(t) + y0(t)−x(t) = t2 El sistema a resolver en notaci´on de operadores diferenciales lineales es:3 3L=d/dt 1.7.2 Ecuaciones Diferenciales Lineales 103 ÃL2−1L+ 1 L−1L! | {z } A Ãx(t) y(t)! | {z } X(t) =Ã−1 t2! | {z } B(t) El primer paso a dar es el c´alculo de la Forma Normal de Smith: Smith[{{L2−1, L + 1},{L−1, L}}, Q[L], Paso−> S´ı] De esta forma se obtiene -S=Ã1 0 0L3−L2−L+ 1 ! -P=Ã0 1 −1−L2+L+ 2 ! -Q=Ã−1−L 1L−1! siendo Sla Forma Normal de Smith de A,Pla matriz de paso en filas y Q la matriz de paso en columnas (S=P·A·Q). A·X(t) = B(t)⇐⇒ P·A·X(t) = P·B(t) Haciendo el cambio de variable X(t) = Q·Y(t) P·A·Q·Y(t) = P·B(t)⇐⇒ S·Y(t) = P·B(t)⇐⇒ ⇐⇒ Ã1 0 0L3−L2−L+ 1 !Ãy1(t) y2(t)!=Ãt2 2t2+ 2t−1! 104 1 Bases de Gr¨obner y la Forma Normal de Smith El sistema a resolver es pues: y1(t) = t2 y3) 2(t)−y2) 2(t)−y) 2(t) + y2(t) = 2t2+ 2t−1 Su soluci´on es: Ãy1(t) y2(t)!=Ãt2 C1et+C2tet+C3e−t+ 2t2+ 6t+ 9 ! Para obtener la soluci´on del sistema planteado inicialmente, s´olo queda por deshacer el cambio de variable: X(t) = Ãx(t) y(t)!=Q·Y(t) = =Ã−C1et−C2et−C2tet+C3e−t−t2−4t−6 −2C3e−t+C2et−t2−2t−3! Ejemplo 1.7.4 Se calcular´a la soluci´on general de: x0 1(t) + x0 2(t) + x0 3(t) + 2x1(t) + x2(t)+3x3(t) = 0 x000 1(t) + x000 2(t)+2x000 3(t) + 2x00 1(t) + x00 2(t)+3x00 3(t) + x0 1(t) + x0 2(t) + x0 3(t) = 0 x00 1(t) + x00 2(t)+3x00 3(t) + 3x0 1(t)+2x0 2(t) + 6x0 3(t)+2x1(t) + x2(t)+3x3(t) = 0 El sistema a resolver en notaci´on de operadores diferenciales lineales es:4    L+ 2 L+ 1 L+ 3 L3+ 2L2+L L3+L2+L2L3+ 3L2+L L2+ 3L+ 2 L2+ 2L+ 1 3L2+ 6L+ 3    | {z } A    x1(t) x2(t) x3(t)    | {z } X(t) =   0 0 0    | {z } B(t) 4L=d/dt 1.7.2 Ecuaciones Diferenciales Lineales 105 El primer paso a dar es el c´alculo de la Forma Normal de Smith de A: Smith[{{L+ 2, L + 1, L + 3},{L3+ 2L2+L, L3+L2+L, 2L3+ 3L2+L}, {L2+ 3L+ 2, L2+ 2L+ 1,3L2+ 6L+ 3}}, Q[L], Paso−> S´ı] De esta forma se obtiene -S=   1 0 0 0L0 0 0 L2+L    -P=   1 2+L2 2−1 20 L3+ 2L2+L−L−2 0 L+ 1 0 −1    -Q=   11 2−1 2L3−1 2L2+ 1 0−11 2L3+L2−1 2 0 0 −1 2    Haciendo el cambio de variable X(t) = Q·Y(t), el sistema a resolver es ahora:      y1(t) = 0 y0 2(t) = 0 y00 3(t) + y0 3(t) = 0      Su soluci´on es:    y1(t) y2(t) y3(t)   =   0 C1 C2+C3e−t    Deshaciendo el cambio de variable: X(t) =    1 2C1+C2+C3e−t −C1−1 2C2 −1 2C2−1 2C3e−t    106 1 Bases de Gr¨obner y la Forma Normal de Smith 1.7.3. Ecuaciones Diof´anticas En esencia, el procedimiento que se utiliza para resolver los sistemas de ecuaciones diferenciales de la subsecci´on anterior, es v´alido para resolver un sistema de ecuaciones lineales diof´anticas Ax =b. Los pasos a dar son los mismos; primero se calcula la Forma Normal de Smith de A, esta vez eso s´ı, sobre Z; se obtienen de este modo tres matrices S, P, Q, tales que Ses la Forma Normal de Smith de AyS=PAQ; segundo, se multiplica el sistema por la matriz Py se hace el cambio de variable X=Q·Y. En tercer lugar se resuelve, si es que se puede, el sistema S·Y=PB, que es trivial pues S es diagonal, y, por ´ultimo, se deshace el cambio de variable para obtener X, para una consulta m´as detallada sobre este particular se recomienda [Lak96]. Ejemplo 1.7.5 Se resolver´a la ecuaci´on diof´antica lineal 8x+ 10y= 1000 El primer paso a dar es expresar el sistema en forma matricial. ³8 10 ´Ãx y!= (1000) A continuaci´on, se calcula la Forma Normal de Smith de A: Smith[{{8,10}}, Z, Paso−> S´ı] Se obtiene de este modo S=³2 0 ´P= (1) Q=Ã−1 5 1−4! siendo Sla Forma Normal de Smith (S=PAQ) AX =b⇐⇒ PAX =Pb 1.7.3 Ecuaciones Diof´anticas 107 Haciendo el cambio de variable X=QY , queda: PAQY =Pb ⇐⇒ SY =Pb ⇐⇒ ³2 0 ´Ãy1 y2!= 1000 Que tiene por soluci´on y1= 500 y2=λ Deshaciendo el cambio de variable Ãx y!=Ã−1 5 1−4!Ã500 λ!=Ã−500 + 5λ 500 −4λ! Por lo tanto la soluci´on del sistema inicial es: Ãx y!=Ã−500 + 5λ 500 −4λ!λ∈Z Ejemplo 1.7.6 Se resolver´a el sistema lineal de ecuaciones diof´anticas lineales 3x+ 6y+ 5z+ 2t=−2 x+y+z−5t= 0 −7x+ 2y−2z+t= 1 El primer paso a dar es expresar el sistema en forma matricial.    3 6 5 2 1 1 1 −5 −7 2 −2 1    | {z } A       x y z t       | {z } X =   −2 0 1    | {z } b 108 1 Bases de Gr¨obner y la Forma Normal de Smith A continuaci´on, se calcula la Forma Normal de Smith de A: Smith[{{3,6,5,2},{1,1,1,−5},{−7,2,−2,1}}, Z, Paso−> S´ı] Se obtiene de este modo S=   1 0 0 0 0 1 0 0 0 0 3 0    P=   0 1 0 1−3 0 −4 19 1    Q=      1 0 40 −39 0 1 53 −51 0−1−88 85 0 0 1 −1       siendo Sla Forma Normal de Smith (S=PAQ) AX =b⇐⇒ PAX =Pb El sistema a resolver es    1 0 0 0 0 1 0 0 0 0 3 0         y1 y2 y3 y4       =   0 −2 9    1.7.3 Ecuaciones Diof´anticas 109 Cuya soluci´on es y1= 0 y2=−2 y3= 3 y4=λ λ∈Z Deshaciendo el cambio de variable se obtiene la soluci´on del sistema de partida       x y z t       =      120 −39λ 157 −51λ −262 + 85λ 3−λ       λ∈Z 116 2 Bases de Gr¨obner y el Algoritmo de Berlekamp Teorema 2.2.5 [GCL92] W={v= (v0, ..., vn−1)/v(Q−I) = 0}1 Teorema 2.2.6 [GCL92, LiN97] Sea h(x)∈Wun polinomio no constante. Entonces se verifica que: a(x) = Q c∈Fq GCD(a(x), h(x)−c) El algoritmo de Berlekamp [Ber67] consiste en: 1. Calcular una Fq-base para W({1, h2(x), ..., hk(x)}) 2. Aplicar el Teorema 2.2.6, tomando h(x) = h2(x) 3. Si a(x) factorizase en un producto de kfactores, entonces el proceso se para. De no ser as´ı, se aplica el Teorema 2.2.6 a cada factor de a(x) obtenido previamente, tomando h(x) = h3(x); y as´ı sucesivamente. 2.3. Berlekamp con Bases de Gr¨obner Calcular una Fq-base para W, es el primer punto a tratar a la hora de aplicar el algoritmo de Berlekamp. El Teorema 2.2.5 proporciona el modo de hacerlo; para ello s´olo hay que resolver el siguiente sistema lineal de ecuaciones: (x1, ..., xn)(Q−I) = (0, ..., 0) para obtener una Fq-base para W. Una de las aplicaciones m´as conocidas de la teor´ıa de las bases de Gr¨obner es la resoluci´on de sistemas de ecuaciones polin´omicas [GCL92, CLO92, AdL94], raz´on por la cual este punto no representa un problema y puede ser resuelto calculando una base de Gr¨obner. 1I es la matriz identidad de orden n 2.3 Berlekamp con Bases de Gr¨obner 117 Desde cierto punto de vista, se podr´ıa decir que el algoritmo de Berlekamp es la aplicaci´on reiterada del Teorema 2.2.6. La mayor dificultad en este resultado es calcular todos los m´aximos comunes divisores. Un problema similar a este, fue tratado y resuelto con bases de Gr¨obner por Czichowski [Czi95]. El contexto era bien distinto, pues el art´ıculo de Czichowski trata sobre el c´alculo de integrales de funciones racionales sobre un cuerpo de caracter´ıstica cero; y aqu´ı se trata el problema de la factorizaci´on de un polinomio en una variable sobre un cuerpo finito. De todas formas, la idea de c´omo calcular estos m´aximos comunes divisores con bases de Gr¨obner es la misma en ambos casos. El punto de partida del art´ıculo de Czichowski es la f´ormula de integraci´on dada por Rothstein [Rot76], Trager [Tra76] y Lazard y Rioboo [LaR90] ZA(x) D(x)dx =X c/R(c)=0 c·log(GCD(A(x)−c·dD dx (x), D(x))) (2.1) siendo R(z) = Resultantex(A(x)−z·dD dx (x), D(x)), D(x) un polinomio m´onico y libre de cuadrados, de grado mayor que cero, deg(A(x)) <deg(D(x)) yGCD(A(x), D(x)) = 1. Czichowski prob´o que la base de Gr¨obner reducida del ideal < A(x)−z· dD dx (x), D(x)>respecto al orden monomial lexicogr´afico con x>z, proporciona los m´aximos comunes divisores buscados. Las ideas de Czichowski, como posteriormente se ver´a, trasladan completamente al contexto de la factorizaci´on de polinomios sobre un cuerpo finito. Curiosamente, las ideas de Czichowski se adaptan mucho mejor a un contex- to de cuerpos finitos que a uno de caracter´ıstica cero; pues en el contexto de cuerpos finitos, como se ver´a a continuaci´on, las ra´ıces de la resultante siempre se pueden calcular, mientras en caracter´ıstica cero no siempre se puede. 118 2 Bases de Gr¨obner y el Algoritmo de Berlekamp Teorema 2.3.1 Sean a(x), h(x)∈Fq[x], con a(x)m´onico, libre de cuadrados y deg(a(x)) = n≥1,h(x)∈W, I =< a(x), h(x)−z >⊂Fq[x, z], y sea G={P1(x, z) = R1(z)·xn1+..., P2(x, z) = R2(z)·xn2+..., ..., Pm(x, z) = Rm(z)·xnm+...}la base de G¨obner Reducida de I, respecto al orden monomial lexicogr´afico con x>z. Se supone adem´as, que Gest´a ordenado con respecto a sus t´erminos principales en orden ascendente. Se verifica: a) Rk+1(z)|Rk(z), k = 1, ..., m −1. b) Rm(z)∈Fq. c) P1(x, z) = R1(z) d) R1(z)tiene las mismas ra´ıces que Resultantex(a(x), h(x)−z) pero con multiplicidad uno. e) Resultantex(a(x), h(x)−z)posee todas sus ra´ıces en Fq. f) Pk(x, z) = Rk(z)·Sk(x, z), k = 1, ..., m. siendo Sk(x, z)un polinomio m´onico con respecto a su mayor potencia en x (Sk(x, z) = xnk+...) g) Si Qk(z), k = 1, ...m −1,denota al polinomio definido por Rk(z) = Qk(z)·Rk+1(z), entonces: a(x) = Q k=1,...,m−1 (Q c/Qk(c)=0 Sk+1(x, c)) Demostraci´on: a) Sea k∈ {1,2, ..., m −1}, con nk< nk+1 yGla base de Gr¨obner Reducida del Ideal I, entonces deg(Rk(z)) > deg(Rk+1(z)).Adem´as existen A(z), B(z)∈Fq[z] tales que A(z)·Rk(z)+B(z)·Rk+1(z) = GCD(Rk(z), Rk+1(z)). Sea P(x, z) = A(z)·xnk+1−nk·Pk(x, z)+B(z)·Pk+1(x, z) = GCD(Rk(z), Rk+1(z))· xnk+1 +... Puesto que P(x, z)∈I, entonces P(x, z) =⇒G0. El t´ermino principal de P(x, z) es GCD(Rk(z), Rk+1(z)) ·xnk+1 y s´olo es divisible por el t´ermino principal de Pk+1(x, z). Es por esto, que se verifica que GCD(Rk(z), Rk+1(z)) = Rk+1(z), y por lo tanto Rk+1(z)|Rk(z) para todo k, k∈ {1, ..., m −1} 2.3 Berlekamp con Bases de Gr¨obner 119 b) Puesto que a(x) =⇒G0 y el t´ermino principal de a(x) es xn, entonces Rm(z) debe ser constante. c) Es bien conocida de Geometr´ıa Algebraica la correspondencia entre ideales de K[x1, ..., xn] y variedades de Kn(Kcuerpo), que viene dada por: Para V⊆Kn i(V) = {f∈K[x1, ..., xn] : f(x) = 0 ∀x∈V} Para un ideal I⊆K[x1, ..., xn] v(I) = {x∈Kn:f(x) = 0 ∀f∈I} Para obtener el resultado, se comprobar´a en primer lugar que iv(I) = I. {a(x), h(x)−z}es una base de Gr¨obner Reducida de I, respecto al orden monomial lexicogr´afico con z > x (este hecho es de comprobaci´on rutinaria). Sea F(x, z)∈iv(I), por el algoritmo de Euclides F(x, z) = Q1(x, z)·a(x) + Q2(x, z)·(h(x)−z) + R(x), con deg(R(x)) < n. Ya que R(x)∈iv(I) y a(x) es libre de cuadrados entonces R(x) = 0 y iv(I) = I. Por hip´otesis, a(x) es libre de cuadrados, es por esto que la ecuaci´on a(x) = 0 tiene nsoluciones diferentes (posiblemente en la clausura algebraica de Fq); sean estas x1, ..., xn. Se define zi=h(xi), i∈ {1, ...n}. Puesto que h(x)∈Wsi y s´olo si hq(x)≡h(x)mod a(x) entonces hq(xi) = h(xi), i∈ {1, ..., n}y por lo tanto zi=h(xi)∈Fq,i∈ {1, ..., n}. Los puntos de la variedad v(I), siempre tienen su segunda componente en Fq. Sea g(z) = Q i=1,...,n (z−zi)∈iv(I) = I. Ya que gtiene todas sus ra´ıces en Fqentonces I1=I∩Fq[z]6=∅. Teniendo en cuenta el orden de Gy el Teorema de Eliminaci´on [CLO92], es posible concluir que P1(x, z) = R1(z) y I1=< R1(z)>. 120 2 Bases de Gr¨obner y el Algoritmo de Berlekamp d) Como g(z)∈I1, existe b(z)∈Fq[z] tal que g(z) = R1(z)·b(z); se sigue entonces que R1(z) posee todas sus ra´ıces en Fq. Ya que Resultantex(a(x), h(x)−z)∈Fq[z]∩I entonces se verifica que R1(z)|Resultantex(a(x), h(x)−z) y Resultantex(a(x), h(x)−z) = Q i=1,...,n (h(xi)− z) = g(z) [GCL92] luego g, R1∈iv(I) = I,g=R1·by las ra´ıces de gson z1, ..., zn. Por lo tanto se puede afirmar que gyR1tienen las mismas ra´ıces, pero con distintas multiplicidades; adem´as R1(z) tiene las mismas ra´ıces que Resultantex(a(x), h(x)−z), pero con multiplicidad uno. e) Resultantex(a(x), h(x)−z) = g(z), con lo cual tiene todas sus ra´ıces en Fq. f) Se comprueba ahora que Pk(x, z) = Rk(z)·Sk(x, z) para k= 1, ..., m. Se procede por inducci´on. Para k= 1 P1(x, z) = R1(z)·S1(x, z), siendo S1(x, z) = 1 (v´ease c)) Se supone que el resultado es cierto para k. Sea Qk(z)∈Fq[z] tal que Rk(z) = Qk(z)·Rk+1(z). Se define: P(x, z) = Qk(z)·Pk+1(x, z)−xnk+1−nk·Pk(x, z)∈I P(x, z) =⇒G0, e incluso m´as, P(x, z) =⇒{P1,...,Pk}0 Entonces: Qk(z)·Pk+1(x, z) = P i=1,...,k ci(x, z)·Pi(x, z) Pk+1(x, z) = Rk(x,z) Qk(z) | {z } ·P i=1,...,k ci(x, z)·Pi(x,z) Rk(x,z) | {z } Rk+1(z)Rk(z)|Ri(z)i= 1, ..., k −1 y por lo tanto Rk+1(z)|Pk+1(x, z) g) 2.3 Berlekamp con Bases de Gr¨obner 121 Sea k∈ {1, ..., m−1}, c ∈Fqtal que Qk(c) = 0. Se proceder´a a comprobar en primer lugar que Sk+1(x, c) = GCD(a(x), h(x)−c) Sea j > k, se define P(x, z) = Qj(z)·Pj+1(x, z)−xnj+1−nj·Pj(x, z) =⇒G0 Entonces Qj(z)·Pj+1(x, z) = P i=1,...,j ci(x, z)·Pi(x, z), evaluado en ces Pj+1(x, c) = P i=k+1,...,j ci(x,c) Qj(c)·Pi(x, c) Se puede concluir entonces que Pk+1(x, c)|Pj(x, c)j∈ {k+ 1, ..., m} Por lo tanto Pk+1(x, c) = GCD({Pj(x, c)}m j=k+1), o si se escoge un polinomio m´onico Sk+1(x, c) = GCD({Pj(x, c)}m j=k+1). Como {P1(x, z), ...Pm(x, z)}es una base de Gr¨obner I=< a(x), h(x)− z >, se verifica que: < P1(x, c), ..., Pm(x, c)>=< a(x), h(x)−c >. Este hecho, junto al Teorema 2.2.6, proporciona el resultado deseado: a(x) = Q k=1,...,m−1 (Q c/Qk(c)=0 Sk+1(x, c)) ¤ Despu´es de este desarrollo te´orico, se hace necesario explicar la potencia de este resultado con un ejemplo. Ejemplo 2.3.2 Se factoriza el polinomio libre de cuadrados a(x) = x4+2 ∈ Z3[x]. Nota: T´engase en cuenta que se est´a trabajando en el anillo cociente Z3[x] <a(x)>, el cual tiene subyacente una estructura de F3-espacio vectorial con 122 2 Bases de Gr¨obner y el Algoritmo de Berlekamp base {1, x, x2, x3}; y que este es el motivo por el que se hablar´a indistintamente del vector (a, b, c, d)o del polinomio a+bx +cx2+dx3. El primer paso a dar es construir la matriz de Berlekamp-Petr: Q=      1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0       Una Z3-base para Wes {(1,0,0,0),(0,0,1,0),(0,1,0,1)}, y por lo tanto el n´umero de factores irreducibles en los cuales a(x)se descompone es 3. Se aplica el Teorema 2.3.1 al vector (0,0,1,0) = x2. Puesto que el ideal Ies: I=< x4+ 2, x2−z >. y la base de Gr¨obner Reducida de Icon respecto al orden monomial lexicogr´afico, con x > z, es G={2 + z2, x2−z}. Entonces P1(z) = 2 + z2=R1(z) P2(x, z) = x2−z R2(z) = 1 S2(x, z) = x2−z y, como consecuencia del Teorema 2.3.1: a(x) = Q k=1,...,2−1 (Q c/Qk(c)=0 Sk+1(x, c)) = Q c/c2+2=0 S2(x, c) = =S2(x, 1) ·S2(x, 2) = (x2−1) ·(x2−2) 2.4 Programaci´on en Maple 123 Como a(x)descompone en 2 factores (y deben ser 3), hay que continuar aplicando el Teorema 2.3.1. Para hacerlo, se toma el siguiente elemento de la base y uno de los factores; se aplica entonces el Teorema 2.3.1 al vector (0,1,0,1) = x+x3y al primer factor, el ideal Ies ahora: I=< x2−1, x3+x−z > La base de Gr¨obner Reducida de Icon respecto al orden monomial lexicogr´afico, con x > z es G={z2+ 2, x +z} As´ı pues P1(x, z) = z2+ 2 = (z−1) ·(z−2) = R1(z) P2(x, z) = x+z R2(z) = 1 S2(x, z) = x+z Entonces x2−1 = S2(x, 2) ·S2(x, 1) = (x+ 2) ·(x+ 1) a(x) = (x+ 2) ·(x+ 1) ·(x2−2) 2.4. Programaci´on en Maple De entre el gran abanico de posibilidades de c´alculo que ofrece Maple se encuentra la factorizaci´on de un polinomio en una variable con coeficientes sobre un cuerpo finito. Para ello, se proporcionan dos comandos sqrfree(f) mod p yBerlekamp(g,x,K) mod p; con el primero se obtiene la factorizaci´on del polinomio fen producto de polinomios libres de cuadrados, mientras que aplicar el segundo comando a cada uno de estos polinomios por separado proporciona su factorizaci´on. El objetivo final de este cap´ıtulo no es otro que hacer el segundo paso utilizando las bases de Gr¨obner como 124 2 Bases de Gr¨obner y el Algoritmo de Berlekamp herramienta de c´alculo, sin entrar en consideraciones de que m´etodo es el m´as r´apido. Con este objetivo en mente se han desarrollado cinco funciones en Maple 9.5, que implementan el algoritmo de factorizaci´on que se desprende del Teorema 2.3.1, ´estas funciones son: 1. GBerlekamp ´ Unica funci´on que est´a a disposici´on del usuario y que calcula la factorizaci´on de un polinomio en una variable, libre de cuadrados y con coeficientes sobre un cuerpo finito. 2. BerlekampPetrMatrix Subrutina de la funci´on GBerlekamp que obtiene la Matriz de Berlekamp- Petr. 3. WBasis Subrutina de la funci´on GBerlekamp que calcula una base para el subespacio W. 4. GroebnerKernel Subrutina de la funci´on GBerlekamp que calcula la factorizaci´on de un polinomio m´onico y libre de cuadrados. 5. CanonicalForm Subrutina de la funci´on GBerlekamp que calcula representantes can´onicos de elementos de un cuerpo finito. En las l´ıneas que siguen se muestra, en primer lugar, un par de ejemplos de utilizaci´on de este paquete y, en segundo lugar el listado de dichas funciones. Ejemplo 2.4.1 Se calcular´a la factorzaci´on de x4+ 2 ∈Z3[x] >GBerlekamp(x^4+2,x,3,alpha,alpha); {2 + x, x2+ 1,1 + x} 2.4 Programaci´on en Maple 125 Ejemplo 2.4.2 Se calcular´a la factorizaci´on de (1 + α+α3) + αx + (1 + α2+α3)x3+ (1 + α+α3)x4+x5∈Z2[α,x] <α4+α+1>=F16. >GBerlekamp(1+alpha+alpha^3+alpha*x+(1+alpha^2+alpha^3)*x^3+ >(1+alpha+alpha^3)*x^4+x^5,x,2,alpha^4+alpha+1,alpha); {α3+1+(α3+α)x+x3+x2(α2+α+ 1), α2+ 1 + (α3+α2)x+x2} # Para ejecutar correctamente este c´odigo, es necesario cargar # previamente el paquete GB de Andreas Pirklbauer‘s. Este paquete, que # est´a localizado en la Share Library, sirve para calcular bases de Gr¨obner # sobre cuerpos finitos. GBerlekamp:=proc(apoly,var,p::prime,irredpoly,alpha) # Esta funci´on devuelve la factorizaci´on de un polinomio m´onico # y libre de cuadrados. local GB apolydeg,GB card::integer,GB W,proceslist,aux,icont, hcont,dimW::integer,blnContinue,cardproceslist::integer, domloop, apolycan,irredpolycan; apolycan:=CanonicalForm(apoly,irredpoly,alpha,p); irredpolycan:=Normal(irredpoly) mod p; proceslist:={apolycan}; blnContinue:=true; GB apolydeg:=degree(apoly,var); GB card:=pˆdegree(irredpoly,alpha); # Se calcula una base para W. GB W:= WBasis(apolycan,var,GB apolydeg,p,GB card, irredpolycan,alpha); GB W:=evalm([seq(varˆicont,icont=0..GB apolydeg-1)] [Ber67] E. Berlekamp, Factoring polynomials over finite fields. Bell System Tech. J. 46, 1853-1859 (1967). [Ber70] E. Berlekamp, Factoring polynomials over large finite fields. Math. Comp. 24, 713-735 (1970). [Ber72] E. Berlekamp, Factoring Polynomials, pp. 1-7 in F. Hoffman, R.B. Levow, and R.S.D. Thomas (eds.), Proc. of the 3rd Southeastern Conference on Combinatorics, GRAPH THEORY AND COMPUTING, Atlantic Univ., Boca Raton, Florida (1972). [Buc65] B. Buchberger, An algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Ideal. Ph. D. Thesis, Univ. of Innsbruck, Math. Inst. (1965). [BuW98] B. Buchberger, F. Winkler, Gr¨obner bases and applications. Papers from the Conference on 33 Years of Gr¨obner Bases held at the University of Linz, Linz, February 2-4 (1998). London Mathematical Society Lecture Note Series, 251. Cambridge University Press, Cambridge (1998) [BGC98] J. L. Bueso, J. G´omez Torrecillas, F. J. Lobillo, F. J. Castro, An introduction to effective calculus in quantum groups. Lecture Notes in Pure and Appl. Math. 197, Dekker, New York, pp. 55-83 (1998). [Cam88] O. C´ampoli, A Principal Ideal Domain That Is Not a Euclidean Domain. Amer. Math. Monthly 95, 868-871 (1988). [CaZ81] D. Cantor, H. Zassenhaus, A new algorithm for factoring polynomials over finite fields. Math. Comp. 36, 587-592 (1981). [ChC82] T. Chou, G. Collins, Algorithms for the solution of systems of linear Diophantine equations. SIAM J. Computing 11, 687-708 (1982). [Coh74] P. Cohn, Algebra. John Wiley & Sons (1974). [CLO92] D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms. Springer-Verlag, New York (1992). [Czi95] G. Czichowski, A Note on Gr¨obner Bases and Integration of Rational Functions. J. Symb. Comput. 20, 163-167 (1995). [Der99] H. Derksen, Computation of invariants for reductive groups. Adv. Math. 141, 366-384 (1999). [Dix96] J. Dixmier, Enveloping Algebras. Graduate Studies in Mathematics, Vol. 11, AMS (1996). [DuF99] D. Dummit, R. Foote, Abstract Algebra, Second Edition. John Wiley & Sons, Inc., New York (1999). [F1879] G. Frobenius, L. Stickelberger, ¨ Uber Gruppen von Vertauschbaren Elementen. J. de Crelle LXXXVI, 217 (1879). [GaS92] J. von zur Gathen, V. Shoup, Computing Frobenius maps and factoring polynomials. Comput. Complexity 2, 187-224 (1992). [GaG99] J. von zur Gathen, J. Gerhard, Modern Computer Algebra. Cambridge University Press (1999). [GCL92] K. Geddes, S. Czapor, G. Labahn, Algorithms for Computer Algebra. Kluwer Academic Publishers (1992). [Gie93] M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms. Ph. D Thesis, Departament of Computer Science, University of Toronto (1993). [GRZ02] M. Giesbrecht, G. Reid, Y. Zang, Non-Conmutative Gr¨obner Bases in Poincar´e-Birkhoff-Witt Extensions. Proceedings of the Fifth International Workshop on Computer Algebra in Scientific Computing, September 22-27, Yalta, Ukraine, pp. 97-106 (2002). [GiS02] M. Giesbrecht, A. Storjhann, Computing Rational Forms of Integer Matrices. J. Symb. Comput. 34, 157-172 (2002). [G1899] P. Gordan, Newer Beweis des Hilbertschen Satzes ¨uber homogene Funktionen. Nachrichten K¨onig. Ges. Der. Wiss. Zu G¨ott. 240-242 (1899). [Gra00] W. Graaf, Lie Algebras: Theory and Algorithms. Elsevier Science B. V., Amsterdam (2000). [Gre94] E. L. Green, An Introduction to Noncommutative Gr¨obner bases. Computational algebra. Lect. Notes in Pure and Appl. Marcel Dekker, Inc., New York pp. 167-190 (1994). [Gre97] J. Greene, Principal Ideal Domains Are Almost Euclidean. Amer. Math. Monthly 104, 154-156 (1997). [Gr¨o39] Gr¨obner W., ¨ Uber die algebraischen Eigenschaften der Integrale von linearen Differentialgleichungen mit konstanten Koeffizienten. Monatsh. der Math. 47, 247-284 (1939). [HaH83] B. Hartley, T. Hawkes, Rings, Modules and Linear Algebra. Chapman and Hall (1983). [Hea95] A. Hearn, Reduce User´s Manual 3.6. Rand (1995). [Her26] G. Hermann, Der Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95, 736-788 (1926). [H1890] D. Hilbert, ¨ Uber die Theorie del algebraischen Formen, Math. Ann. 36, 473-534 (1890). Reprinted in Gesammelte Abhandlungen, Volume II, Chelsea, New York (1965). [H1893] D. Hilbert, ¨ Uber die vollen Invariantensysteme. Math. Ann. 42, 313- 373 (1893). Reprinted in: Theory of Algebraic Invariants, Cambridge University Press, Cambridge (1993). [Hir64] H. Hironaka, Resolution of singularities of an algebraic variety over a field of characteristic zero. Ann. Math. 79, 109-326 (1964). [HiSt97] P. Hilton, U. Stammbach, A Course in Homological Algebra, Second Edition. Springer Verlag (1997). [Jac74] N. Jacobson, Basic Algebra I. W. H. Freeman and Company (1974). [Jea99] C-P. Jeannerod, Formes Normales de Matrices et valeurs propres en calcul formel. Preprint (1999). [KaS98] E. Kaltofen, V. Shoup, Subquadratic-time factoring of polynomials over finite fields. Math. Comp. 67, 1179-1197 (1998). [KaW90] A. Kandri-Rody, V. Weispfenning, Noncommutative Gr¨obner bases in algebras of solvable type. J. Symb. Comput. 9(1), 1-26 (1990). [KaB79] R. Kannan, A. Bachem, Polynomial time algorithms to compute Hermite and Smith normal forms of an integer matrix. SIAM J. Computing 8, 499-507 (1979). [KnB70] D. Knuth, P. Bendix, Simple word problems in universal algebras. In: Leech, J. (ed.), Computational Problems in Abstract Algebra, Pergamon Press, 263-297 (1970). [Kre92] H. Kredel, Solvable polynomial rings. PhD. Thesis, FMI, Universit¨at Passau (1992). [Laz85] D. Lazard, Ideal Bases and Primary Decomposition: Case of Two Variables. J. Symb Comput.1, 261-270 (1985). [LaR90] D. Lazard, R. Rioboo, Integration of Rational Functions: Rational Computation of the Logarithmic Part. J. Symb Comput. 9(2), 113- 116 (1990). [Lak96] F. Lazebnik, On systems of linear diophnatine equations. Mathematics Magazine, Vol. 69, No. 4, October, 261-266 (1996). [ Li02] H. Li, Noncommutative Gr¨obner bases and filtered-graded transfer. Lecture Notes in Math. 1795. Springer-Verlag, Berlin (2002). [LiN97] R. Lidl, H. Niederreiter, Finite Fields. Encyclopedia of Mathematics and its applications 20. Second Edition, Cambridge University Press (1997). [Lod93] J-L. Loday, Une version non commutative des alg`ebres de Lie: les alg`ebres de Leibniz. Enseign. Math. 39, 269-293 (1993). [Lod97] J-L. Loday, Overview on Leibniz algebras, dialgebras and their homology. Fields Inst. Comm. 17, 91-102 (1997). [Lod01] J-L. Loday, Dialgebras in Dialgebras and related operads. Lecture Notes in Math. 1763, Springer, Berlin, 7-66 (2001). [LoP93] J-L. Loday, T. Pirashvili, Universal enveloping algebras of Leibniz algebras and (co)homology. Math. Ann. 296, 139-158 (1993). [LoP98] J-L. Loday, T. Pirashvili, The Tensor Category of Linear Maps and Leibniz Algebras. Georgian Math. J. Vol. 5, No. 3, 263-276 (1998). [M1916] F. Macaulay, The algebraic theory of modular systems. Revised reprint of the 1916 original. With an introduction by Paul Roberts. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1994). [M1927] F. Macaulay, Some properties of enumeration in the theory of modular systems. Proc. London Math. Soc. 26, 531-555 (1927). [Mal72] A. M´altsev, Fundamentos de ´ Algebra Lineal. Editorial Mir Mosc´u (1972). [Mol88] H. M¨oller, On the Construction of Gr¨obner Basis Using Syzygies. J. Symb. Comput. 6, 345-359 (1988). [Mor94] T. Mora, An introduction to commutative and non conmutative Gr¨obner bases. Theor. Comp. Sci. 134, 131-173 (1994). [NaS92] R. Nagle, E. Saff, Fundamentos de Ecuaciones Diferenciales, Segunda Edici´on. Addison-Wesley Iberoamericana (1992). [NaG94] G. Nakos, N. Glinos, Computing Gr¨obner Bases over the Integers. The Mathematica Journal, Vol. 4 (3), 70-75 (1994). [Nie94] H. Niederreiter, Factoring polynomials over finite fields using differential equations and Normal Bases. Math. Comp. 62, 819-830 (1994). [Nor01] P. Nordbeck, On the Finiteness of Gr¨obner Bases Computation in Quotients of the Free Algebra. Appl. Algebra Engrg. Comm. Comput. 11, 157-180 (2001). [NoY02] M. Noro, K. Yokoyama, Yet Another Practical Implementation of Polynomial Factorization over Finite Fields. Proc. ISAAC’2002, ACM Press, New York, pp. 200-206 (2002). [Pan88] L. Pan, On D-bases of Polynomial Ideals Over Principal Ideal Domains. J. Symb. Comput. 7, 55-69 (1988). [Pes94] M. Pesch, Gr¨obner bases in rings of substitution operators. Proc. Workshop Comp. Algebra. Univ. Karlsruhe, 138-143 (1994). [Rei95] B. Reinert, On Gr¨obner Bases in Monoid and Group Rings. Ph. D. Thesis, University of Kaiserslautern (1995). [Rom92] S. Roman, Advanced Linear Algebra. Graduate Texts in Mathematics, Springer-Verlag (1992). [Rot76] M. Rothstein, Aspects of Symbolic Integration and Simplification of Exponential and Primitive Functions. Ph. D. Thesis, University of Wisconsin (1976). [Sch80] F. O. Schreyer, Die Berechnung von Syzygien mit dem verallgemeintern Weierstrass’schen Divisionssatz. Diplomarbeit, Hamburg (1980). [Sei74] A. Seidenberg, Constructions in Algebra. Trans. Amer. Math. Soc. 197, 272-313 (1974). [Ser02] D. Serre, Matrices, Theory and Applications. Graduate Texts in Mathematics. Springer (2002). [Shi62] A. Shirshov, Some algorithmic problems for Lie algebras, Siberian Math. J. 3, 292-296 (1962). [S1861] H. Smith, On systems of indeterminate equations and congruences. Philos. Trans. 151, 293-326 (1861). [S1851] J. Sylvester, An Essay on Canonical Forms, Supplement to a Sketch of a Memoir on Elimination, Transformation and Canonical Forms. London (1851). Reprinted in J. Sylvester’s Collected Mathematical Papers, Vol. 1. Cambridge, England: At the University Press, 209 (1904). [Tra76] B. Trager, Algebraic Factoring and Rational Function Integration. Proc. SYMSAC 76, NY ACM Press, 219-226 (1976). [Vil94] G. Villard, Fast Parallel computation of the Smith Normal Form of Polynomial matrices. In International Symposium on Symbolic and Algebraic Computation, Oxford, UK, 312-317, ACM Press (1994). [Vil95] G. Villard, Generalized subresultants for computing the Smith Normal Form of polynomial matrices. J. Symb. Comput. 20, 269-286 (1995). [Vil97] G. Villard, Fast Parallel Algorithms for Matrix Reduction to Normal Forms. AAECC 8, 511-537 (1997). [Wei89] V. Weispfenning, Gr¨obner bases for polynomial ideals over commutative regular rings. Proc. EUROCAL’87, Springer, LNCS 378, pp. 336-347 (1989). [Wei92] V. Weispfenning, Finite Gr¨obner bases in non-Noetherian skew polynomials rings. Proc. ISAAC’92, ACM Press, New York, pp. 329-334 (1992). ´ Indice alfab´etico B=0A, 21 B≃0A, 21 Lad(A), 22 lc(f), 22 lp(f), 22 lt(f), 22 S(f, g), 22, 142 ´algebra de Leibniz, 144 envolvente universal, 146 di´algebra env. universal, 147 di´algebras, 147 algoritmos Diagonaliza, 18 DiagonalizaG, 47 DiagonalizaG Paso, 58 Divisible, 12 Forma Normal, 140 Frobenius, 72 Generadores P D, 68 Inversa Minimo, 62 Inversa Paso, 61 Jacobson, 83 Jordan, 86 Segunda F C, 76 Smith, 10 SmithG, 48 SmithG Paso, 59 SmithR, 17 base de Gr¨obner, 141 Berlekamp algoritmo, 114 funci´on GBerlekamp, 124 conjunto autorreducido, 141 minimal, 141 reducido, 141 DIP, 7 divisor elemental, 10 f. n. m´odulo G, 139 factor derecha, 135 izquierda, 135 factores invariantes, 2 forma normal, 139 269