An $n\times n$ matrix $A$ is said to be a reducible matrix if and only if for some permutation matrix $P$ , the matrix $P^TAP$ is block upper triangular. If a square matrix is not reducible, it is said to be an irreducible matrix.

The following conditions on an $n\times n$ matrix $A$ are equivalent.

1. $A$ is an irreducible matrix.
2. The digraph associated to $A$ is strongly connected.
3. For each $i$ and $j$ , there exists some $k$ such that $(A^k)_{ij}>0$ .
4. For any partition $J\sqcup K$ of the index set $\{1,2,\dots,n\}$ , there exist $j\in J$ and $k\in K$ such that $a_{jk}\ne 0$ .

For certain applications, irreducible matrices are more useful than reducible matrices. In particular, the Perron-Frobenius theorem gives more information about the spectra of irreducible matrices than of reducible matrices.