title: Matrice irriducibile
text: # 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 $n$, 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.
  