Hadamard matrix

A Hadamard matrix of degree is a - matrix , exclusively the numbers and contains as coefficients and also all columns in the orthogonal to each other, as well as all the rows. ${\displaystyle n}$ ${\displaystyle n\times n}$ ${\displaystyle 1}$ ${\displaystyle -1}$

Hadamard matrices are named after the French mathematician Jacques Hadamard .

properties

From the orthogonality of the rows and columns, the relationship for a Hadamard matrix follows : ${\displaystyle H}$

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

The transposed matrix denotes to and the identity matrix . This equation can also be used to define Hadamard matrices, since among all matrices whose entries consist exclusively of the numbers and , only Hadamard matrices satisfy this equation. ${\displaystyle H^{t}}$ ${\displaystyle H}$ ${\displaystyle E}$ ${\displaystyle 1}$ ${\displaystyle -1}$

The product of a Hadamard matrix with a permutation matrix or a signed permutation matrix results in a Hadamard matrix.

It can be shown that Hadamard matrices can only exist for , or with . ${\displaystyle n=1}$ ${\displaystyle n=2}$ ${\displaystyle n=4k}$ ${\displaystyle k\in \mathbb {N} }$

If the first column and the first row contain only -entries, the matrix is ​​called normalized. ${\displaystyle H}$ ${\displaystyle 1}$

construction

There are several methods of constructing Hadamard matrices. Two of these are described below:

Construction after New Years Eve

This construction goes back to the English mathematician James J. Sylvester . If a Hadamard matrix is ​​of degree , a Hadamard matrix of degree can be constructed as follows: ${\displaystyle H_{n}}$ ${\displaystyle n}$ ${\displaystyle 2n}$

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

The orthogonality property can easily be checked:

${\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&0\\0&2n\cdot E\end{pmatrix}}\\&=2n\cdot E\end{aligned}}}$

Walsh matrices

This results, for example, in the sequence of matrices ( Walsh matrices ) named after the mathematician Joseph L. Walsh :

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

The Walsh matrices are normalized Hadamard matrices of degree , with each row representing a Walsh function . ${\displaystyle 2^{k}}$

Construction using the Legendre symbol

With this construction, one first defines the Jacobsthal matrix of degree (where an odd prime number is) with the help of the Legendre symbol : ${\displaystyle Q=(q_{ij})}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle (a/p)}$

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

Is now with , then applies ${\displaystyle p=4k-1}$ ${\displaystyle k\in \mathbb {N} }$

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

and

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

where denotes the one matrix in which all entries are 1. Now we construct the Hadamard matrix of degree : ${\displaystyle J}$ ${\displaystyle p+1}$

${\displaystyle H_{p+1}={\begin{pmatrix}1&\mathbf {1} \\\mathbf {1} ^{t}&Q-E\end{pmatrix}}}$.

Here, too, you can check that this is a Hadamard matrix (use and ): ${\displaystyle Q^{t}=-Q}$ ${\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}$.

Matrices constructed in this way are called Hadamard matrices of the Paley type, after the English mathematician Raymond Paley .

The Hadamard Conjecture

It is assumed (but could not yet be proven) that there is at least one Hadamard matrix for every number . This assumption probably goes back to Paley. With the two methods mentioned above, one can generate Hadamard matrices for all numbers of the form or for a prime number . There are other methods, but not all options can be covered. Until 2005, no Hadamard matrix was found. In 1977 the question was still unanswered. ${\displaystyle n=4k}$ ${\displaystyle n}$ ${\displaystyle n=2^{k}}$ ${\displaystyle n=p+1}$ ${\displaystyle p}$ ${\displaystyle n=668}$ ${\displaystyle n=268}$

Applications

• The Hadamard transformation , a discrete transformation from the field of Fourier analysis , uses Hadamard matrices.
• Hadamard matrices are used in the field of error-correcting codes , where they are used to generate Hadamard codes or Reed-Muller codes .
• They are used in statistics to calculate variances of variables.
• In discrete mathematics, certain block plans , the Hadamard block plans , are constructed from Hadamard matrices.

literature

• SA Rukova: Hadamard matrix . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).