Hadamard-Matrix

Eine Hadamard-Matrix vom Grad $n$ ist eine $n\times n$-Matrix, die ausschließlich die Zahlen $1$ und $-1$ 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

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

$H\cdot H^{t}=H^{t}\cdot H=n\cdot E$

Dabei bezeichnet $H^{t}$ die transponierte Matrix zu $H$ und $E$ 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 $1$ und $-1$ 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 $n=1$, $n=2$ oder $n=4k$ mit $k\in \mathbb {N}$ existieren können.

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

Konstruktion

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

Konstruktion nach Sylvester

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

$H_{2n}={\begin{pmatrix}H_{n}&H_{n}\\H_{n}&-H_{n}\end{pmatrix}}$

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

${\begin{aligned}H_{2n}\cdot H_{2n}^{t}&={\begin{pmatrix}H_{n}&H_{n}\\H_{n}&-H_{n}\end{pmatrix}}\cdot {\begin{pmatrix}H_{n}^{t}&H_{n}^{t}\\H_{n}^{t}&-H_{n}^{t}\end{pmatrix}}\\&={\begin{pmatrix}H_{n}H_{n}^{t}+H_{n}H_{n}^{t}&H_{n}H_{n}^{t}-H_{n}H_{n}^{t}\\H_{n}H_{n}^{t}-H_{n}H_{n}^{t}&H_{n}H_{n}^{t}+H_{n}H_{n}^{t}\end{pmatrix}}\\&={\begin{pmatrix}2\cdot H_{n}H_{n}^{t}&0\\0&2\cdot H_{n}H_{n}^{t}\end{pmatrix}}={\begin{pmatrix}2n\cdot E_{n}&0\\0&2n\cdot E_{n}\end{pmatrix}}\\&=2n\cdot E_{2n}\end{aligned}}$

Hier bezeichnen $E_{n}$ und $E_{2n}$ die entsprechend dimensionierten Einheitsmatrizen.

Walsh-Matrizen

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

$H_{1}={\begin{pmatrix}1\end{pmatrix}},H_{2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}},H_{4}={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}},\ldots$

Die Walsh-Matrizen sind normalisierte Hadamard-Matrizen vom Grad $2^{k}$, wobei jede Zeile eine Walsh-Funktion darstellt.

Konstruktion über das Legendre-Symbol

Man definiert sich bei dieser Konstruktion zunächst die Jacobsthal-Matrix $Q=(q_{ij})$ vom Grad $p$ (wobei $p$ eine ungerade Primzahl kongruent 3 modulo 4 ist) mit Hilfe des Legendre-Symbols $(a/p)$:

$q_{ij}=\left({\frac {j-i}{p}}\right).$

Ist nun $p=4k-1$ mit $k\in \mathbb {N}$, so gilt

$Q^{t}=-Q$

und

$Q\cdot Q^{t}=p\cdot E-J,$

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

$H_{p+1}={\begin{pmatrix}1&\mathbf {1} \\\mathbf {1} ^{t}&Q-E\end{pmatrix}}$.

Auch hier kann man nachrechnen, dass dies eine Hadamard-Matrix ist (benutze $Q^{t}=-Q$ und $Q\cdot Q^{t}=p\cdot E-J$):

$H_{p+1}\cdot H_{p+1}^{t}={\begin{pmatrix}1+p&\mathbf {0} \\\mathbf {0} &J+(Q-E)(Q^{t}-E)\end{pmatrix}}=(p+1)\cdot E$.

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

Die Hadamard-Vermutung

Es wird vermutet (konnte aber noch nicht bewiesen werden), dass zu jeder Zahl $n=4k$ 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 $n$ der Form $n=2^{k}$ oder $n=p+1$ für eine Primzahl $p$ erzeugen. Es gibt weitere Verfahren, allerdings lassen sich damit nicht alle Möglichkeiten abdecken. So wurde bis 2005 noch keine Hadamard-Matrix zu $n=668$ gefunden. 1977 war die Frage noch für $n=268$ ungeklärt.

Anwendungen

• Die Hadamard-Transformation, eine diskrete Transformation aus dem Bereich der Fourier-Analysis, verwendet Hadamard-Matrizen.
• Hadamard-Matrizen finden Anwendung im Bereich der fehlerkorrigierenden Codes, wo sie zum Erzeugen von Hadamard-Codes oder Reed-Muller-Codes benutzt werden.
• In der Statistik werden sie benutzt, um Varianzen von Variablen zu berechnen.
• In der diskreten Mathematik werden bestimmte Blockpläne, die Hadamard-Blockpläne, aus Hadamard-Matrizen konstruiert.

Literatur

• S. A. Rukova: Hadamard matrix. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org).