In part 1 of this series I outlined an informal method to partition a square matrix into block diagonal form. In this post I provide a formal description of such a method, applicable to any by square matrix. In doing this I use the concept of a partitioning vector introduced in my original post on multiplying block matrices.

(Note that it’s possible that a better approach to partitioning exists, not to mention better notation. However this is the best I’ve been able to come up with.)

Let be an by matrix. Following the discussion in my original post, we can divide the rows and columns of into partitions, where , using a vector of nonnegative integer values defined as follows:

where is the first row and column in the partition, is the last row and column in the partition, and is the number of rows and columns in the partition.

We then define submatrices of , with a given submatrix defined in terms of the entries of as follows:

so that the entry of has the value .

When we have and . When we have so that and . (For a more detailed discussion of why this is so please see the previous post on multiplying block matrices.)

We now attempt to partition into block diagonal form by constructing a partitioning vector as follows:

We first set , so that the first submatrix on the diagonal, , will start with row 1 and column 1. Then for , in turn we calculate by looking for the smallest such that

and

Note that the first property corresponds to having all zeroes to the right of the submatrix on the diagonal while the second property corresponds to having all zeroes below .

If no such exists then we set and have completed partitioning the matrix , with the number of partitions produced by the partitioning vector then being .

Otherwise (i.e., if such a does exist) we set , and repeat the process for and so on until the process terminates.

Note that we are guaranteed that the process described above terminates in no more than steps. As described above, we start by setting , and then for our first step we set and compute . If in computing we cannot find a suitable then the process terminates in one step as we set , with the resulting vector .

If, on the other hand, we are able to find a suitable then by the definition of we have and therefore . We then repeat the process with to find and by similar reasoning have and thus . In general we see that .

Suppose that the process has not terminated when we come to (i.e., the step in the process). From the previous paragraph we know that . Substituting into the above conditions relating to , in assigning we are looking for where

and

Since we conclude that . Then the first condition above cannot hold, because implies that , and is an by matrix for which there are no elements for . Similarly the second condition above cannot hold, because implies that , and there are no elements for . Therefore we terminate the process and set . We are thus guaranteed that the process of constructing the vector will terminate in at most steps.

Also note that the vector thus defined is a valid partition of according to our definition above:

- The first element .
- All elements of are nonnegative integers. ( is zero as noted, and all the other elements are chosen to be row and column indices of , and hence are positive integers.)
- We have for all . (This follows from the way was defined relative to .)
- Since there are at most steps after the initial assignment of , the maximum length of is , and for the number of partitions (which is one less than the length of ) we thus have .

Having constructed the partitioning vector , in my next post I show that partitions A into block diagonal form.

I want something like “fuzzy” block diagonal form of a (pos def, sym) matrix which is an adjacency matrix with weights, such that “weak” elements=links, defined by some criteria, graph topological or in some norm are outside the band / blocks on the diagonal that after will contain strong edges / elements defined as inverse of “weak”.

This is kind of like the problem of minimizing matrix bandwidth solved by e.g.

http://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm

Do you have an implementation of your method described above?

Do you have some pointers for me in the literature or other thoughts?

Unfortunately I’m not a professional mathematician, have no familiarity with the relevant literature, and thus cannot provide pointers for your particular problem. (I also haven’t implemented this as a computer program.)

I just have a B.S. in (applied) mathematics, and that was many many years ago. I did this series of posts because I was really (really) bothered by the fact that I couldn’t find online in the usual places (Wikipedia, Wolfram MathWorld, ProofWiki, etc.) any rigorous description of how to partition a matrix into block diagonal form such that the partitioning was maximal and unique. So I decided to try my hand at writing one.

I have no idea whether the resulting proof would pass muster with “real” mathematicians. I also have to believe that I’m just (imperfectly) replicating work that someone somewhere has already done in better form. Or maybe people think this is an obvious fact and therefore trivial and uninteresting–but it didn’t seem obvious to me at least.