Hadamard-Matrix

Eine Hadamard-Matrix vom Grad ist eine $n\times n$ -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 sind nach dem französischen Mathematiker Jacques Hadamard benannt.

Eigenschaften

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

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

Dabei bezeichnet H^t 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 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 nur -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 , so lässt sich damit folgendermaßen eine Hadamard-Matrix vom Grad 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{align} 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 & 0 \\ 0 & 2n\cdot E \end{pmatrix}\\ &=2n\cdot E \end{align}$

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 (wobei eine ungerade 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

und

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

wobei 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 der Form n=2^k oder n=p+1 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 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.

Basierend auf einem Artikel in:

Wikipedia.de