A counter-example to disprove that not every adjacency matrix can be made block-diagonal?

Question

I have a bunch of clusters of proteins (a disconnected graph) and wanted to present this data as an adjacency matrix for various reasons and have been looking for a way to make these adjacency matrices block-diagonal to make the relationships more apparent, but had no luck. I have tried SciPy's reverse Cuthill-McKee, svd, somebody has recommended Dulmage-Mendehlson and a bunch of other decompositions but to no avail. By this point, somebody told me that this might not even be possible in every case.

Would somebody happen to have an example or a concrete formulation of why exactly? I can't quite convince myself that's it's not possible from just looking at my data which looks like this by the way... Clearly, the structures which I'm trying to present are there (the large and small ribosomal subunits) and would probably become more apparent when I pour more data in there, but I would've so loved to also differentiate the clusters within the two subunits because I know they are there. Should I just use a covariance matrix?

Here is what breadth-first search yields by the way. Still I am not sure what that means, but I can definitely see now that permuting out of this state of band-minimization breaks structure rather than builds it, so maybe that's as far as I get today.

Answer 1

You always can permute the rows and columns of the adjacency matrix so that each block corresponds to a connected component. Just find the connected components and then reorder with all nodes from component 1 first, component 2 next, and so on.

Answer 2

Some questions:

1. What do the colors in your plots represent?
2. How can you be sure your graph is disconnected if you haven't block-diagonalized its adjacency matrix? Is there something in the nature of the data that guarantees this?

Now some comments:

If your graph really does have $n$ disconnected components, than its adjacency matrix certainly can be written in block diagonal form with $n$ blocks, regardless of what anybody says.

Something like the following should work. Let A be an m by m adjacency matrix. Create an array componentIdentifier of length m, with every element initialized to 0. Also create an array permutation of length m.

numberComponents = 0
numberVerticesPermuted = 0
for i from 1 to m:
   if componentIdentifier[i] == 0:
      /* vertex i is in a new component */
      numberComponents = numberComponents + 1
      componentIdentifier[i] = numberComponents
      numberVerticesPermuted = numberVerticesPermuted + 1
      permutation[numberVerticesPermuted] = i

      /* find all vertices connected to i */
      k = numberVerticesPermuted
      while k <= numberVerticesPermuted:
         r = permutation[k]
         for c from 1 to m:
            if A[r,c] == 1 and componentIdentifier[c] == 0:
               componentIdentifier[c] = numberComponents
               numberVerticesPermuted = numberVerticesPermuted + 1
               permutation[numberVerticesPermuted] = c
         k = k + 1

When this concludes, numberComponents will hold the number of disconnected components and permutation will hold the permutation of indices needed to put the adjacency matrix in block-diagonal form.