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 S. 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.

Es lässt sich zeigen, dass nur dann Hadamard-Matrizen existieren können, wenn n = 1, n = 2 oder n = 4k mit $k\in\mathbb{N}$ gilt.

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:

$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}=2n\cdot E$

Walsh-Matrizen

Damit ergibt sich zum Beispiel die nach dem Mathematiker Joseph Leonard 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 Primzahl 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 Matrix 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

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.

Literatur

• S. A. Rukova: Hadamard matrix. In: Michiel Hazewinkel (Hrsg.): Encyclopaedia of Mathematics. Springer-Verlag, Berlin 2002, ISBN 1-4020-0609-8.