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.

 

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.

 

Sylvester trovò un semplice modo per costruire una matrice di ordine 2n a partire da una Matrice di ordine n 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 di un primo dispari. In altri termini, se pm è una potenza di un primo della forma 4k + 1, 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.

 

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.

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.

 

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.