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

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

-
There's a discussion of computing the number of connected components of a graph at en.wikipedia.org/wiki/Connected_component_(graph_theory). It starts, It is straightforward to compute the connected components of a graph in linear time using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, [continued next comment] – Gerry Myerson Apr 12 '12 at 1:39
[continued from previous comment] starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component. Hopcroft and Tarjan (1973)[1] describe essentially this algorithm, and state that at that point it was "well known". – Gerry Myerson Apr 12 '12 at 1:40
Thanks, Gerry. I'll look into this.... – user02138 Apr 12 '12 at 13:04