Matrice de Hadamard

matrice dont les coefficients valent 1 ou −1 et dont les lignes sont orthogonales deux à deux

Une matrice de Hadamard est une matrice carrée dont les coefficients sont tous 1 ou –1 et dont les lignes sont toutes orthogonales entre elles. Le nom retenu pour ces matrices rend hommage au mathématicien français Jacques Hadamard. Des exemples de telles matrices avaient été donnés par James Joseph Sylvester.

Gilbert Strang démontrant la conjecture d'Hadamard au MIT en 2005.

Pour une matrice d'ordre , la propriété d'orthogonalité des lignes peut également s'écrire sous la forme

In est la matrice identité d'ordre et t est la matrice transposée de .

Exemples :

Propriétés

modifier

Une matrice réelle d'ordre , dont les éléments sont bornés, atteint l'égalité dans l'inégalité de Hadamard

si et seulement si c'est une matrice de Hadamard.

Certaines opérations élémentaires transforment une matrice de Hadamard en une autre : permutation de lignes ou de colonnes, multiplication d'une ligne ou d'une colonne par -1.

La transposée d'une matrice de Hadamard est encore une matrice de Hadamard.

Construction de Sylvester

modifier

Les premiers exemples de matrices de Hadamard sont dus au mathématicien James Joseph Sylvester.

La construction est basée sur la propriété suivante. Si est une matrice de Hadamard d'ordre , alors la matrice

est une matrice de Hadamard d'ordre .

En appliquant cette construction de façon itérative, on construit la suite des matrices de Walsh, ou de Sylvester

puis (en utilisant la notation du produit de Kronecker)

Les matrices construites par la méthode de Sylvester ont certaines propriétés intéressantes. Ce sont des matrices symétriques de trace nulle. Les éléments de la première colonne et de la première ligne sont tous positifs. Dans chaque autre ligne ou colonne, la moitié des éléments est positive. Ces matrices sont étroitement liées aux fonctions de Walsh.

Ordre d'une matrice de Hadamard

modifier

L'ordre d'une matrice de Hadamard est nécessairement 1, 2 ou un multiple de 4[1],[2].

La construction de Sylvester montre qu'il existe des matrices de Hadamard d'ordre 2k pour tout entier naturel k.

La construction de matrices de Hadamard d'ordres 12 et 20 est due à Hadamard lui-même. Plus généralement, Raymond Paley a démontré que pour qu'un entier n > 0 multiple de 4 soit l'ordre d'une matrice de Hadamard, il suffit que n – 1 ou n/2 – 1 soit une puissance de nombre premier[3],[4]. Sa méthode utilise les corps finis. D'autres méthodes pour la construction de matrices de Hadamard sont maintenant connues.

Conjecture de Hadamard

modifier

La question ouverte la plus importante à propos des matrices de Hadamard est celle de leur existence. D'après la conjecture de Hadamard (1893)[4],

pour tout entier n > 0 multiple de 4, il existe une matrice de Hadamard d'ordre n.

Paley a formulé explicitement la conjecture de Hadamard[3], qui lui est parfois attribuée[5].

À la suite de l'annonce de la découverte d'une matrice de Hadamard d'ordre 428 le par Hadi Kharaghani et Behruz Tayfeh-Rezaie, le plus petit ordre multiple de 4 pour lequel aucune matrice de Hadamard n'est connue est actuellement 668[4].

Application

modifier

Les matrices de Hadamard sont utilisées dans les codes correcteurs comme celui de Reed-Muller, ou encore pour réaliser les plans d'analyse sensorielle et les plans d'expériences factoriels.

Notes et références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hadamard matrix » (voir la liste des auteurs).
  1. J. Hadamard, « Résolution d'une question relative aux déterminants », Bulletin des sciences mathématiques, vol. 17,‎ , p. 240-246 (lire en ligne) (p. 245).
  2. (en) Fredrick Kennard, Unsolved Problems in Mathematics, , 305 p. (ISBN 978-1-312-93811-3, lire en ligne), p. 73.
  3. a et b (en) R. E. A. C. Paley, « On orthogonal matrices », Journal of Mathematics and Physics, vol. 12,‎ , p. 311-320.
  4. a b et c Shalom Eliahou, « La conjecture de Hadamard » 1re partie et 2e partie sur images des Maths, 22 septembre et 21 décembre 2012.
  5. (en) A. Hedayat et W. D. Wallis, « Hadamard matrices and their applications », Ann. Stat., vol. 6, no 6,‎ , p. 1184-1238 (lire en ligne).

Articles connexes

modifier