\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[francais]{babel}
\usepackage{xspace}
\newcommand{\bs}{\symbol{92}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newtheorem{theorem}{Theorem}
\newtheorem{defn}{Definition}

\begin{document}

\title{Alg\`ebre lin\'eaire sur les entiers}
\author{Préparation agrégation, option C}
\date{Révision du 02/06}

\maketitle

On examine dans ce texte quelques exemples d'algorithmes
d'alg\`ebre lin\'eaire sur les entiers, d'une part pour obtenir
des formes normales de matrice avec des matrices de passage
inversibles dans $\Z$, d'autre part pour obtenir des algorithmes
efficaces.

\section{Forme normale de Hermite et de Smith, applications}
Soit $A$ une matrice \`a coefficients entiers. On va adapter l'algorithme du
r\'eduction dit du pivot de Gauss pour d'une part rester dans $\Z$
et d'autre part effectuer des manipulations ``r\'eversibles'' dans
$\Z$ (ce qui revient \`a dire que les matrices de passage sont
inversibles dans $\Z$).
Supposons que nous souhaitions r\'eduire une colonne $j$ \`a partir
de la ligne $i$, on commence par chercher un pivot $b=A_{i'j}$ non nul,
on \'echange les lignes $i$ et $i'$. La m\'ethode de Gauss 
cr\'ee alors des z\'eros par la manipulation 
$L_k \leftarrow L_k - A_{kj}/b L_i$, op\'eration qui sort de
$\Z$. On peut toutefois adapter cette m\'ethode, soit $a=A_{kj}$, 
on applique l'identit\'e de B\'ezout~:
\[ u a + v b = d = gcd(a,b) \]
on effectue alors simultan\'ement les 2 op\'erations de lignes
\[ 
L_i \leftarrow v*L_i + u*L_k, \quad L_k \leftarrow (-a * L_i + b * L_k)/d
\]
On montre facilement que cette op\'eration correspond \`a
l'\'ecriture de $A=P A'$ avec $P \in SL(\Z)$ et $A'$ a alors un z\'ero
en ligne $k$ colonne $j$, en effectuant l'algorithme de r\'eduction
de Gauss sous-diagonal, on parvient ainsi \`a \'ecrire $A$ comme
produit d'une matrice de $GL(\Z)$ par une matrice triangulaire
sup\'erieure de rang maximal. C'est la forme normale de Hermite de
$A$.

Lorsqu'on s'autorise aussi \`a effectuer des op\'erations
\'el\'ementaires sur les colonnes, on peut \'ecrire la matrice $A$
sous la forme $PBQ$ o\`u $P$ et $Q$ sont inversibles dans $\Z$
et $B$ est une matrice diagonale, on peut m\^eme (quitte \`a
\'echanger des lignes/colonnes et re-r\'eduire) faire en sorte
que les coefficients diagonaux se divisent ($b_{i,i}$ divise
$b_{i+1,i+1}$). C'est la forme normale de Smith.

La forme normale de Hermite permet en particulier de calculer une
$\Z$-base du noyau de $A$ (op\'eration qui est non triviale m\^eme \`a
partir d'une base dans $\Q$ du noyau de $A$).
La forme normale de Smith permet de calculer les diviseurs
\'el\'ementaires d'un groupe ab\'elien de type fini (ce sont
les coefficients diagonaux d'une forme normale de Smith).

\section{Algorithmes efficaces}
\subsection{L'algorithme de Gauss-Bareiss}
Pour cr\'eer un z\'ero en restant dans $\Z$,
au lieu d'effectuer la manipulation $L_k \leftarrow L_k - A_{kj}/b L_i$, 
on pense d'abord \`a effectuer  $L_k \leftarrow bL_k - A_{kj}
L_i$. Mais cette op\'eration va faire apparaitre des entiers
qui sont de taille plus grande que la taille n\'ecessaire \`a la
r\'eduction dans $\Z$. On peut alors penser \`a diviser chaque
ligne par le pgcd des coefficients de la ligne pour optimiser la
taille des entiers utilis\'es. Mais cette op\'erations n'est pas
optimale en temps. Il existe un moyen terme (qui se g\'en\'eralise
par exemple aux polyn\^omes) entre ces deux m\'ethodes qui
consiste \`a diviser par un coefficient calcul\'e \`a priori (dont
on sait \`a l'avance qu'il divise tous les coefficients). On montre
ainsi que l'on peut utiliser le pivot de l'\'etape pr\'ec\'edente
(g\'en\'eriquement il s'agit du pivot utilis\'e 
pour r\'eduire la colonne pr\'ec\'edente)
comme diviseur de la ligne $bL_k - A_{kj}L_i$.
On obtient ainsi une croissance lin\'eaire (en la taille de la
matrice) des coefficients des matrices lors de la r\'eduction.

Cet algorithme est bien adapt\'e aux op\'erations telles que calcul
du noyau dans $\Q$, calcul du d\'eterminant dans $\Z$ (on v\'erifie
que le d\'eterminant est le dernier coefficient diagonal de la 
r\'eduction), calcul de l'inverse.

\subsection{M\'ethodes modulaires}
Pour \'eviter les probl\'emes de croissance des coefficients
interm\'ediaires, on peut aussi calculer la quantit\'e souhait\'ee
modulo plusieurs nombres premiers, puis la reconstruire en utilisant
une borne \`a priori, le th\'eor\`eme des restes chinois et 
la repr\'esentation sym\'etrique. Par exemple pour le d\'eterminant,
on peut utiliser la borne de Hadamard et des nombres premiers dont le produit
est sup\'erieur \`a 2 fois la borne.

\subsection{M\'ethodes p-adiques}
Pour les syst\`emes de Cramer \`a coefficients entiers, 
on peut aussi utiliser une m\'ethode $p$-adique asymptotiquement
plus efficace. On calcule d'abord une borne sur les
coefficients des fractions solutions de l'\'equation $Ax=b$
en utilisant les règles de Cramer et la borne d'Hadamard.
On calcule ensuite l'inverse de $A$ modulo $p$ (en changeant de $p$ si
$A$ n'est pas inversible modulo $p$), puis, si
\[ x=\sum_i x_i p^i, \quad A(\sum_{i<k} x_i p^i)=b \pmod{p^k} \]
on ajoute $x_k p^k $ et on obtient l'\'equation~:
\[ Ax_k = \frac{b-\sum_{i <k}  x_i p^i}{p^k} \pmod p \]
qui d\'etermine $x_k$.
On s'arr\^ete lorsque $k$ est suffisamment grand pour pouvoir reconstruire
les fractions \`a l'aide de l'identité de B\'ezout (cf. la section
\ref{sec:rat} infra).
On peut utiliser cette m\'ethode pour r\'eduire sous forme
\'echelonn\'ee des matrices de rang maximal
ayant plus de colonnes que de lignes, on extrait d'abord une
sous-matrice inversible \`a l'aide d'un petit nombre premier, 
et on traduit l'op\'eration de r\'eduction par une suite
de r\'esolution de syst\`emes de Cramer.

On peut aussi calculer efficacement le d\'eterminant d'une matrice $A$ \`a 
coefficients entiers de mani\`ere probabiliste. Pour cela, on r\'esoud
l'\'equation $Ax=b$ pour $b$ vecteur al\'eatoire \`a coefficients
entiers, le d\'enominateur commun $d$ des composantes de $x$ est en
g\'en\'eral le dernier facteur invariant de $A$, en tous cas c'est
toujours un diviseur du d\'eterminant de $A$. On reconstruit alors
det$(A)/d$ par les restes chinois en calculant det$(A)$ modulo 
plusieurs nombres premiers. On peut soit utiliser la borne de Hadamard
et suffisamment de nombres premiers
pour prouver le d\'eterminant, soit s'arr\^eter lorsqu'on a quelques
nombres premiers pour lesquels la reconstruction modulaire n'\'evolue
plus, la valeur du d\'eterminant \'etant alors probable. Pour des
matrices $A$ al\'eatoires, le calcul de $d$
donne un tr\`es gros facteur du d\'eterminant, ce qui permet
de limiter le nombre de nombres premiers \`a utiliser ensuite. La 
complexit\'e asymptotique du calcul du d\'eterminant prouv\'e
est la m\^eme que par une m\'ethode purement modulaire
(cf. \ref{sec:efficace}), mais la
coefficient moyen devant le terme en $n^4$ est beaucoup plus petit.

\subsection{Reconstruction de rationnels} \label{sec:rat}
Soit $n$ et $a/b$ une fraction irr\'eductible d'entiers tels que 
$b$ est premier avec $n$ et $|a| < \sqrt{n}/2$ et $ 0 \leq b \leq \sqrt{n}/2$.
Il s'agit de reconstruire $a$ et $b$ connaissant 
$x=a \times (b^{-1}) \pmod n$ avec $x\in [0,n[$.

{\bf Unicit\'e}\\
S'il existe une solution $(a,b)$ vérifiant $|a| < \sqrt{n}/2$ et 
$ 0 \leq b \leq \sqrt{n}/2$, soit $(a',b')$ une solution
de $x=a \times (b^{-1}) \pmod n$ et 
vérifiant $|a'| < \sqrt{n}$ et $ 0 \leq b' \leq \sqrt{n}$, alors~:
\[ a b'=a' b \pmod n \]
Comme $|ab'| < n/2$, $|a'b| <n/2$, 
on en d\'eduit que $ab'=a'b$. Donc $a/b=a'/b'$
donc $a=a'$ et $b=b'$ car $a/b$ et $a'/b'$ sont suppos\'ees irr\'eductibles.

{\bf Reconstruction lorsqu'on sait qu'il y a une solution}\\
On suit l'algorithme de calcul des coefficients de B\'ezout
pour les entiers $n$ et $x$. On pose~:
\[ \alpha_k n + \beta_k x= r_k \]
o\`u les $r_k$ sont les restes successifs de l'algorithme d'Euclide,
avec la condition initiale~:
\[ \alpha_0=1, \beta_0=0, \alpha_1=0, \beta_1=1, r_0=n, r_1=x \]
et la relation de r\'ecurrence~:
\[ \beta_{k+2}=\beta_k - q_{k+2} \beta_{k+1}, \quad
q_{k+2}=\frac{r_{k}-r_{k+2}}{r_{k+1}}\]

On a $ \beta_k x= r_k \pmod n$ pour tout rang mais il faut v\'erifier
les conditions de taille sur $\beta_k$ et $r_k$ pour trouver le couple
$(a,b)$.
On montre par r\'ecurrence que~:
\begin{equation} \label{eq:rec}
 \beta_{k+1} r_k - r_{k+1} \beta_k = (-1)^k n 
\end{equation}
On v\'erifie aussi que le signe de $\beta_k$ est positif si $k$ est impair
et n\'egatif si $k$ est pair, on d\'eduit donc de (\ref{eq:rec})~:
\[ |\beta_{k+1}| r_k < n \]
(avec \'egalit\'e si $r_{k+1}=0$)

Consid\'erons la taille des restes successifs, il existe un rang $k$
tel que $r_k \geq \sqrt{n}$ et $r_{k+1}<\sqrt{n}$. On a alors
$|\beta_{k+1}|  < n/r_k \leq \sqrt{n}$.

Donc l'algorithme de Bézout permet de reconstruire l'unique couple
solution si on sait par ailleurs qu'il existe.

\subsection{Exemple de r\'esultats d'efficacit\'e} \label{sec:efficace}
On peut montrer que si $A$ est une matrice $n \times n$
et $b$ un vecteur dont les coefficients
entiers sont de taille inf\'erieure \`a $B$, alors la r\'esolution
du syst\`eme $Au=b$ (suppos\'e de Cramer) n\'ecessite au plus
\begin{itemize}
\item $O(n^5 \ln(nB)^2 )$ op\'erations par la m\'ethode de Gauss-Bareiss
\item $O(n^3 (n+\ln(nB)) \ln(nB)) $ op\'erations par une m\'ethode
modulaire (avec restes chinois)
\item $O(n^3 \ln(nB)^2)$ op\'erations par une m\'ethode $p$-adique.
\end{itemize}

\section{Suggestions de d\'eveloppement}
\begin{itemize}
\item Justification de l'un des algorithmes pr\'esent\'es
et illustration sur machine.
\item Application des formes normales de Hermite et Smith.
\item Comparaison entre algorithmes d'alg\`ebre lin\'eaire sur les
entiers. Par exemple Gauss-Bareiss et d\'eterminant modulaire
ou Gauss-Bareiss/m\'ethode $p$-adique pour les syst\`emes de Cramer.
\end{itemize}

\end{document}