Hadamardova matice

Gilbert Strang demonstruje Hadamardovu domněnku na MIT v roce 2005 pomocí Sylvesterovy konstrukce.

Hadamardova matice, pojmenovaná po francouzském matematikovi Jacquesovi Hadamardovi (1865–1963), je v matematice čtvercová matice, jejíž prvky mají hodnotu buď +1 nebo -1 a jejíž řádky jsou navzájem ortogonální. Ortogonalitu řádků lze geometricky interpretovat tak, že každá dvojice řádků v Hadamardově matici představuje dva navzájem kolmé vektory. Kombinatorická lze ortogonalitu interpretovat tak, že každá dvojice řádků má shodné hodnoty v přesně polovině sloupců a opačné hodnoty ve zbývajících sloupcích. Hadamardovy matice jsou až na skalární násobek ortogonální, a proto všechny jejich vlastnosti platí nejen pro řádky, ale i pro sloupce.

Rovnoběžnostěn dimenze $n$ určený řádky Hadamardovy matice řádu $n$ má maximální možný $n$-rozměrný objem mezi možnými rovnoběžnostěny určenými vektory s prvky absolutní hodnoty nejvýše 1. Jinými slovy, Hadamardovy matice mají největší možnou absolutní hodnotu determinantu mezi maticemi se prvky z intervalu $⟨-1,1⟩$, a tak je extremálním řešením Hadamardova problému maximálního determinantu.

Některé Hadamardovy matice přímo určují Hadamardův samoopravný kód (zobecněn v Reedových–Mullerových kódech). Hadamardovy matice se také používají ve statistice k odhadu rozptylu.

Vlastnosti

Z kolmosti různých řádků Hadamardovy matice $𝑯$ vyplývá, že v součinu ${𝑯𝑯}^{\mathsf{\text{T}}}$, kde ${𝑯}^{\mathsf{\text{T}}}$ značí transpozici matice $𝑯$, jsou mimo diagonálu samé nuly. Na diagonále výsledné matice je hodnota standardního skalárního součinu odpovídajícího řádku se sebou samým, čili eukleidovská délka vektoru. Vektor o $n$ složkách hodnot 1 a -1 má délku $n$.

Reálná čtvercová matice řádu $n$ je proto Hadamardova, právě když pro ni platí:

${𝑯𝑯}^{\mathsf{\text{T}}}=n{𝐈}_n$

kde ${𝐈}_n$ značí jednotkovou matici řádu $n$.

Matice $\frac{1}{\sqrt{n}}𝑯$ (vzniklá vydělením prvků matice $𝑯$ hodnotou $\sqrt{n}$) je ortogonální, neboli matice jejíž transpozice se shoduje s její inverzí.

Inverzní matice

Matici inverzní k Hadamardově matici $𝑯$ lze vyjádřit pomocí transpozice:

${𝑯}^{-1}=\frac{1}{n}{𝑯}^{\mathsf{\text{T}}}$

Poslední vztah lze i obrátit a vyjádřit ${𝑯}^{\mathsf{\text{T}}}=n{𝑯}^{-1}$. Z něj lze odvodit že Hadamardova matice komutuje v součinu se svou transpozicí, neboť:

${𝑯}^{\mathsf{\text{T}}}𝑯=n{𝑯}^{-1}𝑯=n{𝐈}_n={𝑯𝑯}^{\mathsf{\text{T}}}$

Úpravy

Transpozicí Hadamardovy matice vznikne opět Hadamardova matice, protože

${𝑯}^{\mathsf{\text{T}}}({𝑯}^{\mathsf{\text{T}}}{)}^{\mathsf{\text{T}}}={𝑯}^{\mathsf{\text{T}}}𝑯=n{𝐈}_n$

V důsledku lze veškeré vlastnosti či úpravy řádků aplikovat i na sloupce.

Vlastnosti Hadamardovy matice se zachovávají i při přerovnání řádků a sloupců, protože ortogonalita vektorů je nezměněna, jsou-li vektory umístěné v matici v jiném pořadí.

Změna znamének v některém řádku či sloupci Hadamardovy matice odpovídá náhradě vektoru opačným vektorem. Z linearity skalárního součinu vůči skalárním násobkům vyplývá, že tato operace zachovává ortogonalitu, a proto je výsledkem opět Hadamardova matice.

Z libovolné Hadamardovy matice lze proto uvedenými operacemi získat Hadamardovu matici stejného řádu, v jejímž prvním řádku i sloupci jsou samé jedničky.

Determinant

Hadamardova matice má shodný determinant jako její transpozice, a tak z rovnosti:

$(\det 𝑯{)}^2=\det 𝑯\cdot \det {𝑯}^{\mathsf{\text{T}}}=\det ({𝑯𝑯}^{\mathsf{\text{T}}})=\det (n{𝐈}_n)=n^n$

bezprostředně vyplývá:

$\det 𝑯=\pm n^{n/2}$

Hadamardova nerovnost pro komplexní matici $𝑴$ řádu $n$, jejíž prvky mají absolutní hodnotu nejvýše 1, udává horní mez na hodnotu determinantu:

$|\det 𝑴|\le n^{n/2}$

Pro reálné matice se rovnosti nabývá, právě když je $𝑴$ Hadamardovou maticí.

Řád

Hadamardovy matice mají řád 1, 2 nebo dělitelný 4.

Důkaz

Má-li Hadamardova matice řád $n\ge 3$, potom lze její sloupce přerovnat tak, aby první tři řádky byly ve tvaru:

$\left(\underset{\alpha \times }{\underbrace{\begin{array}{ccc}1& \dots & 1\\ 1& \dots & 1\\ 1& \dots & 1\end{array}}}\underset{\beta \times }{\underbrace{\begin{array}{ccc}1& \dots & 1\\ 1& \dots & 1\\ -1& \dots & -1\end{array}}}\underset{\gamma \times }{\underbrace{\begin{array}{ccc}1& \dots & 1\\ -1& \dots & -1\\ 1& \dots & 1\end{array}}}\underset{\delta \times }{\underbrace{\begin{array}{ccc}1& \dots & 1\\ -1& \dots & -1\\ -1& \dots & -1\end{array}}}\right)$

Jinými slovy u dvojic prvků ve druhém a třetím řádku v témže sloupci mohou nastat čtyři různé situace podle toho jaká mají znaménka. Počty těchto případů jsou označeny následovně: $\alpha$ značí počet jedniček ve druhém řádku nad jedničkami ve třetím řádku; $\beta$ je počet 1 ve druhém řádku nad -1 ve třetím řádku; $\gamma$ je počet -1 ve druhém řádku nad 1 ve třetím řádku; a $\delta$ je počet -1 ve druhém řádku nad -1 ve třetím řádku.

Všechny možné situace jsou pokryty, a proto $\alpha +\beta +\gamma +\delta =n$. Druhý a třetí řádek jsou navzájem kolmé, a proto $\alpha -\beta -\gamma +\delta =0$. Ze součtu těchto dvou rovnic vyplývá $2\alpha +2\delta =n$, čili $\delta =\frac{n}{2}-\alpha$.

Jedničky tvoří polovinu prvků ve druhém řádku, neboli $\alpha +\beta =\frac{n}{2}$ a podobně -1 tvoří polovinu prvků ve třetím řádku $\beta +\delta =\frac{n}{2}$. Z rozdílu těchto rovnic vyplývá $\alpha =\delta =\frac{n}{2}-\alpha$ a následně i $n=4\alpha$. Protože je $\alpha$ celé číslo, je $n$ dělitelné čtyřmi.

Sylvesterova konstrukce

Některé Hadamardovy matice ve skutečnosti poprvé zkonstruoval James Joseph Sylvester v roce 1867, konkrétně matice řádu $2^k$ pro každé přirozené číslo $k$. Je-li $𝑯$ Hadamardova matice řádu $n$, potom bloková matice

$\left(\begin{array}{cc}𝑯& 𝑯\\ 𝑯& -𝑯\end{array}\right)$

je Hadamardova matice řádu $2n$. Uvedenou konstrukci lze opakovat, což vede k následující posloupnosti:

$\begin{array}{cc}{𝑯}_1& =\left(\begin{array}{c}1\end{array}\right),\\ {𝑯}_2& =\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),\\ {𝑯}_4& =\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right),\end{array}$

a obecně pro $k\in \mathbb{N}$:

${𝑯}_{2^k}=\left(\begin{array}{cc}{𝑯}_{2^{k-1}}& {𝑯}_{2^{k-1}}\\ {𝑯}_{2^{k-1}}& -{𝑯}_{2^{k-1}}\end{array}\right)={𝑯}_2\otimes {𝑯}_{2^{k-1}},$

kde $\otimes$ označuje Kroneckerův součin matic.

Výsledné matice symetrické a pro $k\ge 1$, mají nulovou stopu. Prvky v prvním sloupci a prvním řádku jsou všechny kladné. Prvky ve všech ostatních řádcích a sloupcích jsou rovnoměrně rozděleny mezi kladné a záporné. Přerovnáním řádků podle počtu změn znamének (z 1 na -1 nebo naopak) lze získat tzv. Walshovy matice. Ty úzce souvisejí s Walshovými funkcemi.

Binární Hadamardova matice jako výsledek součinu generující matice ${𝑭}_4$ se svou transpozicí. Binární matice, kde bílá barva značí 0 a červená 1, je výsledkem operací v konečném tělese ${\mathbb{Z}}_2$, zatímco šedá čísla ukazují výsledek operací v $\mathbb{N}$.

Alternativní popis konstrukce

Sylvesterovu konstrukci lze popsat také pomocí grupového homomorfismu $f:(\{1,-1\},\cdot )\to (\{0,1\},+)$.

Označme ${𝑭}_n$ matici typu $n\times 2^n$, jejíž sloupce se skládají ze všech možných čísel ve dvojkové soustavě s nejvýše $n-1$ ciframi uspořádaných vzestupně. Uvedenou matici ${𝑭}_n$ lze popsat rekurentním předpisem:

${𝑭}_1=\left(\begin{array}{cc}0& 1\end{array}\right)$

${𝑭}_k=\left(\begin{array}{cc}{𝑭}_{k-1}& {𝑭}_{k-1}\\ 0& 1\end{array}\right)$

Bloky $0$ a $1$ jsou typu $1\times 2^{k-1}$.

Matematickou indukcí lze ukázat, že obraz Hadamardovy matice pod výše uvedeným homomorfismem je dán vztahem:

$f({𝑯}_{2^k})={𝑭}_k^{\mathsf{\text{T}}}{𝑭}_k$

Z uvedené konstrukce vyplývá, že řádky Hadamardovy matice ${𝑯}_{2^k}$ odpovídají lineárnímu samoopravnému kódu délky $2^k$ dimenze $k$ a minimální vzdálenosti $2^{k-1}$ s generující maticí ${𝑭}_k$. Uvedený kód se nazývá Walshův kód. Hadamardův kód je naproti tomu zkonstruován z Hadamardovy matice ${𝑯}_{2^k}$ mírně odlišným postupem.

Hadamardova domněnka

V teorii Hadamardových matic je za hlavní otevřenou otázkou považována existence Hadamardových matic všech možných řádů. Hadamardova domněnka tak zní, že pro každé přirozené číslo $k$ existuje Hadamardova matice řádu $4k$. Hadamardova domněnka byla také připisována Paleymu, ačkoli i jiní před Paleyho prací ji nepřímo zvažovali.

Ze zobecnění Sylvesterovy konstrukce vyplývá, že pokud jsou ${𝑯}_n$ a ${𝑯}_m$ Hadamardovy matice řádů $n$ a $m$, tak potom ${𝑯}_n\otimes H_m$ je Hadamardova matice řádu $nm$. Tento vztah lze využít ke konstrukci Hadamardových matic vyšších řádů, jakmile jsou známy matice menších řádů.

Sylvesterova konstrukce z roku 1867 dává návod pro sestavení Hadamardových matic řádu 1, 2, 4, 8, 16, 32 atd. Hadamard sestavil v roce 1893 Hadamardovy matice řádů 12 a 20. Raymond Paley objevil v roce 1933 konstrukci využívající konečných těles, pomocí níž lze sestrojit Hadamardovy matice řádu $q+1$ pro každé prvočíslo $q$, které je kongruentní 3 modulo 4, a také Hadamardovy matice řádu $2(q+1)$, pro všechna prvočísla $q\equiv 1(\mathrm{mod}4)$.

Hadamardova matice řádu 92 je nejmenší, kterou nelze sestrojit kombinací Sylvesterových a Paleyových metod. Baumert, Golomb a Hall z Jet Propulsion Laboratory využili v roce 1962 Wiliamsonovu konstrukci, díky níž pomocí počítače sestavili Hadamardovu matici řádu 92 i mnoha dalších řádů. Nyní je známo mnoho dalších metod pro konstrukci Hadamardových matic.

V roce 2005 Hadi Kharaghani a Behruz Tayfeh-Rezaie publikovali svou konstrukci Hadamardovy matice řádu 428. Nejmenší řád, pro který není v současnosti (2014) známa žádná Hadamardova matice, je 668.

Do roku 2014 bylo 12 násobků 4 méně než 2000, pro které nebyla známa žádná Hadamardova matice tohoto řádu. Jsou to: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 a 1964.

Ekvivalence a jednoznačnost

Dvě Hadamardovy matice jsou považovány za ekvivalentní, pokud lze jednu získat z druhé změnou znamének v řádku či sloupci nebo výměnou řádků či sloupců. Hadamardovy matice řádu 1 jsou si navzájem ekvivalentní (mají jen jednu třídu ekvivalence) a totéž platí i pro řády 2, 4, 8 a 12. Hadamardovy matice řádu 16 mají 5 tříd ekvivalence, řád 20 má 3 třídy, řád 60 má 24 tříd a řád 28 má 487 tříd. Pro řády 32, 36 a 40 počet tříd přesahuje miliony. Při použití hrubšího pojmu ekvivalence, který také umožňuje transpozici, mají Hadamardovy matice řádu 16 celkem 4 třídy, řád 20 má 3 třídy, řád 24 má 36 tříd a řádu 28 má 294 tříd.

Hadamardovy matice jsou také jednoznačně obnovitelné v následujícím smyslu: Pokud je z Hadamardovy matice $𝑯$ řádu $n$ náhodně odstraněno $𝑶(n^2/\log n)$ prvků, potom lze skoro jistě obnovit původní matici $𝑯$. Algoritmus obnovy má stejnou výpočetní složitost jako součin matic.

Zvláštní případy

Šikmé Hadamardovy matrice

Hadamardova matice $𝑯$ je šikmá, pokud pro ni platí: ${𝑯}^{\mathsf{\text{T}}}+𝑯=2\mathrm{I}$. Šikmá Hadamardova matice zůstane šikmou i po změně znamének v libovolném řádku a jemu odpovídajícím sloupci. Šikmé Hadamardovy matici mohou být proto normalizovány tak, aby všechny prvky v prvním řádku byly rovny 1.

Reid a Brown v roce 1972 ukázali, že dvojitě regulární turnaj řádu $n$ existuje, právě když existuje šikmá Hadamardova matice řádu $n+1$. V matematickém turnaji řádu $n$ hraje každý z $n$ hráčů jeden zápas proti každému z ostatních hráčů, přičemž každý zápas vede k výhře jednoho z hráčů a prohře druhého. Turnaj je regulární, pokud každý hráč vyhraje stejný počet zápasů. Turnaj je dvojitě regulární, pokud počet soupeřů poražených dvěma různými hráči je zároveň stejný pro všechny dvojice hráčů. Protože každý z $n(n-1)-2$ odehraných zápasů vede k výhře jednoho z hráčů, každý hráč vyhraje $(n-1)/2$ zápasů (a prohraje stejný počet). Protože každý z $(n-1)/2$ hráčů poražených daným hráčem také prohrává s $(n-3)/2$ dalšími hráči, počet dvojic hráčů $(i,j)$ takových, že $j$ prohraje jak s $i$, tak s daným hráčem je $(n-1)(n-3)/4$. Stejný výsledek by měl být získán, pokud se dvojice počítají obráceně: daný hráč a kterýkoli z $n-1$ ostatních hráčů společně porazí stejný počet společných soupeřů, jmenovitě $(n-3)/4$. Šikmá Hadamardova matice se získá zavedením dalšího hráče, který porazí všechny původní hráče, a poté vytvořením matice s řádky a sloupci označenými hráči podle pravidla, že řádek $i$, sloupec $j$ obsahuje 1, pokud $i=j$ nebo $i$ porazí $j$ a −1, pokud $j$ porazí $i$. Tento předpis interpretován v opačném směru vede ke konstrukci dvojitě regulárního turnaje ze šikmé Hadamardovy matice, za předpokladu, že šikmá Hadamardova matice je normalizována tak, že všechny prvky prvního řádku jsou rovny 1.

Regulární a cirkulační Hadamardovy matice

Regulární Hadamardovy matice jsou reálné Hadamardovy matice, jejichž řádkové i sloupcové součty jsou všechny stejné. Pro existenci regulární Hadamardovy matice je nutné, aby její řád byl čtvercové číslo. Každá cirkulační matice je regulární. Aby mohla cirkulační Hadamardova matice existovat, musela by mít řád, který by byl nejen druhou mocninou nějakého přirozeného čísla, ale pro $n>1$ by musel být ve tvaru $4k^2$ pro liché $k$.

Domněnka o cirkulačních Hadamardových maticích však tvrdí, že kromě řádů 1 a 4 žádné takové matice neexistují. Domněnka byla ověřena až na 26 hodnot pro všechna lichá $k<10^4$.

Použití v praxi

• Olivia MFSK – radioamatérský digitální protokol navržený pro práci v obtížných podmínkách (nízký odstup signálu od šumu plus vícecestné šíření) na pásmech krátkých vln.
• Vyvážená opakovaná replikace (Balanced repeated replication, BRR) - technika používaná statistiky k odhadu rozptylu statistického odhadu.
• Spektrometrie kódované apertury – přístroj pro měření spektra světla. Maska používaná v kódovaných aperturových spektrometrech je často variantou Hadamardovy matice.
• Sítě se zpožděním zpětné vazby – Digitální zařízení pro dozvuk, která používají Hadamardovy matice k míchání hodnot vzorků.
• Plackettův–Burmanův návrh experimentů pro zkoumání závislosti nějaké měřené veličiny na řadě nezávislých proměnných.
• Robustní návrh parametrů pro zkoumání vlivu šumu na odezvy.
• Komprimované snímání pro zpracování signálu a nedourčené soustavy lineárních rovnic.
• Kvantová Hadamardova brána pro kvantové výpočty a Hadamardova transformace pro kvantové algoritmy.

Odkazy

Související články

• Kombinatorický design
• Walshova matice

Externí odkazy

• Šablona:Commonscat