Matrice irriducibile

In matematica, in particolare in algebra lineare, una matrice ${\displaystyle A}$ che agisce su uno spazio vettoriale ${\displaystyle V}$ si dice riducibile se ${\displaystyle V}$ possiede un sottospazio proprio non banale ${\displaystyle W}$ stabile per ${\displaystyle A}$ (o ${\displaystyle A}$-invariante), ovvero per cui ${\displaystyle AW}$ è contenuto in ${\displaystyle W}$.

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

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

Una matrice ${\displaystyle A}$ che non è riducibile si dice irriducibile.

Matrice irriducibile per permutazioni

Una matrice ${\displaystyle A}$ per cui esiste una matrice di permutazione ${\displaystyle P}$ tale per cui ${\displaystyle PAP^{-1}=PAP^{T}}$[1] sia triangolare a blocchi diagonali quadrati si dice riducibile per permutazioni[2]. 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 ${\displaystyle i}$-esimo al nodo ${\displaystyle j}$-esimo se e solo se l'elemento ${\displaystyle a_{ij}}$ è diverso da ${\displaystyle 0}$. Il grafo associato si dice fortemente connesso se per ogni coppia ${\displaystyle (i,j)}$ esiste un cammino che permetta di raggiungere ${\displaystyle j}$ a partire da ${\displaystyle 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 ${\displaystyle P}$ matrice di permutazione, il grafo associato alla matrice ${\displaystyle B=PAP^{T}=(b_{ij})}$ è lo stesso grafo associato ad ${\displaystyle A=(a_{ij})}$, a meno di riordinare i nodi secondo la permutazione ${\displaystyle \sigma \in S_{n}}$[3] associata a ${\displaystyle P}$. Infatti vale che:

${\displaystyle 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 ${\displaystyle B}$ esiste un arco da ${\displaystyle \sigma (i)}$ a ${\displaystyle \sigma (j)}$ se e solo se ne esiste uno da ${\displaystyle i}$ a ${\displaystyle j}$ nel grafo di ${\displaystyle A}$.

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

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

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

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

Note

1. Una matrice di permutazione è sempre ortogonale, ovverosia ${\displaystyle PP^{T}=I}$, e dunque ${\displaystyle P^{T}=P^{-1}}$.
2. In alcuni contesti è utilizzato il termine matrice riducibile per riferirsi alle matrici riducibili per permutazioni.
3. ${\displaystyle S_{n}}$ rappresenta il gruppo simmetrico.

Bibliografia

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