Hadamard-Matrix

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

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

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

Enthalten die erste Spalte und die erste Zeile von ${\displaystyle H}$ nur ${\displaystyle 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 ${\displaystyle H_{n}}$ eine Hadamard-Matrix vom Grad ${\displaystyle n}$, so lässt sich damit folgendermaßen eine Hadamard-Matrix vom Grad ${\displaystyle 2n}$ konstruieren:

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

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

${\displaystyle {\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 ${\displaystyle E_{n}}$ und ${\displaystyle 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):

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle Q=(q_{ij})}$ vom Grad ${\displaystyle p}$ (wobei ${\displaystyle p}$ eine ungerade Primzahl kongruent 3 modulo 4 ist) mit Hilfe des Legendre-Symbols ${\displaystyle (a/p)}$:

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

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

${\displaystyle Q^{t}=-Q}$

und

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

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

${\displaystyle 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 ${\displaystyle Q^{t}=-Q}$ und ${\displaystyle Q\cdot Q^{t}=p\cdot E-J}$):

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ der Form ${\displaystyle n=2^{k}}$ oder ${\displaystyle n=p+1}$ für eine Primzahl ${\displaystyle p}$ erzeugen. Es gibt weitere Verfahren, allerdings lassen sich damit nicht alle Möglichkeiten abdecken. So wurde bis 2005 noch keine Hadamard-Matrix zu ${\displaystyle n=668}$ gefunden. 1977 war die Frage noch für ${\displaystyle 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).