Sia G = ({1, 2, . . . , n}, E) un grafo orientato. Definizione di matrici di Adiacenza e di Transizione del grafo G:
[Adiac(G)] ij = 1 ij ∈ E
0 ij / ∈ E , [Trans(G)] ij = 1/ deg (i) ij ∈ E
0 ij / ∈ E
( deg (i) = #archi uscenti dal vertice i). Notiamo che se sommiamo gli elementi di ogni riga della matrice Trans(G) otteniamo 1 oppure 0. Precisamente,
X
j
[Trans(G)] ij = 1 deg (i) > 0 0 deg (i) = 0 .
Osservazione importante: la matrice Trans(G) compare nel momento in cui scriviamo in forma vettoriale le seguenti condizioni
p j = X
i: i→j
p i
deg (i) , j = 1, 2, . . . , n, (−1) soddisfatte dalle “importanze” (authorities) p j dei vertici j di G. Infatti, (−1) `e equivalente all’identit`a p = [Trans(G)] T p, dove p = [p 1 p 2 · · · p n ] T `e il vettore delle importanze.
Definizione. Una matrice A n × n si dice riducibile se esiste P n × n matrice di permu- tazione tale che
P T AP = M R O N
, M, N quadrate.
Se A n × n `e riducibile, allora esiste P n × n matrice di permutazione tale che P T AP = M R
O N
, M, N quadrate, con M nulla o irriducibile.
Dunque nella definizione potremmo anche richiedere che M sia nulla oppure irriducibile.
Proposizione. Sia A n × n irriducibile non negativa e tale che P
j a ij ≤ 1 ∀ i & ∃ k per cui P
j a kj < 1. Allora 1 non `e autovalore di A.
Dimostrazione. ` E una conseguenza immediata del terzo teorema di Gershgorin. Teorema. Dato un grafo orientato G, affinch´e possa essere vera la seguente affermazione
∃ ! p ∈ R n , p > 0, kpk 1 = 1 tale che p = [Trans(G)] T p , (0) la matrice Trans (G) deve essere stocastica per righe ed irriducibile.
Dimostrazione. Supponiamo che vale (0). L’identit`a p = [Trans(G)] T p e la condizione kpk 1 = 1 implicano
1 = X
i
p i = X
i
([Trans(G)] T p) i = X
i
X
j
([Trans(G)] T ) ij p j
= X
i
X
j
([Trans(G)]) ji p j = X
j
X
i
([Trans(G)]) ji
p j
= X
j: deg (j)>0
X
i
([Trans(G)]) ji
p j + X
j: deg (j)=0
X
i
([Trans(G)]) ji p j
= X
j: deg (j)>0
1
p j + X
j: deg (j)=0
0
p j =: α .
Se esistesse un indice j ∗ per cui deg (j ∗ ) = 0, allora, dall’identit`a 1 = α appena dimostrata e dal fatto che ogni componente di p `e positiva e che la somma delle componenti di p `e uguale a 1, seguirebbe che 1 = α < 1, il che `e assurdo. Dunque si deve avere che deg (j) > 0 per ogni j = 1, 2, . . . , n, o, equivalentemente, Trans(G) deve essere stocastica per righe.
Ora supponiamo di nuovo che vale (0) e, inoltre, che Trans(G) `e stocastica per righe.
Dimostriamo che allora Trans(G) deve essere irriducibile.
Supponiamo per assurdo che Trans(G) `e riducibile. Dunque esiste P n × n matrice di permutazione tale che
P T Trans(G)P = M R O N
, M, N quadrate, con M nulla o irriducibile. (1)
Notiamo che dal fatto che Trans(G) `e stocastica per righe segue che anche la matrice M R O N
qui sopra deve essere stocastica per righe.
La (1) implica Trans(G) = P M R O N
P T . Dunque (0) implica
p = [Trans(G)] T p = P M T O R T N T
P T p, P T p = M T O R T N T
P T p,
(P T p) up
(P T p) down
= M T O R T N T
(P T p) up
(P T p) down
, (2)
dove (P T p) up `e il vettore costituito dalle prime k componenti di P T p, essendo k (1 ≤ k < n) l’ordine della matrice M e (P T p) down `e il vettore costituito dalle ultime n − k componenti di P T p. Osserviamo che la matrice M T O
R T N T
`e stocastica per colonne.
Faremo ora vedere che dalla (2) segue
- o che, oltre p, vi sono un numero infinito di altri vettori z α ∈ R n , z α > 0, kz α k 1 = 1, tali che z α = [Trans(G)] T z α , [Caso R = O]
- oppure che almeno una delle componenti di p deve essere nulla. [Caso R 6= O]
Poich´e questi sono entrambi eventi che contraddicono le ipotesi, ne seguir`a che Trans(G)
deve essere irriducibile.
Caso R = O: in questo caso l’uguaglianza (2), che diventa
(P T p) up
(P T p) down
= M T O O N T
(P T p) up
(P T p) down
, implica
"
α k(P (PTTp) p)
upupk
1
(1 − α) k(P (PTTp) p)
downdownk
1
#
= M T O O N T
"
α k(P (PTTp) p)
upupk
1
(1 − α) k(P (PTTp) p)
downdownk
1
#
, α ∈ C.
Sia z α ∈ R n la famiglia di vettori definiti dall’identit`a
P T z α =
"
α k(P (PTTp) p)
upupk
1
(1 − α) k(P (PTTp) p)
downdownk
1
#
, α ∈ (0, 1).
Si noti che tali vettori z α sono tutti distinti tra loro, sono positivi e hanno norma-1 uguale a 1. Inoltre, per come sono stati definiti, essi soddisfano le identit`a
P T z α = M T O O N T
P T z α , z α = P M T O O N T
P T z α = [Trans(G)] T z α .
Quindi, oltre p, vi sono altri infiniti vettori z α (costruibili a partire da p) che verificano le condizioni x > 0, kxk 1 = 1, x = Trans(G) T x, mentre avevamo supposto che ne esisteva uno solo.
Caso R 6= O: l’uguaglianza (2)
(P T p) up
(P T p) down
= M T O R T N T
(P T p) up
(P T p) down
(dove, ricordiamo, M T O R T N T
`e stocastica per colonne) implica
(P T p) up = M T (P T p) up , M nulla o irriducibile. (3) Se M `e nulla, allora (3) implica (P T p) up = 0, cio`e almeno k elementi di p devono essere nulli. (Si ricorda che k ≥ 1).
Supponiamo in alternativa che M `e irriducibile. Poich´e R `e non nulla, c’`e almeno una colonna di R T , diciamo quella di indice u, in cui c’`e almeno un elemento positivo. Dunque M T `e non negativa, irriducibile e tale che P
j [M T ] ji ≤ 1 ∀ i e P
j [M T ] j,u < 1, ovvero M `e non negativa, irriducibile e tale che P
j M ij ≤ 1 ∀ i e P
j M u,j < 1. Quindi, per la Proposizione,
1 non pu`o essere autovalore di M, ovvero non pu`o essere autovalore di M T . Questo fatto e il
fatto che vale la condizione (3) implicano (P T p) up = 0, cio`e almeno k elementi di p devono
essere nulli. (Si ricorda che k ≥ 1).
In conclusione, nel caso R 6= O, abbiamo mostrato che almeno una componente di p deve essere nulla, contro l’ipotesi iniziale che tutte le componenti di p sono positive.
Abbiamo visto che in entrambi i casi R = O e R 6= O giungiamo a contraddire le ipotesi.
Dunque Trans(G) non pu`o essere riducibile (se vale (0)). Esempio di “riduzione” di una matrice. Sia
A =
∗ 0 0 ∗ 0 ∗ 0
∗ a 0 ∗ b ∗ 0
∗ i l ∗ m ∗ n
∗ 0 0 ∗ 0 ∗ 0
∗ c 0 ∗ d ∗ 0
∗ 0 0 ∗ 0 ∗ 0
∗ e f ∗ g ∗ h
, h, f, n, l 6= 0
A → P T A =
∗ e f ∗ g ∗ h
∗ a 0 ∗ b ∗ 0
∗ i l ∗ m ∗ n
∗ c 0 ∗ d ∗ 0
∗ 0 0 ∗ 0 ∗ 0
∗ 0 0 ∗ 0 ∗ 0
∗ 0 0 ∗ 0 ∗ 0
→ P T AP =
h e f g ∗ ∗ ∗ 0 a 0 b ∗ ∗ ∗ n i l m ∗ ∗ ∗ 0 c 0 d ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗
(P scambia le righe/colonne 1 e 7 e le righe/colonne 4 e 5) (Nota:
h e f g
0 a 0 b
n i l m
0 c 0 d
`e riducibile)
→ Q T P T AP =
h e f g ∗ ∗ ∗ n i l m ∗ ∗ ∗ 0 a 0 b ∗ ∗ ∗ 0 c 0 d ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗
→ (P Q) T A(P Q) =
h f e g ∗ ∗ ∗ n l i m ∗ ∗ ∗ 0 0 a b ∗ ∗ ∗ 0 0 c d ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗
(Q scambia le righe/colonne 2 e 3)
Nota: la matrice P Q `e una matrice di permutazione; la matrice h f n l
`e irriducibile.
Vedi anche l’articolo “Berkhin survey pagerank computing Internet Mathematics”
Si `e visto che se vale la seguente affermazione
∃ ! p > 0, kpk 1 = 1 tale che p = [Trans(G)] T p (∗) allora necessariamente [Trans(G)] T deve essere, oltre che non negativa, stocastica per colonne e irriducibile.
Pi` u avanti si noter`a che, data A ∈ R n×n , il problema z = Az, se A `e non negativa, stocastica per colonne, e irriducibile, ammette una unica soluzione z > 0, kzk 1 = 1. Quindi, per il nostro particolare problema, se [Trans(G)] T , oltre che non negativa, fosse stocastica per colonne e irriducibile, allora si avrebbe effettivamente (*). Nella maggior parte dei casi, per`o, la matrice [Trans(G)] T non soddisfa queste condizioni, quindi, in questi casi, il risultato di esistenza e unicit`a (*) si potr`a ottenere se e solo se si sostituisce [Trans(G)] T con una matrice A “vicina” a [Trans(G)] T , che sia stocastica per colonne e irriducibile (oltre che non negativa).
Osservazione. Prima di proseguire, accenniamo a un modello di visita del grafo che porter`a ad un metodo per il calcolo del vettore p in (*), se quest’ultimo `e ben definito. Sia p (k) i la probabilit`a che un visitatore del grafo al passo k della sua visita sia nel vertice i. ` E ragionevole richiedere che p (k) i > 0 ∀ i (c’e probabilit`a che al passo k della sua visita il visitatore sia sul vertice i, ∀ i) e che P
i p (k) i = 1 (al passo k della sua visita il visitatore deve essere in uno dei vertici del grafo). Inoltre, `e ragionevole dire che
p (k+1) j = X
i: i→j
p (k) i deg (i) =
n
X
i=1
T ji p (k) i
dove T ji = [Trans(G)] ij (uguale a deg 1 (i) se deg (i) > 0 e a zero se deg (i) = 0) `e la probabilit`a che il visitatore dal vertice i vada nel vertice j. Ne segue che i vettori delle probabilit`a p (k) e p (k+1) soddisfano l’identit`a p (k+1) = ([Trans(G)] T p (k) .
Dato un vettore iniziale p (0) , p (0) > 0, P
i p (0) i = 1, la legge p (k+1) = ([Trans(G)] T p (k) genera una successione di vettori che vorremmo fossero tutti tali che p (k) > 0 e kp (k) k 1 = 1, e vorremmo inoltre che p (k) → p = [Trans(G)] T p, quando k → +∞, in modo da avere un metodo per calcolare il vettore p = [Trans(G)] T p, se ben definito. 1
1
Dato in generale il problema di determinare in un certo spazio S un x
∗che rimanga invariato sotto
l’azione di un operatore ϕ, il primo metodo che viene in mente per calcolare un tale x
∗∈ S `e il metodo delle
approssimazioni successive che, a partire da un certo x
0∈ S, tramite la legge x
k+1= ϕ(x
k), k = 0, 1, . . .,
genera una successione x
k∈ S che si spera converga ad x
∗. In particolare, se lo spazio S `e R e ϕ : R → R,
allora da uno studio grafico della successione x
k+1= ϕ(x
k) si possono intuire facilmente delle condizioni su
x
0e su ϕ che obbligano tale successione a convergere ad un punto x
∗ascissa di una delle intersezioni (che
si suppongono esistenti) tra la funzione ϕ e la bisettrice. Ad esempio, se ϕ ∈ C
1in un intorno di x
∗, allora
{x
k} converge a x
∗se |ϕ
′(x
∗)| < 1 e x
0non `e troppo lontano da x
∗; e non converge a x
∗se |ϕ
′(x
∗)| > 1 (a
meno di eventi fortuiti). . . .
Premessa (risultati di algebra lineare). Si osserva che
B =
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
⇒ B 2 =
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
, B 3 =
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
, B k = O, k ≥ 4.
Si osserva che, per ogni α ∈ C,
α 1 0 0 α 1 0 0 α
k
=
α k kα k−1 k(k−1) 2 α k−2 0 α k kα k−1
0 0 α k
,
α 1 0 0 0 α 1 0 0 0 α 1 0 0 0 α
k
=
α k kα k−1 k(k−1) 2 α k−2 k(k−1)(k−2)
6 α k−3
0 α k kα k−1 k(k−1) 2 α k−2
0 0 α k kα k−1
0 0 0 α k
,
k = 0, 1, 2, . . .. Pi` u in generale, si dimostra che
B = B s (α) =
α 1
α ·
· 1 α
s ⇒ B k =
min{k,s−1}
X
j=0
c k,j+1 (Z T ) j , Z T =
1
. ..
1
s ,
dove
c k,j+1 = 1 j!
d j (α k ) dα = 1
j! k(k − 1) · · · (k − j + 1)α k−j .
E evidente che B ` k → O se e solo se |α| < 1. Nel caso α = 0 si ha che B k = O per k ≥ s.
Teorema di Jordan. Ogni matrice M ∈ C n×n `e simile a una matrice J diagonale a blocchi i cui blocchi diagonali sono fatti come B (tale matrice J `e detta forma canonica di Jordan di M). In ogni blocco diagonale, al posto di α, ovviamente, c’`e un autovalore λ di M. Lo stesso autovalore pu`o comparire in pi` u blocchi diagonali. La matrice M `e diagonalizzabile se e solo se i blocchi diagonali della forma canonica di Jordan sono tutti 1 × 1.
M ∈ C n×n ⇒ ∃ X : X −1 MX =
· O O
O B s (λ) O
O O ·
=: J. (T eoJordan)
Corollario del Teorema di Jordan. Data M ∈ C n×n , la successione di matrici M k , k ∈ N, tende alla matrice nulla se e solo se tutti gli autovalori di M hanno modulo minore di 1.
Dimostrazione. La tesi segue dalla seguente rappresentazione di M k :
M k = X
· O O
O B s (λ) O
O O ·
X −1 k
= X
· O O
O B s (λ) O
O O ·
k
X −1 = X
· O O
O B s (λ) k O
O O ·
X −1 .
Sia ora A n × n non negativa, stocastica per colonne, irriducibile.
Per il fatto che A `e stocastica per colonne (A T e = e) il numero reale 1 deve essere autovalore di A, dunque deve esistere z ∈ R n z 6= 0 tale che z = Az.
Per il fatto che A `e non negativa e stocastica per colonne, gli altri autovalori di A, λ 2 (A), . . . , λ n (A), devono avere modulo minore o uguale di uno.
Per il fatto che A `e non negativa, stocastica per colonne e irriducibile, nessuno degli auto- valori λ j (A), j = 2, . . . , n, pu`o essere uguale a 1, cio`e 1 come autovalore di A ha molteplicit`a algebrica uguale a uno, e ogni autovettore di 1 – che `e definito a meno di un multiplo – ha le sue componenti tutte non nulle e dello stesso segno. (Questi ultimi risultati, di cui si omette la dimostrazione, fanno parte della teoria di Perron-Frobenius).
Ne segue che vale il seguente
TEOREMA PF. A ≥ O, stocastica per colonne, irriducibile ⇒
λ 1 (A) = 1, |λ j (A)| ≤ 1, j = 2, . . . , n e ∃ ! z > 0, kzk 1 = 1 tale che z = Az. (∗∗) Se A fosse anche stocastica per righe (cio`e Ae = e), allora `e semplice capire chi `e il vettore z in (**): z = n 1 e. Altrimenti, occorre fare calcoli per ottenere z.
Esempio. Sia
A =
0 1 0
1 − a 0 1
a 0 0
, a ∈ [0, 1].
Se a ∈ (0, 1], allora A `e non negativa, stocastica per colonne, irriducibile, quindi vale (**).
Se a = 1, A `e anche stocastica per righe, quindi z = [ 1 3 1 3 1 3 ] T . Se a ∈ (0, 1), per ottenere z occorre fare qualche conto:
−1 1 0
1 − a −1 1
a 0 −1
z 1
z 2
z 3
= 0, z i > 0 ∀ i, X
i
z i = 1 . . . ⇔ . . .
z 1
z 2
z 3
= 1 2 + a
1 1 a
. Si osserva che per a = 0 esiste ed `e unico un vettore z tale che z = Az, che z `e non negativo, ma z non `e positivo (z 3 = 0); cio`e non vale (**). E infatti A `e riducibile se a = 0. Si osserva inoltre che A = [Trans(G)] T per un grafo G se e solo se a = 0, 1, 1 2 .
TEOREMA Potenze (calcolo di z: costruzione di una successione di vettori convergente a z).
Sia z 0 > 0 kz 0 k 1 = 1 arbitrario. Definiamo z 1 = Az 0 , z 2 = Az 1 , z k+1 = Az k , k = 0, 1, 2, . . ..
Se A `e non negativa, stocastica per colonne e irriducibile, allora i vettori z k sono tutti positivi e di norma-1 uguale a 1. Se inoltre |λ j (A)| < 1, j = 2, . . . , n, allora per k che tende a pi` u infinito i vettori z k convergono al vettore z in (**), e pi` u max j=2,...,n |λ j (A)| `e minore di 1, pi` u rapida `e la convergenza.
Osservazione. Prima di dimostrare questo risultato, notiamo che la condizione |λ j (A)| < 1,
j = 2, . . . , n, non `e in generale soddisfatta da una matrice A non negativa, stocastica per
colonne, irriducibile. Vedi ad esempio le matrici A = 0 1 1 0
, σ(A) = {1, −1};
A =
0 1 0 0 0 1 1 0 0
, σ(A) = {1, e i2π/3 , e i4π/3 }; A =
0 a 0
1 0 1
0 1 − a 0
, a ∈ (0, 1), σ(A) = {1, 0, −1}.
Dimostrazione. Si verifica che z k > 0, kz k k 1 = 1 ⇒ z k+1 > 0, kz k+1 k 1 = 1. Poich´e z k+1 = Az k
con A ≥ O e z k > 0, il vettore z k+1 deve essere non negativo. Se una componente i di z k+1 fosse nulla, allora la riga i di A dovrebbe essere nulla e A sarebbe riducibile, contro il fatto che invece A si suppone irriducibile. Ne segue che ogni componente di z k+1 deve essere positiva.
Inoltre P
i (z k+1 ) i = P
i (Az k ) i = P
i
P
j A ij (z k ) j = P
j
P
i A ij (z k ) j = P
j (z k ) j = 1. Dunque kz k+1 k 1 = 1.
Supponiamo ora |λ j (A)| < 1, j = 2, . . . , n. Dalle equazioni z = Az e z k+1 = Az k segue l’identit`a z − z k+1 = A(z − z k ) che mette in relazione l’errore commesso al passo k + 1 con l’errore al passo k (∀ k). Scrivendo questa identit`a per k = 0, 1, 2, . . ., z − z 1 = A(z − z 0 ), z − z 2 = A(z − z 1 ) = A(A(z − z 0 )) = A 2 (z − z 0 ), z − z 3 = A(z − z 2 ) = A(A 2 (z − z 0 )) = A 3 (z−z 0 ), ci si accorge che l’errore al passo k `e legato all’errore iniziale z−z 0 dall’uguaglianza z − z k = A k (z − z 0 ) (∀ k). La successione A k sicuramente non converge alla matrice nulla perch´e uno degli autovalori di A `e uguale a 1 (per il Corollario del teorema di Jordan), quindi questa espressione di z − z k non ci permette di concludere che z − z k → 0, se k → +∞.
Essendo per`o e T z = 1 ed e T z k = 1 ∀ k, si ha anche z − z k+1 = A(z − z k ) = (A − ze T + ze T )(z−z k ) = (A−ze T )(z−z k ). Dunque vale anche l’identit`a z−z k+1 = (A−ze T )(z−z k ) e, di conseguenza, si ha la seguente espressione alternativa per l’errore al passo k: z −z k = (A−
ze T ) k (z − z 0 ) (∀ k). Poich´e σ(A − ze T ) = {0, λ 2 (A), . . . , λ n (A)} 2 , stavolta (A − ze T ) k → O, se k → +∞, dunque z − z k → 0.
I Teoremi PF e Potenze ci dicono che se [Trans(G)] T `e non negativa, stocastica per colonne, irriducibile e n−1 dei suoi autovalori hanno modulo strettamente minore di 1, allora (*) `e vera e il p in (*) `e calcolabile come limite della successione di distribuzioni discrete di probabilit`a (d.d.p.) p (0) > 0, kp (0) k 1 = 1, p (k+1) = [Trans(G)] T p (k) , k = 0, 1, 2, . . ..
Se invece [Trans(G)] T non soddisfa quelle ipotesi, allora gli stessi Teoremi PF e Potenze ci inducono a modificare [Trans(G)] T in una matrice A (vicina a [Trans(G)] T ) non negativa, stocastica per colonne, irriducibile, con n − 1 dei suoi autovalori di modulo strettamente minore di 1, in modo che
∃ ! ˜ p > 0, k˜ pk 1 = 1 tale che ˜ p = A˜ p, (˜∗)
2
