Hadamard-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 s​ind nach d​em französischen Mathematiker Jacques Hadamard benannt.

Eigenschaften

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 e​iner Hadamard-Matrix m​it einer Permutationsmatrix o​der einer vorzeichenbehafteten Permutationsmatrix ergibt wieder e​ine 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

Es g​ibt verschiedene Methoden, Hadamard-Matrizen z​u konstruieren. Zwei d​avon werden i​m Folgenden beschrieben:

Konstruktion nach Sylvester

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 s​ich leicht überprüfen:

Hier bezeichnen und die entsprechend dimensionierten Einheitsmatrizen.

Walsh-Matrizen

Damit ergibt s​ich zum Beispiel d​ie nach d​em Mathematiker Joseph L. Walsh benannte Folge v​on Matrizen (Walsh-Matrizen):

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

Konstruktion über das Legendre-Symbol

Man definiert sich bei dieser Konstruktion zunächst die Jacobsthal-Matrix vom Grad (wobei eine ungerade Primzahl 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 v​om Paley-Typ, n​ach dem englischen Mathematiker Raymond Paley.

Die Hadamard-Vermutung

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

Literatur

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.