Hadamard matrix

Hadamard -matricen er en n × n kvadratisk matrix sammensat af tallene 1 og −1, hvis søjler er ortogonale , således at $H$

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

hvor er identitetsmatrixen af størrelse n . Hadamard-matricer har applikationer inden for forskellige områder, herunder kombinatorik , numerisk analyse , signalbehandling . $E_{n}$

Den ubeviste Hadamard-formodning siger, at der eksisterer en Hadamard-matrix af orden 4k for hver naturlig k .

Egenskaber

På sættet af Hadamard-matricer af størrelse er der en gruppe af transformationer genereret af inversioner af rækker og kolonner (multiplikation med -1), samt permutationer af rækker og kolonner. $n\ gange n$ $G$

To Hadamard-matricer og kaldes ækvivalente , hvis der findes et element, sådan at . Således opdeles alle Hadamard-matricer af en given størrelse i ækvivalensklasser . $H_1$ $H_2$ $g\in G$ $H_{2}=gH_{1}$

Sætning 1. Der findes en algoritme til optælling af normaliserede Hadamard-matricer.

Sætning 2. For ordre 1, 2, 4, 8, 12, 16, 20, 24 er der henholdsvis 1, 1, 1, 1, 2, 118, 6520, 43966313 (sekvens A147774 i OEIS ) ækvivalentklasser matricer med hensyn til ækvivalens af permutationer af rækker og kolonner.

Definition. En autotopi af Hadamard-matricen H er et element sådan, at . $g\in G$ $g(H)=H$

Sætning 3. Der findes en algoritme til beregning af Hadamard-matricens autotopigruppe.

Sætning 4. Der er en algoritme til at kontrollere ækvivalensen af to Hadamard-matricer, der finder det nødvendige element . $g\in G$

Sætning 5. Der er polynomielt beregnelige funktioner på Hadamard-matricer, der er invariante under påvirkning af gruppen , og tillader i visse tilfælde at skelne mellem ikke-ækvivalente Hadamard-matricer. $G$

Sætning 6. Der er en algoritme, der kun opregner én matrix fra hver ækvivalent klasse, for alle matricer af en given størrelse (under udvikling).