En álgebra , las ecuaciones lineales y los sistemas de ecuaciones lineales sobre un campo se estudian ampliamente. "Sobre un campo" significa que los coeficientes de las ecuaciones y las soluciones que uno está buscando pertenecen a un campo dado, comúnmente los números reales o complejos . Este artículo está dedicado a los mismos problemas en los que "campo" se reemplaza por " anillo conmutativo " o, típicamente, " dominio integral noetheriano ".
En el caso de una sola ecuación, el problema se divide en dos partes. Primero, el problema de pertenencia ideal , que consiste, dada una ecuación no homogénea
con y b en un anillo dado R , para decidir si tiene una solución conen R , y, si lo hay, para proporcionar uno. Esto equivale a decidir si b pertenece al ideal generado por a i . El ejemplo más simple de este problema es, para k = 1 y b = 1 , para decidir si una es una unidad en R .
El problema de la sicigia consiste, dados k elementosen R , para proporcionar un sistema de generadores del módulo de las sicigias deque es un sistema de generadores del submódulo de esos elementosen R k que son solución de la ecuación homogénea
El caso más simple, cuando k = 1 equivale a encontrar un sistema de generadores del aniquilador de un 1 .
Dada una solución del problema de pertenencia ideal, se obtienen todas las soluciones añadiéndole los elementos del módulo de sicigias. En otras palabras, todas las soluciones las proporciona la solución de estos dos problemas parciales.
En el caso de varias ecuaciones, se produce la misma descomposición en subproblemas. El primer problema se convierte en el problema de pertenencia al submódulo . El segundo también se llama problema de sicigia .
Un anillo tal que existan algoritmos para las operaciones aritméticas (suma, resta, multiplicación) y para los problemas anteriores puede llamarse anillo computable o anillo efectivo . También se puede decir que el álgebra lineal en el anillo es eficaz .
El artículo considera los anillos principales para los que el álgebra lineal es eficaz.
Generalidades
Para poder resolver el problema de la sicigia, es necesario que el módulo de las sicigias se genere de forma finita, porque es imposible generar una lista infinita. Por lo tanto, los problemas considerados aquí tienen sentido solo para un anillo noetheriano , o al menos un anillo coherente . De hecho, este artículo está restringido a dominios integrales noetherianos debido al siguiente resultado. [1]
Dado un dominio integral noetheriano, si hay algoritmos para resolver el problema de pertenencia ideal y el problema de sicigias para una sola ecuación, entonces se pueden deducir de ellos algoritmos para problemas similares relacionados con sistemas de ecuaciones.
Este teorema es útil para demostrar la existencia de algoritmos. Sin embargo, en la práctica, los algoritmos de los sistemas se diseñan directamente.
Un campo es un anillo efectivo tan pronto como uno tiene algoritmos para la suma, resta, multiplicación y cálculo de inversos multiplicativos . De hecho, resolver el problema de pertenencia al submódulo es lo que comúnmente se llama resolver el sistema , y resolver el problema de la sicigia es el cálculo del espacio nulo de la matriz de un sistema de ecuaciones lineales . El algoritmo básico para ambos problemas es la eliminación gaussiana .
Propiedades de los anillos efectivos
Sea R un anillo conmutativo efectivo.
- Existe un algoritmo para probar si un elemento a es un divisor de cero : esto equivale a resolver la ecuación lineal ax = 0 .
- Existe un algoritmo para probar si un elemento a es una unidad , y si lo es, calcular su inverso: esto equivale a resolver la ecuación lineal ax = 1 .
- Dado un ideal I generada por un 1 , ..., un k ,
- hay un algoritmo para probar si dos elementos de R tienen la misma imagen en R / I : probar la igualdad de las imágenes de una y b equivale a resolver la ecuación un = b + a 1 z 1 + ⋯ + un k z k ;
- El álgebra lineal es eficaz sobre R / I : para resolver un sistema lineal sobre R / I , basta con escribirlo sobre R y sumar a un lado de la i- ésima ecuación a 1 z i , 1 + ⋯ + a k z i , k (para i = 1, ... ), donde z i , j son nuevas incógnitas.
- El álgebra lineal es eficaz en el anillo polinomial si y solo si uno tiene un algoritmo que calcula un límite superior del grado de los polinomios que pueden ocurrir al resolver sistemas lineales de ecuaciones: si uno tiene algoritmos de resolución, sus salidas dan los grados. Por el contrario, si se conoce un límite superior de los grados que ocurren en una solución, se pueden escribir los polinomios desconocidos como polinomios con coeficientes desconocidos. Entonces, como dos polinomios son iguales si y solo si sus coeficientes son iguales, las ecuaciones del problema se convierten en ecuaciones lineales en los coeficientes, que se pueden resolver sobre un anillo efectivo.
Sobre los enteros o un dominio ideal principal
Existen algoritmos para resolver todos los problemas que se abordan en este artículo sobre los números enteros. En otras palabras, el álgebra lineal es eficaz sobre los números enteros . Consulte Sistema diofantino lineal para obtener detalles.
De manera más general, el álgebra lineal es eficaz en un dominio ideal principal si existen algoritmos para la suma, resta y multiplicación, y
- resolver ecuaciones de la forma ax = b , es decir, probar si a es un divisor de b y, si es el caso, calcular el cociente a / b ,
- el cálculo de la identidad de Bézout , es decir, dado un y b , calcular s y t de tal manera que como + bt es un máximo común divisor de p y q .
Es útil extender al caso general la noción de matriz unimodular llamando unimodular a una matriz cuadrada cuyo determinante es una unidad . Esto significa que el determinante es invertible e implica que las matrices unimodulares son exactamente las matrices invertibles, de modo que todas las entradas de la matriz inversa pertenecen al dominio.
Los dos algoritmos anteriores implican que dados a y b en el dominio ideal principal, existe un algoritmo que calcula una matriz unimodular
tal que
(Este algoritmo se obtiene tomando para s y t los coeficientes de la identidad de Bézout, y para u y v el cociente de - b y una por como + bt ; esta elección implica que el determinante de la matriz cuadrada es 1 ).
Con tal algoritmo, la forma normal de Smith de una matriz puede calcularse exactamente como en el caso de números enteros, y esto es suficiente para aplicar lo descrito en Sistema diofantino lineal para obtener un algoritmo para resolver cada sistema lineal.
El caso principal donde esto se usa comúnmente es el caso de sistemas lineales sobre el anillo de polinomios univariados sobre un campo. En este caso, el algoritmo euclidiano extendido puede usarse para calcular la matriz unimodular anterior. Consulte Polinomio máximo común divisor § Identidad de Bézout y algoritmo GCD extendido para obtener más detalles.
Sobre polinomios, anillos sobre un campo
El álgebra lineal es eficaz en un anillo polinomial sobre un campo k . Esto fue probado por primera vez en 1926 por Grete Hermann . [2] Los algoritmos resultantes de los resultados de Hermann son solo de interés histórico, ya que su complejidad computacional es demasiado alta para permitir una computación eficaz.
Las pruebas de que el álgebra lineal es eficaz en los anillos polinomiales y las implementaciones informáticas se basan actualmente en la teoría de bases de Gröbner .
Referencias
- ^ Richman, Fred (1974). "Aspectos constructivos de los anillos noetherianos" . Proc. Amer. Matemáticas. Soc . 44 (2): 436–441. doi : 10.1090 / s0002-9939-1974-0416874-9 .
- ^ Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale". Mathematische Annalen . 95 : 736–788. doi : 10.1007 / BF01206635 . S2CID 115897210 .. Traducción al inglés en Communications in Computer Algebra 32/3 (1998): 8–30.
- David A. Cox; John Little; Donal O'Shea (1997). Ideales, variedades y algoritmos (segunda ed.). Springer-Verlag . ISBN 0-387-94680-2. Zbl 0861.13012 .
- Aschenbrenner, Matthias (2004). "Membresía ideal en anillos polinomiales sobre los enteros" (PDF) . J. Amer. Matemáticas. Soc . AMS. 17 (2): 407–441. doi : 10.1090 / S0894-0347-04-00451-5 . S2CID 8176473 . Consultado el 23 de octubre de 2013 .