système linéaire homogène à coef dans Z

imi0 · May 2006

coucou les gens

je cherche des références et des idées sur les problemes suivant :

soit A un matrice à coefficient dans Z à p lignes et q colonnes.

on cherche x vecteur 1 colonne, q lignes tel que x est à coefficients dans Z et tel que A*x=0.

deux problemes: 1) trouver de tels x.
2) trouver des solutions de petites normes ( norme l(1)) .
3) avoir des algorithmes.

j'ai réfléchi un peu, il y a un rapport avec les réseaux, je cherche une référence la dessus pour pouvoir mieux comprendre.
merci

kilébo · May 2006

En fait, je n'ai plus l'algorithme exacte en tête mais il ne doit pas être très difficile à retrouvé.

En gros tu choisis un pivot (avec un critère à déterminer mais probablement un élement premier avec tout le monde s'il existe et à affiner sinon). Puis, tu fais un pivot de Gauss évidemment pas en divisant mais en utilisant une formule de Bezout. Pour te ramener à une situation où ton pivot deviens un 1. Et là tu peux mettre des zéros partout ailleurs.

A affiner mais cherche de ce côté là.

Alain Debreil · May 2006

Bonsoir Imi

Ton système étant linéaire (pas de 2ème membre), si $x$ est solution alors $\lambda x$ est encore solution.
Pourquoi alors ne pas résoudre ton système dans $\Q$, puis s'il existe une solution, tu multiplies par le $\mathrm{ppcm}$ des dénominateurs des coordonnées de $x$, pour avoir un vecteur dans $\Z^n$ qui sera solution.

Alain

[Utilisateur supprimé] · May 2006

Pour Alain Breuil. Car cette methode donne en générales des solutions qui sont grandes par rapport aux coefficients du système. L'idée géniale de Thue et Siegel a été de montrer qu'une "petite" solution de ce systeme existe. C'est le lemme de Siegel. L'idée repose sur le principe des tiroirs.

Voir le Duverney pour le cas à coefficients dans $\mathbb Z$, et Waldschmidt (lecture notes in mathematics n°402) pour le cas où les coefficients sont dans un corps de nombres.

Joaopa

Sire-Anno · May 2006

Je recommande vivement un livre écrit par Claude Quitté et Patrice Naudin

<http://www.amazon.fr/exec/obidos/ASIN/2225827036/qid=1147923579/sr=1-2/ref=sr_1_8_2/402-6739177-5292168>

imi0 · May 2006

Merci à tous
J'ai regardé un peu cet après midi à la BU, un livre de Cohen (je me souviens plus du titre). A partir de l'algorithme de Smith ou de la forme normale de Hermite on peut faire des choses... C'est un premier pas.

Sinon, j'ai une nouvelle question, connaissez-vous des applications concrètes ( on part d'un problème concret et on arrive à la résolution d'un tel système linéaire).

Merci
imi

système linéaire homogène à coef dans Z

Réponses

Bonjour!

Catégories

In this Discussion