Determinant 08/06/2018 18:07

Déterminant, cofacteurs, etc.

Marc Lorenzi - 21 mars 2018

Il est bien connu que l'algorithme de calcul d'un déterminant par un développement selon
une ligne ou une colonne est hautement inefficace, pour ne pas dire inutilisable. Cela
n'empêche, c'est un excellent exercice de programmation. Et puis sait-on jamais ?

NB : le lecteur est invité à l'indulgence à propos des blagues absurdes émaillant ce

notebook.

1. Dark Side of the Determinant

(Roger Waters)

1.1 Introduction

In [1]: import random, sys

compteur = 0

La fonction print_joli affiche beaucoup joli les matrices.

In [2]: def print_joli(A):

for i in range(len(A)):
for j in range(len(A[0])):
sys.stdout.write('%3d' % A[i][j])
sys.stdout.write('\n')

In [3]: print_joli([[1,2,3],[4,5,6],[7,8,9]])

1 2 3
4 5 6
7 8 9

1.2 Mineurs, cofacteurs, comatrice

Étant donnée une matrice A de taille n , le mineur de A ligne i, colonne j est le déterminant
de la matrice extraite de A en rayant sa ligne i et sa colonne j. Les fonctions
supprimer_ligne_colonne et determinant restent évidemment à écrire.

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 1 sur 9

Determinant 08/06/2018 18:07

In [4]: def mineur(A, i, j):

A1 = supprimer_ligne_colonne(A, i, j)
return determinant(A1)

Le cofacteur de A ligne i, colonne j est égal à (−1)i+j fois le mineur correspondant.

In [5]: def cofacteur(A, i, j):

m = mineur(A, i, j)
if i + j % 2 == 0: return m
else: return -m

La comatrice de A est la matrice de ses cofacteurs.

In [6]: def comatrice(A):

n = len(A)
B = [[None for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(n):
B[i][j] = cofacteur(A, i, j)
return B

Enfin, la transcomatrice de A , est la transposée de sa comatrice.

In [7]: def transposee(A):

m = len(A)
n = len(A[0])
B = [[None for i in range(n)] for j in range(m)]
for i in range(n):
for j in range(n):
B[i][j] = A[j][i]
return B

In [8]: def tilde(A):

return transposee(comatrice(A))

Mais ça veut dire quoi, tilde ? Un peu de culture !

Étymol. et Hist. 1834 orth. esp. (Boiste). Mot esp. att. dep. 1433 (E. de Villena ds Cor.-Pasc.),
issu du lat. titulus (titre*) qui signifiait propr. « ce qui désigne, signale ». Cf. a. fr. title, fr. mod.
ti(l)tre « signe abréviatif » (v. titre, étymol. 1 b; FEW t. 13, 1, p. 360a).

Ah, maintenant on comprend mieux. Ou moins.

1.3 Déterminant, enfin

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 2 sur 9

Determinant 08/06/2018 18:07

Le déterminant de A peut être calculé par un développement par rapport à la première ligne,
le cas d'un déterminant vide étant évident. Remarquons que nous allons écrire une fonction
determinant qui se prépare à appeler cofacteur qui appelle mineur qui appelle ...
determinant . Nous avons là un exemple de fonctions mutuellement récursives. Mais
comme ces fonctions s'appellent sur des matrices de tailles strictement décroissantes et que
l'on sait traiter le cas de la matrice "vide", nous sommes assurés de la terminaison de
l'algorithme.

La variable compteur qui apparaît dans le code ci-dessous est une variable globale, qui
compte le nombre d'additions et de multiplications effectuées par l'algorithme. C'est très mal
de faire cela mais c'est pédagogique. Nous aurons ainsi une idée de la complexité du calcul
d'un déterminant par cette mauvaise (?) méthode.

In [9]: def determinant(A):

global compteur
n = len(A)
if n == 0: return 1
else:
s = 0
for j in range(n):
s = s + A[0][j] * cofacteur(A, 0, j)
compteur = compteur + 2 # 1 addition, 1 multiplication !
return s

Il reste à écrire la fonction supprimant une ligne et une colonne de la matrice A . Nous
l'écrivons sans peur mais pas sans reproche. Une petite fonction auxiliaire phi nous évite
d'avoir à considérer 4 cas dans la fonction principale.

In [10]: def phi(p, i):

if p < i: return p
else: return p + 1

In [11]: def supprimer_ligne_colonne(A, i, j):

n = len(A)
rg = range(n - 1)
B = [[None for p in rg] for q in rg]
for p in rg:
for q in rg:
B[p][q] = A[phi(p, i)][phi(q, j)]
return B

Testons.

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 3 sur 9

Determinant 08/06/2018 18:07

In [12]: A = [[1,2,3],[4,5,6],[7,8,8]]
print_joli(A)

1 2 3
4 5 6
7 8 8

In [13]: B = supprimer_ligne_colonne(A, 1, 0)
print_joli(B)

2 3
8 8

In [14]: determinant(A)

Out[14]: 3

In [15]: print_joli(tilde(A))

-8 8 3
10 13 6
-3 6 3

1.4 Matrices "aléatoires"

Pour des tests un peu plus conséquents, définissons une fonction prenant en paramètre un
entier n et renvoyant une matrice n × n dont les coefficients sont des entiers aléatoires entre
−9 et 9 .

In [16]: def random_matrix(n):

rg = range(n)
return [[random.randint(-9, 9) for i in rg] for j in rg]

Pour une matrice 3 × 3 , le calcul du déterminant demande 30 opérations.

In [17]: A = random_matrix(3)
print_joli(A)
compteur = 0
print('Déterminant : ', determinant(A))
print("Nombre d'opérations : ", compteur)

9 5 0
-2 -6 -1
-7 -4 6
Déterminant : -265
Nombre d'opérations : 30

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 4 sur 9

Determinant 08/06/2018 18:07

Et pour une matrice 8 × 8 ?

In [18]: A = random_matrix(8)
print_joli(A)
compteur = 0
print('Déterminant : ', determinant(A))
print("Nombre d'opérations : ", compteur)

-3 0 -1 -4 -8 -1 0 -7
6 -9 1 4 -2 -5 -9 -9
8 8 7 -5 -1 9 -2 1
-3 9 6 -1 2 2 4 -2
7 8 8 -1 5 8 2 2
-1 -2 -1 0 -8 1 -2 -1
0 -5 3 0 -4 2 1 9
-2 4 6 -1 -7 8 -7 9
Déterminant : 8959848
Nombre d'opérations : 219200

Il nous faut 219200 opérations. C'est beaucoup.

2. I am Your Factorial
(Dark Vador)

2.1 Complexité du calcul du déterminant

Faisons un petit calcul. Calculer un déterminant 0 × 0 est immédiat et demande 0 opération.

Pour calculer un déterminant de taille n , il faut calculer n déterminants de taille n − 1 , les
multiplier par des nombres, puis additionner. Appelons Cn le nombre d'opérations
nécessaires au calcul d'un détermant de taille n . Nous avons C0 = 0 et, pour tout entier
n > 0, Cn = nCn−1 + 2n .

In [19]: def C(n):

if n == 0: return 0
else: return n * C(n - 1) + 2 * n

In [20]: print([(k, C(k)) for k in range(10)])

[(0, 0), (1, 2), (2, 8), (3, 30), (4, 128), (5, 650), (6, 3912), (7,
27398), (8, 219200), (9, 1972818)]

On est tout bons, C8 = 219200 . Et Cn , il vaut combien ? Le lecteur consciencieux montrera

n−1 1
par récurrence sur n que Cn = 2n! ∑k=0 k! .

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 5 sur 9

Determinant 08/06/2018 18:07

Juste pour le plaisir d'écrire du Python ....

In [21]: def fact(n):

p = 1
for k in range(1, n + 1): p *= k
return p

In [22]: [fact(n) for n in range(11)]

Out[22]: [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

In [23]: def complexite(n):

p = 2 * fact(n)
s = 0
for k in range(n ):
s = s + 1.0 / fact(k)
return p * s

In [24]: complexite(8)

Out[24]: 219200.0

n−1 1
Il est bien connu (?) que ∑k=0 k! tend vers e lorsque n tend vers l'infini. Ainsi, un équivalent
de la complexité du calcul d'un déterminant de taille n est Cn ∼ 2en!. Cela signifie que le
temps de calcul d'un temps déterminant est Tn ∼ 2Ken! où la constante K dépend
évidemment de l'ordinateur utilisé. Que vaut K pour ma machine ?

2.2 Tests IRL (In Real Life)

(World of Warcraft)

In [25]: %%time
A = random_matrix(8)
print(A)
compteur = 0
print(determinant(A))
print(compteur)

[[-6, 1, -4, -5, 5, 0, 4, 3], [-8, 8, -4, 7, -4, 9, -2, -4], [-9, 8,
0, -2, 0, -4, -4, 2], [-4, 1, 1, -5, 4, -3, -9, 0], [-6, -2, -7, -3,
2, -5, -2, 9], [0, 8, -8, 9, -3, 8, -7, -2], [-7, -2, -8, 6, 8, 9, -
4, 9], [3, 1, -4, 5, -1, -2, 1, -9]]
110369124
219200
CPU times: user 500 ms, sys: 4.14 ms, total: 504 ms
Wall time: 502 ms

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 6 sur 9

Determinant 08/06/2018 18:07

Python me dit que pour calculer un déterminant de taille 8 il lui faut environ 0.5 seconde.
Ainsi, 2ke8! ≃ 0.5 , d'où la valeur de K pour ma machine :

In [26]: K = 0.5 / (2 * fact(8) * 2.71828)

print(K)

2.281000053488539e-06

In [27]: 2 * K * 2.718281828

Out[27]: 1.2400801990129846e-05

Pour calculer un déterminant de taille n , ma machine met environ 1.24 × 10−5 n! secondes.
Voici donc le temps prévisionnel pour un déterminant de taille 9.

In [28]: 1.24e-5 * fact(9)

Out[28]: 4.499712

On essaye ?

In [29]: %%time
A = random_matrix(9)
print(determinant(A))

-51623551
CPU times: user 4.41 s, sys: 3.14 ms, total: 4.42 s
Wall time: 4.42 s

Et pour un déterminant de taille 17 ? Rappelons qu'il y a 86400 secondes dans une journée
et 365 jours par an.

In [30]: 1.24e-5 * fact(17) / 86400 / 365

Out[30]: 139.85680201643834

140 ans. Eh bien non, on ne teste pas :-). Alors tout cela ne sert à rien ? Pas si sûr.

3. I'll Be Back ...

(Arnold Schwarzenegger)

3.1 Calcul formel

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 7 sur 9

Determinant 08/06/2018 18:07

Soit m ∈ ℂ . La matrice A = [[1, 1, 1 − m], [1 + m, −1, 2], [2, −m, 3]] est-elle inversible ?

In [31]: from sympy import *

m = Symbol('m')
init_printing()

In [32]: A = [
[1, 1, 1 - m],
[1 + m, -1, 2],
[2, -m, 3]
]
Matrix(A)
 1 −m + 1 
 
Out[32]: 1
m+1 −1 2 
 2 −m 3 

In [33]: e = determinant(A)
print(e)

-m + (-m + 1)*(-m*(m + 1) + 2) - 2

In [34]: factor(e)

Out[34]: m (m − 2) (m + 2)

La matrice st inversible si et seulement si m est différent de −2, 0, 2 .

Tentons l'exo 4 du TD 20. Et ayons une pensée pour ceux qui n'ont toujours pas installé
Jupyter.

In [35]: alpha, beta, gamma = symbols('alpha beta gamma')

In [36]: A = [
[alpha - beta - gamma, 2 * alpha, 2 * alpha],
[2 * beta, beta - alpha - gamma, 2 * beta],
[2 * gamma, 2 * gamma, gamma - alpha - beta]
]
Matrix(A)
α−β−γ 
 
Out[36]: 2α 2α
 2β −α + β − γ 2β 
 2γ 2γ −α − β + γ 

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 8 sur 9

Determinant 08/06/2018 18:07

In [37]: D = determinant(A)
D

Out[37]: 2α (4βγ − 2β (−α − β + γ)) + 2α (4βγ − 2γ (−α + β − γ)) + (−4βγ + (−α − β + γ) (−α

In [38]: factor(D)

Out[38]: (α + β + γ)3

3.2 Conclusion

Tout n'est pas sombre en Terre du Milieu (Gandalf). Pour des matrices de taille raisonnable
dont certains coefficients contiennent des paramètres, nous pouvons déterminer si oui ou
non ces matrices sont inversibles, grâce à notre algorithme de calcul de déterminant.

http://localhost:8888/notebooks/Documents/Projets/Determinant/Determinant.ipynb Page 9 sur 9