3.8 Élimination de Gauss-Jordan

À la section précédente, nous avons vu comment caractériser les solutions de \(\mathbf{A}\mathbf{x} = \mathbf{b}\) si \(\mathbf{A}\) est sous FER. En transformant un système général d’équations linéaires en un système équivalent ayant la FER, le problème est résolu. L’élimination de Gauss-Jordan est un algorithme de transformation menant à un système équivalent d’équations linéaires \(\mathbf{R} \mathbf{x} = \mathbf{d}\), où \(\mathbf{R}\) est sous FER, qui n’utilise que des opérations élémentaires sur les lignes. En langage courant, on dit que la transformation d’une matrice en FER est une réduction.

Rappelons les trois types d’opérations élémentaires permises:

1. \(L_i \leftarrow \alpha L_i\) (on remplace la \(i\)-ième ligne par le produit de la \(i\)-ième ligne par \(\alpha\), où \(\alpha \neq 0\))

2. \(L_i \leftarrow L_i + \alpha L_j\) (on remplace la \(i\)-ième ligne par la somme de la \(i\)-ième ligne et du produit de la \(j\)-ième ligne par \(\alpha\), où \(\alpha \neq 0\) et \(i \neq j\))

3. \(L_i \leftrightarrow L_j\) (on échange ligne \(i\) et ligne \(j\), où \(i \neq j\)).

Soit \(\mathbf{A} = \begin{bmatrix} 1 & -1 & 2 & 1\\ 2 & -2 & 0 & 2 \\ -1 & 3 & 0 & 1 \end{bmatrix}\), \(\mathbf{x} = \begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix}\), et \(\mathbf{b} = \begin{bmatrix} 3\\ 1\\ 1\end{bmatrix}\).

La matrice augmentée associée au système \(\mathbf{A}\mathbf{x} = \mathbf{b}\) est \(\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 2 & -2 & 0 & 2 & 1\\ -1 & 3 & 0 & 1 & 1 \end{array}\right].\) Nous la transformons maintenant en matrice sous FER en utilisant les opérations élémentaires sur les lignes.

L’élément de la première ligne se retrouvant dans la première colonne est le pivot de cette ligne. Nous devons donc nous assurer que tout les éléments sous ce pivot soient nuls en utilisant les opérations élémentaires sur les lignes. Ceci peut être accomplit en appliquant \(L_2 \leftarrow L_2 + (-2)\times L_1\) et \(L_3 \leftarrow L_3 + L_1\). La matrice résultante est \[\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 0 & -4 & 0 & -5\\ 0 & 2 & 2 & 2 & 4 \end{array}\right].\]

Notons que l’élément non nul le plus à gauche des deuxième et troisième lignes sont distincts de \(1\). Nous pouvons obtenir les valeurs requises en appliquant \(L_2 \leftarrow -\frac{1}{4} L_2\) et \(L_3 \leftarrow \frac{1}{2} L_3\). La matrice résultante est \[\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 0 & \frac{5}{4}\\ 0 & 1 & 1 & 1 & 2 \end{array}\right].\]

Le pivot de la troisième ligne se retrouve à la gauche de celui de la seconde ligne. Nous échangerons alors les deux lignes en appliquant \(L_2 \leftrightarrow L_3\) afin d’obtenir \[\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 0 & \frac{5}{4} \end{array}\right].\]

On transforme l’élément au-dessus du pivot de la deuxième ligne en appliquant \(L_1 \leftarrow L_1 + L_2\) afin d’obtenir \[\left[\begin{array}{cccc|c} 1 & 0 & 3 & 2 & 5 \\ 0 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 0 & \frac{5}{4} \end{array}\right].\]

Il ne reste qu’à transformer les éléments au-dessus du pivot de la troisième ligne en appliquant \(L_1 \leftarrow L_1 + (-3)\times L_3\) et \(L_2 \leftarrow L_2 + (-1)\times L_3\) afin d’obtenir \[\left[\begin{array}{cccc|c} 1 & 0 & 0 & 2 & \frac{5}{4} \\ 0 & 1 & 0 & 1 & \frac{3}{4} \\ 0 & 0 & 1 & 0 & \frac{5}{4} \end{array}\right].\] Cette matrice est sous FER. Les variables correspondantes aux trois premières colonnes sont des variables pivots. Une des solutions de \(\mathbf{A}\mathbf{x} = \mathbf{b}\) est alors donnée par \(\mathbf{x} = \begin{bmatrix} 5/4 \\ 3/4 \\ 5/4 \\ 0\end{bmatrix}\). On obtient toutes les solutions en posant \(x_4 = s\) (la seule variable libre) et en résolvant ensuite pour les variables pivots \(x_1,x_2,x_3\) en terme du paramètre \(s\). Les solutions prennent alors la forme \(\mathbf{x} = \begin{bmatrix} \frac{5}{4} - 2s\\ \frac{3}{4} - s \\ \frac{5}{4} \\ s\end{bmatrix}\), pour \(s \in \mathbb{R}\).

Remarque: La FER d’une matrice est unique. Indépendamment de la séquence des opérations élémentaires utilisées, le résultat final est toujours le même.

3.8.1 Pseudo-code

II est possible de codifier la procédure. Voici le pseudo-code pour l’implémentation de la réduction d’une matrice \(\mathbf{A}\) de dimension \(m \times n\) :

• poser \(p = 1\)

• pour \(k = 1,\ldots, n\), alors

  • s’il existe \(i \in \{p,\ldots,m\}\) tel que \(a_{ik} \neq 0,\) alors

    • si \(i \neq p\), échanger la \(p\)-ième ligne et la \(i\)-ième ligne
    • appliquer \(L_p \leftarrow \alpha^{-1} L_p\), où \(\alpha\) est l’élément de la colonne \(k\) de la ligne \(p\)
    • appliquer \(L_q \leftarrow L_q - \alpha_{q}L_R\) pour tout \(q \neq p\), où \(\alpha_q\) est l’élément de la colonne \(k\) de la \(q\)-ième ligne
    • \(p = p+1\)
    • arrêter lorsque \(p > m\)

Exercices

1. Transformer chacune des matrices suivantes en FER en utilisant les opérations élémentaires sur les lignes.

   1. \(\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix}\)

   2. \(\begin{bmatrix} 0 & 2 & 2 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 1 & 2 & 1 \end{bmatrix}\)

2. Déterminez tous les nombres réels \(x, y, z\) satisfaisant au système d’équations linéaires \[\begin{align*} 3 x - 2y - z & = 1 \\ 2z + x - y & = 5 \end{align*}\]

3. Soit \(\mathbf{A}\in \mathbb{K}^{m\times n}\), \(\mathbb{K}\) un corps. Démontrez l’unicité de la FER de \(\mathbf{A}\).

Solutions

1. 1. Notons que \[\begin{align*} & \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix} \\ \xrightarrow{L_1 \leftrightarrow L_3}~ & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{bmatrix} \\ \xrightarrow{L_2 \leftrightarrow L_3}~& \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \\ \end{align*}\]

   2. Notons que \[\begin{eqnarray*} & \begin{bmatrix} 0 & 2 & 2 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 1 & 2 & 1 \end{bmatrix} \\ \xrightarrow{L_1 \leftrightarrow L_3}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & -1 & 0 & 1 \\0 & 2 & 2 & 0 \end{bmatrix} \\ \xrightarrow{L_2 \leftarrow L_2 + L_1}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 \\0 & 2 & 2 & 0 \end{bmatrix} \\ \xrightarrow{L_3 \leftarrow L_3 - 2L_1}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 \\0 & 0 & -2 & -2 \end{bmatrix} \\ \xrightarrow{L_3 \leftarrow L_3 + L_2}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 \\0 & 0 & 0 & 0 \end{bmatrix} \\ \xrightarrow{L_2 \leftarrow \frac{1}{2}L_2}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 1 \\0 & 0 & 0 & 0 \end{bmatrix} \\ \xrightarrow{L_1 \leftarrow L_1 -2 L_2}~& \begin{bmatrix} 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \\0 & 0 & 0 & 0 \end{bmatrix} \\ \end{eqnarray*}\]

2. Ce système peut s’écrire sous la forme \(\begin{bmatrix} 3 & -2 & -1 \\ 1 & -1 & 2 \end{bmatrix} \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} 1\\ 5 \end{bmatrix}.\) (Faites attention. Les variables de la deuxième équation sont données de façon désordonnée dans la question.) La matrice augmentée du système est \[\left[\begin{array}{rrr|r} 3 & -2 & -1 & 1\\ 1 & -1 & 2 & 5 \end{array}.\right]\]

   L’application de \(L_1 \leftrightarrow L_2\) donne \[\left[\begin{array}{rrr|r} 1 & -1 & 2 & 5 \\ 3 & -2 & -1 & 1 \end{array}\right].\]

   L’application de \(L_2 \leftarrow L_2 - 3 L_1\) donne \[\left[\begin{array}{rrr|r} 1 & -1 & 2 & 5 \\ 0 & 1 & -7 & -14 \end{array}\right].\]

   L’application de \(L_1 \leftarrow L_1 + L_2\) donne \[\left[\begin{array}{rrr|r} 1 & 0 & -5 & -9 \\ 0 & 1 & -7 & -14 \end{array}\right].\]

   Ainsi, \(z\) est la seule variable libre. En prenant \(z = s\), la deuxième ligne devient \(y - 7s = -14\) et la première ligne devient \(x - 5s = -9\). Donc, les solutions sont \(\begin{bmatrix} x\\y\\z \end{bmatrix} = \begin{bmatrix} -9 + 5s \\ -14 + 7s \\ s\end{bmatrix}\) pour \(s \in \mathbb{R}\).

3. Ce résultat signifie que l’on peut parler de la forme échelonnée réduite de \(\mathbf{A}\).

   Supposons que \(\mathbf{A}\) puisse être transformée en deux matrices en FER \(\mathbf{B}\) et \(\mathbf{C}\) en appliquant différentes suites d’opérations élémentaires sur les lignes. Nous voulons montrer que \(\mathbf{B} = \mathbf{C}\).

   Premièrement, notons que les systèmes \(\mathbf{B}\mathbf{x} = \mathbf{0}\) et \(\mathbf{C}\mathbf{x} = \mathbf{0}\) doivent avoir les mêmes solutions que \(\mathbf{A}\mathbf{x} = \mathbf{0}\).

   Soit \(i\) le plus petit indice tel que \(\mathbf{B}\) et \(\mathbf{C}\) diffèrent à la \(i\)-ième colonne. Parce que \(\mathbf{B}\) et \(\mathbf{C}\) sont en FER, \(\mathbf{B}_i\) (colonne \(i\) de \(\mathbf{B}\)) et \(\mathbf{C}_i\) ne peuvent être tous les deux des colonnes pivots. Sans perte de généralité, on suppose que \(\mathbf{C}_i\) n’est pas une colonne pivot. Donc, \(x_i\) est une variable libre pour \(\mathbf{C}\mathbf{x} = \mathbf{0}\). En résolvant pour \(\mathbf{x}\) dans \(\mathbf{C}\mathbf{x} = \mathbf{0}\) (après avoir fixé \(x_i = 1\)) et toutes les autres variables libres par \(0\), on obtient une solution \(\mathbf{x}'\) telle que \(x'_i = 1\) et \(x'_j = 0\) pour tout \(j > i\). Puisque \(\mathbf{C}\mathbf{x}' = \mathbf{0}\) et \(\mathbf{B}_j = \mathbf{C}_j\) pour \(j = 1,\ldots,i-1\), on obtient \[\begin{align*} \mathbf{B}\mathbf{x}' & = \mathbf{B}\mathbf{x}' - \mathbf{C}\mathbf{x}' \\ & = \sum_{j=1}^n \mathbf{B}_jx'_j-\sum_{j=1}^n \mathbf{C}_jx'_j \\ & = \sum_{j=1}^n (\mathbf{B}_j-\mathbf{C}_j)x'_j \\ & = \sum_{j=1}^i (\mathbf{B}_j-\mathbf{C}_j)x'_j \\ & = (\mathbf{B}_i - \mathbf{C}_i)x'_i \\ & = \mathbf{B}_i - \mathbf{C}_i \neq \mathbf{0}. \end{align*}\] Ainsi, \(\mathbf{x}'\) n’est pas une solution de \(\mathbf{B}\mathbf{x} = \mathbf{0}\), ce qui contredit que \(\mathbf{B}\mathbf{x} = \mathbf{0}\) et \(\mathbf{C}\mathbf{x} = \mathbf{0}\) ont les mêmes solutions.