Similar matrices share many invariants: determinant, trace, characteristic polynomial, rank, eigenvalues, etc., but the reverse implication is not true. Two matrices sharing any of these invariants does not prove that they are similar.
Under which necessary and/or sufficient conditions (like the value of some or more invariant quantities) can one ensure that a non-negative, integral square matrix is non-trivially permutation-similar to a block diagonal matrix of non-negative, integral square matrices, i.e., a (non-trivial) direct sum of such matrices? My question is one of reducibility. That is, given $A \in \mathbb{Z}_{\geqslant 0}^{n \times n}$, under which conditions does one have $A = P^{-1} (\bigoplus_i A_i) Q$, where $P$ and $Q$ are $n \times n$ permutation matrices, $A_i \in \mathbb{Z}_{\geqslant 0}^{n_i \times n_i}$ for 1 \leqslant n_i < n for all indices $i$.
It seems like combinatorics plays a significant role here. For example, by simply counting the number of zero entries of $A$, one can rule out certain decompositions. For instance, if $A$ has no zero entries or an odd number of zero entries, then it certainly cannot decompose into any non-trivial block diagonal form.