Équation linéaire sur un anneau - Linear equation over a ring

En algèbre , les équations linéaires et les systèmes d'équations linéaires sur un champ sont largement étudiés. «Sur un champ» signifie que les coefficients des équations et des solutions que l'on cherche appartiennent à un champ donné, couramment les nombres réels ou complexes . Cet article est consacré aux mêmes problèmes où « champ » est remplacé par « anneau commutatif », ou, en général « Noetherian domaine intégral ».

Dans le cas d'une seule équation, le problème se divise en deux parties. Premièrement, le problème d'appartenance idéal , qui consiste, étant donné une équation non homogène

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

avec et b dans un cycle R donné , pour décider s'il a une solution avec dans R , et, le cas échéant, pour en fournir une. Cela revient à décider si b appartient à l'idéal généré par a _i . L'instance de ce problème est plus simple, pour k = 1 et b = 1 , de décider si un est une unité de R . ${\ displaystyle a_ {1}, \ ldots, a_ {k}}$${\ displaystyle x_ {1}, \ ldots, x_ {k}}$

Le problème de syzygie consiste, étant donné k éléments dans R , à fournir un système de générateurs du module des syzygies de qui est un système de générateurs du sous - module de ces éléments dans R ^k qui sont solution de l'équation homogène ${\ 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.}$

Le cas le plus simple, quand k = 1 revient à trouver un système de générateurs de l' annihilateur d' un ₁ .

Étant donné une solution du problème d'appartenance idéal, on obtient toutes les solutions en y ajoutant les éléments du module de syzygies. En d'autres termes, toutes les solutions sont apportées par la solution de ces deux problèmes partiels.

Dans le cas de plusieurs équations, la même décomposition en sous-problèmes se produit. Le premier problème devient le problème de l'appartenance au sous - module . Le second est également appelé problème de syzygie .

Un anneau tel qu'il existe des algorithmes pour les opérations arithmétiques (addition, soustraction, multiplication) et pour les problèmes ci-dessus peut être appelé un anneau calculable ou un anneau efficace . On peut aussi dire que l'algèbre linéaire sur l'anneau est efficace .

L'article considère les principaux anneaux pour lesquels l'algèbre linéaire est efficace.

Généralités

Pour pouvoir résoudre le problème de syzygy, il faut que le module de syzygies soit de génération finie, car il est impossible de sortir une liste infinie. Par conséquent, les problèmes considérés ici n'ont de sens que pour un anneau noéthérien , ou du moins un anneau cohérent . En fait, cet article est limité aux domaines intégraux noéthériens en raison du résultat suivant.

Étant donné un domaine intégral noétérien, s'il existe des algorithmes pour résoudre le problème d'appartenance idéale et le problème de syzygies pour une seule équation, alors on peut en déduire des algorithmes pour les problèmes similaires concernant les systèmes d'équations.

Ce théorème est utile pour prouver l'existence d'algorithmes. Cependant, dans la pratique, les algorithmes des systèmes sont conçus directement.

Un champ est un anneau efficace dès que l'on dispose d'algorithmes d'addition, de soustraction, de multiplication et de calcul des inverses multiplicatifs . En fait, la résolution du problème d'appartenance à un sous-module est ce que l'on appelle communément la résolution du système , et la résolution du problème de la syzygie est le calcul de l' espace nul de la matrice d'un système d'équations linéaires . L'algorithme de base pour les deux problèmes est l'élimination gaussienne .

Propriétés des anneaux efficaces

Soit R un anneau commutatif efficace.

• Il existe un algorithme pour tester si un élément a est un diviseur nul : cela revient à résoudre l'équation linéaire ax = 0 .
• Il existe un algorithme pour tester si un élément a est une unité , et si c'est le cas, calculer son inverse: cela revient à résoudre l'équation linéaire ax = 1 .
• Étant donné un idéal I généré par un ₁ , ..., un _k ,
  • il existe un algorithme pour tester si deux éléments de R ont la même image dans R / I : tester l'égalité des images de a et b revient à résoudre l'équation a = b + a ₁ z ₁ + ⋯ + a _k z _k ;
  • l'algèbre linéaire est efficace sur R / I : pour résoudre un système linéaire sur R / I , il suffit de l'écrire sur R et d'ajouter d'un côté de la i ème équation a ₁ z _{i , 1} + ⋯ + a _k z _{i , k} (pour i = 1, ... ), où les z _{i , j} sont de nouvelles inconnues.
• L'algèbre linéaire est efficace sur l' anneau polynomial si et seulement si on a un algorithme qui calcule une borne supérieure du degré des polynômes qui peuvent se produire lors de la résolution de systèmes d'équations linéaires: si on a des algorithmes de résolution, leurs sorties donnent les degrés. Inversement, si l'on connaît une borne supérieure des degrés apparaissant dans une solution, on peut écrire les polynômes inconnus comme des polynômes avec des coefficients inconnus. Alors, comme deux polynômes sont égaux si et seulement si leurs coefficients sont égaux, les équations du problème deviennent des équations linéaires dans les coefficients, qui peuvent être résolues sur un anneau effectif. ${\ displaystyle R [x_ {1}, \ ldots, x_ {n}]}$

Sur les entiers ou un domaine idéal principal

Il existe des algorithmes pour résoudre tous les problèmes abordés dans cet article sur les entiers. En d'autres termes, l'algèbre linéaire est efficace sur les entiers . Voir Système diophantien linéaire pour plus de détails.

Plus généralement, l'algèbre linéaire est efficace sur un domaine idéal principal s'il existe des algorithmes d'addition, de soustraction et de multiplication, et

• résoudre des équations de la forme ax = b , c'est-à-dire tester si a est un diviseur de b , et, si c'est le cas, calculer le quotient a / b ,
• le calcul de l'identité de Bezout , qui, étant donné un et b , calcul s et t de telle sorte que comme + bt est un plus grand commun diviseur de p et q .

Il est utile d'étendre au cas général la notion de matrice unimodulaire en appelant unimodulaire une matrice carrée dont le déterminant est une unité . Cela signifie que le déterminant est inversible et implique que les matrices unimodulaires sont exactement les matrices inversibles de sorte que toutes les entrées de la matrice inverse appartiennent au domaine.

Les deux algorithmes ci-dessus impliquent que, étant donné a et b dans le domaine idéal principal, il existe un algorithme calculant une matrice unimodulaire

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

tel que

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

(Cet algorithme s'obtient en prenant pour s et t les coefficients d'identité de Bézout, et pour u et v le quotient de - b et a par as + bt ; ce choix implique que le déterminant de la matrice carrée est 1. )

Ayant un tel algorithme, la forme normale de Smith d'une matrice peut être calculée exactement comme dans le cas des nombres entiers, et cela suffit pour appliquer le système diophantien linéaire décrit pour obtenir un algorithme pour résoudre chaque système linéaire.

Le cas principal où cela est couramment utilisé est le cas des systèmes linéaires sur l'anneau de polynômes univariés sur un champ. Dans ce cas, l' algorithme euclidien étendu peut être utilisé pour calculer la matrice unimodulaire ci-dessus. Voir le plus grand diviseur commun polynomial § Identité de Bézout et algorithme GCD étendu pour plus de détails.

Sur les polynômes, les anneaux sur un champ

L'algèbre linéaire est efficace sur un anneau polynomial sur un corps k . Cela a été prouvé pour la première fois en 1926 par Grete Hermann . Les algorithmes issus des résultats d'Hermann n'ont qu'un intérêt historique, car leur complexité de calcul est trop élevée pour permettre un calcul informatique efficace. ${\ displaystyle k [x_ {1}, \ ldots, x_ {n}]}$

Les preuves que l'algèbre linéaire est efficace sur les anneaux polynomiaux et les implémentations informatiques sont actuellement toutes basées sur la théorie de base de Gröbner .

Les références

• David A. Cox; John Little; Donal O'Shea (1997). Idéaux, variétés et algorithmes (deuxième éd.). Springer-Verlag . ISBN   0-387-94680-2 . Zbl   0861.13012 .
• Aschenbrenner, Matthias (2004). "Appartenance idéale aux anneaux polynomiaux sur les entiers" (PDF) . J. Amer. Math. Soc . AMS. 17 (2): 407–441. doi : 10.1090 / S0894-0347-04-00451-5 . S2CID   8176473 . Récupéré le 23 octobre 2013 . CS1 maint: paramètre découragé ( lien )