Sia data una matrice $m\times n$ di reali nonnegativi. Si sa che, se una riga e una colonna si intersecano in un elemento positivo, allora la somma degli elementi della riga è uguale alla somma degli elementi della colonna. Inoltre non ci sono righe e colonne con solo elementi nulli.
Dimostrare che $m=n$.
29. Una strana matrice
29. Una strana matrice
This is it. This is your story. It all begins here.
Re: 29. Una strana matrice
Allora,
costruiamo un grafo bipartito sugli insiemi $R$, $C$ che contengono rispettivamente tutte le righe e le colonne. 2 elementi $r\in R$, $c\in C$ sono collegati iff $r$ e $c$ si intersecano in un elemento non-nullo.
Osservazione 1: otterremo delle componenti connesse (anche una sola), ciascuna delle quali contenente almeno un elemento per ciascuno dei 2 insiemi $R,C$, perché ciascun riga\colonna ha almeno un elemento nonnullo, cioè un arco.
Osservazione 2: presa una componente connessa $c_0$, ogni elemento nonnullo che appartiene ad una riga di $c_0$ appartiene anche ad una colonna di $c_0$ e viceversa, ossia, posso trovare elementi positivi solo negli incroci di $c_0$.
Osservazione 3: in una stessa componente connessa, tutti gli elementi hanno stessa somma, dato che, per ipotesi, quando 2 elementi sono adiacenti hanno la stessa somma.
Claim: in ogni componente connessa il numero di righe è uguale al numero delle colonne.
Dim: Sia $S$ la somma degli elementi di una componente connessa $c_0$. Allora, detta $s_e$ la somma di un elemento di $c_0$ (che sappiamo essere uguale per tutti gli elementi di $c_0$ per l'osservazione 3), sommando per righe, $S=\#righe\cdot s_e$, per colonne $S=\#colonne\cdot s_e$, non salto elementi perché me l'assicura l'osservazione 2, da cui le righe sono tante quante le colonne.
Osservazione 4: il claim implica la tesi: basta applicarlo a tutte le componenti connesse!
costruiamo un grafo bipartito sugli insiemi $R$, $C$ che contengono rispettivamente tutte le righe e le colonne. 2 elementi $r\in R$, $c\in C$ sono collegati iff $r$ e $c$ si intersecano in un elemento non-nullo.
Osservazione 1: otterremo delle componenti connesse (anche una sola), ciascuna delle quali contenente almeno un elemento per ciascuno dei 2 insiemi $R,C$, perché ciascun riga\colonna ha almeno un elemento nonnullo, cioè un arco.
Osservazione 2: presa una componente connessa $c_0$, ogni elemento nonnullo che appartiene ad una riga di $c_0$ appartiene anche ad una colonna di $c_0$ e viceversa, ossia, posso trovare elementi positivi solo negli incroci di $c_0$.
Osservazione 3: in una stessa componente connessa, tutti gli elementi hanno stessa somma, dato che, per ipotesi, quando 2 elementi sono adiacenti hanno la stessa somma.
Claim: in ogni componente connessa il numero di righe è uguale al numero delle colonne.
Dim: Sia $S$ la somma degli elementi di una componente connessa $c_0$. Allora, detta $s_e$ la somma di un elemento di $c_0$ (che sappiamo essere uguale per tutti gli elementi di $c_0$ per l'osservazione 3), sommando per righe, $S=\#righe\cdot s_e$, per colonne $S=\#colonne\cdot s_e$, non salto elementi perché me l'assicura l'osservazione 2, da cui le righe sono tante quante le colonne.
Osservazione 4: il claim implica la tesi: basta applicarlo a tutte le componenti connesse!
Re: 29. Una strana matrice
Sarà possibile continuare la staffetta? 
Re: 29. Una strana matrice
Io l'avevo fatto senza grafi, ma la sostanza è sempre la stessa (solo è formulata in maniera più brutta)...
Prendo una riga a caso con somma $k$ e la metto in un insieme di righe e colonne inizialmente vuoto che chiamo $X$, poi opero il seguente passaggio: per ogni elemento nonnullo la cui riga è in $X$ ma la cui colonna non è in $X$ (o viceversa), prendo la sua colonna (o riga) e la metto in $X$. In questo modo tutti gli elementi che metto nell'insieme avranno somma $k$. Ripeto questo passaggio fino a quando non posso includere più nessuna riga o colonna in $X$.
Sia la sottomatrice di dimensione $r\times c$ che è formata da tutti e soli gli elementi intersezione di righe e colonne di $X$. Fuori dalla sottomatrice, ma nelle stesse righe o colonne della sottomatrice, ho solo elementi nulli perchè altrimenti avrei potuto ampliare $X$. Quindi la somma degli elementi della sottomatrice è $rk=ck\Rightarrow r=c$.
Ora elimino dalla matrice di partenza le righe e le colonne di $X$, ottengo una matrice con la stessa differenza tra numero di righe e numero di colonne, e inoltre dalle righe e dalle colonne superstiti ho tolto solo elementi nulli, quindi la somma di righe e colonne rimane invariata.
Reiterando questa operazione avrò una "matrice" di $n$ righe e 0 colonne (o viceversa) prima o poi. Ma se $n>0$, allora ho delle righe che hanno somma $0$ (non hanno elementi!) e quindi avevano somma 0 anche all'inizio. Quindi posso arrivare solo a una "matrice" $0\times 0$ , che implica che all'inizio avevo lo stesso numero di righe e colonne.
(In realtà non so se posso parlare di matrice con righe e senza colonne, in ogni caso avrei potuto fermarmi al passaggio precedente)
Prendo una riga a caso con somma $k$ e la metto in un insieme di righe e colonne inizialmente vuoto che chiamo $X$, poi opero il seguente passaggio: per ogni elemento nonnullo la cui riga è in $X$ ma la cui colonna non è in $X$ (o viceversa), prendo la sua colonna (o riga) e la metto in $X$. In questo modo tutti gli elementi che metto nell'insieme avranno somma $k$. Ripeto questo passaggio fino a quando non posso includere più nessuna riga o colonna in $X$.
Sia la sottomatrice di dimensione $r\times c$ che è formata da tutti e soli gli elementi intersezione di righe e colonne di $X$. Fuori dalla sottomatrice, ma nelle stesse righe o colonne della sottomatrice, ho solo elementi nulli perchè altrimenti avrei potuto ampliare $X$. Quindi la somma degli elementi della sottomatrice è $rk=ck\Rightarrow r=c$.
Ora elimino dalla matrice di partenza le righe e le colonne di $X$, ottengo una matrice con la stessa differenza tra numero di righe e numero di colonne, e inoltre dalle righe e dalle colonne superstiti ho tolto solo elementi nulli, quindi la somma di righe e colonne rimane invariata.
Reiterando questa operazione avrò una "matrice" di $n$ righe e 0 colonne (o viceversa) prima o poi. Ma se $n>0$, allora ho delle righe che hanno somma $0$ (non hanno elementi!) e quindi avevano somma 0 anche all'inizio. Quindi posso arrivare solo a una "matrice" $0\times 0$ , che implica che all'inizio avevo lo stesso numero di righe e colonne.
(In realtà non so se posso parlare di matrice con righe e senza colonne, in ogni caso avrei potuto fermarmi al passaggio precedente)
This is it. This is your story. It all begins here.