Hadamard matris

Hadamard- matrisen är en n × n kvadratisk matris som består av talen 1 och −1 vars kolumner är ortogonala , så att $H$

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

var är identitetsmatrisen av storlek n . Hadamard-matriser har tillämpningar inom olika områden inklusive kombinatorik , numerisk analys , signalbehandling . $E_{n}$

Den obevisade Hadamard-förmodan säger att en Hadamard-matris av ordningen 4k existerar för varje naturlig k .

Egenskaper

På uppsättningen av Hadamard-matriser av storlek finns det en grupp transformationer som genereras av inversioner av rader och kolumner (multiplikation med -1), såväl som permutationer av rader och kolumner. $n\ gånger n$ $G$

Två Hadamard-matriser och kallas ekvivalenta om det finns ett element så att . Således bryts alla Hadamard-matriser av en given storlek upp i ekvivalensklasser . $H_1$ $H_2$ $g\in G$ $H_{2}=gH_{1}$

Sats 1. Det finns en algoritm för att räkna upp normaliserade Hadamard-matriser.

Sats 2. För order 1, 2, 4, 8, 12, 16, 20, 24 finns det respektive 1, 1, 1, 1, 2, 118, 6520, 43966313 (sekvens A147774 i OEIS ) ekvivalenta klasser matriser med avseende på ekvivalens av permutationer av rader och kolumner.

Definition. En autotopi av Hadamard-matrisen H är ett element så att . $g\in G$ $g(H)=H$

Sats 3. Det finns en algoritm för att beräkna autotopigruppen för Hadamard-matrisen.

Sats 4. Det finns en algoritm för att kontrollera ekvivalensen av två Hadamard-matriser som hittar det nödvändiga elementet . $g\in G$

Sats 5. Det finns polynomiellt beräkningsbara funktioner på Hadamard-matriser som är invarianta under inverkan av gruppen och tillåter i vissa fall att skilja mellan icke-ekvivalenta Hadamard-matriser. $G$

Sats 6. Det finns en algoritm som endast räknar upp en matris från varje ekvivalent klass, för alla matriser av en given storlek (under utveckling).

Exempel

H_{0}=+1,

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

var och betyder Kronecker-produkten . $\k\in N$ $\ ibland$

Använda Hadamard-matriser

Används ibland i rymdkodade röntgenteleskop med bländare .
Används vid kodning av information (felkorrigeringskoder, ECC ).

Se även

Walsh funktion

Länkar

A Library of Hadamard Matrices , NJA Sloane
Hedayat, A.; Wallis, W.D. Hadamard- matriser och deras tillämpningar // Annals of Statistics : journal. - 1978. - Vol. 6 , nr. 6 . - P. 1184-1238 . - doi : 10.1214/aos/1176344370 . — . (Engelsk)
Haralambos Evangelaras, Applications of Hadamard-matriser , Journal of Telecommunications and Information Technology (2003): 3-10. (Engelsk)
Seberry et al. På vissa tillämpningar av Hadamard-matriser , Metrika, 62(2-3), 221-239. 2005. (engelska)
Weisstein, Eric W. "Hadamard Matrix." / MathWorld, en webbresurs från Wolfram. (Engelsk)
Hadamard-matriser / The Encyclopaedia of Design Theory
McWilliams F. J., Sloan N. J. A. Teori om felkorrigerande koder: Per. från engelska. - M: Kommunikation, 1979. - 744 sid. - sida 52 "2.3 Hadamard-matriser och Hadamard-koder"
Yu.Bugakov, E. Kuzhamaliev, Algoritm för element-för-element-konstruktion av en Hadamard-matris av grad 2 , algowiki