Matrice irriducibile

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}}$ 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.