Hadamard-Matrix

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

${\displaystyle H_{2n}={\begin{pmatrix}H_{n}&H_{n}\\H_{n}&-H_{n}\end{pmatrix}}}$

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

${\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 ${\displaystyle E_{n}}$ und ${\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):

${\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 ${\displaystyle 2^{k}}$, wobei jede Zeile eine Walsh-Funktion darstellt.

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

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

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

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

und

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

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

${\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 ${\displaystyle Q^{t}=-Q}$ und ${\displaystyle Q\cdot Q^{t}=p\cdot E-J}$):

${\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.