Aspect algorithmique : application de la méthode du Pivot de Gauss au calcul d'un déterminant

Description de l'algorithmique

Soit \(n\) un entier supérieur ou égal à 2 et \(M\) une matrice appartenant à \(M_n(K)\).

La \(i\)-ième ligne de la matrice \(M\) est notée \(L_i\). Alors on peut noter \(M\) de la façon suivante : \(M=\left(\begin{array}{c}L_1\\L_2\\\ldots\\L_n\end{array}\right)\).

Si la première colonne de M n'est composée que de zéros, son déterminant est nul et c'est fini.

Sinon, \(M=\left(\begin{array}{cccc}m_1&\ast&\ldots&\ast\\m_2&\ast&&\ast\\\vdots&\vdots&&\vdots\\m_n&\ast&\ldots&\ast\end{array}\right)\), sa première colonne comporte au moins un élément non nul, donc il existe au moins tel que soit non nul.

  • Si est non nul, on choisit \(i_0=1\),

  • Sinon on se ramène à une matrice dont l'élément de la première ligne première colonne est non nul, en remplaçant la ligne \(L_1\) par \(L_1+L_{i_0}\)et en laissant les autres inchangées.

On obtient la matrice \(M_1=\left(\begin{array}{cccc}b_1&\ast&\ldots&\ast\\b_2&\ast&&\ast\\\vdots&\vdots&&\vdots\\b_n&\ast&\ldots&\ast\end{array}\right)\) avec \(b_1\) non nul.

De plus, les matrices \(M\) et \(M_1\) ont le même déterminant.

On construit la matrice \(M'_1\) en conservant la première ligne de \(M_1\) et en remplaçant successivement, pour tout \(i\) supérieur ou égal à 2, la ligne \(L_i\) par \(L_i-(\frac{b_i}{b_1})L_1\). On obtient alors la matrice \(M'_1=\left(\begin{array}{cccc}b_1&\ast&\ldots&\ast\\0&C_2&&\ast\\\vdots&\vdots&&\vdots\\0&C_n&\ldots&\ast\end{array}\right)\)

La matrice \(M'_1\) a le même déterminant que \(M_1\), donc que \(M\).

Cette première étape a nécessité au plus n opérations de la forme : ajouter à une ligne un multiple d'une autre ligne.

Si la première colonne de la matrice \(\left(\begin{array}{ccc}C_2&\ldots&\ast\\\vdots&&\vdots\\C_n&\ldots&\ast\end{array}\right)\) n'est composée que de zéros, on s'arrête.

En effet son déterminant est nul, donc aussi celui de \(M\) puisque \(\det M=\det M'_1=b_1\left|\begin{array}{cccc}0&\ast&\ldots&\ast\\\vdots&\vdots&&\vdots\\\vdots&\vdots&&\vdots\\0&\ast&\ldots&\ast\end{array}\right|\)

Sinon, on recommence à partir de la matrice \(M'_1=\left(\begin{array}{cccc}b_1&\ast&\ldots&\ast\\0&C_2&&\ast\\\vdots&\vdots&&\vdots\\0&C_n&\ldots&\ast\end{array}\right)\) en considérant la deuxième colonne. Pour une meilleure compréhension, on va expliciter encore cette étape.

Il existe au moins \(i_0\geq2\) tel que \(C_{i_0}\) soit non nul.

  • Si \(c_2\) est non nul, on choisit \(i_0=2\),

  • Sinon on se ramène à une matrice dont l'élément de la deuxième ligne deuxième colonne est non nul, en remplaçant la ligne \(L_2\) par \(L_2+L_{i_0}\) et en laissant les autres inchangées ; on obtient ainsi une matrice \(M_2=\left(\begin{array}{cccc}b_1&\ast&\ldots&\ast\\0&d_2&&\ast\\\vdots&\vdots&&\vdots\\0&d_n&\ldots&\ast\end{array}\right)\), avec \(d_2\) non nul

On construit la matrice \(M'_2\) en conservant les deux premières lignes de \(M_2\) et en remplaçant successivement, pour tout \(i\) supérieur ou égal à 3, la ligne \(L_i\) par \(L_i-(\frac{d_i}{d_2})L_2\).

On obtient alors la matrice :

\(M'_2=\left(\begin{array}{ccccc}b_1&\ast&\ast&\ldots&\ast\\0&d_2&\ast&&\vdots\\\vdots&0&e_3&&\\\vdots&\vdots&\vdots&&\\0&0&e_n&\ldots&\ast\end{array}\right)\)

La matrice \(M'_2\) a le même déterminant que \(M_2\), donc que \(M\) et est telle que \(b_1d_2\neq0\).

On recommence jusqu'à ce que l'on aboutisse à une matrice de l'une des deux formes suivantes :

  • soit une matrice \(M'_k\), de même déterminant que \(M\), de la forme

    \(M'_k=\left(\begin{array}{cccccccc}a_1&\ast&&&&&&\ast\\0&a_2&&&&&&\\\vdots&&\ddots&&&&&\\&&&a_k&&&&\ast\\&&&0&0&\ast&\ldots&\ast\\\vdots&&&&\vdots&\vdots&\ldots&\vdots\\0&\ldots&\ldots&0&0&\ast&&\ast\end{array}\right)\)

    \(a_1a_2\ldots a_k\neq 0\)

  • soit, une matrice de même déterminant que \(M\), de la forme \(\left(\begin{array}{cccc}a_1&\ast&\ldots&\ast\\0&a_2&&\ast\\\vdots&\vdots&\ddots&\vdots\\0&0&\ldots&a_n\end{array}\right)\),

    avec \(a_1a_2\ldots a_n\neq 0\)

Dans les deux cas, l'on s'arrête car on connaît immédiatement la valeur du déterminant de la matrice trouvée : dans le premier cas, c'est 0, dans le second c'est \(a_1a_2\ldots a_n\).

Remarqueà propos du nombre d'opérations nécessaires dans cet algorithme

La description de l'algorithme montre qu'il y a besoin d'au plus \(n+(n-1)+(n-2)+\ldots+1=\frac{n(n+1)}{2}\) opérations de la forme " ajouter à une ligne un multiple d'une autre ligne " et donc que cette méthode nécessite au plus \(n\frac{n(n+1)}{2}+n-1\) multiplications. Le nombre de multiplications croît donc comme \(n\) au cube.

Or le développement par rapport à une ligne ou une colonne en nécessite \(n!\) et la formule explicite \(n(n!)\).

Ceci explique que ce soit cet algorithme qui est utilisé en informatique.

Cependant, il peut " exploser " si les coefficients sont trop gros.