Algorithme naïf

Pour le calcul on peut toujours s'en tenir à la définition. Voir à ce propos le calcul fait en langage Python et donné en exemple ici. Toutefois, pour une matrice d'ordre n, le nombre des termes de la somme est n!. Le calcul de chaque terme nécessite n-1 multiplications. L'algorithme est donc en n!(n-1) du point de vue des multiplications, ce qui fait qu'en pratique on n'aura guère recours à lui pour des matrices de rang élevé.

Développement suivant une ligne (ou une colonne)

L'algorithme ci-après, de type récursif, est certainement un des plus faciles à mettre en oeuvre pour un calcul manuel avec des matrices de taille modeste. Il est traité ci-dessous dans un exemple python.
Commençons par la notion de 'mineur'.
Dans un déterminant un 'mineur' est obtenu en supprimant un certain nombre de lignes et autant de colonnes du déterminant d'origine. Un mineur d'ordre n-1 s'obtient en supprimant une ligne et une colonne exactement.
Ainsi à tout déterminant D et à tout couple d'indice i,j on peut associer le mineur Di,j d'ordre n-1, obtenu à partir de D en supprimant la i-ième ligne et la j-ième colonne. Soit donc D= |αi,j| un déterminant.
L'appliquette qui suit donne des exemples de calculs de mineurs.
Matrice A
ℤ/5ℤ
Ordre de la matrice carrée A  :
Le résultat suivant est intéressant:
Si i est un indice ligne quelconque
D = Σ (-1)i+jαi,jDi,j
1≤j≤n
Donnons la démonstration pour n=3. Dans le cas général elle n'est pas plus difficile, mais les notations indicées sont assez lourdes et posent un problème essentiellement typographique.
a b c
d e f
g h i
=
a 0 0
d e f
g h i
+
0 b 0
d e f
g h i
+
0 0 c
d e f
g h i
Comme le déterminant est multilinéaire alterné:
a b c
d e f
g h i
=
a 0 0
d e f
g h i
-
b 0 0
e d f
h g i
-
c 0 0
f e d
i h g
Considérons maintenant le déterminant:
a 0 0
d e f
g h i
On s'aperçoit en le développant que tous les termes correspondant à des permutations changeant le premier indice sont nuls. Ce déterminant vaut donc:
a ×
e f
h i
et il en est de même des deux autres:
b ×
d f
g i
et
c ×
e d
h g
La somme des 3 est donc avec nos notations: aD1,1-bD1,2-c(-D1,3)=aD1,1-bD1,2+cD1,3
CQFD dans le cas n=3 donc.
Cette formule s'appelle 'le développement du déterminant suivant la i-ième ligne'.
On a évidemment l'analogue suivant la j-ième colonne.
On privilégiera donc les lignes et les colonnes comportant un maximum de zéros à chaque étape du calcul et de façon récursive.
Du point de vue de l'efficacité, cependant ce n'est guère meilleur que la méthode précédente. le nombre des multiplications reste en O(n!).

Le pivot de Gauss

Supposons que notre matrice A soit de la forme:
a x x . x 0 0 . 0         B    
Alors en développant suivant la première colonne. Det(A)=aDet(B). Le calcul du déterminant de A se résume à un calcul de déterminant d'ordre n-1 et une multiplication.
L'idée de la méthode de Gauss est d'amener la matrice A à une forme telle que celle montrée ici, par des manipulations sur les lignes ne changeant pas la valeur du déterminant (ajout à une ligne d'une combinaison linéaire des autres lignes).
Remarquons tout d'abord que si tous les coefficients de la première colonne sont nuls alors le calcul est terminé, le déterminant est nul. Soit donc le premier indice i tel que le premier coefficient de la ligne i ne soit pas nul, coefficient que nous appelerons le 'pivot'. Quitte à changer le signe du déterminant nous pouvons par permutation des lignes, amener la ligne i en première position. Cela fait, nous soustrayons à chaque ligne i pour i > 1 la ligne αi,11,1L1 où L1 est la première ligne. Notre matrice prend la forme voulue. On peut montrer que cet algorithme est polynomial en n3, ce qui est nettement meilleur que n!.
Voici une appliquette qui montre comment fonctionne l'algorithme, étape par étape. Quand le processus est terminé, vous pouvez constater que le déterminant affiché est le produit des éléments diagonaux.
Réels Rationnels ℤ/5ℤ Complexes
Nombre de lignes     :

Calcul par blocs

Supposons que notre matrice M soit de la forme:
A B 0 C
où A et C sont des matrices carrées sur la diagonale, 0 désignant ici une matrice nulle et B une matrice quelconque. Dans ces conditions:
Det(M)=Det(A)Det(C)
La preuve résulte dans le produit:
A B 0 C = I 0 0 C × A B 0 I
et le théorème sur le déterminant d'un produit.
Cela se généralise récursivement au cas où M est 'triangulaire par blocs'.
Cas particulier: Les matrices triangulaires. Leur déterminant est simplement le produit des coefficients diagonaux.

Exemple avec le corps des rationnels

Voici une appliquette qui vous permet de tester si vous savez calculer un déterminant d'ordre 3.

Numérateur    :
Dénominateur :
Matrice A

Exemple avec les corps ℤ/pℤ

Voici une appliquette qui vous permet de tester si vous savez calculer un déterminant d'ordre 3. Si votre réponse est exacte un message 'Bonne réponse' sera envoyé.

Résultat mod 5 :
Matrice A

Café Python

Voici un programme qui utilise le développement suivant une ligne pour calculer un déterminant de matrice:

Voici un programme qui utilise la méthode de Gauss pour calculer un déterminant de matrice: