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 $W$ stabile per $A$ (o $A$-invariante), ovvero per cui $AW$ è contenuto in $W$.

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=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ 0& A_{22}\end{array}\right)$

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

Matrice irriducibile per permutazioni

Una matrice $A$ per cui esiste una matrice di permutazione $P$ tale per cui $PA{P}^{-1}=PA{P}^T$ sia triangolare a blocchi diagonali quadrati si dice riducibile per permutazioni. Analogamente si definisce una matrice irriducibile per permutazioni.

Relazione tra l'irriducibilità per permutazioni e il grafo associato

Data una qualsiasi matrice, è possibile costruire un grafo associatole avente come nodi gli indici della matrice con il seguente schema: esiste un arco dal nodo $i$-esimo al nodo $j$-esimo se e solo se l'elemento $a_{ij}$ è diverso da $0$. Il grafo associato si dice fortemente connesso se per ogni coppia $(i,j)$ esiste un cammino che permetta di raggiungere $j$ a partire da $i$.

Teorema. Una matrice è riducibile per permutazioni se e solo se il grafo ad essa associato non è fortemente connesso. Equivalentemente, una matrice è irriducibile per permutazioni se e solo se il grafo ad essa associato è fortemente connesso.

Dimostrazione. Osserviamo preliminarmente che, data $P$ matrice di permutazione, il grafo associato alla matrice $B=PA{P}^T=(b_{ij})$ è lo stesso grafo associato ad $A=(a_{ij})$, a meno di riordinare i nodi secondo la permutazione $\sigma \in S_n$ associata a $P$. Infatti vale che:

$a_{ij}={{𝐞}_i}^T{P}^{T}BP{𝐞}_j=(P{𝐞}_i{)}^{T}B(P{𝐞}_j)={{𝐞}_{\sigma (i)}}^{T}B{𝐞}_{\sigma (j)}=b_{\sigma (i)\sigma (j)}.$

e dunque nel grafo di $B$ esiste un arco da $\sigma (i)$ a $\sigma (j)$ se e solo se ne esiste uno da $i$ a $j$ nel grafo di $A$.

• Supponiamo che il grafo di $A$ non sia fortemente connesso. Esistono allora due nodi $p$, $q$ tali per cui da $p$ non è possibile raggiungere $q$. Sia $P$ l'insieme dei nodi raggiungibili da $p$ e $Q$ l'insieme dei nodi non raggiungibili da $p$. Si osserva che $p\in P$ e che $q\in Q$, e dunque entrambi gli insiemi sono non vuoti. Si osserva inoltre che nessun nodo di $P$ può essere collegato ad uno di $Q$ (altrimenti esisterebbe un cammino da $p$ a un nodo di $Q$, assurdo). Sia $\sigma \in S_n$ una permutazione tale per cui $\sigma (Q)=\{1,\dots ,|Q|\}$ e $\sigma (P)=\{|Q|+1,\dots ,|Q|+|P|=n\}$. Allora la matrice $B=PA{P}^T$ è triangolare a blocchi, e dunque $A$ è riducibile.

• Viceversa, supponiamo che $A$ sia riducibile. Tramite una matrice di permutazione $P$ è dunque possibile ottenere una matrice $B=PA{P}^T$ della seguente forma:

$B=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ 0& A_{22}\end{array}\right),$

con $A_{11}$ e $A_{22}$ matrici quadrate. Sia $m$ la dimensione del blocco $A_{11}$. I nodi del grafo da $m+1$ a $n$ non possono essere connessi con quelli da $1$ a $m$, dal momento che sono collegati solo a sé stessi. Pertanto il grafo non è fortemente connesso.

Bibliografia

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