Matrice stendibile
Matrice stendibile
In ciascuna delle caselle di una matrice di kxn (con k<n) si scrive un numero da 1 a n, in maniera tale che in ogni riga e ogni colona tutti i numeri sono diversi. Dimostrare che questa matrice si può stendere a una matrice di nxn (cioè aggiungere n-k righe senza alterare i numeri ormai mesi) tale che in ogni riga e ogni colona tutti i numeri sono diversi.
Genio es aquel que no se limita a la escasa percepción de sus sentidos para describir el universo que lo rodea.
Uhm... la soluzione che ho trovato per questo problema è un poco strana...
Associo alla matrice kxn una matrice quadrata nxn con soli 0 e 1. In particolare la casella i,j è 1 se e solo se nella riga i-esima della matrice kxn non è presente j. È facile mostrare che la matrice ottenuta ha un numero di 1 costante in ogni riga e colonna (sono esattamente n-k). Ora se io mostro che questa è la somma di n-k matrici di permutazione ho concluso, perchè associo alla z-esima riga mancante la matrice di permutazione z-k, e la matrice ottenuta soddisfa l'ipotesi. Fortunatamente quest'ultimo è un risultato noto (non so bene a chi...):
http://en.wikipedia.org/wiki/Permutation_matrix
All'ultimo paragrafetto compare un lemma più forte di quello che serve a me ;)
Ho provato dimostrare il fatto senza passare per qualche cannone, ma non ce l'ho fatta. In particolare ho dimostrato che non mi sono perso per strada nessuna ipotesi... per fare questo ho usato il combinatorial nullstellenstatz... ma questo evito di scriverlo un po perchè non sono certo dell'esattezza, un po perchè non serve a concludere (serve solo a mostrare che effettivamente il problema da me trovato è equivalente e non più forte). Per chi volesse provarci consiglio di usare un polinomio che si annulla se 2 variabili sono uguali... scoprendo che per k piccolo non si può annullare sempre con le variabili prese dalle rimanenti di ogni riga... Questo mostra che resta da analizzare solo il caso k>n/2 che comunque è un bel fardello.
p.s. insomma ho bombardato un problema senza capire manco cosa sto usando, peggio di così si muore. Tin Tan, se hai una dimostrazione che non passa per il lemma che ho linkato dimmelo che provo a cercarla.
EDIT: Ho trovato un articolo dedicato unicamente alle matrici 0,1 con somma righe,colonne fissa.
http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
In particolare alla fine della sesta pagina compare proprio il lemma che uso (ne più forte ne più debole). Non ho letto l'articolo (non ci capisco una mazza) quindi potrei aver sbagliato ad intendere il lemma (che comunque mi pare venga fornito senza dimostrazione).
Per dimostrare il lemma basta mostrare che in una matrice 0,1 nxn con somma delle linee costante, si possono scegliere n uni in modo che ce ne sia uno su ogni riga e colonna.. Da qui si conclude per induzione, il problema è che non sono riuscito a mostrare neanche questo :(
EDIT2: Se di qua passa qualche bel laureato in matematica, potrebbe dire se il lemma è conosciuto/banale/falso/tostissimo...
Associo alla matrice kxn una matrice quadrata nxn con soli 0 e 1. In particolare la casella i,j è 1 se e solo se nella riga i-esima della matrice kxn non è presente j. È facile mostrare che la matrice ottenuta ha un numero di 1 costante in ogni riga e colonna (sono esattamente n-k). Ora se io mostro che questa è la somma di n-k matrici di permutazione ho concluso, perchè associo alla z-esima riga mancante la matrice di permutazione z-k, e la matrice ottenuta soddisfa l'ipotesi. Fortunatamente quest'ultimo è un risultato noto (non so bene a chi...):
http://en.wikipedia.org/wiki/Permutation_matrix
All'ultimo paragrafetto compare un lemma più forte di quello che serve a me ;)
Ho provato dimostrare il fatto senza passare per qualche cannone, ma non ce l'ho fatta. In particolare ho dimostrato che non mi sono perso per strada nessuna ipotesi... per fare questo ho usato il combinatorial nullstellenstatz... ma questo evito di scriverlo un po perchè non sono certo dell'esattezza, un po perchè non serve a concludere (serve solo a mostrare che effettivamente il problema da me trovato è equivalente e non più forte). Per chi volesse provarci consiglio di usare un polinomio che si annulla se 2 variabili sono uguali... scoprendo che per k piccolo non si può annullare sempre con le variabili prese dalle rimanenti di ogni riga... Questo mostra che resta da analizzare solo il caso k>n/2 che comunque è un bel fardello.
p.s. insomma ho bombardato un problema senza capire manco cosa sto usando, peggio di così si muore. Tin Tan, se hai una dimostrazione che non passa per il lemma che ho linkato dimmelo che provo a cercarla.
EDIT: Ho trovato un articolo dedicato unicamente alle matrici 0,1 con somma righe,colonne fissa.
http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
In particolare alla fine della sesta pagina compare proprio il lemma che uso (ne più forte ne più debole). Non ho letto l'articolo (non ci capisco una mazza) quindi potrei aver sbagliato ad intendere il lemma (che comunque mi pare venga fornito senza dimostrazione).
Per dimostrare il lemma basta mostrare che in una matrice 0,1 nxn con somma delle linee costante, si possono scegliere n uni in modo che ce ne sia uno su ogni riga e colonna.. Da qui si conclude per induzione, il problema è che non sono riuscito a mostrare neanche questo :(
EDIT2: Se di qua passa qualche bel laureato in matematica, potrebbe dire se il lemma è conosciuto/banale/falso/tostissimo...
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
uhm, in tema di cannoni:
ad ogni colonna associamo i numeri mancanti in essa; le ipotesi ci dicono che, per qualunque insieme di m colonne, l'insieme dei numeri che mancano in almeno una di esse è composto da almeno m elementi, quindi possiamo applicare il teorema di Hall e trovare un matching. In questo modo possiamo aggiungere una riga.
E le ipotesi del teorema di Hall accadono finché le righe sono meno delle colonne.
PS: la faccenda delle matrici con righe e colonne a somma costante si fa nello stesso modo, pensaci, dario2994!
PS2: purtroppo non sono bello ...
ad ogni colonna associamo i numeri mancanti in essa; le ipotesi ci dicono che, per qualunque insieme di m colonne, l'insieme dei numeri che mancano in almeno una di esse è composto da almeno m elementi, quindi possiamo applicare il teorema di Hall e trovare un matching. In questo modo possiamo aggiungere una riga.
E le ipotesi del teorema di Hall accadono finché le righe sono meno delle colonne.
PS: la faccenda delle matrici con righe e colonne a somma costante si fa nello stesso modo, pensaci, dario2994!
PS2: purtroppo non sono bello ...
Sisi si fa allo stesso identico modo, anche perchè è equivalente al problema.
Tra l'altro, era stata la prima cosa che avevo pensato, tutti i lemmi sono equivalenti al lemma dei matrimoni. Solo che non sono riuscito a dimostrare l'equivalenza (dato che non conosco il lemma dei matrimoni) l'ho solo letta in un articolo sul teorema di Hall, che praticamente è il problema stesso xD
Tra l'altro, era stata la prima cosa che avevo pensato, tutti i lemmi sono equivalenti al lemma dei matrimoni. Solo che non sono riuscito a dimostrare l'equivalenza (dato che non conosco il lemma dei matrimoni) l'ho solo letta in un articolo sul teorema di Hall, che praticamente è il problema stesso xD
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai