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

Per ogni matrice riducibile esiste una matrice di cambiamento di base tale che è una matrice triangolare a blocchi:

Una matrice che non è riducibile si dice irriducibile.

Matrice irriducibile per permutazioni Una matrice per cui esiste una matrice di permutazione tale per cui Una matrice di permutazione è sempre ortogonale, ovverosia , e dunque . sia triangolare a blocchi diagonali quadrati si dice riducibile per permutazioniIn alcuni contesti è utilizzato il termine matrice riducibile per riferirsi alle matrici riducibili 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 -esimo al nodo -esimo se e solo se l'elemento è diverso da . Il grafo associato si dice fortemente connesso se per ogni coppia esiste un cammino che permetta di raggiungere a partire da .

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 matrice di permutazione, il grafo associato alla matrice è lo stesso grafo associato ad , a meno di riordinare i nodi secondo la permutazione rappresenta il gruppo simmetrico. associata a . Infatti vale che:

e dunque nel grafo di esiste un arco da a se e solo se ne esiste uno da a nel grafo di .

Supponiamo che il grafo di non sia fortemente connesso. Esistono allora due nodi , tali per cui da non è possibile raggiungere . Sia l'insieme dei nodi raggiungibili da e l'insieme dei nodi non raggiungibili da . Si osserva che e che , e dunque entrambi gli insiemi sono non vuoti. Si osserva inoltre che nessun nodo di può essere collegato ad uno di (altrimenti esisterebbe un cammino da a un nodo di , assurdo). Sia una permutazione tale per cui e . Allora la matrice è triangolare a blocchi, e dunque è riducibile.

Viceversa, supponiamo che sia riducibile. Tramite una matrice di permutazione è dunque possibile ottenere una matrice della seguente forma:

con e matrici quadrate. Sia la dimensione del blocco . I nodi del grafo da a non possono essere connessi con quelli da a , dal momento che sono collegati solo a sé stessi. Pertanto il grafo non è fortemente connesso.

Note

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

Categoria:Matrici quadrate