Quelques rappels

Cet article est une suite de La conjecture de Hadamard (I). Nous y avions introduit les matrices de Hadamard de diverses façons, dont celle d’échiquiers anallagmatiques. En voici une définition similaire, où l’échiquier avec des cases bicoloriées est remplacé par un tableau de nombres tous égaux à $1$ ou $-1$. Une matrice de Hadamard d’ordre $n$ est un tableau à $n$ lignes et $n$ colonnes tel que :

• tous ses coefficients valent $1$ ou $-1$,

• pour chaque paire de lignes, il y a autant de concordances que de discordances, c’est-à-dire de colonnes où les coefficients sont égaux que de colonnes où les coefficients sont distincts.

Matrice de Hadamard d’ordre 4

Ces matrices ont été inventées par Sylvester en 1867, qui en a construit de tout ordre une puissance de 2, grâce à son idée de “doublement” [1]. Quelques 26 ans plus tard, Hadamard en a construit d’ordre 12 et 20, et a formulé sa célèbre conjecture :

Malgré plus d’un siècle de recherches intensives et l’invention de nombreuses méthodes de construction, cette question reste largement ouverte de nos jours. Jusqu’à l’ordre 1000, il reste trois cas non-résolus, à savoir 668, 716 et 892. Mais le nombre de cas actuellement non-résolus augmente rapidement au-delà.

Au menu

Dans cette suite, c’est avec un peu plus de détails mathématiques que nous revenons sur divers aspects de cette conjecture.

Nous commencerons par évoquer brièvement la motivation originelle de Hadamard. Ensuite, nous apprendrons les bases de l’arithmétique modulaire et l’appliquerons au problème qui nous occupe. Puis, au-delà de cette première approche, nous utiliserons la notion algébrique de “corps fini” pour construire une matrice de Hadamard d’ordre 28.

Nous évoquerons également certaines tentatives d’obtenir des matrices de Hadamard d’ordre $n$ de façon aussi économique que possible, en ne spécifiant qu’une petite partie seulement du total de ses $n^2$ coefficients.

Par exemple, dans le concept de matrice circulante présenté plus bas, la donnée de la seule première ligne, et donc des $n$ premiers coefficients seulement, suffit pour déterminer toute la matrice. Peut-on espérer trouver beaucoup de matrices de Hadamard circulantes ? Hélas non, une conjecture étonnamment difficile de Ryser postule que cette tentative est vouée à l’échec.

Par contre, une autre construction, dans laquelle $4n$ coefficients sont requis pour déterminer toute la matrice, semble nettement plus prometteuse, comme prédit par la conjecture de Turyn.

Pour finir, nous évoquerons la “conjecture de Hadamard $m$-modulaire”, version plus faible que l’originale, mais sur laquelle on peut espérer faire des progrès plus rapides.

Le déterminant des matrices carrées

C’est Hadamard qui a révélé l’importance fondamentale des matrices portant son nom, en les liant au problème de la maximisation du déterminant. Ce lien est brièvement expliqué ici.

Commençons par quelques préliminaires. Le déterminant des matrices carrées est un vrai joyau mathématique, tant par ses remarquables propriétés que par son utilité et son ubiquité. Il s’agit d’une fonction, à première vue assez compliquée, des coefficients de la matrice considérée, mais satisfaisant des propriétés qui la rendent incontournable. Il sert notamment d’outil pour comprendre les systèmes d’équations linéaires en plusieurs variables.

Pour une matrice $2 \times 2$, la formule est encore simple : si
\[ A = \left( \begin{array}{cc} a_1 & a_2 \\ b_1 &b_2 \end{array} \right), \]
le déterminant de $A$ est donné par la formule : $\det(A) = a_1 \times b_2 -a_2 \times b_1$. Cela se complique un peu en taille $n=3$ : si
\[ A = \left( \begin{array}{ccc} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3, \end{array} \right), \]
alors, en supprimant le symbole $\times$ pour alléger, la formule est donnée par
\[ \det(A) = a_1b_2c_3 + a_2b_3c_1 + a_3b_1c_2 - a_1b_3c_2 - a_2b_1c_3 - a_3b_2c_1. \]
On a une somme analogue de 24 termes pour $n=4$, une somme de 120 termes pour $n=5$, etc. Pour $n$ quelconque, le nombre de termes dans la formule du déterminant est donné par la fonction « $n$ factoriel », c’est-à-dire le produit de tous les entiers de $1$ à $n$ :
\[n!=1\times 2 \times 3 \times \dots \times (n-1) \times n.\]
La formule générale du déterminant ne nous sera pas utile ici, mais on peut la trouver là sur Wikipedia. Parmi bien d’autres choses, on peut y lire que le déterminant d’une matrice carrée $A$ d’ordre $n$ mesure le volume du parallélépipède défini par les colonnes de $A$ dans l’espace euclidien de dimension $n$.

Le théorème de Hadamard

Parmi toutes les matrices carrées d’ordre $n$, considérons celles dont les coefficients sont des nombres réels compris entre $-1$ et $1$. Du fait de cette restriction à des coefficients bornés, il suit que les déterminants de ces matrices sont eux aussi bornés [2]. La motivation de Hadamard était de fournir une bonne estimation explicite d’une telle borne.

Il faut deux clés pour comprendre l’idée derrière ce théorème. La première, c’est le lien évoqué ci-dessus entre déterminant et volume. La seconde, c’est le fait, évoqué plus loin, que les colonnes d’une matrice de Hadamard forment des vecteurs deux à deux orthogonaux dans l’espace euclidien, ce qui maximise le volume du parallélépipède qu’elles définissent. Voilà donc pourquoi les matrices de Hadamard maximisent le déterminant.

On le voit, l’encadrement ci-dessus du déterminant est optimal pour les $n$ qui sont des nombres de Hadamard, c’est-à-dire qui sont l’ordre d’une matrice de Hadamard donnée. La conjecture de Hadamard apparaît donc sous un éclairage nouveau, d’importance fondamentale, de par son lien intime avec le problème de la maximisation du déterminant. Lorsqu’elle sera validée [3], elle fournira automatiquement la valeur maximale du déterminant cherchée ci-dessus, c’est-à-dire $n^{n/2}$, pour tous les ordres $n$ multiples de 4.

Hélas, pour les autres valeurs de $n$, l’encadrement fourni par le théorème de Hadamard n’est pas optimal : on ignore en général la valeur maximale du déterminant sur les matrices concernées. Pour une fonction aussi fondamentale et aussi amplement étudiée et utilisée que l’est le déterminant, cela n’est-il pas surprenant, voire un peu choquant ?

L’arithmétique modulaire

L’arithmétique modulaire joue un rôle important en théorie des nombres et en mathématiques discrètes en général, et en particulier dans les travaux autour de la conjecture qui nous occupe ici. Les trois sections qui suivent ont pour objet d’enseigner les bases de cette arithmétique aussi sympathique qu’utile au lecteur qui ne la connaîtrait pas. En fait, quiconque sait que « 17h » signifie « 5h de l’après-midi » connaît déjà, peut-être à la Monsieur Jourdan, l’arithmétique modulo 12.

L’arithmétique pair/impair

Pour commencer, tout lecteur connaît évidemment l’arithmétique pair/impair. Celle-ci porte sur juste deux objets, à savoir pair et impair. Ceux-ci peuvent être additionnés et multipliés de façon très naturelle, comme les nombres entiers, selon les règles suivantes :
\[ \textit{pair + pair} = \textit{pair},\quad \textit{pair + impair} = \textit{impair},\quad \textit{impair + impair} = \textit{pair}, \]
et
\[ \textit{pair} \times \textit{pair} = \textit{pair},\quad \textit{pair} \times \textit{impair} = \textit{pair},\quad \textit{impair} \times \textit{impair} = \textit{impair}. \]
Notons que cette arithmétique n’a rien d’arbitraire. Bien au contraire, elle est imposée par les propriétés de l’arithmétique ordinaire, comme chacun peut l’observer sur des exemples. En vue de la généraliser à plus d’objets, reprenons ce qu’on vient juste d’expliquer, mais avec des symboles : on écrira $\mathbf{0}$ pour pair et $\mathbf{1}$ pour impair. L’addition et la multiplication sont donc données par
\[ \begin{array}{ccc} \mathbf{0}+\mathbf{0}=\mathbf{0}, & \mathbf{0}+\mathbf{1}=\mathbf{1}, & \mathbf{1}+\mathbf{1}=\mathbf{0},\\ \mathbf{0}\times \mathbf{0}=\mathbf{0}, & \mathbf{0}\times \mathbf{1}=\mathbf{0}, & \mathbf{1}\times \mathbf{1}=\mathbf{1}. \end{array} \]
Bref, l’arithmétique pair/impair, c’est une arithmétique particulièrement simple sur un ensemble à deux éléments. C’est l’arithmétique modulo 2. On peut faire des choses tout à fait analogues avec plus que deux éléments, voyons comment.

L’arithmétique modulo 3

L’arithmétique modulo $3$ n’est guère plus compliquée que celle modulo 2, à cela près qu’elle porte sur trois éléments. On notera ici ces trois éléments par $\mathbf{0}$, $\mathbf{1}$, $\mathbf{2}$, en gras comme ci-dessus, pour bien les distinguer des entiers ordinaires $0$, $1$, $2$.

En fait, par commodité, on introduit un quatrième symbole, noté $\mathbf{3}$, mais on lui impose d’emblée de satisfaire l’égalité $\mathbf{3}=\mathbf{0}$ ! Autrement dit, on reste toujours sur nos trois éléments $\mathbf{0}$, $\mathbf{1}$, $\mathbf{2}$, mais on s’est donné quatre symboles pour les désigner.

Notre guide pour définir une addition et une multiplication naturelles sur ces trois éléments, c’est

• la cohérence : on impose à notre arithmétique grasse de mimer l’arithmétique sur les entiers ordinaires ;

• l’égalité fondamentale $\, \mathbf{3}=\mathbf{0}$.

Tout est dit, tout découle de là, comme on va le voir sur quelques exemples.

• Sur les entiers ordinaires, on a $1+1=2$. La cohérence nous impose donc l’égalité
  $\mathbf{1}+\mathbf{1}=\mathbf{2}$.

• De même, on a $1+2=3$. Ce sont maintenant la cohérence et l’égalité fondamentale qui nous imposent $\mathbf{1}+\mathbf{2}=\mathbf{0}$.

• Et enfin, quel est l’analogue en gras de l’égalité $2+2=4$ ? C’est simple, il suffit de se rappeler que $4$ est égal à $1+3$. Du coup, notre guide nous impose pour résultat $\mathbf{2}+\mathbf{2}=\mathbf{1}$.

Pour la multiplication, on procède exactement comme pour l’addition. Cela donne, par exemple, les égalités

\[ \begin{array}{ccc} \mathbf{0}\times \mathbf{1} & = & \mathbf{0}, \\ \mathbf{1}\times \mathbf{2} & = & \mathbf{2}, \\ \mathbf{2}\times \mathbf{2} & = & \mathbf{1}. \end{array} \]

L’arithmétique $m$-modulaire

Plus généralement, définissons maintenant l’arithmétique modulo $m$, où $m$ est un entier naturel quelconque supérieur à 2. On souhaite ardemment que ces quelques explications suffiront au lecteur pour apprendre à calculer modulo $m$.

Eh bien, avec le cas $m=3$ à l’esprit, le cas général ne présente aucune nouvelle difficulté. Considérons donc l’ensemble à $m$ éléments
\[\mathbf{0}, \mathbf{1}, \ldots, \mathbf{m-1}.\]

Comme pour $m=3$, rajoutons le symbole supplémentaire $\mathbf{m}$, auquel on s’empresse d’imposer l’égalité fondamentale
\[ \mathbf{m} = \mathbf{0}. \]
Toujours comme pour $m=3$, on utilise les deux mêmes ingrédients pour définir une arithmétique naturelle sur ces $m$ éléments, à savoir

• la cohérence : l’arithmétique modulo $m$ doit mimer l’arithmétique sur les entiers ordinaires ;

• l’égalité fondamentale $\, \mathbf{m} = \mathbf{0}$.

Et à nouveau, toute l’arithmétique modulo $m$ découle de là.

Pour $m=11$ par exemple, que doit valoir $\mathbf{5}+\mathbf{9}$ en arithmétique 11-modulaire ? Sur les entiers ordinaires, on a $5+9=14$. Or $14$ est égal à $3+11$. Donc, par la cohérence et l’égalité fondamentale, pas d’échappatoire : on a forcément $\mathbf{5}+\mathbf{9}=\mathbf{3}$.

Toujours en arithmétique 11-modulaire, que doit valoir $\mathbf{5} \times \mathbf{9}$ ? Sur les entiers ordinaires, on a $5 \times 9 = 45 = 4 \times 11 +1$. Donc modulo $11$, on aura forcément $\mathbf{5} \times \mathbf{9}= \mathbf{1}$, puisque \[\mathbf{4}\times\mathbf{11}+\mathbf{1} \,=\, \mathbf{4}\times\mathbf{0}+\mathbf{1} \,=\, \mathbf{1}.\]

Une construction d’ordre 12

Montrons maintenant comment l’arithmétique modulaire permet de construire des matrices de Hadamard de certains ordres, bien qu’elle n’ait pas du tout été inventée dans ce but. Ce lien a priori inattendu, découvert par Gilman en 1930, est une manifestation très concrète de l’unité des mathématiques.

Penchons-nous sur un cas spécifique, sur lequel on s’est d’ailleurs déjà exercé : l’arithmétique modulo $m=11$. Sachant que 11 est un nombre premier, ce qu’on va voir maintenant est un cas particulier de la construction générale de Gilman-Paley évoquée dans l’article précédent.

L’étape-clé de la construction, c’est maintenant [4] : elle consiste à déterminer les carrés parfaits non-nuls modulo 11. Pour ce faire, considérons la suite des carrés parfaits dans les entiers naturels, c’est-à-dire des nombres de la forme $n^2$ où $n$ lui-même est un entier naturel. En voici les dix premiers termes :
\[ 1,\, 4,\, 9,\, 16,\, 25,\, 36,\, 49,\, 64,\, 81,\, 100. \]
Maintenant, réduisons ceux-ci modulo 11, en se rappelant que $\mathbf{11}=\mathbf{0}$ en arithmétique 11-modulaire. On obtient
\[ \mathbf{1},\, \mathbf{4},\, \mathbf{9},\, \mathbf{5},\, \mathbf{3},\, \mathbf{3},\, \mathbf{5},\, \mathbf{9},\, \mathbf{4},\, \mathbf{1}. \]

Reprenons notre liste des carrés parfaits non-nuls modulo 11, mais ici ordonnée et avec les doublons supprimés :
\[ \mathbf{1},\, \mathbf{3},\, \mathbf{4},\, \mathbf{5},\, \mathbf{9}. \]

Codons maintenant cette liste par une suite binaire de longueur 10 :

Codage binaire des carrés parfaits non-nuls modulo 11

Ce codage est très simple : on place des cases blanches en position 1, 3, 4, 5, 9, et des cases orange ailleurs. Rajoutons encore une case orange tout à gauche :

Ajout d’une case orange à gauche

On construit maintenant un échiquier $11 \times 11$ en répétant dix fois, sous cette suite, la même suite mais tournée à chaque fois d’un cran supplémentaire vers la droite. Voici le résultat obtenu :

Echiquier circulant d’ordre 11

Pour finir, on rajoute une première ligne et une première colonne de cases blanches. La récompense de tout cela, c’est une matrice de Hadamard d’ordre 12 :

Matrice de Hadamard d’ordre 12 de type Gilman-Paley

Telle est la construction découverte par Gilman en 1930, dont l’idée clé, une fois de plus, est la répartition des carrés parfaits modulo 11. Cette même construction marche plus généralement pour n’importe quel nombre premier $p$ de la forme $p=4k+3$, comme 19, 23, 31, 43, etc. Elle donne alors une matrice de Hadamard d’ordre $p+1$, qui est bien un multiple de 4 puisque $p+1=4k+4$.

Corps finis

Paley a découvert en 1933 une construction similaire lorsque $n$ est un multiple de 4 pour lequel $n-1$ ou $n/2-1$ est une puissance d’un nombre premier, et ce grâce à la notion algébrique de « corps fini ». On vient d’ailleurs d’en voir un exemple : les entiers modulo 11 forment un corps fini à 11 éléments. Mais on en verra un exemple plus compliqué, à 27 éléments, pas du tout lié à l’arithmétique modulo 27.

Informellement, un « corps » en Algèbre est une collection d’éléments qu’on peut additionner et multiplier entre eux comme on le ferait avec des nombres, et qui jouit de la propriété supplémentaire que tout élément non-nul y est inversible [5]. Les exemples les plus connus sont le corps des nombres rationnels et celui des nombres réels. On parle de « corps fini » si le corps considéré n’a qu’un nombre fini d’éléments. A priori, ça ressemble à un beau joujou abstrait pour mathématiciens. C’était peut-être vrai au début du 20ème siècle. Mais de nos jours, la réalité est bien différente : aucun spécialiste en téléphonie ou en cryptographie ne peut se passer de cette notion et des constructions qu’elle permet !

Un beau théorème en Algèbre révèle que le nombre d’éléments dans un corps fini est forcément une puissance $p^r$ d’un nombre premier $p$ ; et que réciproquement, pour tout tel nombre $p^r$, il existe effectivement un corps fini à $p^r$ éléments [6].

Puisqu’on dispose d’une opération de multiplication dans un corps, on y dispose automatiquement de la notion de carré parfait : ce sont les éléments du corps de la forme
\[ x^2 \]
où $x$ est un élément quelconque du corps considéré. Comme pour les entiers modulo 11, c’est la répartition des carrés parfaits dans un corps fini à $k$ éléments qui va permettre de fabriquer une matrice de Hadamard, qui sera d’ordre $k+1$ ou $2(k+1)$ selon que $k+1$ est multiple de 4 ou de 2 seulement.

Cette construction est vraiment de toute beauté, puisque tout en faisant appel à une structure algébrique plutôt abstraite, elle permet de redescendre sur terre en produisant des matrices très concrètes à coefficients $1$ et $-1$ dotées de propriétés très fines. L’abstrait permet de mieux maîtriser le concret !

Un corps d’ordre 27...

A titre d’exemple, construisons un corps fini à 27 éléments, qui nous permettra ensuite de construire une matrice de Hadamard d’ordre 28 via la méthode de Paley.

Voilà l’une des constructions possibles pour ce corps, que l’on notera $\mathbf{F_{27}}$. On prend un symbole $X$. Avec celui-ci, listons déjà les 27 éléments constitutifs de $\mathbf{F_{27}}$ : ce sont tous les polynômes en $X$ de degré au plus $2$ à coefficients entiers modulo $3$. En clair, on prend toutes les expressions de la forme
\[ a_0 + a_1 X + a_2X^2, \]
où les coefficients $a_0, a_1, a_2$ sont des entiers modulo 3, c’est-à-dire pris parmi $\mathbf{0},\, \mathbf{1},\, \mathbf{2}$. Voici les quelques premiers éléments de $\mathbf{F_{27}}$ : \[\mathbf{0},\, \mathbf{1},\, \mathbf{2},\, X,\, \mathbf{1}+X,\, \mathbf{2}+X,\, \mathbf{2}X,\,\mathbf{1}+\mathbf{2}X, \dots.\]

En les listant tous, on trouve bel et bien 27 éléments au total, puisqu’il il y a 3 valeurs possibles pour chacun des 3 coefficients $a_0, a_1, a_2$, et que $3 \times 3 \times 3 =27$.

Il s’agit maintenant de décrire l’addition et la multiplication dans $\mathbf{F_{27}}$. A quelques détails près, on fait comme si c’étaient des polynômes. Pour être tout à fait précis, donnons-nous deux éléments quelconques de $\mathbf{F_{27}}$ :
\[ \begin{array}{l} & a_0 + a_1 X + a_2 X^2, \\ & b_0 + b_1 X + b_2 X^2. \end{array} \]

Définir l’addition de ces deux éléments est très facile, on somme terme à terme, comme pour les polynômes :
\[ (a_0 + a_1 X + a_2 X^2) \,+\, (b_0 + b_1 X + b_2 X^2) \,\, =\,\, (a_0+b_0) + (a_1+b_1) X + (a_2+b_2) X^2. \]

Pour la multiplication, c’est un peu plus délicat. Cela dit, il suffit en fait de spécifier quelle combinaison de $1,\,X,\, X^2$ représente $X^3$. Plusieurs choix sont possibles. Mais en voici un qui marche bien : on définit
\[ X^3 \,=\, \mathbf{2}+X^2. \]

A nouveau tout est dit, toute l’arithmétique dans $\mathbf{F_{27}}$ découle de là. Par exemple, que vaut $X^4$ ? Voici un petit calcul, utilisant les règles ci-dessus, pour obtenir la réponse :
\[ \begin{array}{lll} X^4 & = & X \cdot X^3 \\ & = & X \cdot (\mathbf{2}+X^2) \\ & = & \mathbf{2}X + X^3 \\ & = & \mathbf{2}X + (\mathbf{2}+X^2) \\ & = & \mathbf{2}+\mathbf{2}X + X^2. \end{array} \]
On vient d’identifier $X^4$ au polynôme $\mathbf{2}+\mathbf{2}X+X^2$ dans $\mathbf{F_{27}}$.

... et sa matrice de Hadamard associée

Eh bien, maintenant que nous savons additionner et multiplier dans $\mathbf{F_{27}}$, c’est un jeu d’adulte que de trouver tous ses carrés parfaits non-nuls. Sachant que $z^2 = (-z)^2$, on doit en trouver au plus la moitié de $27-1$, c’est-à-dire $13$. En fait, on trouve exactement 13 carrés parfaits non-nuls dans $\mathbf{F_{27}}$ [7]. Les voici :

\[ \begin{array}{ccccccc} \mathbf{1}, & \mathbf{1}+X, & \mathbf{2}X, & \mathbf{1}+\mathbf{2}X, & X^2, & \mathbf{1}+X+X^2, & \mathbf{2}+X+X^2, \\ & \mathbf{2}X+X^2, & \mathbf{1}+\mathbf{2}X+X^2, & \mathbf{2}+\mathbf{2}X+X^2, & \mathbf{1}+\mathbf{2}X^2, & \mathbf{2}+\mathbf{2}X^2, & \mathbf{2}X+\mathbf{2}X^2. \end{array} \]

Selon la méthode de Gilman-Paley, c’est la répartition de ces 13 éléments dans $\mathbf{F_{27}}$ qui donne la clé de construction de la matrice de Hadamard cherchée. Il nous faut donc trouver leurs positions parmi les 27 éléments de $\mathbf{F_{27}}$. Pour ce faire, appelons
\[ z_0,\, z_1,\, z_2,\, \dots,\, z_{25},\, z_{26} \]
ces 27 éléments, ordonnés lexicographiquement [8] :
\[ \mathbf{0},\, \mathbf{1},\, \mathbf{2},\, X,\, \mathbf{1}+X,\, \mathbf{2}+X,\, \mathbf{2}X,\,\mathbf{1}+\mathbf{2}X,\, \dots,\, \mathbf{2}X+\mathbf{2}X^2,\, \mathbf{1}+\mathbf{2}X+\mathbf{2}X^2,\, \mathbf{2}+\mathbf{2}X+\mathbf{2}X^2. \]
On trouve alors que, dans cet ordre-là, les carrés parfaits non-nuls listés ci-dessus sont exactement les 13 éléments suivants :
\[ z_{1},\, z_{4},\, z_{6},\, z_{7},\, z_{9},\, z_{13},\, z_{14},\, z_{15},\, z_{16},\, z_{17},\, z_{19},\, z_{20},\, z_{24}. \]
L’étape suivante consiste à en déduire une matrice carrée $A$ d’ordre 27 à coefficients $1$ ou $-1$, voici comment. D’abord, on indexe les 27 lignes et les 27 colonnes de $A$ par les 27 éléments $z_0,z_1,\dots, z_{26}$ de $\mathbf{F_{27}}$. Maintenant, à l’intersection de la ligne indexée par $z_i$ et de la colonne indexée par $z_j$ dans $A$, on place un $1$ si l’élément $z_j-z_i$ est un carré parfait non-nul dans $\mathbf{F_{27}}$, un $-1$ sinon. Pour finir, on ajoute à $A$ une ligne et une colonne supplémentaires de $1$.

Voici le résultat, une splendide matrice de Hadamard d’ordre 28, avec les $1$ codés par des cases blanches et les $-1$ par des cases orange :

Matrice de Hadamard d’ordre 28 de type Paley

Le théorème de Jennifer Seberry Wallis

La théorie des nombres étant tellement riche en mystères divers et variés, on pourrait craindre que certains entiers $n$ multiples de 4 auraient des propriétés arithmétiques si exotiques qu’elles empêcheraient l’existence de matrices de Hadamard de cet ordre. Par exemple, pourrait-il exister un nombre premier $p$ si pathologique qu’aucun entier $n$ multiple de $p$ ne puisse être un nombre de Hadamard ? Un tel cas de figure invaliderait la conjecture, et expliquerait a posteriori pourquoi les chercheurs auraient failli pendant si longtemps dans leurs tentatives de la valider.

Fort heureusement, un théorème de Jennifer Seberry Wallis, obtenu en 1976, montre que ces craintes sont largement infondées. Il nous garantit que, pour tout nombre impair $q$, la suite de nombres
\[ 4q,\, 8q,\, 16q,\, 32q,\, 64q,\, 128q,\, etc., \]
contient forcément un nombre de Hadamard.

Autrement dit, pour tout nombre impair $q$, il existe une matrice de Hadamard d’ordre $n=2^t q$ dès que $t$ est assez grand par rapport à $q$.

Sans vouloir trop entrer dans les détails, l’idée de la construction est une sorte d’assemblage très futé, via les matrices de Sylvester d’ordre $2^r$, de quelques matrices toutes simples et de celles de Gilman-Paley liées aux nombres premiers.

Pour démontrer la conjecture de Hadamard, il ne « reste plus » qu’à trouver comment remplacer l’hypothèse « $t$ assez grand » dans l’énoncé ci-dessus par juste « $t \ge 2$ ».

Matrices circulantes

Une matrice circulante est une matrice carrée munie d’une propriété très spéciale : chaque ligne de la matrice, sauf la première, est obtenue à partir de la ligne précédente par une rotation circulaire d’un cran vers la droite. Ainsi donc, la matrice est complètement déterminée par la seule connaissance de sa première ligne. On en a déjà vu un avatar plus haut, sous forme d’échiquier circulant d’ordre 11.

Voici un exemple de matrice circulante d’ordre 4 : prenons pour première ligne
\[ \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \end{array} \right). \]
La 2ème ligne s’obtient en poussant tout d’un cran vers la droite, circulairement parlant :
\[ \left( \begin{array}{cccc} 4 & 1 & 2 & 3 \end{array} \right). \]
Les 3ème et 4ème lignes s’obtiennent de la même façon. En fin de compte, la matrice circulante déterminée par la première ligne est la suivante :
\[ \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{array} \right). \]
Le grand avantage des matrices circulantes est leur économie de spécification : dès qu’on connaît leur première ligne, on les connaît entièrement !

Y a-t-il des matrices de Hadamard circulantes ?

De ce point de vue, ce serait extraordinaire, et pour tout dire inespéré, que la nature ait le bon goût d’héberger plein de matrices de Hadamard circulantes. Car alors, pour en découvrir une d’ordre $n$ si elle existait, il suffirait de savoir répartir astucieusement les $n$ symboles $1$ ou $-1$ de sa première ligne pour obtenir la totalité de ses $n^2$ coefficients.

Hélas, cet espoir un peu naïf est très vite refroidi par l’expérience. On connaît bien une matrice de Hadamard circulante d’ordre 4, par exemple celle-ci :
\[ \left( \begin{array}{cccc} -* 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ 1 & 1 & 1 & -1 \end{array} \right). \]
Mais c’est essentiellement la seule que l’on connaisse ! La conjecture de Ryser, formulée en 1963 et toujours non résolue à ce jour, postule justement que l’ordre maximal des matrices de Hadamard circulantes est... 4.

De beaux travaux, d’abord dûs à Richard Turyn en 1965 puis poursuivis plus tard par d’autres chercheurs, montrent que cette question élémentaire et d’apparence anodine est étroitement liée à la théorie algébrique des nombres. Grâce à ce lien, Turyn a pu montrer que s’il existe une matrice de Hadamard circulante d’ordre $n \ge 4$, alors $n$ doit être de la forme $n=4m^2$ avec $m$ entier impair, c’est-à-dire appartenir à la suite
\[ 4,\, 36,\, 100,\, 196,\, 324,\, 484,\, 676,\, etc. \]
De plus, toujours grâce à ce lien et aux outils sophistiqués qu’il permet de mettre en oeuvre, on sait aujourd’hui établir qu’il n’existe aucune matrice de Hadamard circulante d’ordre $n$ compris entre 36 et un milliard... à la possible exception de $n =4\times 11715^2=548.964.900$, ultime cas ouvert sous cette barre.

Quadruples de Turyn

Toujours dans le même souci d’économie de spécification, celui de chercher des matrices carrées de structure si spéciale qu’il suffit d’en connaître quelques coefficients pour les connaître entièrement, voici une construction fort intéressante : si l’on peut trouver quatre suites de $1,-1$ de longueur $r$ satisfaisant une certaine propriété décrite ci-dessous, alors on peut construire une matrice de Hadamard d’ordre $n=4r$.

La construction se base sur la notion de corrélations d’une suite, notion indispensable en théorie du signal et pour toutes sortes d’applications telles que les radars, la téléphonie, etc. Nous nous restreindrons ici aux corrélations apériodiques.

Corrélations d’une suite

Considérons une suite $X$ de $r$ nombres, disons $X = (x_1,x_2,\dots,x_r)$. Le 1er coefficient de corrélation de $X$, notons-le $c_1(X)$, est défini ainsi :
\[ c_1(X) = x_1x_2+x_2x_3+x_3x_4+\dots+x_{r-1}x_r. \]
Il s’agit donc de la somme des $r-1$ termes de la forme $x_ix_{i+1}$.
Le 2ème coefficient de corrélation de $X$ est défini de façon analogue, en prenant maintenant la somme des $r-2$ termes de la forme $x_ix_{i+2}$ :
\[ c_2(X) = x_1x_3+x_2x_4+x_3x_5+\dots+x_{r-2}x_r. \]
Plus généralement, le $k$ème coefficient de corrélation de $X$ est défini comme la somme des $r-k$ termes possibles de la forme $x_ix_{i+k}$. On peut ainsi aller jusqu’à $k=r-1$, pour lequel il ne reste plus qu’un seul terme :
\[ c_{r-1}(X) = x_1x_r. \]
Voici trois exemples en longueur $r=3$. Pour alléger, écrivons $c_i$ au lieu de $c_i(X)$ dans le tableau ci-dessous.
\[ \begin{array}{|c|r|r|} X & c_1 & c_2 \\ \hline (1,1,1) & 2 & 1\\ \hline (1,-1,1) & -2 & 1\\ \hline (1,1,-1) & 0 & -1\\ \hline \end{array} \]

Des quadruples de Turyn...

On va maintenant chercher quatre suites binaires $X_1,X_2,X_3, X_4$, toutes de même longueur, dont les coefficients de corrélations $c_i$ se compensent mutuellement pour tout $i$.

Plus précisément, appelons quadruple de Turyn un quadruple de suites $X_1,X_2,X_3, X_4$ de longueur $r$, à coefficients $1$ et $-1$, qui vérifie les $r-1$ égalités
\[ c_i(X_1)+c_i(X_2)+c_i(X_3)+c_i(X_4) \,=\, 0 \]
pour tout $i$ allant de 1 à $r-1$.

Par exemple, grâce au petit tableau ci-dessus, on trouve facilement un quadruple de Turyn en longueur $r=3$. En effet, posons
\[ \begin{array}{rcl} S_1 & = & (1,1,1) \\ S_2 & = & (1,-1,1) \\ S_3 & = & (1,1,-1). \end{array} \]
Alors le quadruple $S_1, S_2, S_3, S_3$ est bien un quadruple de Turyn, puisque
\[ \begin{array}{ccc} c_1(S_1)+c_1(S_2)+c_1(S_3)+c_1(S_3) & = & 2-2+0+0 & = & 0,\\ c_2(S_1)+c_2(S_2)+c_2(S_3)+c_2(S_3) & = & 1+1-1-1 & = & 0.\\ \end{array} \]

... aux matrices de Hadamard

Pourquoi cette question est-elle si intéressante ? Eh bien, une splendide construction de Goethals et Seidel vers 1970 permet de fabriquer une matrice de Hadamard d’ordre $4r$ à partir d’un quadruple de Turyn de longueur $r$, et donne donc le résultat suivant.

Juste pour son ingéniosité, et sans commentaire [9], voici la grille de Goethals-Seidel qui permet cette spectaculaire réduction :
\[ \left( \begin{array}{cccc} A & -BR & -CR & -DR \\ BR & A & -D^\top R & C^\top R \\ CR & D^\top R & A & -B^\top R \\ DR & -C^\top R & B^\top R & A \end{array} \right). \]

La conjecture de Turyn postule l’existence d’un quadruple de Turyn de toute longueur $r$. Grâce au théorème ci-dessus, on voit qu’une solution positive de cette conjecture entraînerait automatiquement une solution positive de celle de Hadamard. En fait, il suffirait même de résoudre la conjecture de Turyn pour toute longueur $r$ impaire, grâce au doublement de Sylvester.

Orthogonalité

La notion de matrice de Hadamard peut s’exprimer de façon très succincte en termes d’orthogonalité entre vecteurs. Pour des vecteurs $x=(x_1,x_2,x_3)$ et $y=(y_1,y_2,y_3)$ dans l’espace habituel de dimension 3, dire que $x$ et $y$ sont orthogonaux signifie simplement qu’ils forment un angle droit. Algébriquement, l’orthogonalité entre $x$ et $y$ se traduit de façon très sympathique, par la nullité du produit scalaire entre $x$ et $y$. Autrement dit, $x$ et $y$ sont orthogonaux si et seulement si
\[ x_1y_1 + x_2y_2 + x_3y_3 = 0. \]

Fort heureusement, cette condition algébrique est valable en toute dimension ! A nouveau, deux vecteurs $x=(x_1,x_2, \dots, x_n)$ et $y=(y_1,y_2, \dots, y_n)$ dans l’espace euclidien de dimension $n$ sont orthogonaux si et seulement si leur produit scalaire est nul, c’est-à-dire si et seulement si
\[ x_1y_1 + x_2y_2 + \dots + x_ny_n = 0. \]
Voici le lien promis entre orthogonalité et matrices de Hadamard. Considérons une matrice carrée $A$ d’ordre $n$, dont tous les coefficients valent $1$ ou $-1$. Alors $A$ est une matrice de Hadamard si et seulement si ses $n$ lignes, vues comme vecteurs dans l’espace euclidien de dimension $n$, sont orthogonales deux à deux. Cela avait déjà été évoqué dans La conjecture de Hadamard (I).

Cette traduction en termes de nullité des produits scalaires des lignes nous sera utile dès à présent, pour évoquer une version affaiblie de la conjecture de Hadamard.

La conjecture de Hadamard $m$-modulaire

Que faire lorsque l’on est confronté à un problème apparemment inextricable ? Eh bien, on peut en chercher une version simplifiée, dans l’espoir qu’une éventuelle solution de celle-ci puisse fournir de nouvelles idées et de nouveaux outils pour se replonger, plus fort, dans le problème original.

La conjecture de Hadamard se prête bien à cette démarche. Dans les années 1970, deux mathématiciens, Marrero et Butson, ont proposé la recherche de matrices analogues à celles de Hadamard mais moins contraignantes, et donc peut-être plus faciles à construire.

Rappelons que dans une matrice de Hadamard, le produit scalaire de deux lignes distinctes quelconques est nul. Comment affaiblir cette contrainte ? Eh bien par exemple, en exigeant non pas la nullité absolue des produits scalaires des paires de lignes, mais seulement leur nullité modulo un entier $m$ fixé à l’avance [10]. Cela donne plus de souplesse et permet d’espérer plus de solutions.

Nous voilà conduits à la définition suivante, dûe à Marrero et Butson.

Notons que toute authentique matrice de Hadamard est automatiquement une matrice de Hadamard $m$-modulaire, quel que soit le module $m$ choisi. En effet, la nullité absolue entraîne la nullité modulo $m$.

Voici un exemple très naïf de matrice de Hadamard 4-modulaire, qui n’est évidemment pas une authentique matrice de Hadamard :

\[ \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right). \]

Cela nous conduit directement à la conjecture suivante, version simplifiée de celle de Hadamard, dépendant du choix de $m$.

Pour $m=4$ par exemple, que la conjecture correspondante soit vraie est immédiat : il suffit, comme ci-dessus, de prendre la matrice carrée d’ordre $n$ dont tous les coefficients sont égaux à 1. Dans ce cas, le produit scalaire de deux lignes quelconques vaut $n$, et il vaut donc bien $0$ modulo 4, puisque $n$ est un multiple de 4 par hypothèse.

Bien sûr, ce cas est très particulier. Il faut évidemment s’attendre à ce que plus $m$ soit grand, plus la conjecture correspondante soit difficile.

Marrero et Butson ont résolu le cas $m=12$ dans les années 1970 [11] : il est bien vrai que, pour tout $n$ multiple de 4, il existe une matrice de Hadamard $12$-modulaire d’ordre $n$. La structure des solutions est encore relativement simple.

Le cas du module 32

Mais après ce premier succès, il a fallu attendre 2002 pour voir la solution d’un nouveau cas de la conjecture de Hadamard $m$-modulaire. Cette année-là en effet, Michel Kervaire et l’auteur en ont résolu le cas $m=32$. La structure des solutions obtenues est sensiblement plus vache, si j’ose dire, que dans le cas $m=12$. Elle fait appel, entre autre, à des analogues modulaires des quadruples de Turyn et à la grille magique de Goethals-Seidel.

Voici par exemple, issue de ce travail, une matrice de Hadamard 32-modulaire d’ordre 668, ordre pour lequel on ignore toujours s’il existe une vraie matrice de Hadamard. Il n’y a bien que deux couleurs, même si on peut avoir l’impression d’en voir plus [12].

Matrice de Hadamard 32-modulaire d’ordre 668

Pour finir

Et maintenant ? On attend avec impatience la solution de la conjecture de Hadamard [13], ou entretemps, de nouveaux cas de la conjecture $m$-modulaire, par exemple pour $m=64$ [14]. Notons que le jeu modulaire en vaut la chandelle : en effet, si l’on pouvait résoudre la conjecture de Hadamard $m$-modulaire pour une infinité de modules $m$, cela résoudrait automatiquement sa version classique !

Bref, il reste du pain sur la planche, et sans doute pour bien longtemps encore.