Hadamard-Matrix

mathematische Matrix

Eine Hadamard-Matrix vom Grad ist eine -Matrix, die ausschließlich die Zahlen und als Koeffizienten enthält und bei der zudem alle Spalten orthogonal zueinander sind, ebenso alle Zeilen.

Hadamard-Matrizen sind nach dem französischen Mathematiker Jacques Hadamard benannt.

Eigenschaften

Bearbeiten

Aus der Orthogonalität der Zeilen und Spalten folgt für eine Hadamard-Matrix   die Beziehung:

 

Dabei bezeichnet   die transponierte Matrix zu   und   die Einheitsmatrix. Diese Gleichung kann auch zur Definition von Hadamard-Matrizen benutzt werden, da unter allen Matrizen, deren Einträge ausschließlich aus den Zahlen   und   bestehen, nur Hadamard-Matrizen diese Gleichung erfüllen.

Das Produkt einer Hadamard-Matrix mit einer Permutationsmatrix oder einer vorzeichenbehafteten Permutationsmatrix ergibt wieder eine Hadamard-Matrix.

Es lässt sich zeigen, dass Hadamard-Matrizen nur für  ,   oder   mit   existieren können.

Enthalten die erste Spalte und die erste Zeile von   nur  -Einträge, so heißt die Matrix normalisiert.

Konstruktion

Bearbeiten

Es gibt verschiedene Methoden, Hadamard-Matrizen zu konstruieren. Zwei davon werden im Folgenden beschrieben:

Konstruktion nach Sylvester

Bearbeiten

Diese Konstruktion geht auf den englischen Mathematiker James J. Sylvester zurück. Ist   eine Hadamard-Matrix vom Grad  , so lässt sich damit folgendermaßen eine Hadamard-Matrix vom Grad   konstruieren:

 

Die Orthogonalitätseigenschaft lässt sich leicht überprüfen:

 

Hier bezeichnen   und   die entsprechend dimensionierten Einheitsmatrizen.

Walsh-Matrizen

Bearbeiten

Damit ergibt sich zum Beispiel die nach dem Mathematiker Joseph L. Walsh benannte Folge von Matrizen (Walsh-Matrizen):

 

Die Walsh-Matrizen sind normalisierte Hadamard-Matrizen vom Grad  , wobei jede Zeile eine Walsh-Funktion darstellt.

Konstruktion über das Legendre-Symbol

Bearbeiten

Man definiert sich bei dieser Konstruktion zunächst die Jacobsthal-Matrix   vom Grad   (wobei   eine ungerade Primzahl kongruent 3 modulo 4 ist) mit Hilfe des Legendre-Symbols  :

 

Ist nun   mit  , so gilt

 

und

 

wobei   die Einsmatrix bezeichnet, bei der alle Einträge 1 sind. Nun konstruiert man die Hadamard-Matrix vom Grad  :

 .

Auch hier kann man nachrechnen, dass dies eine Hadamard-Matrix ist (benutze   und  ):

 .

So konstruierte Matrizen heißen Hadamard-Matrizen vom Paley-Typ, nach dem englischen Mathematiker Raymond Paley.

Die Hadamard-Vermutung

Bearbeiten

Es wird vermutet (konnte aber noch nicht bewiesen werden), dass zu jeder Zahl   wenigstens eine Hadamard-Matrix existiert. Diese Vermutung geht wahrscheinlich auf Paley zurück. Mit den beiden oben genannten Verfahren kann man Hadamard-Matrizen für alle Zahlen   der Form   oder   für eine Primzahl   erzeugen. Es gibt weitere Verfahren, allerdings lassen sich damit nicht alle Möglichkeiten abdecken. So wurde bis 2005 noch keine Hadamard-Matrix zu   gefunden. 1977 war die Frage noch für   ungeklärt.

Anwendungen

Bearbeiten

Literatur

Bearbeiten