Matrice bistocastica
Ciao.
Potreste dirmi come si fa per esprimere una matrice bistocastica come combinazione convessa di matrici di permutazione?
Ad esempio per tale matrice:
$((1/3,1/4,1/3,1/2),(5/12,1/6,1/6,1/4),(0,7/12,1/12,1/3),(1/4,0,5/12,1/3))$
Sulle dispense dice che devo prendere un insieme indipendente di valori >0 nella matrice e poi scegliere il più piccolo. Ma questo insieme viene scelto a caso o devo seguire un criterio ben preciso? Perché non riesco praticamente mai a finire tutto il procedimento per decomporla!!!!!!
Potreste dirmi come si fa per esprimere una matrice bistocastica come combinazione convessa di matrici di permutazione?
Ad esempio per tale matrice:
$((1/3,1/4,1/3,1/2),(5/12,1/6,1/6,1/4),(0,7/12,1/12,1/3),(1/4,0,5/12,1/3))$
Sulle dispense dice che devo prendere un insieme indipendente di valori >0 nella matrice e poi scegliere il più piccolo. Ma questo insieme viene scelto a caso o devo seguire un criterio ben preciso? Perché non riesco praticamente mai a finire tutto il procedimento per decomporla!!!!!!
Risposte
"Manugal":
Ciao.
Potreste dirmi come si fa per esprimere una matrice bistocastica come combinazione convessa di matrici di permutazione?
Ad esempio per tale matrice:
$((1/3,1/4,1/3,1/2),(5/12,1/6,1/6,1/4),(0,7/12,1/12,1/3),(1/4,0,5/12,1/3))$
Sulle dispense dice che devo prendere un insieme indipendente di valori >0 nella matrice e poi scegliere il più piccolo. Ma questo insieme viene scelto a caso o devo seguire un criterio ben preciso? Perché non riesco praticamente mai a finire tutto il procedimento per decomporla!!!!!!
moltiplico per 12:
$A = ((4,3,4,6),(5,2,2,3),(0,7,1,4),(3,0,5,4))$
provo ad applicare quello che dici:
$A = 5*((0,0,0,1),(1,0,0,0),(0,1,0,0),(0,0,1,0)) + ((4,3,4,1),(0,2,2,3),(0,2,1,4),(3,0,0,4)) = $
$= 5*((0,0,0,1),(1,0,0,0),(0,1,0,0),(0,0,1,0)) + 2*((1,0,0,0),(0,0,1,0),(0,1,0,0),(0,0,0,1)) + ((2,3,4,1),(0,2,0,3),(0,0,1,4),(3,0,0,2))$
e così via...
quello che non mi è chiaro (non conosco l'algoritmo che citi) è se questa procedura può andare avanti scegliendo "a pera" (o "a naso") come ho fatto io o se bisogna seguire un ordine preciso. E questo è il punto importante della tua domanda.
quello che dici: "devo prendere un insieme indipendente di valori >0 nella matrice e poi scegliere il più piccolo" non è chiaro
potresti ricontrollare le dispense, dove potrebbe essere scritto in modo più accurato
Ti scrivo per filo e per segno quello che ho sulla dispensa.
Questo sarebbe il teorema di Birkhoff-Von Neumann che dice che se $A=(a_(i,j))$ è una matrice bistocastica n x n di somma $lambda > 0$ su righe e colonne, allora A è somma di multipli non negativi di matrici di permutazione:
$A = lambda_(1)P_(1)+lambda_(2)P(2)+ ... +lambda_(m)P_(m), lambda_(i)>=0$
per un opportuno m.
Dim: Per induzione sul numero di elementi diversi da zero della matrice. Essendo $lambda > 0$ vi sono almeno n elementi di questo tipo. Se ve ne sono esattamente n, allora ve ne è uno e uno solo in ogni riga e colonna, e tutti valgono $lambda$. Ne segue che $A=lambdaP$, dove P è la matrice di permutazione che ha 1 nei posti nei quali in A c'è $lambda$. Supponiamo allora che A abbia k > n elementi diversi da zero e supponiamo, per induzione, il teorema vero per matrici con meno di k elementi diversi da zero. Scegliamo un insieme indipendente S di elementi diversi da zero, uno per ogni riga, e sia $lambda_(1)$ il più piccolo di questi. La matrice che ha 1 nel posto (i,j), se nel posto (i,j) di A c'è un elemento di S e zero altrove, è una matrice di permutazione $P_(1)$. Se $A_(1)=A-lambdaP_(1)$ non è la matrice nulla, è ancora una matrice a elementi non negativi, ogni riga e colonna ha somma $lambda-lambda_(1)$, e $A_(1)$ ha meno elementi diversi da zero di A. Per induzione,
$A_(1)=sum_(i=2)^mlambda_(i)P_(i)$
per un certo m e dunque:
$A=lambda_(1)P_(1)+A_(1)=lambda_(1)P_(1)+sum_(i=2)^mlambda_(i)P_(i)=sum_(i=1)^mlambda_(i)P_(i)$
Questa dimostrazione fornisce un algoritmo per trovare l'espressione richiesta, che termina quando si trova la matrice nulla.
Questo sarebbe il teorema di Birkhoff-Von Neumann che dice che se $A=(a_(i,j))$ è una matrice bistocastica n x n di somma $lambda > 0$ su righe e colonne, allora A è somma di multipli non negativi di matrici di permutazione:
$A = lambda_(1)P_(1)+lambda_(2)P(2)+ ... +lambda_(m)P_(m), lambda_(i)>=0$
per un opportuno m.
Dim: Per induzione sul numero di elementi diversi da zero della matrice. Essendo $lambda > 0$ vi sono almeno n elementi di questo tipo. Se ve ne sono esattamente n, allora ve ne è uno e uno solo in ogni riga e colonna, e tutti valgono $lambda$. Ne segue che $A=lambdaP$, dove P è la matrice di permutazione che ha 1 nei posti nei quali in A c'è $lambda$. Supponiamo allora che A abbia k > n elementi diversi da zero e supponiamo, per induzione, il teorema vero per matrici con meno di k elementi diversi da zero. Scegliamo un insieme indipendente S di elementi diversi da zero, uno per ogni riga, e sia $lambda_(1)$ il più piccolo di questi. La matrice che ha 1 nel posto (i,j), se nel posto (i,j) di A c'è un elemento di S e zero altrove, è una matrice di permutazione $P_(1)$. Se $A_(1)=A-lambdaP_(1)$ non è la matrice nulla, è ancora una matrice a elementi non negativi, ogni riga e colonna ha somma $lambda-lambda_(1)$, e $A_(1)$ ha meno elementi diversi da zero di A. Per induzione,
$A_(1)=sum_(i=2)^mlambda_(i)P_(i)$
per un certo m e dunque:
$A=lambda_(1)P_(1)+A_(1)=lambda_(1)P_(1)+sum_(i=2)^mlambda_(i)P_(i)=sum_(i=1)^mlambda_(i)P_(i)$
Questa dimostrazione fornisce un algoritmo per trovare l'espressione richiesta, che termina quando si trova la matrice nulla.
"Scegliamo un insieme indipendente S di elementi diversi da zero"
era questo che mi preoccupava
ma a prima vista direi che non dovrebbero esserci problemi, per la ipotesi che la matrice sia bistocastica
intendo dire che la scelta la possiamo fare "a pera"
quindi, basta aumentare ad ogni passo il numero di zeri nella matrice
dovrebbe fungere
continuo i conti:
$B = ((2,3,4,1),(0,2,0,3),(0,0,1,4),(3,0,0,2)) = $
$ = 1*((1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)) + ((1,3,4,1),(0,1,0,3),(0,0,0,4),(3,0,0,1)) $
$C = ((1,3,4,1),(0,1,0,3),(0,0,0,4),(3,0,0,1)) = $
$ = 1*((0,0,1,0),(0,1,0,0),(0,0,0,1),(1,0,0,0)) + ((1,3,3,1),(0,0,0,3),(0,0,0,3),(2,0,0,1)) $
toh, ora mi accorgo che c'è qualcosa che non quadra...
non l'avevo verificato, ma la matrice che hai indicato ovviamente [size=150]NON E' BISTOCASTICA!!![/size]
era questo che mi preoccupava
ma a prima vista direi che non dovrebbero esserci problemi, per la ipotesi che la matrice sia bistocastica
intendo dire che la scelta la possiamo fare "a pera"
quindi, basta aumentare ad ogni passo il numero di zeri nella matrice
dovrebbe fungere
continuo i conti:
$B = ((2,3,4,1),(0,2,0,3),(0,0,1,4),(3,0,0,2)) = $
$ = 1*((1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)) + ((1,3,4,1),(0,1,0,3),(0,0,0,4),(3,0,0,1)) $
$C = ((1,3,4,1),(0,1,0,3),(0,0,0,4),(3,0,0,1)) = $
$ = 1*((0,0,1,0),(0,1,0,0),(0,0,0,1),(1,0,0,0)) + ((1,3,3,1),(0,0,0,3),(0,0,0,3),(2,0,0,1)) $
toh, ora mi accorgo che c'è qualcosa che non quadra...
non l'avevo verificato, ma la matrice che hai indicato ovviamente [size=150]NON E' BISTOCASTICA!!![/size]
Aspetta la mia matrice dovrebbe essere bistocastica perché ho controllato ogni riga e ogni colonna e la somma fa sempre 1. Da dove hai visto che non è bistocastica?
ricontrolla la prima riga 
E' vero scusa hai ragione lì ho sbagliato a trascrivere l'ultima cifra della prima riga non è $1/2$ ma $1/12$. Ecco perché non finiva mai 
Cmq riepilogando:
Basta che prendo ogni volta un insieme indipendente da ogni matrice "risultante" e continuo finché non ho la matrice nulla giusto?
Cmq riepilogando:
Basta che prendo ogni volta un insieme indipendente da ogni matrice "risultante" e continuo finché non ho la matrice nulla giusto?
sì, secondo me viene, non vedo che problemi dovrebbeo spuntar fuori
Ok, ti ringrazio. Ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo