Teoremi di Gershgorin

In matematica, e più precisamente in algebra lineare, i teoremi di Gershgorin sono tre teoremi riguardanti la localizzazione degli autovalori di una matrice a termini nel campo complesso. Il nome di questi teoremi è dovuto a quello del matematico bielorusso Semyon Aranovich Gershgorin, che per primo li ha enunciati nel 1931.

Cerchi di Gershgorin

Rappresentazione nel piano complesso dei cerchi di Gershgorin della matrice $A={\begin{pmatrix}-2&1&0\\-1&2&-1\\1&-2&4\end{pmatrix}}$. Le croci indicano la posizione effettiva degli autovalori.

Una definizione di basilare importanza nella comprensione di questi teoremi è quella del cerchio di Gershgorin.

Sia $A=(a_{ij})$ una matrice in $\mathbb {C} ^{n\times n}$. Si consideri l'elemento $i$-esimo $a_{ii}$ della diagonale principale di $A$ e la somma dei moduli degli elementi della riga $i$-esima fuori della diagonale:

$R_{i}=\sum _{j=1,\,j\neq i}^{n}|a_{ij}|.$

Queste due quantità individuano il seguente sottoinsieme del piano complesso:

$K_{i}:={\bar {B}}_{R_{i}}(a_{ii})=\{z\in \mathbb {C} :|z-a_{ii}|\leq R_{i}\},$

corrispondente ad un disco di raggio $R_{i}$ centrato in $a_{ii}$, che viene detto $i$-esimo cerchio di Gershgorin della matrice $A$.

Primo teorema di Gershgorin

Teorema. Sia $A\in \mathbb {C} ^{n\times n}$ e sia $\lambda \in \operatorname {sp} (A)$ un suo autovalore. Se $x_{h}$ è una coordinata di modulo massimo di un autovettore $\mathbf {x}$ relativo a $\lambda$, allora $\lambda \in K_{h}$. In particolare esiste $h$ tale per cui $\lambda \in K_{h}$, ovverosia $\lambda$ appartiene almeno ad un cerchio di Gershgorin di $A$.

Dimostrazione. Sia $\lambda$ un autovalore di $A$ e sia $\mathbf {x} =(x_{j})$ un autovettore relativo a $\lambda$. Sia $h$ l'indice di una coordinata di $\mathbf {x}$ con modulo massimo tra tutte le coordinate. Dal momento che $\mathbf {x}$ è autovettore, $\mathbf {x}$ non è nullo, e dunque $|x_{h}|\neq 0$. Sempre perché $\mathbf {x}$ è un autovettore, vale l'identità $A\mathbf {x} =\lambda \mathbf {x}$, che, applicata all'$h$-esima coordinata, implica che:

$\sum _{j=1}^{n}a_{hj}x_{j}=\lambda x_{h}.$

Allora, manipolando la somma, otteniamo che:

$\lambda x_{h}-a_{hh}x_{h}=\sum _{j=1,\,j\neq h}^{n}a_{hj}x_{j}.$

Dividendo entrambi i membri per $x_{h}$ (che ricordiamo essere non nullo), passando ai moduli e applicando la disuguaglianza triangolare otteniamo che:

$|\lambda -a_{hh}|=\left|\sum _{j=1,\,j\neq h}^{n}a_{hj}{\frac {x_{j}}{x_{h}}}\right|\leq \sum _{j=1,\,j\neq h}^{n}|a_{hj}|{\frac {|x_{j}|}{|x_{h}|}}\overbrace {\leq } ^{(*)}\sum _{j=1,\,j\neq h}^{n}|a_{hj}|=R_{h},$

dove la disuguaglianza $(*)$ vale poiché $|x_{j}|\leq |x_{h}|$ $\forall j$ data la scelta iniziale di $h$. Pertanto $\lambda \in K_{h}$, da cui la tesi.

Estensione del teorema e generalizzazione agli ovali di Cassini

Dal momento che gli autovalori di $A=(a_{ij})$ sono invarianti per similitudine, se $D$ è una matrice diagonale invertibile, allora $D^{-1}AD=(d_{i}^{-1}a_{ij}d_{j})$ ha gli stessi autovalori di $A$, mantenendone invariati i centri dei cerchi di Gershgorin e riscalandone soltanto il raggio. In particolare, il nuovo raggio, indicato con $R_{i}'$, è calcolato mediante la seguente formula:

$R_{i}'={\frac {1}{|d_{i}|}}\sum _{j=1,\,j\neq i}|a_{ij}|\cdot |d_{j}|.$

Pertanto, il primo teorema di Gershgorin può essere esteso al seguente risultato:

Teorema. Sia $A\in \mathbb {C} ^{n\times n}$. Allora $\operatorname {sp} (A)\subseteq \bigcap _{d\in D}\bigcup _{i=1}^{n}\left\{z\in \mathbb {C} :|z-a_{ii}|\leq {\frac {1}{d_{i}}}\sum _{j=1,\,j\neq i}^{n}a_{ij}\cdot d_{j}\right\}$, dove $D\subseteq \mathbb {C} ^{n}$ è un insieme di vettori con coordinate positive.

Confronto tra i cerchi di Gershgorin (in blu, verde e giallo) e gli ovali di Cassini (in rosso) relativi alla matrice $A={\begin{pmatrix}-2&1&0\\-1&2&-1\\1&-2&4\end{pmatrix}}$. Le croci indicano la posizione effettiva degli autovalori.

Il teorema può essere esteso anche abbandonando la struttura dei cerchi di Gershgorin e riducendosi a degli ovali di Cassini della forma $C(a,b,r):=\{z\in \mathbb {C} :|(z-a)(z-b)|\leq r\}$, secondo il seguente enunciato:

Teorema (degli ovali di Brauer). Sia $A\in \mathbb {C} ^{n\times n}$ e sia $\lambda \in \operatorname {sp} (A)$ un suo autovalore. Allora $\lambda$ è contenuto nell'unione $\bigcup _{i>j}C(a_{ii},a_{jj},r_{i}r_{j})$ di ovali di Cassini, dove $r_{i}$ è il raggio dell'$i$-esimo cerchio di Gershgorin di $A$.

Secondo teorema di Gershgorin

Teorema. Sia $A\in \mathbb {C} ^{n\times n}$. Siano $I_{1}$ e $I_{2}$ due famiglie di indici con $I_{1}\cup I_{2}=\{1,\ldots ,n\}$ e $I_{1}\cap I_{2}=\varnothing$.

Si definiscano $M_{1}:=\bigcup _{i\in I_{1}}K_{i}$ e $M_{2}:=\bigcup _{i\in I_{2}}K_{i}$. Se $M_{1}\cap M_{2}=\varnothing$, allora esattamente $|I_{1}|$ autovalori appartengono a $M_{1}$ (contati con molteplicità algebrica) e i restanti $|I_{2}|=n-|I_{1}|$ appartengono a $M_{2}$.

Questo teorema porta con sé delle importanti implicazioni. Ad esempio, per $A\in \mathbb {R} ^{n\times n}$, si ricava immediatamente che un cerchio disgiunto da tutti gli altri deve per forza contenere un solo autovalore, che, in quanto unico, dovrà per forza essere reale (se fosse complesso non reale, allora nello stesso cerchio dovrebbe trovarsi anche il suo autovalore complesso coniugato, e dunque il cerchio conterrebbe due autovalori invece che uno solo).

Idea di dimostrazione: La dimostrazione fa uso di un argomento di continuità. Sia $D=\operatorname {diag} (A)$ la matrice diagonale ottenuta prendendo la diagonale di $A$ e ponendo $0$ tutti gli altri termini. Si consideri la funzione $B:[0,1]\to \mathbb {C} ^{n\times n}$ tale per cui $B(t)=D+t(A-D)$ (ovverosia $B$ parametrizza il cammino fatto sul segmento $[D,A]$ che congiunge $D$ ad $A$). Chiaramente $B$ è una funzione continua dallo spazio topologico $[0,1]$ con l'usuale topologia euclidea allo spazio $\mathbb {C} ^{n\times n}$ avente la topologia indotta dall'analoga euclidea di $\mathbb {C} ^{n^{2}}$. Sia $K_{i}(t)$ l'$i$-esimo cerchio di Gershgorin di $B(t)$. Si osserva che $K_{i}(t)$ ha centro $a_{ii}$ indipendentemente da $t$, mentre il suo raggio è $tR_{i}$, dove $R_{i}$ è il raggio di $K_{i}(1)$, il cerchio riferito ad $A$. Pertanto $K_{i}(t_{1})\subseteq K_{i}(t_{2})$ per $t_{1}\leq t_{2}$. Si ricorda che gli zeri di un polinomio dipendono continuamente dai coefficienti, e che gli autovalori di $B(t)$ sono gli zeri del polinomio caratteristico di $B(t)$, i cui coefficienti dipendono continuamente dai termini di $B(t)$, e dunque da $t$. Pertanto, poiché anche $B(t)$ è continua, gli autovalori di $B(t)$ dipendono continuamente da $t$. Sia $\lambda (t)$ il cammino continuo di uno degli autovalori. Allora, se $\lambda (0)\in M_{1}$, $\lambda (t)\in M_{1}$ per ogni $t\in [0,1]$; altrimenti esisterebbe uno $t_{0}$ per cui $\lambda (t)\notin K_{i}(1)\supseteq K_{i}(t_{0})$ per ogni $i$ (il che violerebbe il primo teorema di Gershgorin) o varrebbe $t_{0}\in M_{1}\cap M_{2}=\varnothing$, assurdo. Analogamente vale lo stesso per $M_{2}$. Pertanto $M_{1}$ contiene lo stesso numero di autovalori di $\bigcup _{i\in I_{1}}K_{i}(0)=\bigcup _{i\in I_{1}}\{a_{ii}\}$, e quindi $|I_{1}|$ autovalori. Analogamente $M_{2}$ ne contiene $|I_{2}|$, da cui la tesi.

Terzo teorema di Gershgorin

Teorema. Sia $\lambda$ un autovalore di una matrice $A\in \mathbb {C} ^{n\times n}$ irriducibile per permutazioni. Se vale l'implicazione $\lambda \in K_{i}\implies \lambda \in \partial K_{i}$, allora $\lambda \in K_{i}$ $\forall i$, e dunque $\lambda \in \cap _{i=1}^{n}\partial K_{i}$.

Dimostrazione. Sia $h$ tale per cui $\lambda \in K_{h}$. Ripercorrendo la stessa dimostrazione del primo teorema di Gershgorin si ottiene che:

$|\lambda -a_{hh}|\leq \sum _{j=1,\,j\neq h}^{n}|a_{hj}|{\frac {|x_{j}|}{|x_{h}|}}\leq \sum _{j=1,\,j\neq h}^{n}|a_{hj}|=R_{h}.$

Dal momento che $\lambda$ appartiene alla frontiera $\partial K_{h}$, allora il primo e l'ultimo membro devono essere uguali, e così tutte le disuguaglianze si rivelano essere uguaglianze. Affinché ciò accada, è necessario che valga $|x_{j}|=|x_{h}|$ per tutti gli indici $j$ per cui $a_{hj}\neq 0$; ciò implica che per tutti questi indici $j$ anche $x_{j}$ è una coordinata di modulo massimo per $\mathbf {x}$: per il primo teorema di Gershgorin, allora $\lambda \in K_{j}$ per tali $j$.

Poiché $A$ è irriducibile per permutazioni, il grafo associato ad $A$ è fortemente connesso, e dunque deve esistere una sequenza di cammini di indici (eventualmente ripetuti) $h_{1}=h$, $h_{2}$, ..., $h_{m}$ con $m\geq n$ tale per cui appaiano in essa tutti i numeri da $1$ a $n$. Dacché esiste dunque un arco da $h_{1}=h$ a $t:=h_{2}$, $a_{ht}\neq 0$, e dunque, per il ragionamento di prima, $\lambda \in K_{t}$. Reiterando la stessa dimostrazione fino alla fine della sequenza sostituendo ad $h$ e $t$ gli indici successivi nella sequenza, si è mostrato dunque che $\lambda \in K_{i}$ per ogni $i$, da cui la tesi.

Bibliografia

• D. Bini, M. Capovani, O. Menchi, Metodi numerici per l'algebra lineare, Zanichelli, Bologna, 1988.
• R. S. Varga, Geršgorin and His Circles, Springer, 2004.