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={\begin{pmatrix}A_{11}&A_{12}\\0&A_{22}\\\end{pmatrix}}$

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 che $PAP^{-1}=PAP^{T}$ è triangolare a blocchi 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 associatagli 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=PAP^{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}={\mathbf {e} _{i}}^{T}P^{T}BP\mathbf {e} _{j}=(P\mathbf {e} _{i})^{T}B(P\mathbf {e} _{j})={\mathbf {e} _{\sigma (i)}}^{T}B\mathbf {e} _{\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,\ldots ,|Q|\}$ e $\sigma (P)=\{|Q|+1,\ldots ,|Q|+|P|=n\}$. Allora la matrice $B=PAP^{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=PAP^{T}$ della seguente forma:

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

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.