Déterminant maximal d'une matrice carrée
d'éléments entiers 1, 2, ..., n²

Problème

La suite A085000 de N. Sloane donne les valeurs 1, 10, 412 comme valeurs maximales des déterminants des matrices carrées à n lignes et n colonnes dont les éléments sont les premiers entiers non nuls : 1, 2, 3, 4, ..., n².


Un fil "Déterminant inaccessible" du groupe de discussion fr.sci.maths donne, sans prouver la maximalité, une matrice de déterminant 40800 et au même moment la suite de N. Sloane a été prolongée jusqu'à n=4, toujours sans justification.

En utilisant un programme, cette page permet de montrer que 40800 est bien le maximum.

n =	Matrice	Déterminant D	Programme C
n=1	[1]	D = 1
n=2	3 1 2 4	D = 10
n=3	1 4 8 7 2 6 5 9 3	D = 412	det3.c
n=4	1 8 11 13 9 16 4 6 14 3 5 12 10 7 15 2	D = 40800	det4.c

Le nombre de matrices carrées dont les éléments sont les entiers de 1 à n² est n! = 1×2×3×4× ... ×(n-1)×n.
1! = 1, 4! = 24, 3²! = 9! = 362880, 4²! = 16! = 20922789888000.
Lorsque n ne dépasse pas 3, on peut calculer rapidement tous les déterminants à l'aide d'un programme et déterminer ainsi le plus grand.


Lorsque n est égal à 4, on peut se limiter aux déterminants de la forme

1 a b c

d . . .

e . . .

f . . .

tels que 1 < a < b < c, a < d, d < e et d < f.

En effet :

En échangeant deux lignes ou deux colonnes le déterminant change de signe.
Toute matrice (carrée) et sa transposée ont même déterminant.

On peut toujours obtenir une matrice de déterminant maximum satisfaisant les inégalités ci-dessus : il suffit de prencre n'importe quelle matrice de déterminant maximum, de permuter convenablement des lignes ou des colonnes et de la transposer si nécessaire.
(Aucune condition d'ordre n'est donnée sur les deux lignes inférieures de la matrice, on peut les permuter pour obtenir un déterminant positif).

Un programme C vérifie tous les cas possibles et donne la solution 40800. (En moins de 5 heures sur un pentium 800 Mhz).
Une version javascript, plus lente, du même programme peut être lancée ci-dessous.

Liens