Don't take life too seriously: it's just a temporary situation

Matrici di Hadamard (numero di)

Matematica combinatoria 

Una matrice di Hadamard Hn di ordine n è una matrice contenente esclusivamente 1 e –1 e tale che HnHnT = nI, ossia tale che il prodotto con la sua trasposta sia una matrice con valori n sulla diagonale e 0 altrove.

Alcuni esempi: [1], Matrice di Hadamard di ordine 2, Matrice di Hadamard di ordine 2.

 

Le matrici prendono il nome dal matematico francese Jacques Salomon Hadamard (Versailles, Francia, 8/12/1865 – Parigi, 17/10/1963), anche se furono studiate già da James Joseph Sylvester (Londra, 3/9/1814 – 15/3/1897) nel 1867.

Sylvester trovò un semplice modo per costruire una matrice di ordine 2n a partire da una Matrice H di ordine n: Schema per la costruzione di una matrice di Hadamard di ordine 2n; partendo dalla matrice di ordine 2 mostrata sopra poté quindi costruire matrici di ordine 2n e dimostrare che le matrici di Hadamard sono infinite.

Le matrici costruite col metodo di Sylvester hanno la particolarità che i numeri di cambiamento di segno tra un elemento e il successivo sulle righe (o colonne) sono gli interi da 0 a 2n – 1, ciascuno occorrendo esattamente una volta. Per esempio, nella matrice di ordine 4 mostrata i numeri di cambiamenti di segno scorrendo le righe sono: 0, 3, 1, 2.

 

Tra le proprietà interessanti delle matrici di Hadamard:

  • due righe (colonne) distinte sono ortogonali, ossia il loro prodotto scalare è nullo;

  • due righe (o colonne) qualsiasi differiscono in metà dei valori delle caselle corrispondenti (ossia con lo stesso indice);

  • il determinante di una matrice di Hadamard di ordine n è Determinante di una matrice di Hadamard di ordine n;

  • una matrice di Hadamard di ordine n contiene esattamente Numero di occorrenze di uno dei valori in una matrice di Hadamard di ordine n volte un valore e Numero di occorrenze di uno dei valori in una matrice di Hadamard di ordine n volte quello di segno opposto;

  • permutando righe o colonne di una matrice di Hadamard o moltiplicando una riga o una colonna per –1 si ottiene un’altra matrice di Hadamard, considerata equivalente a quella originale

  • le matrici di Hadamard simmetriche e con somme lungo righe e colonne uguali, dette “regolari”, hanno ordine della forma 4m2 e somma di ogni riga e colonna uguale a 2m o –2m.

 

Una matrice di Hadamard può essere “normalizzata”, scambiando righe e colonne e invertendo i segni lungo righe e colonne, in modo da avere tutti 1 nella prima riga e colonna. In una matrice normalizzata in ogni riga (colonna), tranne le prima, gli elementi hanno per metà segno positivo e per metà negativo e due righe (colonne) qualsiasi, sempre escludendo la prima, hanno metà dei valori 1 e metà dei valori –1 nella stessa posizione.

 

Hadamard le studiò nel risolvere il problema dei determinanti massimi nel 1893. Hadamard dimostrò, infatti, che una matrice di ordine n contenente numeri complessi non superiori a 1 in valore assoluto ha determinante non superiore a Massimo valore assoluto del determinante di una matrice di ordine n contenente elementi non superiori a 1 in valore assoluto e che questo valore si può raggiungere solo per le matrici di Vandermonde generate utilizzando radici n-esime dell’unità per i valori di x1, x2, … xn. Le matrici di Vandermonde hanno la forma Matrice di Vandermonde di ordine n e determinante Determinante di una matrice di Vandermonde di ordine n.

Tra le matrici di Vandermonde, quelle di Hadamard sono le uniche contenenti esclusivamente 1 e –1 e quindi sono le uniche matrici contenenti esclusivamente 1 e –1 che hanno il massimo possibile valore assoluto del determinante.

 

Se i valori degli elementi di una matrice di ordine n sono esclusivamente 0 e 1, il valore massimo del determinante è Massimo valore assoluto del determinante di una matrice di ordine n contenente elementi uguali a 0 o 1 (D.K. Faddeev e I.S. Sominskii, 1965). Se i valori sono esclusivamente –1, 0 e 1, il valore massimo del determinante resta Massimo valore assoluto del determinante di una matrice di ordine n contenente elementi uguali a –1, 0 o 1 (H. Ehlich, 1964).

 

Possono esistere matrici di Hadamard solo se n è 1, 2 o un multiplo di 4; Hadamard stesso avanzò la congettura che esistano per tutti questi ordini e costruì esempi di ordine 12 e 20.

 

Nel 1933 Raymond Edward Alan Christopher Paley (Bournemouth, Inghilterra, 7/1/1907 – Deception Pass, Canada, 7/4/1933) scoprì un modo per costruire matrici di Hadamard per n multiplo di 4 e della forma 2e(pm + 1), con e e m non negativi e p primo dispari.

In seguito furono trovati numerosi modi per costruire matrici di Hadamard di varie dimensioni (v. congettura di Hadamard). Il minimo ordine non coperto dalle costruzioni note è 92; la prima matrice di Hadamard di ordine 92 fu costruita da L. Baumert, S.W. Golomb e M. Hall nel 1962.

K. Sawade costruì la prima matrice di ordine 268 nel 1985.

All’inizio del millennio il minimo caso non risolto era l’ordine 428; La prima matrice di Hadamard di ordine 428 fu costruita nel 2005 da Hadi Kharaghani e Behruz Tayfeh-Rezaie.

In seguito furono costruite altre matrici per vari ordini non coperti dalle costruzioni di Sylvester e Paley; i casi non risolti minori di 2000 sono: 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 e 1964.

 

Le matrici di Hadamard sono importanti per il loro utilizzo nei codici a correzione d’errore, in particolare il codice di Reed – Muller.

I vantaggi che offrono codici di questo genere sono la capacità di correggere errori (la massima teoricamente possibile a parità di lunghezza) e la possibilità di eseguire la codifica usando solo addizioni e non moltiplicazioni, più lente, soprattutto sui calcolatori di potenza limitata. Per esempio, le missioni spaziali Mariner e Voyager utilizzavano un codice a correzione d’errore basato sulle matrici di Hadamard di ordine 32 per rimediare agli inevitabili errori dovuti alla trasmissione interplanetaria.

Tra le possibili applicazioni al di fuori della matematica, segnalo l’uso per creare schemi di tessitura.

 

Non è stato stabilito per quali ordini possano esistere matrici di Hadamard simmetriche con tutti gli elementi sulla diagonale principale uguali; si sa che esistono se l’ordine è una potenza di 2 (Wallis) o della forma 4n2, con n uguale a:

  • 3, 5, 6 o 7 (S.S. Shrikhande, 1952);

  • 9, 25, 36, 49 (Jennifer Seberry Wallis, 1976);

  • 169, 841, 2601;

  • (p – 1)2, se p è una potenza di un primo e p ≡ 3 mod 4.

Inoltre partendo da una matrice di Hadamard di ordine 4n, se ne può costruire una simmetrica e con tutti gli elementi sulla diagonale principale uguali di ordine 16n2 e partendo da due matrici di ordine 4m2 e 4n2 con la stessa proprietà e regolari, se ne può costruire una con le stesse proprietà di ordine 4m2n2.

 

Un altro problema sulle matrici di Hadamard è quanto possa essere la massima somma σ(n) degli elementi di una matrice di ordine n. Alcuni risultati noti:

  • σ(n) = n, per n uguale a 1, 2 e 4;

  • σ(8) = 20;

  • Limite superiore per il valore di σ(n);

  • se n = (2k + 1)2 + 3, ossia se è un quadrato dispari più 3, Limite superiore per il valore di σ(n) (N. Farmakis e S. Kounias 1897);

  • se n = 4k(k – 1), σ(n) ≤ 4(k – 1)2(2k + 1) (N. Farmakis, H. Kharaghani e S. Kounias);

  • Limite superiore per il valore di σ(n), dove Formula per la definizione di t(n), se Massimo intero non superiore alla radice quadrata di n è pari, Formula per la definizione di t(n) altrimenti (J. Hammer, R. Levingston e Seberry, 1978);

  • σ(2n) ≥ n;

  • σ(2n) ≥ 2σ(n) + 4;

  • σ(mn) ≥ σ(m)σ(n);

  • se esiste una matrice di Hadamard di ordine 2n, σ(4n2) = 8n3.

 

Due matrici di Hadamard si dicono equivalenti se una può essere trasformata nell’altra trasponendola o scambiando righe o colonne o invertendo i segni dei valori lungo righe o colonne. Determinare il numero di matrici di Hadamard non equivalenti per un valore di n fissato è un compito piuttosto difficile. La tabella mostra i risultati noti.

n

Numero di matrici

1

1

2

1

4

1

8

1

12

1

16

5

20

3

24

60

28

487

32

13710027

60

3

 

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.