Exercice 71

Idée. C'est un algorithme d'Euclide matriciel : multiplier à gauche par $D^{-1}$ ou $G^{-1}$ retranche une ligne à l'autre. La condition $ad - bc = 1$ impose que l'une des lignes domine l'autre, et la somme des coefficients diminue à chaque étape.

On a $D^{-1}M = \begin{pmatrix} a - c & b - d \\ c & d \end{pmatrix}$ et $G^{-1}M = \begin{pmatrix} a & b \\ c - a & d - b \end{pmatrix}$, et ces deux matrices vérifient encore $(a - c)d - (b - d)c = ad - bc = 1$, de même pour la seconde.

Étape clé. Soit $M \in \mathcal{S}$, $M \neq I_{2}$. Montrons que les lignes de $M$ sont comparables coefficient par coefficient. Si l'on avait $a > c$ et $b < d$, alors $ad - bc \geqslant (c + 1)(b + 1) - bc = b + c + 1$ ; l'égalité $ad - bc = 1$ forcerait $b = c = 0$, puis $ad = 1$, soit $M = I_{2}$, exclu. Si l'on avait $a < c$ et $b > d$, alors $ad - bc \leqslant (c - 1)d - (d + 1)c = -c - d < 1$, exclu. Les deux lignes ne sont pas égales, sinon $ad - bc = 0$. Donc exactement l'une des deux matrices $D^{-1}M$, $G^{-1}M$ appartient à $\mathcal{S}$, et la somme de ses coefficients est strictement inférieure à celle de $M$, puisqu'on a retranché une ligne non nulle.

Existence. On répète l'étape clé ; la somme des coefficients, entier naturel, décroît strictement, donc on aboutit à $I_{2}$ en un nombre fini d'étapes, et $M$ est le produit des facteurs $D$ ou $G$ retranchés.

Unicité. Si $M = M_{1}M_{2} \cdots M_{r}$ avec $r \geqslant 1$ et $M_{k} \in \{D, G\}$, la matrice $M_{1}^{-1}M = M_{2} \cdots M_{r}$ est à coefficients entiers naturels : par l'étape clé, $M_{1}$ est imposé. De plus, $M \neq I_{2}$, car multiplier à gauche par $D$ ou $G$ une matrice de $\mathcal{S}$ augmente strictement la somme de ses coefficients. Une récurrence sur la somme des coefficients conclut. $$\boxed{\text{tout } M \in \mathcal{S} \text{ s'écrit de façon unique comme produit de facteurs } D \text{ et } G}$$ Par exemple, $\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} = DG$ et $\begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} = DDG$. La suite des facteurs code le développement en fraction continue de $\frac{a}{c}$, ce que l'on pourra relier à l'algorithme d'Euclide du chapitre 12.