A complex Hadamard matrix of order 94

En modifiant une construction fondamentale de Kharaghani et Seberry et en utilisant des matrices circulantes $\{-1,1\}$ d'ordre impair trouvées par ordinateur, les auteurs construisent pour la première fois une matrice de Hadamard complexe d'ordre 94.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire un gratte-ciel parfaitement stable. En mathématiques, ce « gratte-ciel » s'appelle une matrice de Hadamard. C'est une grille de nombres (généralement des +1 et des -1) où chaque ligne est parfaitement perpendiculaire à toutes les autres, comme des poutres d'acier qui ne se touchent jamais, garantissant une structure inébranlable.

Pour construire ces tours, les mathématiciens utilisent des « briques » spéciales. Pendant longtemps, on pensait qu'il existait toujours un type de brique très régulier et symétrique (appelé les matrices de Williamson) pour construire des tours de n'importe quelle taille. Mais il s'est avéré que pour certaines tailles, comme celle de 47 étages, ces briques parfaites n'existent tout simplement pas. C'est comme si on cherchait une clé pour une serrure, mais qu'elle n'existait pas.

Voici comment l'auteur de ce papier, Ferenc Szöllősi, a résolu le problème pour construire une tour de 94 étages (une taille qui était un mystère jusqu'à présent) :

1. Le problème : La serrure sans clé

L'objectif était de construire une tour de 94 étages. La méthode classique consistait à assembler quatre briques symétriques de 47 étages. Mais comme on l'a dit, pour 47, ces briques symétriques n'existent pas. C'était un mur infranchissable.

2. La solution : Un nouveau plan d'architecte

Au lieu d'abandonner, l'auteur a pris un vieux plan de construction (une méthode inventée par Kharaghani et Seberry) et l'a modifié.

• L'ancienne méthode : Demandait quatre briques parfaitement symétriques (comme des miroirs).
• La nouvelle méthode : L'auteur a dit : « Et si on acceptait que seules deux des briques soient symétriques, et qu'on utilise un petit outil spécial pour les deux autres ? »

Cet outil spécial est une opération mathématique appelée « matrice R » (une sorte de retournement ou de miroir inversé). Imaginez que vous avez deux pièces de puzzle qui sont des miroirs parfaits, et deux autres qui sont un peu tordues. Au lieu de rejeter les pièces tordues, l'auteur les a retournées et combinées avec les pièces droites d'une manière très astucieuse pour créer une nouvelle structure qui, une fois assemblée, devient parfaitement stable.

3. La chasse au trésor : L'ordinateur comme détective

Le nouveau plan exigeait de trouver quatre « briques » (des matrices circulantes) de taille 47 qui obéissent à des règles très strictes.

• Le défi : Il y a des milliards de combinaisons possibles de +1 et de -1. Chercher la bonne combinaison à la main, c'est comme essayer de trouver une aiguille dans une botte de foin... mais la botte de foin est aussi grande que l'univers.
• L'outil : L'auteur a écrit un programme informatique (un algorithme de recherche) qui a agi comme un détective ultra-rapide.
  • Il a d'abord éliminé les combinaisons impossibles (comme un trieur qui jette les fausses clés).
  • Il a utilisé une « empreinte digitale » mathématique (un hachage) pour regrouper les briques prometteuses.
  • Il a fait tourner des milliards de tests sur un ordinateur puissant pendant plus d'une journée.

4. La découverte

Après avoir épluché des milliards de possibilités, l'ordinateur a trouvé deux ensembles de briques qui fonctionnaient !

• Ces briques n'étaient pas toutes symétriques (ce qui était le problème), mais elles respectaient la nouvelle règle de l'auteur : deux étaient symétriques, et les deux autres, une fois « retournées » par l'outil spécial, s'emboîtaient parfaitement.
• En assemblant ces briques selon le nouveau plan (le théorème 4 du papier), l'auteur a réussi à construire pour la première fois dans l'histoire une matrice de Hadamard complexe de taille 94.

En résumé

Ce papier raconte l'histoire d'un mathématicien qui, face à un mur (l'impossibilité de trouver des briques parfaites pour la taille 47), n'a pas abandonné. Il a :

1. Réinventé la méthode de construction en acceptant des briques imparfaites mais en les manipulant intelligemment.
2. Utilisé la puissance brute de l'ordinateur pour fouiller dans un océan de possibilités.
3. Trouvé la combinaison gagnante qui permet de construire un édifice mathématique de 94 étages, résolvant un problème qui restait ouvert depuis longtemps.

C'est une victoire de la créativité (changer les règles du jeu) couplée à la technologie (la recherche informatique).

Résumé technique

Voici un résumé technique détaillé de l'article « A COMPLEX HADAMARD MATRIX OF ORDER 94 » de Ferenc Szöllősi, rédigé en français.

1. Problématique et Contexte

L'article s'attaque à un problème fondamental en théorie des matrices : la construction de matrices de Hadamard complexes d'ordre spécifique.

• Définition : Une matrice de Hadamard réelle d'ordre $n$ est une matrice carrée à coefficients $\{-1, 1\}$ telle que $HH^T = nI_n$. Une matrice de Hadamard complexe est une matrice à coefficients $\{-1, -i, 1, i\}$ dont les lignes sont orthogonales deux à deux (i.e., $HH^* = nI_n$).
• Le défi : Bien que les matrices de Hadamard réelles soient bien étudiées, leur existence pour certains ordres reste un problème ouvert. Une méthode classique, celle de Williamson, permet de construire une matrice réelle d'ordre $4p$à partir de quatre matrices circulaires symétriques${-1, 1}$d'ordre$p$satisfaisant une condition d'orthogonalité spécifique. Cependant, il a été démontré que de telles matrices de Williamson n'existent pas pour certains ordres, notamment$p=35$et **$p=47$**.
• L'objectif : L'auteur vise à construire une matrice de Hadamard complexe d'ordre 94 (soit $2p$avec$p=47$). Avant ce travail, l'existence d'une telle matrice pour$p=47$était inconnue, bien que des matrices complexes aient été trouvées pour$p=35$ (ordre 70).

2. Méthodologie

L'auteur propose une approche en deux temps : une modification théorique d'une construction existante et une recherche assistée par ordinateur pour trouver les blocs manquants.

A. Modification de la construction de Kharaghani et Seberry

L'article modifie une construction fondamentale de Kharaghani et Seberry (qui utilisait des matrices de Williamson pour créer des matrices complexes d'ordre $2p$).

• Limitation de l'approche précédente : La méthode originale exigeait que les quatre matrices circulaires soient symétriques. Or, pour $p=47$, de telles matrices n'existent pas.
• Nouvelle construction (Théorème 4) : Szöllősi introduit une variante de l'array de Goethels-Seidel. Il montre qu'il est possible de construire une matrice de Hadamard complexe d'ordre $2p$à partir de quatre matrices circulaires${-1, 1}$d'ordre$p$ satisfaisant la condition d'orthogonalité standard, à la seule condition que deux d'entre elles soient symétriques (les deux autres n'ont pas besoin d'être symétriques).
• Rôle de la matrice $R$ : La construction intègre la matrice $R$ (matrice anti-diagonale) pour transformer les blocs non symétriques en blocs compatibles avec l'orthogonalité complexe, en exploitant les propriétés de commutation des matrices circulaires.

B. Recherche assistée par ordinateur (Algorithme)

Pour $p=47$, l'auteur a dû trouver explicitement quatre matrices circulaires $\{-1, 1\}$ (deux symétriques, deux quelconques) satisfaisant l'équation fondamentale :
$$AA^T + BB^T + CC^T + DD^T = 4pI_p$$

• Contraintes : Les matrices doivent avoir un type de symétrie spécifique (ssxx) (deux symétriques, deux quelconques).
• Algorithme de recherche :
  1. Filtrage par sommes de lignes : Utilisation du lemme de la somme des carrés des sommes de lignes ($\sigma_A^2 + \sigma_B^2 + \sigma_C^2 + \sigma_D^2 = 4p$) pour restreindre l'espace de recherche.
  2. Bornes spectrales : Application de bornes sur les valeurs propres (Lemme 5) pour éliminer rapidement les vecteurs candidats non valides.
  3. Hachage des autocorrélations : L'algorithme calcule les vecteurs d'autocorrélation périodique $I(a)$. Il génère des paires de matrices symétriques $(A, B)$, calcule la somme de leurs autocorrélations, et stocke le résultat dans une table de hachage basée sur une fonction $h$ utilisant des nombres premiers.
  4. Recherche de complément : Il génère ensuite des matrices aléatoires $(C, D)$, calcule l'autocorrélation négative requise, et vérifie si cette valeur existe dans la table pré-calculée.
• Ressources : La recherche a été menée en C++ sur une machine mono-thread, utilisant environ 20 Go de mémoire et nécessitant environ $8 \times 10^9$ essais sur une période d'un jour.

3. Résultats Principaux

• Théorème 1 : L'auteur démontre l'existence d'une matrice de Hadamard complexe d'ordre 94.
• Découverte de matrices spécifiques : L'article fournit deux exemples explicites de quadruplets de matrices circulaires d'ordre 47 (de type symétrique (ssxx)) satisfaisant les conditions requises.
  • Exemple 1 : Sommes de lignes $\sigma_A=3, \sigma_B=7, \sigma_C=7, \sigma_D=9$.
  • Exemple 2 : Sommes de lignes $\sigma_A=-1, \sigma_B=-5, \sigma_C=9, \sigma_D=9$.
• Preuve constructive : La combinaison des matrices trouvées dans l'Exemple 1 avec la construction du Théorème 4 constitue une preuve constructive de l'existence de la matrice d'ordre 94.

4. Contributions Clés

1. Généralisation théorique : La modification de la construction de Kharaghani-Seberry pour ne requérir que deux matrices symétriques au lieu de quatre élargit considérablement la classe de matrices utilisables pour générer des matrices de Hadamard complexes.
2. Résolution d'un cas ouvert : C'est la première fois qu'une matrice de Hadamard complexe d'ordre 94 est construite, résolvant un problème qui restait ouvert malgré les progrès sur les ordres inférieurs.
3. Méthodologie de recherche : L'article présente une implémentation efficace d'un algorithme de recherche par hachage d'autocorrélations, capable de naviguer dans un espace de recherche combinatoire massif pour des ordres premiers comme 47.

5. Signification et Perspectives

• Avancée dans la classification : Ce résultat comble un vide dans la classification des matrices de Hadamard complexes. À ce jour, toutes les matrices complexes sont connues jusqu'à l'ordre 18 ; l'ordre 94 est un saut significatif.
• Implications pour les ordres supérieurs : L'auteur suggère que l'ordre suivant non résolu est probablement $p=59$ (ordre 118).
• Futur de la recherche : Le papier ouvre la voie à deux axes de développement :
  1. Modifier davantage l'array pour n'exiger qu'une seule matrice symétrique (permettant d'utiliser d'autres types de matrices trouvées dans la littérature).
  2. Utiliser des ressources de calcul haute performance (supercalculateurs) et des algorithmes plus sophistiqués pour repousser les limites au-delà de $p=47$.

En résumé, cet article combine une innovation théorique élégante (relâchement des conditions de symétrie) avec une puissance de calcul brute pour résoudre un problème de construction de matrices qui résistait aux approches classiques.