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