Hadamardova matice

Hadamardova matice je n × n čtvercová matice složená z čísel 1 a −1, jejíž sloupce jsou ortogonální , takže $H$

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

kde je matice identity velikosti n . Hadamardovy matice mají aplikace v různých oblastech včetně kombinatoriky , numerické analýzy , zpracování signálu . $E_{n}$

Neprokázaná Hadamardova domněnka tvrdí, že pro každé přirozené k existuje Hadamardova matice řádu 4k .

Vlastnosti

Na množině Hadamardových matic velikosti , existuje skupina transformací generovaných inverzemi řádků a sloupců (násobení −1) a také permutacemi řádků a sloupců. $n\krát n$ $G$

Dvě Hadamardovy matice a se nazývají ekvivalentní , pokud existuje prvek takový, že . Všechny Hadamardovy matice dané velikosti se tedy rozpadají do tříd ekvivalence . $H_1$ $H_2$ $g\in G$ $H_{2}=gH_{1}$

Věta 1. Existuje algoritmus pro výčet normalizovaných Hadamardových matic.

Věta 2. Pro objednávky 1, 2, 4, 8, 12, 16, 20, 24 existují 1, 1, 1, 1, 2, 118, 6520, 43966313 (sekvence A147774 v OEIS ) ekvivalentní třídy normalizovaných matice s ohledem na ekvivalenci permutací řádků a sloupců.

Definice. Autotopie Hadamardovy matice H je takový prvek , že . $g\in G$ $g(H)=H$

Věta 3. Existuje algoritmus pro výpočet skupiny autotopií Hadamardovy matice.

Věta 4. Existuje algoritmus pro kontrolu ekvivalence dvou Hadamardových matic, který najde požadovaný prvek . $g\in G$

Věta 5. Na Hadamardových maticích existují polynomiálně vyčíslitelné funkce, které jsou při působení grupy invariantní a umožňují v určitých případech rozlišovat mezi neekvivalentními Hadamardovými maticemi. $G$

Věta 6. Existuje algoritmus, který vyjmenovává pouze jednu matici z každé ekvivalentní třídy pro všechny matice dané velikosti (ve vývoji).

Příklady

H_{0}=+1,

H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}{\begin{array}{rr}1&1\\1&-1\end{array}}\ konec{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}},

kde a znamená produkt Kronecker . $\k\in N$ $\otimes$

Použití Hadamardových matic

Někdy se používá v prostorově kódovaných aperturních rentgenových dalekohledech .
Používá se při kódování informací (kódy pro opravu chyb, ECC ).

Viz také

Walshova funkce

Odkazy

Knihovna Hadamardových matrik , NJA Sloane
Hedayat, A.; Wallis, W.D. Hadamardovy matice a jejich aplikace // Annals of Statistics : deník. - 1978. - Sv. 6 , č. 6 . - S. 1184-1238 . - doi : 10.1214/aos/1176344370 . — . (Angličtina)
Haralambos Evangelaras, Aplikace Hadamardových matic , Journal of Telecommunications and Information Technology (2003): 3-10. (Angličtina)
Seberry a kol. O některých aplikacích Hadamardových matric , Metrika, 62(2-3), 221-239. 2005. (anglicky)
Weisstein, Eric W. "Hadamard Matrix." / MathWorld, webový zdroj Wolfram. (Angličtina)
Hadamardovy matice / The Encyclopaedia of Design Theory
McWilliams F. J., Sloan N. J. A. Theory of error-corpairing codes: Per. z angličtiny. - M: Komunikace, 1979. - 744 s. - strana 52 "2.3 Hadamardovy matice a Hadamardovy kódy"
Yu.Bugakov, E. Kuzhamaliev, Algoritmus pro konstrukci Hadamardovy matice stupně 2 prvek po prvku , algowiki