Numero matrici
Numero matrici
Trovare il numero di matrici con $m$ righe, $n$ colonne i cui elementi appartengono a $\left \{-1,+1\right \}$ tali che il prodotto degli elementi su ogni riga e su ogni colonna sia $-1$.
"We' Inge!"
LTE4LYF
LTE4LYF
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Numero matrici
Parte 1, "solo se"
La configurazione è realizzabile solo se \(n \equiv m \pmod{2}\). Infatti il prodotto di tutti gli elementi è \((-1)^m\) moltiplicando secondo le righe, \((-1)^n\) moltiplicando secondo le colonne. Allora \( (-1)^n = \mbox{prodotto di tutti gli elementi} = (-1)^m\), da cui \(n \equiv m \pmod{2}\).
Parte 2, "se" ( e pure "quante")
Emarginiamo per un attimo l'ultima colonna e l'ultima riga. Sia \(r_i\) per \(i=1, \ldots, m\) il prodotto di tutti gli elementi sull'\(i\)-esima riga eccetto l'ultimo, similmente \(c_i\) per le colonne, con \(i=1, \ldots, n\). Scelgo come voglio il resto della matrice \( (n-1) \mbox{ x } (m-1) \) in \(2^{(n-1)(m-1)}\) modi, e poi prendo in modo obbligato l'ultimo elemento dell'\(i\)-esima riga, e lo prendo pari a \(-r_i\): così il prodotto sull'intera riga sia \(- (r_i)^2 = -1\). Similmente faccio con le colonne.
Mi manca da sistemare la casella d'angolo. Notiamo che il prodotto dell'ultima riga e dell'ultima colonna (casella d'angolo a parte) sono uguali (sfruttando l'ipotesi \(n \equiv m \pmod{2}\) e un double counting su righe e colonne della matrice \((n-1) \mbox{ x } (m-1)\) ):
\( \displaystyle c_n = \prod_{1 \le i < m}{-r_i} = (-1)^{m-1} \prod_{1 \le i < m}{r_i} = (-1)^{n-1} \prod_{1 \le i < n}{c_i} = \prod_{1 \le i < n}{-c_i} = r_m\)
Dunque mi basta scegliere la casella d'angolo pari a \(-c_n = -r_m\): in questo modo sia la riga, sia la colonna sono sistemate.
In definitiva i modi sono \(2^{(n-1)(m-1)}\), l'unica cosa che ho scelto.
La configurazione è realizzabile solo se \(n \equiv m \pmod{2}\). Infatti il prodotto di tutti gli elementi è \((-1)^m\) moltiplicando secondo le righe, \((-1)^n\) moltiplicando secondo le colonne. Allora \( (-1)^n = \mbox{prodotto di tutti gli elementi} = (-1)^m\), da cui \(n \equiv m \pmod{2}\).
Parte 2, "se" ( e pure "quante")
Emarginiamo per un attimo l'ultima colonna e l'ultima riga. Sia \(r_i\) per \(i=1, \ldots, m\) il prodotto di tutti gli elementi sull'\(i\)-esima riga eccetto l'ultimo, similmente \(c_i\) per le colonne, con \(i=1, \ldots, n\). Scelgo come voglio il resto della matrice \( (n-1) \mbox{ x } (m-1) \) in \(2^{(n-1)(m-1)}\) modi, e poi prendo in modo obbligato l'ultimo elemento dell'\(i\)-esima riga, e lo prendo pari a \(-r_i\): così il prodotto sull'intera riga sia \(- (r_i)^2 = -1\). Similmente faccio con le colonne.
Mi manca da sistemare la casella d'angolo. Notiamo che il prodotto dell'ultima riga e dell'ultima colonna (casella d'angolo a parte) sono uguali (sfruttando l'ipotesi \(n \equiv m \pmod{2}\) e un double counting su righe e colonne della matrice \((n-1) \mbox{ x } (m-1)\) ):
\( \displaystyle c_n = \prod_{1 \le i < m}{-r_i} = (-1)^{m-1} \prod_{1 \le i < m}{r_i} = (-1)^{n-1} \prod_{1 \le i < n}{c_i} = \prod_{1 \le i < n}{-c_i} = r_m\)
Dunque mi basta scegliere la casella d'angolo pari a \(-c_n = -r_m\): in questo modo sia la riga, sia la colonna sono sistemate.
In definitiva i modi sono \(2^{(n-1)(m-1)}\), l'unica cosa che ho scelto.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
