Matrice di Hadamard

In matematica, una matrice di Hadamard è una matrice quadrata le cui entrate sono ${\displaystyle +1}$ o ${\displaystyle -1}$ e le cui righe sono mutuamente ortogonali. Ciò vuol dire che ogni coppia di righe diverse, in una matrice di Hadamard, rappresenta due vettori perpendicolari. Tali matrici sono utilizzate in codici di correzione degli errori, come il codice di Reed–Muller.

Le matrici di Hadamard sono anche usate nella replica a ripetizione bilanciata (Balanced Repeated Replication, in sigla BRR), adoperata dagli statistici per stimare la varianza di un parametro indice.

Queste matrici prendono il nome dal matematico francese Jacques Hadamard (1865-1963). Sono usate per rappresentare le porte di Hadamard in computazione quantistica.

Dalla definizione segue che una matrice di Hadamard ${\displaystyle H}$ di ordine ${\displaystyle n}$ soddisfa la relazione seguente

${\displaystyle H^{\mathrm {T} }H=nI_{n}}$

dove I_n è la matrice identità di ordine ${\displaystyle n}$. Quindi, risulta ${\displaystyle \det H=\pm n^{n/2}}$.

Supponiamo che ${\displaystyle M}$ sia una matrice complessa di ordine ${\displaystyle n}$, le cui entrate soddisfano le limitazioni |M_ij| ≤1. Allora la diseguaglianza di Hadamard afferma che

${\displaystyle |\operatorname {det} (M)|\leq n^{n/2}.}$

L'eguaglianza vale per una matrice reale ${\displaystyle M}$ se e solo se ${\displaystyle M}$ è una matrice di Hadamard.

L'ordine di una matrice di Hadamard deve essere ${\displaystyle 1}$, ${\displaystyle 2}$ o un multiplo di ${\displaystyle 4}$.

Esempi di matrici di Hadamard furono in principio costruiti dal matematico inglese James Joseph Sylvester nel 1867 (cfr. Matrice di Sylvester). Sia ${\displaystyle H}$ una matrice di Hadamard di ordine ${\displaystyle n}$, allora la matrice di partizione

${\displaystyle {\begin{bmatrix}H&H\\H&-H\end{bmatrix}}}$

è una matrice di Hadamard di ordine ${\displaystyle 2n}$. Questa osservazione può essere applicata ripetutamente e porta alla successiva sequenza di matrici, dette anche matrici di Walsh.

${\displaystyle H_{1}={\begin{bmatrix}1\end{bmatrix}}}$

${\displaystyle H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}$

e

${\displaystyle H_{2^{k}}={\begin{bmatrix}H_{2^{k-1}}&H_{2^{k-1}}\\H_{2^{k-1}}&-H_{2^{k-1}}\end{bmatrix}}=H_{2}\otimes H_{2^{k-1}}}$

per ${\displaystyle 2\leq k\in N}$, dove ${\displaystyle \otimes }$ indica il prodotto di Kronecker di matrici.

In questo modo Sylvester costruì matrici di Hadamard di ordine 2^k, per ogni intero naturale ${\displaystyle k}$. ^[1]

Le matrici di Sylvester hanno numerose proprietà speciali: sono simmetriche e a traccia nulla; le entrate nella prima colonna e nella prima riga sono tutte positive; le entrate in tutte le altre righe e colonne sono equamente distribuite fra valori positivi e negativi; esse sono strettamente connesse alle funzioni di Walsh.

Se si mappano gli elementi della matrice di Hadamard usando l'omomorfismo di gruppi ${\displaystyle \{1,-1,\times \}\mapsto \{0,1,\oplus \}}$, si può descrivere una costruzione alternativa delle matrici di Hadamard-Sylvester. In primo luogo si considera la matrice ${\displaystyle F_{n}}$, la matrice ${\displaystyle n\times 2^{n}}$ la cui colonna consiste tutta in numeri ${\displaystyle n\times 2^{n}}$-bit sistemati in ordine crescente. Si può definire ${\displaystyle F_{n}}$ ricorsivamente mediante la seguente formula

${\displaystyle F_{1}={\begin{bmatrix}0&1\end{bmatrix}}}$

${\displaystyle F_{n}={\begin{bmatrix}0_{1\times 2^{n-1}}&1_{1\times 2^{n-1}}\\F_{n-1}&F_{n-1}\end{bmatrix}}}$

Si può dimostrare per induzione che l'immagine della matrice di Hadamard sotto l'omomorfismo di cui sopra è data da

${\displaystyle H_{2^{n}}=F_{n}^{T}F_{n}}$

Questa costruzione dimostra che le colonne della matrice di Hadamard ${\displaystyle H_{2^{n}}}$ possono essere viste come una lunghezza ${\displaystyle 2^{n}}$ di un codice lineare di rango ${\displaystyle n}$, e distanza minima ${\displaystyle 2^{n-1}}$ con matrice generatrice ${\displaystyle F_{n}.}$

Questo codice è anche detto codice di Walsh.

La più importante questione aperta nella teoria delle matrici di Hadamard è quella di esistenza. La congettura di Hadamard afferma che esiste una matrice di Hadamard di ordine ${\displaystyle 4k}$ per ogni intero positivo ${\displaystyle k}$.

La costruzione di Sylvester del 1867 porta a matrici di Hadamard di ordine ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle 4}$, ${\displaystyle 8}$,${\displaystyle 16}$,${\displaystyle 32}$, ... Le matrici di Hadamard di ordine ${\displaystyle 12}$ e ${\displaystyle 20}$ furono successivamente costruite da Hadamard nel 1893. ^[2]

In seguito, nel 1933, Raymond Paley mostrò come costruire una matrice di Hadamard di ordine ${\displaystyle q+1}$, dove ${\displaystyle q}$ è una qualsiasi potenza prima uguale a ${\displaystyle 3}$ modulo ${\displaystyle 4}$. ^[3]

Paley costruì anche matrici di ordine ${\displaystyle 2(q+1)}$ per potenze prime ${\displaystyle q}$ che sono uguali a 1 modulo 4. Il suo metodo utilizza i campi finiti. La teoria di Hadamard potrebbe essere attribuita a Raymond Paley. Il più piccolo ordine che non può essere costruito mediante una combinazione dei metodi di Sylvester e Paley è ${\displaystyle 92}$. Una matrice di Hadamard di questo ordine fu trovata nel 1962 mediante l'uso del computer da parte di Baumert, Golomb, e Hall, i quali usarono una costruzione, dovuta a Williamson, che portò a ordini successivi. Oggi sono noti molti altri metodi per costruire matrici di Hadamard.

Hadi Kharaghani e Behruz Tayfeh-Rezaie annunciarono il 21 giugno 2004 di aver costruito una matrice Hadamard di ordine 428. Come conseguenza, il più piccolo ordine per cui nessuna matrice di Hadamard è ad oggi nota è 668.

Due matrici Hadamard sono considerate equivalenti se una può essere ottenuta dall'altra attraverso negazione dalle righe, negazione delle colonne, scambio di righe e scambio di colonne. A meno dell'equivalenza relativa alle suddette trasformazioni, vi è un'unica matrice di Hadamard di ordini ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle 4}$,${\displaystyle 8}$ e ${\displaystyle 12}$. Ci sono ${\displaystyle 5}$ matrici non equivalenti di ordine ${\displaystyle 16}$, ${\displaystyle 3}$ di ordine ${\displaystyle 20}$, ${\displaystyle 60}$ di ordine ${\displaystyle 24}$, e ${\displaystyle 487}$ di ordine ${\displaystyle 28}$. Sono noti milioni di matrici non equivalenti degli ordini ${\displaystyle 32}$, ${\displaystyle 36}$ e ${\displaystyle 40}$.

Una matrice di Hadamard ${\displaystyle H}$ è diagonale se ${\displaystyle H^{T}+H=2I}$.

Reid e Brown nel 1972 mostrarono che esiste un grafo torneo doppiamente regolare di ordine ${\displaystyle n}$ se e solamente se esiste una matrice di Hadamard diagonale di ordine ${\displaystyle n+1}$.

Nella letteratura matematica sono state molte le generalizzazioni e i casi speciali di matrici di Hadamard su cui si è studiato. Una generalizzazione fondamentale è quella di matrice pesata per la quale come entrate della matrice sono permessi anche zeri e si richiede che il numero dei ${\displaystyle +1}$ e ${\displaystyle -1}$ costituisca una costante per tutte le linee della matrice.

Un'altra generalizzazione sono le matrici complesse di Hadamard in cui le entrate sono numeri complessi di modulo unitario e per cui la matrice soddisfa la relazione

${\displaystyle HH^{*}=nI_{n}}$

dove H^* denota la matrice trasposta coniugata di ${\displaystyle H}$. Le matrici complesse di Hadamard sono presenti nello studio delle algebre degli operatori e della teoria del calcolo quantistico.

Le matrici di Hadamard di tipo Butson sono un caso speciale di matrici complesse di Hadamard in cui le entrate sono q^th radici dell'unità. Il termine '"matrici complesse di Hadamard'" è stato utilizzato da qualche autore per riferirsi nello specifico al caso in cui ${\displaystyle q=4}$. Un caso particolare di matrici reali di Hadamard sono le matrici circolanti di Hadamard. Una tale matrice quadrata è definita dalla sua prima riga, e ogni altra riga è una permutazione ciclica della sua riga precedente. Le matrici Hadamard Circulant di ordini ${\displaystyle 1}$ e ${\displaystyle 4}$ sono note e si suppone che non ne esiste di alcun altro ordine.

• Olivia MFSK - un protocollo digitale radioamatoriale progettato per consentire la comunicazione in condizioni difficoltose in bande a onde corte (con basso rapporto segnale-rumore e inoltre con propagazione multidirezionale).

• H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428 Archiviato il 22 luglio 2011 in Internet Archive., 2004.
• S. Georgiou, C. Koukouvinos, J. Seberry, Hadamard matrices, orthogonal designs and construction algorithms, pp. 133–205 in DESIGNS 2002: Further computational and constructive design theory, Kluwer 2003.
• K.B. Reid & E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices, J. Combinatorial Theory A 12 (1972) 332-338.

• Wikimedia Commons contiene immagini o altri file sulla matrice di Hadamard

• Hadamard, matrice di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Hadamard Matrix, su MathWorld, Wolfram Research.
• (EN) Hadamard matrix, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• Skew Hadamard matrices of all orders up to 100, including every type with order up to 28;
• N.J.A. Sloane's Library of Hadamard Matrices, su research.att.com.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica