Matrice di Hadamard
# Matrice di Hadamard

In matematica, una matrice di Hadamard è una matrice quadrata le cui entrate sono $+1$ o $-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.

## Proprietà

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

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

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

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

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

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

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

## Costruzione di Sylvester

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

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

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

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

e

    $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 $2\leq k\in N$, dove $\otimes$ indica il prodotto di Kronecker di matrici.

In questo modo Sylvester costruì matrici di Hadamard di ordine $2^k,$ per ogni intero naturale $k$.

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.

## Costruzione Alternativa

Se si mappano gli elementi della matrice di Hadamard usando l'omomorfismo di gruppi $\{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 $F_{n}$, la matrice $n\times 2^{n}$ la cui colonna consiste tutta in numeri $n\times 2^{n}$-bit sistemati in ordine crescente. Si può definire $F_{n}$ ricorsivamente mediante la seguente formula

    $F_{1}={\begin{bmatrix}0&1\end{bmatrix}}$
    $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

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

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

Questo codice è anche detto codice di Walsh.

## La congettura di Hadamard

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 $4k$ per ogni intero positivo $k$.

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

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

Paley costruì anche matrici di ordine $2(q+1)$ per potenze prime $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 è $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.

## Equivalenza di matrici di Hadamard

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 $1$, $2$,$4$,$8$ e $12$. Ci sono $5$ matrici non equivalenti di ordine $16$, $3$ di ordine $20$, $60$ di ordine $24$, e $487$ di ordine $28$. Sono noti milioni di matrici non equivalenti degli ordini $32$, $36$ e $40$.

## Matrici diagonali di Hadamard

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

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

## Generalizzazione e casi speciali

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 $+1$ e $-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

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

dove $H^*$ denota la matrice trasposta coniugata di $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 $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 $1$ e $4$ sono note e si suppone che non ne esiste di alcun altro ordine.

## Applicazioni pratiche

* 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).
