Ecuación lineal sobre un anillo

En álgebra , las ecuaciones lineales y los sistemas de ecuaciones lineales sobre un cuerpo son ampliamente estudiados. "Sobre un cuerpo" significa que los coeficientes de las ecuaciones y las soluciones que se buscan pertenecen a un cuerpo dado, comúnmente los números reales o complejos . Este artículo está dedicado a los mismos problemas donde "cuerpo" 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. En primer lugar, el problema de pertenencia ideal , que consiste, dada una ecuación no homogénea

${\displaystyle a_{1}x_{1}+\cdots +a_{k}x_{k}=b}$

con y b en un anillo dado R , para decidir si tiene una solución con en R , y, si la hay, proporcionar una. 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 , decidir si a es una unidad en R . ${\displaystyle a_{1},\ldots ,a_{k}}$ ${\displaystyle x_{1},\ldots ,x_{k}}$

El problema de sicigia consiste, dados k elementos en R , en proporcionar un sistema de generadores del módulo de las sicigias de que sea un sistema de generadores del submódulo de aquellos elementos en R ^k que sean soluciones de la ecuación homogénea ${\displaystyle a_{1},\ldots ,a_{k}}$ ${\displaystyle (a_{1},\ldots ,a_{k}),}$ ${\displaystyle (x_{1},\ldots ,x_{k})}$

${\displaystyle a_{1}x_{1}+\cdots +a_{k}x_{k}=0.}$

El caso más simple, cuando k = 1, consiste en encontrar un sistema de generadores del aniquilador de a ₁ .

Dada una solución del problema de pertenencia ideal, se obtienen todas las soluciones agregá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 a submódulos . El segundo también se denomina problema de sicigia .

Un anillo tal que existen 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 sobre el anillo es efectivo .

El artículo considera los principales anillos para los cuales el álgebra lineal es efectiva.

Generalidades

Para poder resolver el problema de la sicigia, es necesario que el módulo de sicigias sea finitamente generado , porque es imposible obtener como salida 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 existen 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 cuerpo es un anillo efectivo en cuanto se tienen algoritmos para la suma, resta, multiplicación y cálculo de inversos multiplicativos . De hecho, resolver el problema de pertenencia de submódulos es lo que comúnmente se llama resolver el sistema , y ​​resolver el problema de 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 comprobar si un elemento a es divisor de cero : esto equivale a resolver la ecuación lineal ax = 0 .
• Existe un algoritmo para comprobar si un elemento a es una unidad y, si lo es, calcular su inversa: esto equivale a resolver la ecuación lineal ax = 1 .
• Dado un ideal I generado por un ₁ , ..., un _k ,
  • Existe un algoritmo para comprobar si dos elementos de R tienen la misma imagen en R / I : comprobar la igualdad de las imágenes de a y b equivale a resolver la ecuación a = b + a ₁  z ₁ + ⋯ + a _k  z _k ;
  • El álgebra lineal es eficaz sobre R / I : para resolver un sistema lineal sobre R / I , basta escribirlo sobre R y añadir a un lado de la i ésima ecuación a ₁  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 de polinomios si y solo si se tiene un algoritmo que calcula un límite superior del grado de los polinomios que pueden ocurrir al resolver sistemas lineales de ecuaciones: si se tienen algoritmos de resolución, sus resultados 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 en un anillo efectivo. ${\displaystyle R[x_{1},\ldots ,x_{n}]}$

Sobre los números enteros o un dominio ideal principal

Existen algoritmos para resolver todos los problemas abordados en este artículo sobre los números enteros . En otras palabras, el álgebra lineal es eficaz sobre los números enteros ; consulte el sistema diofántico lineal para obtener más detalles.

De manera más general, el álgebra lineal es eficaz en un dominio ideal principal si existen algoritmos para la suma, la resta y la multiplicación, y

• Resolver ecuaciones de la forma ax = b , es decir, comprobar si a es divisor de b y, si es el caso, calcular el cociente a / b ,
• Calcular la identidad de Bézout , es decir, dados a y b , calcular s y t tales que como + bt es el máximo común divisor de a y b .

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.

${\displaystyle {\begin{bmatrix}s&t\\u&v\end{bmatrix}}}$

de tal manera que

${\displaystyle {\begin{bmatrix}s&t\\u&v\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}\gcd(a,b)\\0\end{bmatrix}}.}$

(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 a 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 se puede calcular exactamente como en el caso entero, y esto basta para aplicar lo descrito en el sistema diofántico lineal para obtener un algoritmo para resolver cada sistema lineal.

El caso principal en el que esto se utiliza comúnmente es el de los sistemas lineales sobre el anillo de polinomios univariados sobre un cuerpo. En este caso, se puede utilizar el algoritmo euclidiano extendido para calcular la matriz unimodular anterior; consulte Máximo común divisor de polinomios § Identidad de Bézout y algoritmo MCD extendido para obtener más detalles.

Anillos sobre polinomios sobre un campo

El álgebra lineal es eficaz en un anillo de polinomios sobre un cuerpo k . Esto fue demostrado 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 un cálculo computacional efectivo. ${\displaystyle k[x_{1},\ldots ,x_{n}]}$

Las pruebas de que el álgebra lineal es efectiva en anillos polinomiales y en implementaciones informáticas se basan actualmente en la teoría de bases de Gröbner .

Referencias

1. Richman, Fred (1974). "Aspectos constructivos de los anillos noetherianos". Proc. Amer. Math. Soc . 44 (2): 436–441. doi : 10.1090/s0002-9939-1974-0416874-9 .
2. Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale". Annalen Matemáticas . 95 : 736–788. doi :10.1007/BF01206635. S2CID  115897210.Traducción al inglés en Communications in Computer Algebra 32/3 (1998): 8–30.

Enlaces externos

• David A. Cox; John Little; Donal O'Shea (1997). Ideales, variedades y algoritmos (segunda edición). Springer-Verlag . ISBN 0-387-94680-2.Zbl 0861.13012  .
• Aschenbrenner, Matthias (2004). "Pertenencia ideal en anillos polinomiales sobre números enteros" (PDF) . J. Amer. Math. Soc . 17 (2). AMS: 407–441. doi : 10.1090/S0894-0347-04-00451-5 . S2CID  8176473 . Consultado el 23 de octubre de 2013 .