Matrice irriducibile

In matematica, in particolare in algebra lineare, una matrice $A$ che agisce su uno spazio vettoriale $V$ si dice riducibile se $V$ possiede un sottospazio proprio non banale $V_{1}$ stabile per $A$, ovvero per cui $AV_{1}$ è contenuto in $V_{1}$.

Per ogni matrice riducibile esiste una matrice di cambiamento di base $B$ tale che $B^{-1}AB$ è una matrice triangolare a blocchi:

$B^{-1}AB={\begin{pmatrix}A_{11}&A_{12}\\0&A_{22}\\\end{pmatrix}}$

Una matrice $A$ che non è riducibile si dice irriducibile.

Attenzione.

In alcuni contesti, una matrice riducibile è una matrice $A$ per cui esiste una matrice di permutazione $P$ tale che $PAP^{-1}$ è triangolare a blocchi.

Irriducibilità e grafo associato

Data una qualsiasi matrice, posso costruire un grafo avente come nodi gli indici della matrice: in particolare, il nodo $i$-esimo è connesso al nodo $j$-esimo se l'elemento $a_{ij}$ è diverso da $0$. Il grafo associato si dice fortemente connesso se per ogni coppia $(i,j)$ posso raggiungere $j$ a partire da $i$. Una matrice è irriducibile se e solo se il grafo di adiacenza ad esso associato è fortemente connesso. In altre parole, una matrice è riducibile se e solo se il grafo di adiacenza ad esso associato non è fortemente connesso.

Dimostrazione:

Provo che una matrice è riducibile se e solo se il grafo non è fortemente connesso. Noto che il grafo non varia se permuto gli elementi di una matrice.

• Suppongo che una matrice sia riducibile, posso portarla pertanto nella forma

${\begin{pmatrix}A_{11}&A_{12}\\0&A_{22}\\\end{pmatrix}}$

Sia $m$ la dimensione del blocco $A_{11}$; i nodi del grafo da $m+1$ a $n$ non saranno perciò connessi con quelli da $1$ a $m$, quindi il grafo non è fortemente connesso.

• Viceversa, sia il grafo non fortemente connesso. In particolare, esiste un nodo $p$ dal quale non posso raggiungere un nodo $q$, definisco i due insiemi seguenti: $P$ l'insieme dei nodi raggiungibili da $p$ e $Q$ l'insieme dei nodi non raggiungibili da $p$. Noto che tutti i nodi di $Q$ non sono raggiungibili dai nodi di $P$. Dispongo la matrice in modo che su riga e colonna tutti gli indici di $Q$ precedano quelli di $P$ ed ottengo una matrice nella forma ridotta desiderata.

Bibliografia

• D.Bini, M.Capovani, O.Menchi. Metodi Numerici per l'Algebra Lineare. Zanichelli, Bologna 1988.