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.
Best Answer
I still don't really understand the question (what kind of conditions do you care about? Theoretical? Algorithmic?) but here are some thoughts. $A$ is the adjacency matrix of a directed graph, and conjugating $A$ by a permutation just corresponds to relabeling the vertices. What you want is more or less to compute the connected components of the underlying undirected graph, or at least to determine whether there is one or more than one such component.
Probably there are many algorithms to do this efficiently; here's two off the top of my head.
Compute $B = (A + A^T)^{2^k}$ by repeated squaring, where $k$ is the smallest positive integer such that $2^k \ge n$. Then check whether at least one entry in $B$ is equal to zero. (If the entries of the matrices get large enough to be annoying, at any step you can replace all positive entries by $1$.)
Compute the Laplacian matrix $\Delta$ of the underlying undirected graph. $\dim \ker \Delta$ is equal to the number of connected components, and this can be efficiently computed by row reduction.