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

Hadamard (congettura di)

Congetture  Matematica combinatoria 

Una matrice di Hadamard Hn di ordine n è una matrice quadrata 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 4.

 

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.

 

Le righe di una matrice di Hadamard sono ortogonali a coppie, vale a dire che il prodotto scalare tra due righe diverse è zero e lo stesso vale per le colonne.

Una matrice di Hadamard ha il massimo determinante possibile tra quelle dello stesso ordine n contenenti esclusivamente 1 e –1: per una matrice M del genere, infatti, vale Limite superiore per valore assoluto del determinante di una matrice contenente solo 1 e –1, mentre per le sole matrici di Hadamard Valore assoluto del determinante di una matrice di Hadamard.

Due matrici di Hadamard si dicono equivalenti se una si può ottenere dall’altra permutando righe e colonne di una matrice e invertendo il segno dei numeri di una riga o colonna. Ogni matrice di Hadamard è equivalente a una, detta normalizzata, che ha tutti gli elementi della prima riga e della prima colonna uguali a 1. In una matrice di Hadamard normalizzata di ordine 2n tutte le righe tranne la prima e tutte le colonne tranne la prima contengono n volte 1 e altrettante volte –1.

 

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

 

Le matrici di Hadamard complesse sono una generalizzazione delle matrici di Hadamard e contengono solo 1, –1, i e – i. Possono esistere solo se l’ordine è 1, 2 o un multiplo di 4; la versione complessa della congettura è che come le matrici di Hadamard esistano per tutti questi ordini.

 

Sylvester dimostrò che se H è una matrice di Hadamard di ordine n, Matrice di Hadamard di ordine 2nè una matrice di Hadamard di ordine 2n e partendo dalla matrice di Hadamard di ordine 2 mostrata sopra poté quindi costruire matrici di ordine 2n e dimostrare che le matrici di Hadamard sono infinite.

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 altri termini, se pm è della forma 4k + 1 ed è una potenza di un primo, si può costruire una matrice di ordine 2(p + 1), mentre se pm è una potenza di un primo della forma 4k + 3, si può costruire una matrice di ordine p + 1.

In seguito vennero scoperti altri metodi per costruire matrici di ordine di particolari forme; per esempio sono stati trovati metodi per costruire matrici di Hadamard di ordine:

  • 3n, se n è della forma 4k + 3 ed è una potenza di un primo ed esiste una matrice di Hadamard di ordine 2n – 3 (M. Miyamoto, 1991);

  • 4n, per 3 ≤ n ≤ 33 e n = 37,43,67, 113, 127, 157, 163, 181, 241;

  • 4n, se n e n – 2 sono potenze di primi e n è della forma 4k + 1 (E. Spence, 1975);

  • 4n, se n è una potenza di un primo ed esiste un intero m maggiore di zero tale che (n – 2^m – 1) / 2^m sia una potenza di un primo dispari (E. Spence, 1975);

  • 4n, se n è della forma 4k + 1 ed è una potenza di un primo ed esiste una matrice di Hadamard di ordine n – 1 (M. Miyamoto, 1991);

  • 4n, se n è della forma 8k + 1 ed è una potenza di un primo ed esiste una matrice di Hadamard di ordine (n – 1) / 2 (M. Yamada, 1989);

  • 8n, se n e n – 2 sono potenze di primi e n è della forma 4k + 3 (E. Spence, 1975);

  • n2, se esiste una matrice di Hadamard di ordine n, (J.M. Goethals e J.J. Seidel, 1967);

  • n2, se n è della forma 4k + 3 ed è una potenza di un primo (J. Seberry e A.L. Whiteman, 1988);

  • 4n2, per n pari e n ≤ 210;

  • 4n2, per n della forma 9m o 25 • 9m e m ≥ 0;

  • 4(n2 + n + 1), se n2 + n + 1 è un primo della forma 8k + 1 (E. Spence, 1975);

  • 4(n2 + n + 1), se n2 + n + 1 è un primo della forma 8k + 3, 8k + 5 o 8k + 7 e n è una potenza di un primo (E. Spence, 1975);

  • 4(n2 + n + 1), se 2n2 + 2n + 3 e n sono potenze di primi (E. Spence, 1975);

  • 2(n2(n – 2) + 1), se n è della forma 4k + 3 e n e n – 2 sono potenze di primi (R. Mathon, 1978);

  • n^2 * (n + 1) / 2, se n è della forma 4k + 1 ed è una potenza di un primo (J. Seberry);

  • n^2 * (n + 1) / 4, se n è della forma 4k + 3 ed è una potenza di un primo (J. Seberry);

  • 8 • 49 • 3n, per n ≥ 0;

  • 2(5 • 92n + 1 + 1), per n ≥ 0 (J. Seberry e A.L. Whiteman, 1988);

  • 9m(n + 1)n2, per m ≥ 0, se n è della forma 4k + 3 ed è una potenza di un primo;

  • 4 • pn, per p = 17, 29, 37, 41, 53, 61, 101 e n ≥ 0;

  • 4 • pn, 4 • pn + 1, 4 • pn + 2, 8 • pn + 3, per p = 7, 11 e n ≥ 0;

  • 4 • pn, per p primo della forma 2a10b26c + 1 e n ≥ 0;

  • Prodotto di m(k) + 1 per k da 1 a n, se i vari mn sono della forma 4k + 3 e potenze di primi (R.E.A.C. Paley, 1933).

 

Analoghi risultati furono ottenuti per le matrici di Hadamard complesse; in particolare:

  • esiste una matrice di Hadamard complessa di ordine 4n(4n + 1) per n ≥ 0 (R Kharaghani e J. Seberry, 1990);

  • esistono matrici di Hadamard complesse di ordine 2n, per n = 33, 39, 53, 73, 81, 83, 89, 93, 101, 105, 109, 113, 125, 137, 149, 153, 173, 189, 193, 197, 233, 241, 243, 257, 277, 281, 293.

  • se esistono una matrice di Hadamard complessa di ordine 2n e una matrice di Hadamard di ordine 4m, si può costruire una matrice di Hadamard di ordine 8mn (R.J. Turyn, 1970);

  • se esistono due matrici di Hadamard complesse di ordine m e n, se ne può costruire una di ordine mn (R.J. Turyn, 1970);

 

I metodi d’attacco alla congettura possono seguire due strade: la prima consiste nel trovare una costruzione valida per matrici di ordine 4n, per qualsiasi n.

Il più importante risultato in questa direzione è la dimostrazione di Jennifer Seberry Wallis del 1976, che per ogni intero dispari q, esiste un intero m non superiore a 2log2(q – 3), tale che è possibile costruire una matrice di Hadamard di ordine 2mq e quindi, grazie al metodo di Sylvester, di ogni ordine 2nq con n > m. I migliori limiti noti per q primo sono m ≤ log2((q – 1)(q – 5)) + 1 per q ≡ 1 mod 4 e m ≤ log2((q – 3)(q – 7)) – 1 per q ≡ 3 mod 4.

La dimostrazione naturalmente rafforzò negli esperti la convinzione che la congettura sia vera.

 

La seconda strada si basa sull’idea di trovare una costruzione solo per matrici di ordine 4p, per p primo, poi un metodo per costruire una matrice di ordine 4mn a partire da una di ordine 4n e una di ordine 4m. Per la prima parte i migliori risultati sono quelli di Paley e della Wallis, per la seconda è facile dimostrare che a partire da una matrice di ordine m e una di ordine n si può costruire una matrice di ordine mn, ma in questo modo ci si ritrova con potenze di due sempre crescenti nell’ordine della matrice finale.

Sono note matrici di Hadamard di ordine 12, 20 e 28, quindi per si possono costruire per gli ordini delle forme 2n3, 2n5 e 2n7, per n > 1.

S.S. Agayan e Sarukbanyan (1985) dimostrarono che a partire da una matrice di ordine 2mp e una di ordine 2nq se ne può costruire una di ordine 2m + n – 1pq.

R. Craigen, J. Seberry e X.-M. Zhang. dimostrarono nel 1992 che a partire da 4 matrici di ordine 4a, 4b, 4c e 4d se ne può costruire una di ordine 16abcd. Per esempio, partendo dalle matrici di Hadamard di ordine 12 = 4 • 3 e 20 = 4 • 5 se ne ottiene una di ordine 3600 = 16 • 32 • 52.

J. Seberry e X.-M. Zhang dimostrarono nel 1991 che se esistono matrici di Hadamard complesse di ordini 4m e 4n, se ne può costruire una reale di ordine 4mn.

 

Accanto a questi metodi sono intanto state cercate costruzioni sporadiche per ordini non affrontabili altrimenti. 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 varie costruzioni; i casi non risolti minori di 2000 sono: 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 e 1964.

Contattami

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