Ecuación lineal sobre un anillo

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 se buscan pertenecen a un campo determinado, comúnmente los números reales o los 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 membresía 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 las sicigias consiste, dados k elementos en R , en proporcionar un sistema de generadores del módulo de las sicigias de es decir un sistema de generadores del submódulo de aquellos elementos en R ^k que son 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 equivale a encontrar un sistema de generadores del aniquilador de a ₁ .

Dada una solución del problema de membresía ideal, se obtienen todas las soluciones añadiéndole los elementos del módulo de sizigias. En otras palabras, todas las soluciones provienen de 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 sizigia .

Un anillo tal que existen algoritmos para las operaciones aritméticas (suma, resta, multiplicación) y para los problemas anteriores puede denominarse anillo computable o anillo efectivo . También se puede decir que el álgebra lineal sobre el anillo es efectiva .

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

Generalidades

Para poder resolver el problema de sizigias, es necesario que el módulo de sizigias se genere de forma finita , porque es imposible generar una lista infinita. Por lo tanto, los problemas aquí considerados sólo tienen sentido para un anillo noetheriano , o al menos para un anillo coherente . De hecho, este artículo está restringido a los dominios integrales noetherianos debido al siguiente resultado. ^[1]

Dado un dominio integral noetheriano, si existen algoritmos para resolver el problema de membresía ideal y el problema de sizigias 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 se tienen algoritmos para suma, resta, multiplicación y cálculo de inversas multiplicativas . De hecho, resolver el problema de membresía de submódulos es lo que comúnmente se llama resolver el sistema , y ​​resolver el problema de sizigia 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 a ₁ , ..., a _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 efectiva sobre R / I : para resolver un sistema lineal sobre R / I , basta escribirlo sobre R y sumar 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 polinómico si y sólo 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 sólo si sus coeficientes son iguales, las ecuaciones del problema se convierten en ecuaciones lineales en los coeficientes, que pueden resolverse sobre 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 efectiva sobre los números enteros ; consulte 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, probar si a es divisor de b y, si este 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 as + 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 matrices invertibles, por lo 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}}}$

tal 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 identidad de Bézout, y para u y v el cociente de − b y a por as + bt ; esta elección implica que el determinante de la matriz cuadrada es 1. )

Con un algoritmo de este tipo, la forma normal de Smith de una matriz se puede calcular exactamente como en el caso de los números enteros, y esto es suficiente para aplicar el sistema diofántico lineal descrito en el sistema para obtener un algoritmo que resuelva 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, se puede utilizar el algoritmo euclidiano extendido para calcular la matriz unimodular anterior; consulte Máximo común divisor polinómico § Identidad de Bézout y algoritmo MCD extendido para obtener más detalles.

Sobre polinomios suena sobre un campo.

El álgebra lineal es eficaz en un anillo polinomial sobre un campo k . Esto lo demostró por primera vez en 1926 Grete Hermann . ^[2] Los algoritmos resultantes de los resultados de Hermann son sólo de interés histórico, ya que su complejidad computacional es demasiado alta para permitir un cálculo informático eficaz. ${\displaystyle k[x_{1},\ldots ,x_{n}]}$

Actualmente, todas las pruebas de que el álgebra lineal es eficaz en anillos polinómicos e implementaciones informáticas se basan en la teoría de bases de Gröbner .

Referencias

1. Hombre rico, Fred (1974). "Aspectos constructivos de los anillos noetherianos". Proc. América. Matemáticas. 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; Juan pequeño; Donal O'Shea (1997). Ideales, variedades y algoritmos (segunda ed.). Springer-Verlag . ISBN 0-387-94680-2. Zbl  0861.13012.
• Aschenbrenner, Matías (2004). "Pertenencia ideal en anillos polinomiales sobre los números enteros" (PDF) . J.Amer. Matemáticas. Soc . 17 (2). AMS: 407–441. doi : 10.1090/S0894-0347-04-00451-5 . S2CID  8176473 . Consultado el 23 de octubre de 2013 .