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

Matrici a segni alternati (congettura delle)

Congetture  Matematica combinatoria 

Si chiamano “matrici a segni alternati” le matrici quadrate contenenti solo 0, 1 e –1, tali che la somma di ogni riga e di ogni colonna sia 1 e che, escludendo gli zeri, 1 e –1 si alternino su ogni riga e colonna. La congettura delle matrici a segni alternati, proposta da William H. Mills, David P. Robbins e Howard Rumsey nel 1983, afferma che le matrici a segni alternati tali che, escludendo gli zeri, il primo e l’ultimo elemento di ogni riga e colonna siano 1 sono Formula per il numero di matrici a segni alternati di ordine n, ovvero il numero di Robbins Rn.

Per esempio, vi sono Formula per il numero di matrici a segni alternati di ordine 3 matrici del genere di ordine 3: Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3.

 

Queste matrici hanno un unico 1 sulla prima e ultima riga e sulla prima e ultima colonna.

 

La congettura fu dimostrata da Doron Zeilberger nel 1992, ma la correzione di alcune imperfezioni e la verifica della complessa dimostrazione da parte di una schiera di ben 88 persone, armate di calcolatori elettronici, furono completate solo nel 1995. Ironicamente nello stesso anno Greg Kuperberg trovò una dimostrazione notevolmente più semplice, basata sulle proprietà del reticolo del “ghiaccio quadrato” (v. costante di Lieb).

 

Nel 1996 Zeilberger dimostrò la versione più raffinata della congettura, cioè che il numero di matrici a segni alternati con l’unico 1 della prima riga sulla colonna m è Formula per il numero di matrici a segni alternati di ordine n con 1 nella prima riga sulla colonna m.

Vedi anche

Numeri di Robbins.

Bibliografia

  • Bressoud, David M.;  Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Cambridge, Cambridge University Press, 1999.

Contattami

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