# On Permutation-Similarity and Block Diagonals

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.

-
I don't understand the question. A non-negative integral square matrix is already a block matrix of non-negative integral square matrices. I also don't understand what the first paragraph has to do with the rest of the question. – Qiaochu Yuan Apr 11 '12 at 15:51
Certainly permutation-similarity preserves the nonnegativity and integrality of entries, as well as the squareness of the matrix. It sounds like you want to determine the smallest blocks into which nonzero entries of a given matrix can be arranged. This can probably be attacked by graph closure ideas. Search for matrix bandwidth minimization algorithm for some related ideas. – hardmath Apr 11 '12 at 16:33
Thanks for the comments, QY and Hardmath. I've clarified my question. – user02138 Apr 11 '12 at 18:43

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.
• 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.