---
tag: 7Q60BB01YG
kind: concept
name: Irreducible matrix
msc: [15B48, 05C50]
specializes: [0JXZKX526R]
sources:
  - url: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem
---

## Summary

A square matrix is irreducible when no simultaneous permutation of its rows and columns puts it into block upper triangular form.
For a nonnegative matrix this means that its directed graph is strongly connected: every index can reach every other index.
Irreducibility is the main hypothesis of the [[Perron–Frobenius theorem|62NS7PV1M9]] for nonnegative matrices that are not positive.

## Explanations

### L1 human

Read an $n \times n$ matrix as a network: there is an arrow from $i$ to $j$ when the entry $a_{ij}$ is not zero.
The matrix is irreducible when you can travel along arrows from any node to any other node.
Then the matrix does not split into a part that never feeds back into the rest.
For example, $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ has arrows $1 \to 2$ and $2 \to 1$, so it is irreducible.
The matrix $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ has no arrow from $2$ to $1$, so it is reducible.