Hadamard-Matrix
Eine Hadamard-Matrix vom Grad <math>n</math> ist eine <math>n\times n</math>-Matrix, die ausschließlich die Zahlen <math>1</math> und <math>-1</math> 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 <math>H</math> die Beziehung:
- <math>
H\cdot H^t=H^t\cdot H=n\cdot E </math> Dabei bezeichnet <math>H^t</math> die transponierte Matrix zu <math>H</math> und <math>E</math> 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 <math>1</math> und <math>-1</math> 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 <math>n=1</math>, <math>n=2</math> oder <math>n=4k</math> mit <math> k\in\mathbb{N} </math> existieren können.
Enthalten die erste Spalte und die erste Zeile von <math>H</math> nur <math>1</math>-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 <math>H_n</math> eine Hadamard-Matrix vom Grad <math>n</math>, so lässt sich damit folgendermaßen eine Hadamard-Matrix vom Grad <math>2n</math> konstruieren:
- <math>
H_{2n}=\begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix} </math> Die Orthogonalitätseigenschaft lässt sich leicht überprüfen:
- <math>
\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_n & 0 \\ 0 & 2n\cdot E_n \end{pmatrix}\\ &=2n\cdot E_{2n} \end{align} </math>
Hier bezeichnen <math>E_n</math> und <math>E_{2n}</math> die entsprechend dimensionierten Einheitsmatrizen.
Walsh-Matrizen
Damit ergibt sich zum Beispiel die nach dem Mathematiker Joseph L. Walsh benannte Folge von Matrizen (Walsh-Matrizen):
- <math>
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 </math> Die Walsh-Matrizen sind normalisierte Hadamard-Matrizen vom Grad <math>2^k</math>, wobei jede Zeile eine Walsh-Funktion darstellt.
Konstruktion über das Legendre-Symbol
Man definiert sich bei dieser Konstruktion zunächst die Jacobsthal-Matrix <math>Q=(q_{ij})</math> vom Grad <math>p</math> (wobei <math>p</math> eine ungerade Primzahl kongruent 3 modulo 4 ist) mit Hilfe des Legendre-Symbols <math>(a/p)</math>:
- <math>
q_{ij}=\left(\frac{j-i}{p}\right). </math> Ist nun <math>p=4k-1</math> mit <math> k\in\mathbb{N} </math>, so gilt
- <math>
Q^t=-Q </math> und
- <math>
Q\cdot Q^t=p\cdot E-J, </math> wobei <math> J</math> die Einsmatrix bezeichnet, bei der alle Einträge 1 sind. Nun konstruiert man die Hadamard-Matrix vom Grad <math>p+1</math>:
- <math>
H_{p+1}=\begin{pmatrix} 1 & \mathbf{1} \\ \mathbf{1}^t & Q-E \end{pmatrix} </math>. Auch hier kann man nachrechnen, dass dies eine Hadamard-Matrix ist (benutze <math>Q^t=-Q</math> und <math> Q\cdot Q^t=p\cdot E-J</math>):
- <math>
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 </math>. 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 <math>n=4k</math> 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 <math>n</math> der Form <math>n=2^k</math> oder <math>n=p+1</math> für eine Primzahl <math>p</math> erzeugen. Es gibt weitere Verfahren, allerdings lassen sich damit nicht alle Möglichkeiten abdecken. So wurde bis 2005 noch keine Hadamard-Matrix zu <math>n=668</math> gefunden. 1977 war die Frage noch für <math>n=268</math> 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
- {{#invoke:Vorlage:Literatur|f}}{{#if:|}}
Weblinks
|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:
| {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
|1/= und Videos
|1/1=, Videos und Audiodateien
|/1= und Audiodateien}}
| , Videos und Audiodateien
}}
|#default= – }}{{#if: Hadamard matrix
| {{#ifeq: {{#invoke:Str|left|hadamard matrix|9}}
| category:
| FEHLER: Ohne Category: angeben!}}}}