Matrice di Hadamard

Da Wikipedia, l'enciclopedia libera.

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

Proprietà[modifica | modifica wikitesto]

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

 H^{\mathrm{T}} H = n I_n \

dove   In   è 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   |Mij| ≤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 | modifica wikitesto]

Esempi di matrici di Hadamard furono in principio costruiti dal matematico inglese James Joseph Sylvester nel 1867. 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 \le k \in N ,  dove  \otimes  indica il prodotto di Kronecker di matrici.

In questo modo Sylvester costruì matrici di Hadamard di ordine   2k,  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 | modifica wikitesto]

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^TF_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 | modifica wikitesto]

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 | modifica wikitesto]

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 | modifica wikitesto]

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 | modifica wikitesto]

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

H H*= n In

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   qth  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 | modifica wikitesto]

  • 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 | modifica wikitesto]

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


Collegamenti esterni[modifica | modifica wikitesto]


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