Hadamard-Matrix

Hadamard-Matrix

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 S. Hadamard benannt.

Inhaltsverzeichnis

Eigenschaften

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 Ht 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 nur dann Hadamard-Matrizen existieren können, wenn n = 1, n = 2 oder n = 4k mit  k\in\mathbb{N} gilt.

Enthalten die erste Spalte und die erste Zeile von H nur 1-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 Hn 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:


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}=2n\cdot E

Walsh-Matrizen

Damit ergibt sich zum Beispiel die nach dem Mathematiker Joseph Leonard 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 2k, wobei jede Zeile eine Walsh-Funktion darstellt.

Konstruktion über das Legendre-Symbol

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

Qt = − Q

und:


Q\cdot Q^t=p\cdot E-J

wobei J die Matrix 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 Qt = − 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

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 = 2k 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

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.

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hadamard matrix — In mathematics, a Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. This means that every two different rows in a Hadamard matrix represent two perpendicular vectors. Such matrices can… …   Wikipedia

  • Complex Hadamard matrix — A complex Hadamard matrix is any complex matrix H satisfying two conditions: unimodularity (the modulus of each entry is unity): orthogonality: , where denotes the Hermitian transpose of H and …   Wikipedia

  • Regular Hadamard matrix — In mathematics a regular Hadamard matrix is a Hadamard matrix whose row and column sums are all equal. While the order of a Hadamard matrix must be 1, 2, or a multiple of 4, regular Hadamard matrices carry the further restriction that the order… …   Wikipedia

  • Butson-type Hadamard matrix — In mathematics, a complex Hadamard matrix H of size N with all its columns (rows) mutually orthogonal, belongs to the Butson type H ( q , N ) if all its elements are powers of q th root of unity,:: (H {jk})^q=1 {quad m for quad} j,k=1,2,dots,N.… …   Wikipedia

  • Hadamard-Code — Matrix des [32,6,16] Hadamard Codes der NASA Raumsonde Mariner 9 (1971/1972). Die Farbe Schwarz kodiert die Binärziffer 1, und die Farbe Weiß kodiert die Binärziffer 0 …   Deutsch Wikipedia

  • Hadamard (disambiguation) — Hadamard may refer to* Jacques Hadamard * Hadamard gate * Hadamard matrix * Hadamard s inequality * Hermite–Hadamard inequality * Walsh–Hadamard transform * Fast Walsh–Hadamard transform …   Wikipedia

  • Hadamard transform — The Hadamard transform (also known as the Walsh Hadamard transform, Hadamard Rademacher Walsh transform, Walsh transform, or Walsh Fourier transform) is an example of a generalized class of Fourier transforms. It is named for the French… …   Wikipedia

  • Hadamard code — The Hadamard code, named after Jacques Hadamard, is a system used for signal error detection and correction. It is one of the family of [2 n , n + 1, 2 n − 1] codes. Especially for large n it has a poor rate but it is capable of correcting many… …   Wikipedia

  • Hadamard — Jacques Salomon Hadamard Jacques Salomon Hadamard (* 8. Dezember 1865 in Versailles; † 17. Oktober 1963 in Paris) war ein französischer Mathematiker. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Hadamard's inequality — In mathematics, Hadamard s inequality, named after Jacques Hadamard, bounds above the volume in Euclidean space of n dimensions marked out by n vectors: vi for 1 le; i le; n .It states, in geometric terms, that this is at a maximum when the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”