Matricea Hadamard

Matricea Hadamard este o matrice pătrată n × n compusă din numerele 1 și -1 ale căror coloane sunt ortogonale , astfel încât $H$

H_{n}\cdot H_{n}^{T}=n\cdot E_{n},

unde este matricea de identitate de dimensiunea n . Matricele Hadamard au aplicații în diverse domenii, inclusiv combinatorie , analiză numerică , procesare a semnalului . $E_{n}$

Conjectura Hadamard nedovedită afirmă că o matrice Hadamard de ordinul 4k există pentru fiecare k natural .

Proprietăți

Pe setul de matrici Hadamard de mărime , există un grup de transformări generate de inversiuni de rânduri și coloane (înmulțire cu −1), precum și permutări de rânduri și coloane. $n\ ori n$ $G$

Două matrice Hadamard și sunt numite echivalente dacă există un element astfel încât . Astfel, toate matricele Hadamard de o dimensiune dată se descompun în clase de echivalență . $H_1$ $H_2$ $g\în G$ $H_{2}=gH_{1}$

Teorema 1. Există un algoritm pentru enumerarea matricelor Hadamard normalizate.

Teorema 2. Pentru ordinele 1, 2, 4, 8, 12, 16, 20, 24, există, respectiv, 1, 1, 1, 1, 2, 118, 6520, 43966313 (secvența A147774 în OEIS ) clase echivalente Hadamard normalizate matrici în raport cu echivalența permutărilor rândurilor și coloanelor.

Definiție. O autotopie a matricei Hadamard H este un element astfel încât . $g\în G$ $g(H)=H$

Teorema 3. Există un algoritm pentru calcularea grupului de autotopie a matricei Hadamard.

Teorema 4. Există un algoritm pentru verificarea echivalenței a două matrice Hadamard care găsește elementul necesar . $g\în G$

Teorema 5. Există funcții calculabile polinomial pe matrice Hadamard care sunt invariante sub acțiunea grupului , și permit în anumite cazuri să se facă distincția între matrice Hadamard neechivalente. $G$

Teorema 6. Există un algoritm care enumera o singură matrice din fiecare clasă echivalentă, pentru toate matricele de o dimensiune dată (în curs de dezvoltare).

Exemple

H_{0}=+1,

H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}{\begin{array}{rr}1&1\\1&-1\end{matrice}}\ sfârșit{pmatrix}}

H_{2}={\frac {1}{2}}{\begin{pmatrix}{\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\ 1&-1&-1&1\end{array}}\end{pmatrix}}

{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix))={\begin{bmatrix}1&1\\1&-1 \end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}

\quad H_{2^{k+1}}={\begin{bmatrix}H_{2^{k}}&H_{2^{k}}\\H_{2^{k}}&- H_{2^{k}}\end{bmatrix}}=H_{2}\otimes H_{2^{k}},

unde și înseamnă produsul Kronecker . $\k\in N$ $uneori$

Folosind matrice Hadamard

Uneori folosit în telescoapele cu raze X cu deschidere codificată în spațiu .
Folosit la codificarea informațiilor (coduri de corectare a erorilor, ECC ).

Vezi și

Funcția Walsh

Link -uri

A Library of Hadamard Matrices , NJA Sloane
Hedayat, A.; Wallis, W.D. Matricele Hadamard și aplicațiile lor // Annals of Statistics : jurnal. - 1978. - Vol. 6 , nr. 6 . - P. 1184-1238 . - doi : 10.1214/aos/1176344370 . — . (Engleză)
Haralambos Evangelaras, Applications of Hadamard matrices , Journal of Telecommunications and Information Technology (2003): 3-10. (Engleză)
Seberry şi colab. Despre unele aplicații ale matricelor Hadamard , Metrika, 62(2-3), 221-239. 2005. (engleză)
Weisstein, Eric W. „Matricea Hadamard”. / MathWorld, o resursă web Wolfram. (Engleză)
Matrice Hadamard / The Encyclopaedia of Design Theory
McWilliams F. J., Sloan N. J. A. Teoria codurilor de corectare a erorilor: Per. din engleza. - M: Comunicare, 1979. - 744 p. - pagina 52 „2.3 Matrici Hadamard și coduri Hadamard”
Yu.Bugakov, E. Kuzhamaliev, Algoritm pentru construcția element cu element a unei matrice Hadamard de gradul 2 , algowiki