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à modifica

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 modifica

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$ . ^[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.

Costruzione Alternativa modifica

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 modifica

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. ^[2]

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$ . ^[3]

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 modifica

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 modifica

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 modifica

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 modifica

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

Note modifica

^ J.J. Sylvester. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers. Philosophical Magazine, 34:461-475, 1867
^ J. Hadamard. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques, 17:240-246, 1893
^ R. E. A. C. Paley. On orthogonal matrices. Journal of Mathematics and Physics, 12:311–320, 1933.

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.

Altri progetti modifica

Wikimedia Commons contiene immagini o altri file sulla matrice di Hadamard

Collegamenti esterni modifica

matrice di Hadamard, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
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

[1] J.J. Sylvester. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers. Philosophical Magazine, 34:461-475, 1867

[2] J. Hadamard. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques, 17:240-246, 1893

[3] R. E. A. C. Paley. On orthogonal matrices. Journal of Mathematics and Physics, 12:311–320, 1933.

[1]

[2]

[3]