Hadamard-Matrix

Eine Hadamard-Matrix vom Grad n {\displaystyle n} ist eine n × n {\displaystyle n\times n} -Matrix, die ausschließlich die Zahlen 1 {\displaystyle 1} und − 1 {\displaystyle -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.

Aus der Orthogonalität der Zeilen und Spalten folgt für eine Hadamard-Matrix H {\displaystyle H} die Beziehung:

H ⋅ H t = H t ⋅ H = n ⋅ E {\displaystyle H\cdot H^{t}=H^{t}\cdot H=n\cdot E}

Dabei bezeichnet H t {\displaystyle H^{t}} die transponierte Matrix zu H {\displaystyle H} und E {\displaystyle 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 {\displaystyle 1} und − 1 {\displaystyle -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 {\displaystyle n=1} , n = 2 {\displaystyle n=2} oder n = 4 k {\displaystyle n=4k} mit k ∈ N {\displaystyle k\in \mathbb {N} } existieren können.

Enthalten die erste Spalte und die erste Zeile von H {\displaystyle H} nur 1 {\displaystyle 1} -Einträge, so heißt die Matrix normalisiert.

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

Diese Konstruktion geht auf den englischen Mathematiker James J. Sylvester zurück. Ist H n {\displaystyle H_{n}} eine Hadamard-Matrix vom Grad n {\displaystyle n} , so lässt sich damit folgendermaßen eine Hadamard-Matrix vom Grad 2 n {\displaystyle 2n} konstruieren:

H 2 n = ( H n H n H n − H n ) {\displaystyle H_{2n}={\begin{pmatrix}H_{n}&H_{n}\\H_{n}&-H_{n}\end{pmatrix}}}

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

H 2 n ⋅ H 2 n t = ( H n H n H n − H n ) ⋅ ( H n t H n t H n t − 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 + H n H n t ) = ( 2 ⋅ H n H n t 0 0 2 ⋅ H n H n t ) = ( 2 n ⋅ E n 0 0 2 n ⋅ E n ) = 2 n ⋅ E 2 n {\displaystyle {\begin{aligned}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{aligned}}}

Hier bezeichnen E n {\displaystyle E_{n}} und E 2 n {\displaystyle E_{2n}} die entsprechend dimensionierten Einheitsmatrizen.

Damit ergibt sich zum Beispiel die nach dem Mathematiker Joseph L. Walsh benannte Folge von Matrizen (Walsh-Matrizen):

H 1 = ( 1 ) , H 2 = ( 1 1 1 − 1 ) , H 4 = ( 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ) , … {\displaystyle 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 {\displaystyle 2^{k}} , wobei jede Zeile eine Walsh-Funktion darstellt.

Man definiert sich bei dieser Konstruktion zunächst die Jacobsthal-Matrix Q = ( q i j ) {\displaystyle Q=(q_{ij})} vom Grad p {\displaystyle p} (wobei p {\displaystyle p} eine ungerade Primzahl kongruent 3 modulo 4 ist) mit Hilfe des Legendre-Symbols ( a / p ) {\displaystyle (a/p)} :

q i j = ( j − i p ) . {\displaystyle q_{ij}=\left({\frac {j-i}{p}}\right).}

Ist nun p = 4 k − 1 {\displaystyle p=4k-1} mit k ∈ N {\displaystyle k\in \mathbb {N} } , so gilt

Q t = − Q {\displaystyle Q^{t}=-Q}

und

Q ⋅ Q t = p ⋅ E − J , {\displaystyle Q\cdot Q^{t}=p\cdot E-J,}

wobei J {\displaystyle J} die Einsmatrix bezeichnet, bei der alle Einträge 1 sind. Nun konstruiert man die Hadamard-Matrix vom Grad p + 1 {\displaystyle p+1} :

H p + 1 = ( 1 1 1 t Q − E ) {\displaystyle 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 {\displaystyle Q^{t}=-Q} und Q ⋅ Q t = p ⋅ E − J {\displaystyle Q\cdot Q^{t}=p\cdot E-J} ):

H p + 1 ⋅ H p + 1 t = ( 1 + p 0 0 J + ( Q − E ) ( Q t − E ) ) = ( p + 1 ) ⋅ E {\displaystyle 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.

Es wird vermutet (konnte aber noch nicht bewiesen werden), dass zu jeder Zahl n = 4 k {\displaystyle 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 {\displaystyle n} der Form n = 2 k {\displaystyle n=2^{k}} oder n = p + 1 {\displaystyle n=p+1} für eine Primzahl p {\displaystyle 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 {\displaystyle n=668} gefunden. 1977 war die Frage noch für n = 268 {\displaystyle n=268} ungeklärt.

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

• S. A. Rukova: Hadamard matrix. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). 

Commons: Hadamard-Matrix – Sammlung von Bildern, Videos und Audiodateien