OliForum Matematico

problemino carino, di provenienza rumena: (tanto ormai ho stracciato i maroni a tutti, proponendolo a destra e a manca, qui a pisa ).
sia $ m = 2^n - 1 $, e siano $ X_1, X_2, \cdots X_m $ i sottoinsiemi non vuoti di $ \{1,2,\cdots,n\} $.
associamo a questa numerazione dei sottoinsiemi una matrice $ A = (a_{ij}) $ definita in questo modo: $ a_{ij} = 0 $ se $ X_i $ e $ X_j $ sono disgiunti,e $ 1 $ altrimenti.
quanto vale il determinante di $ A $?

ma_go ha scritto:problemino carino, di provenienza rumena: (tanto ormai ho stracciato i maroni a tutti, proponendolo a destra e a manca, qui a pisa ).

confermo

non vorrei dire cavolate... è per caso -1 il determinante in questione?
perché credo che con un'opportuna scelta dell'ordine degli X si ha che la matrice ha tutti 1 nell'anti-diagonale e tutti 1 anche sotto (o sopra, volendo) l'antidiagonale. Riducendo con Gauss (usando forse anche Laplace) e sfruttando il fatto che 2^n -1 è dispari, si vede che il det è -1 (tranne quando n=1)

il claim sembrerebbe corretto...
sinceramente, non mi torna quello che hai scritto... nel senso, io e fph l'abbiamo fatto in un altro modo.
magari, se espliciti i conti, mi dai anche una mano
c'è solo un piccolo particolare: c'è una piccola cosuccia da giustificare (è banale, lo so, però bisogna farlo... e in realtà era compresa nelle richieste esplicite del problema, però così mi pare più bello).

mmm... non capisco cosa non ti torni, provo a esprimermi meglio
innanzitutto osserviamo che l'ordine di numerazione degli X non influisce sul determinante, in quanto se ne scambio due, li devo scambiare sia sulle righe che sulle colonne, e quindi moltiplicare due volte per -1 il determinante, cioè lasciarlo invariato
cmq, ovviamente la matrice coincide con la sua trasposta
inoltre è possibile avere un ordine per cui la matrice ha appunto tutti uno sull'antidiagonale e anche sotto di essa, e inoltre ha tutti 0 subito sopra l'antidiagonale (ossia in tutte le entrate di posto (i, 2^n - 1 - i)). Se non sbaglio (non ho controllato bene) basta sceglierli così: l'ultimo è tutto l'insieme iniziale; il penultimo è il complementare del primo, il terzultimo è il complementare del secondo e così via, badando però ad inserire prima tutti i sottoinsiemi di 1 elemento, poi tutti quelli di 2, eccetera.
A questo punto si riduce con Gauss in questo modo: partendo da quella più a destra, ad ogni colonna sottraiamo la precedente. In questo modo abbiamo una matrice con tutti 1 sull'antidiagonale e 0 sotto. Non dovrebbe essere difficile verificare che matrici di questo tipo, e di dimensione congrua a 3 modulo 4 (questo in effetti non l'avevo scritto nel precedente msg, ma avevo erroneamente generalizzato a tutte quelle di dimensione dispari) hanno determinante -1. E in effetti 2^n - 1 è congruo a 3 mod 4 per n > 1

Ciao

ok, direi che così va bene...
comunque mi tornava anche prima...
ottimo
altre idee? io l'ho fatto in altro modo... (poi in realtà suppongo sia molto simile)