Appendice B — Il teorema di Perron-Frobenius
B.1 Introduzione
Il teorema di Perron-Frobenius è fondamentale nello studio degli splitting non negativi e dei teoremi di confronto sulle M-matrici. In questa sezione dimostriamo i due risultati principali.
Autovalori e raggio spettrale
Teorema B.1 Sia \bm{A}\geq 0 una matrice quadrata, \bm{x}\geq 0 un vettore non nullo e \alpha\geq 0. Se vale
\alpha\bm{x}\leq\bm{A}\bm{x}
allora \alpha\leq\varrho(\bm{A}). Se inoltre \alpha\bm{x}<\bm{A}\bm{x} allora \alpha<\varrho(\bm{A}).
Dimostrazione. Osserviamo che
\begin{aligned} \alpha\bm{A}\bm{x}\leq\bm{A}^2\bm{x} &\quad\implies\quad \alpha^2\bm{x}\leq\bm{A}^2\bm{x} \\ \alpha\bm{A}^{k-1}\bm{x}\leq\bm{A}^k\bm{x} &\quad\implies\quad \alpha^k\bm{x}\leq\bm{A}^k\bm{x} \end{aligned} \tag{B.1}
moltiplicando le disuguaglianze B.1 per il vettore \bm{e}=\begin{pmatrix}1,1,\ldots,1\end{pmatrix}^T
\alpha^k\bm{e}^T\bm{x}\leq\bm{e}^T\bm{A}^k\bm{x} \\ \Downarrow\\ \alpha^k\left|\left|\bm{x}\right|\right|_1\leq\bm{e}^T\bm{A}^k\bm{x} \leq\left|\left|\bm{e}\right|\right|_1\left|\left|\bm{A}^k\right|\right|_1\left|\left|\bm{x}\right|\right|_1
estraendo le radici k-esime e passando al limite per k\mapsto\infty usando il corollario Corollario 25.1
\alpha\left|\left|\bm{x}\right|\right|_1^{\tfrac{1}{k}}\leq \left|\left|\bm{e}\right|\right|_1^{\tfrac{1}{k}} \left|\left|\bm{A}^k\right|\right|_1^{\tfrac{1}{k}} \left|\left|\bm{x}\right|\right|_1^{\tfrac{1}{k}} \\[.25em] \alpha=\lim_{k\mapsto\infty}\alpha \left|\left|\bm{x}\right|\right|_1^{\tfrac{1}{k}}\leq \lim_{k\mapsto\infty} \left|\left|\bm{e}\right|\right|_1^{\tfrac{1}{k}} \left|\left|\bm{A}^k\right|\right|_1^{\tfrac{1}{k}} \left|\left|\bm{x}\right|\right|_1^{\tfrac{1}{k}} =\varrho(\bm{A})
se \alpha\bm{x}<\bm{A}\bm{x} allora esiste \alpha<\alpha' tale che \alpha'\bm{x}\leq\bm{A}\bm{x} e quindi \alpha<\alpha'\leq\varrho(\bm{A}).
Autovalore matrice irriducibile
Lemma B.1 Sia \bm{A}\geq 0 irriducibile. Allora \varrho(\bm{A})>0 è un autovalore di \bm{A} ed esiste un vettore \bm{u}>0 tale che \bm{A}\bm{u}=\varrho(\bm{A})\bm{u}.
Dimostrazione. Poiché \bm{A} è irriducibile, si ha
\bm{A}\bm{e}>0
da cui, scegliendo \epsilon>0 sufficientemente piccolo, segue
\bm{A}\bm{e}>\epsilon\bm{e}
Applicando il teorema Teorema B.1 otteniamo \varrho(\bm{A})>\epsilon>0. Sia \bm{A}\bm{x}=\lambda\bm{x},\ \bm{x}\neq 0 con \left\lvert\lambda\right\rvert=\varrho(\bm{A}), ne segue,
\bm{A}\left\lvert\bm{x}\right\rvert=\varrho(\bm{A})\left\lvert\bm{x}\right\rvert\qquad\text{con}\qquad\left\lvert\bm{x}\right\rvert\geq 0,
da cui
\varrho(\bm{A})\left\lvert\bm{x}\right\rvert=\left\lvert\lambda\right\rvert\left\lvert\bm{x}\right\rvert= \left\lvert\lambda\bm{x}\right\rvert=\left\lvert\bm{A}\bm{x}\right\rvert \leq\left\lvert\bm{A}\right\rvert\left\lvert\bm{x}\right\rvert=\left\lvert\bm{A}\right\rvert\left\lvert\bm{x}\right\rvert.
Abbiamo quindi
\bm{y}=\bm{A}\left\lvert\bm{x}\right\rvert-\varrho(\bm{A})\left\lvert\bm{x}\right\rvert\geq 0 \tag{B.2}
Osserviamo che dalla B.2
(\bm{A}\left\lvert\bm{x}\right\rvert)_i=0 \quad\implies\quad \left\lvert x_i\right\rvert=0
ed ancora
\left\lvert x_i\right\rvert>0 \quad\implies\quad (\bm{A}\left\lvert\bm{x}\right\rvert)_i=0
quindi il vettore \left\lvert\bm{x}\right\rvert ed il vettore \bm{A}\left\lvert\bm{x}\right\rvert hanno gli eventuali zeri nelle stesse posizioni. Sia
\bm{w}\quad\text{definito come:}\quad w_i=\begin{cases} 1 & \left\lvert x_i\right\rvert=0 \\ 0 & \text{altrimenti} \end{cases}
senza perdere in generalità effettuando eventualmente una permutazione di indici possiamo supporre che
\bm{w}=\begin{pmatrix}0,0,\ldots,0,1,1,\ldots,1\end{pmatrix}^T= \begin{pmatrix}0\\\bm{e}\end{pmatrix}
possiamo quindi scrivere
0=\bm{w}^T\bm{A}\left\lvert\bm{x}\right\rvert= \begin{matrix} \begin{pmatrix}0&\bm{e}^T\end{pmatrix} \\ \vphantom{0} \end{matrix} \begin{pmatrix}\bm{B}&\bm{C}\\\bm{D}&\bm{E}\end{pmatrix} \begin{pmatrix}\left\lvert\bm{x}^1\right\rvert\\ 0\end{pmatrix}
dove
\left\lvert\bm{x}\right\rvert=\begin{pmatrix}\left\lvert\bm{x}^1\right\rvert\\ 0\end{pmatrix}
e sviluppando i termini
0=\bm{e}^T\bm{D}\left\lvert\bm{x}^1\right\rvert \quad\implies\quad \bm{D}=0
contraddicendo l’ipotesi di irriducibilità. Da questo segue che \left\lvert\bm{x}\right\rvert>0 e \bm{A}\left\lvert\bm{x}\right\rvert>0. Se \bm{y}=0 il teorema è dimostrato, altrimenti poniamo
\bm{E}=\begin{pmatrix}1 & 1 & \cdots & 1 \\ 1 & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & 1 \\ 1 & \cdots & 1 & 1\end{pmatrix}
e definiamo la matrice
\bm{A}_\epsilon = \bm{A}+\epsilon\bm{E}>0,\quad \forall\epsilon>0
ripetendo i ragionamenti fin qui fatti ora per la matrice \bm{A}_\epsilon arriviamo alla conclusione che \bm{y}=\bm{A}_\epsilon\left\lvert\bm{x}_\epsilon\right\rvert-\varrho(\bm{A}_\epsilon)\left\lvert\bm{x}_\epsilon\right\rvert\geq 0. Supponiamo \bm{y}\neq 0 moltiplicando \bm{y} per \bm{A}_\epsilon otteniamo
0<\bm{A}_\epsilon\bm{y}=\bm{A}^2_\epsilon\left\lvert\bm{x}_\epsilon\right\rvert- \varrho(\bm{A}_\epsilon)\bm{A}_\epsilon\left\lvert\bm{x}_\epsilon\right\rvert =\bm{A}_\epsilon\bm{z}-\varrho(\bm{A}_\epsilon)\bm{z} \\ \bm{z}=\bm{A}_\epsilon\left\lvert\bm{x}_\epsilon\right\rvert>0
cioè \varrho(\bm{A}_\epsilon)\bm{z}<\bm{A}_\epsilon\bm{z} ed applicando il teorema Teorema B.1 si ha \varrho(\bm{A}_\epsilon)<\varrho(\bm{A}_\epsilon) cioè una contraddizione. Quindi
\bm{A}_\epsilon\left\lvert\bm{x}_\epsilon\right\rvert= \varrho(\bm{A}_\epsilon)\left\lvert\bm{x}_\epsilon\right\rvert, \qquad \epsilon>0
usando la continuità e passando al limite per \epsilon\mapsto 0 segue \bm{A}\left\lvert\bm{x}\right\rvert=\varrho(\bm{A})\left\lvert\bm{x}\right\rvert. Allora \bm{u}=\left\lvert\bm{x}\right\rvert>0 è l’autovettore con autovalore \left\lvert\lambda\right\rvert=\varrho(\bm{A})>0 che cercavamo.
Autovalori e raggio spettrale
Lemma B.2 Sia \bm{A}\geq 0 irriducibile ed \bm{A}\bm{x}=\lambda\bm{x}, \bm{x}\neq 0 con \left\lvert\lambda\right\rvert=\varrho(\bm{A}) allora per un qualche angolo \theta\in\mathbb{R} vale e^{-i\theta}\bm{x}=\left\lvert\bm{x}\right\rvert.
Dimostrazione. osserviamo che dal lemma Lemma B.1 possiamo scrivere
\bm{A}\left\lvert\bm{x}\right\rvert=\varrho(\bm{A})\left\lvert\bm{x}\right\rvert \quad\text{con}\quad\left\lvert\bm{x}\right\rvert>0
da questa possiamo ricavare
\varrho(\bm{A})\left\lvert\bm{x}\right\rvert=\left\lvert\lambda\right\rvert\left\lvert\bm{x}\right\rvert =\left\lvert\bm{A}\bm{x}\right\rvert\leq\bm{A}\left\lvert\bm{x}\right\rvert =\varrho(\bm{A})\left\lvert\bm{x}\right\rvert \\ \Downarrow\\ \left\lvert\bm{A}\bm{x}\right\rvert=\bm{A}\left\lvert\bm{x}\right\rvert
e passando alle componenti
\sum_{j=1}^n A_{i,j}\left\lvert x_j\right\rvert= \left\lvert\displaystyle{\sum_{j=1}^n A_{i,j}x_j}\right\rvert \qquad\text{per $i=1,2,\ldots,n$}
Per avere l’uguaglianza tutti i numeri A_{i,j}x_j devono stare sullo stesso raggio nel piano complesso. Sia \theta\in\mathbb{R} l’ angolo di questo raggio, allora
A_{i,j}x_j=e^{i\theta} A_{i,j}\left\lvert x_j\right\rvert \qquad\text{e quindi}\qquad A_{i,j}e^{-i\theta}x_j= A_{i,j}\left\lvert x_j\right\rvert>0
e poiché \bm{A} è irriducibile, fissato j esisterà un indice i per cui A_{i,j}>0 e da questo e^{-i\theta}x_j>0
Limitazione autovalori
Teorema B.2 Sia data una matrice \bm{A}\geq 0 irriducibile, allora risulta \left\lvert\lambda\right\rvert<\varrho(\bm{A}) per ogni autovalore \lambda\neq\varrho(\bm{A}).
Dimostrazione. Per definizione di raggio spettrale \left\lvert\lambda\right\rvert\leq\varrho(\bm{A}) per ogni \lambda autovalore di \bm{A}. Supponiamo \left\lvert\lambda\right\rvert=\varrho(\bm{A}) con \bm{A}\bm{x}=\lambda\bm{x}, dal lemma precedente ponendo \bm{w}=e^{-i\theta}\bm{x}>0 otteniamo \bm{A}\bm{w}=\lambda\bm{w} ed essendo i vettori \bm{A}\bm{w} e \bm{w} reali segue che \lambda è reale e quindi \lambda=\varrho(\bm{A}).
Raggio spettrale e autovalore
Teorema B.3 Sia \bm{A}\geq 0 irriducibile allora \varrho(\bm{A}) è un autovalore algebricamente semplice di \bm{A}.
Dimostrazione. Se così non fosse esisterebbero due autovettori \bm{x} ed \bm{y} tali che \bm{A}\bm{x}=\varrho(\bm{A})\bm{x},\quad\bm{A}\bm{y}=\varrho(\bm{A})\bm{y} \qquad\text{con}\qquad \left|\left|\bm{x}\right|\right|_1=\left|\left|\bm{y}\right|\right|_1=1.
per il lemma Lemma B.2 \bm{p}=e^{-i\theta_1}\bm{x}>0, \bm{q}=e^{-i\theta_2}\bm{y}>0, per due opportuni angoli \theta_1 e \theta_2. Sia
\beta=\min\left\{\dfrac{q_i}{p_i}\,:\,i=1,2,\ldots,n\right\},\qquad \bm{r}=\bm{q}-\beta\bm{p}
allora \bm{r}\geq 0 ed almeno una sua componente è nulla, se \bm{r} non fosse identicamente nullo si avrebbe
\bm{A}\bm{r}=\bm{A}\bm{q}-\beta\bm{A}\bm{p}=\varrho(\bm{A})(\bm{q}-\beta\bm{p}) =\varrho(\bm{A})\bm{r}
e quindi \bm{A}\bm{r}-\varrho(\bm{A})\bm{r}=0. Ripetendo i ragionamenti fatti nel lemma Lemma B.1 per l’B.2 dalla irriducibilità segue che \bm{r}>0 e poiché questo non può essere vero concludiamo che \bm{r}=0 da cui \bm{q}=\beta\bm{p} e di conseguenza \bm{x}=\beta e^{i(\theta_1-\theta_2)}\bm{y}.
Questi risultati si riassumono nel ben noto teorema di Perron-Frobenius:
B.2 Teorema di Perron-Frobenius
Teorema B.4 Se \bm{A}\geq0 è irriducibile allora
\varrho(\bm{A})>0
\varrho(\bm{A}) è un autovalore algebricamente semplice di \bm{A}
\left\lvert\lambda\right\rvert<\varrho(\bm{A}) per ogni autovalore \lambda\neq\varrho(\bm{A}) cioè \varrho(\bm{A}) è l’unico autovalore di massimo modulo.
all’ autovalore \varrho(\bm{A}) corrisponde un autovettore \bm{x}>0 detto vettore di Perron1.
\varrho(\bm{A}) è una funzione crescente nelle variabili A_{i,j} cioè se \bm{B}\geq\bm{A}>0 con \bm{A}\neq\bm{B} allora \varrho(\bm{B})>\varrho(\bm{A}).
Dimostrazione. I punti 1-4 sono stati dimostrati nei teoremi precedenti. Bisogna solo provare la proprietà di monotonia del punto 5. Sia \bm{x}>0 il vettore di Perron per la matrice \bm{A} allora avremo
\bm{B}\bm{x}\geq\bm{A}\bm{x}=\varrho(\bm{A})\bm{x}, \qquad\text{con}\qquad \bm{A}\bm{x}\neq\bm{B}\bm{x}
e definendo
\bm{y}=\bm{B}\bm{x}-\varrho(\bm{A})\bm{x}\geq0, \qquad\text{con}\qquad \bm{y}\neq 0
e \bm{z}=\bm{B}\bm{x}>0 possiamo calcolare
0<\bm{B}\bm{y}=\bm{B}\bm{z}-\varrho(\bm{A})\bm{B}\bm{x}=\bm{B}\bm{z}-\varrho(\bm{A})\bm{z}
e quindi \bm{B}\bm{z}>\varrho(\bm{A})\bm{z} ed applicando il teorema Teorema B.1 otteniamo \varrho(\bm{A})<\varrho(\bm{B})
con procedimenti di passaggio al limite possiamo provare dei risultati analoghi per matrici non negative. Infatti se \bm{A}\geq 0 definendo la matrice \bm{E}>0 come nel lemma Lemma B.1
\bm{A}_\epsilon=\bm{A}+\epsilon\bm{E}>0,\qquad\forall\epsilon>0
è irriducibile e quindi possiamo applicare il teorema di Perron. Passando al limite per \epsilon\mapsto 0 in generale perdiamo le disuguaglianze strette e le molteplicità; quindi:
Monotonia raggio spettrale
Teorema B.5 Se \bm{A}\geq 0 allora
\varrho(\bm{A}) è un autovalore di \bm{A}
Se \varrho(\bm{A})>0 esiste un corrispondente autovettore \bm{x}\geq 0.
\varrho(\bm{A}) è una funzione non decrescente nelle entrate A_{i,j} cioè se \bm{A}\geq\bm{B}\geq 0 allora \varrho(\bm{A})>\varrho(\bm{B}).
Dimostrazione. basta osservare che
\begin{aligned} \bm{Q}_2 \geq \bm{Q}_1 & \implies \bm{A}^{-1} \bm{Q}_2 \geq \bm{A}^{-1}\bm{Q}_1 \quad\implies \\ \sigma(\bm{A}^{-1}\bm{Q}_2 )\geq \sigma(\bm{A}^{-1}\bm{Q}_1 ) & \implies \sigma(\bm{P}_2^{-1}\bm{Q}_2 ) \geq \sigma(\bm{P}_1^{-1}\bm{Q}_1 ) \end{aligned}