Hadamard-Matrix

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 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[Bearbeiten]

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

Konstruktion nach Sylvester[Bearbeiten]

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{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[Bearbeiten]

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[Bearbeiten]

Man definiert sich bei dieser Konstruktion zunächst die Jacobsthal-Matrix Q=(q_{ij}) vom Grad p (wobei p 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


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[Bearbeiten]

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[Bearbeiten]

Literatur[Bearbeiten]