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}=\left(\begin{array}{cc}{H}_n& H_n\\ H_n& -H_n\end{array}\right)$

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

$\begin{array}{cc}{H}_{2n}\cdot H_{2n}^t& =\left(\begin{array}{cc}{H}_n& H_n\\ H_n& -H_n\end{array}\right)\cdot \left(\begin{array}{cc}{H}_n^t& H_n^t\\ H_n^t& -H_n^t\end{array}\right)\\ & =\left(\begin{array}{cc}{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{array}\right)\\ & =\left(\begin{array}{cc}2\cdot H_n{H}_n^t& 0\\ 0& 2\cdot H_n{H}_n^t\end{array}\right)=\left(\begin{array}{cc}2n\cdot E_n& 0\\ 0& 2n\cdot E_n\end{array}\right)\\ & =2n\cdot E_{2n}\end{array}$

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=\left(\begin{array}{c}1\end{array}\right),H_2=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),H_4=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right),\dots$

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}=\left(\begin{array}{cc}1& \mathrm{𝟏}\\ {\mathrm{𝟏}}^t& Q-E\end{array}\right)$.

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=\left(\begin{array}{cc}1+p& \mathrm{𝟎}\\ \mathrm{𝟎}& J+(Q-E)(Q^t-E)\end{array}\right)=(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

• Vorlage:EoM