In my previous two posts I described a method for constructing a partitioning vector for an by square matrix (part 2 of this series) and showed that the vector thus constructed partitions into block diagonal form (part 3). In this post I begin the task of showing that the vector is maximal and unique: cannot also be partitioned as a block diagonal matrix with partitions, where , and if we partition into block diagonal form with partitions using a vector then we have .
In the previous posts I showed that we can construct a vector that will partition into block diagonal form with partitions (where is one less than the length of ), such that
Now suppose that we have a vector that also partitions A into block diagonal form, using partitions:
My approach in this post is to try to find some sort of connection between and . In particular, I claim that for all where we have for some where . In other words, any partition boundary specified by is also a partition boundary specified by .
My proof is by induction. Since and are both partition vectors we already have by definition. The claim therefore holds true for (with in this case). Suppose that for some we have for some (with ), and consider . We want to show that for some where .
We can select such that and . This is done as follows: We have so we know that for at least one (i.e., ). We select to be the smallest less than or equal to for which . By the definition of and the fact that we then conclude that . (If we had then would not be the smallest less than or equal to for which .) We also have , which means that . We then have . Finally, and implies that and thus . The result is that has the properties noted above.
From the above we see that . I now claim that . The proof is by contradiction. Suppose instead that . The submatrix includes entries from rows through of and columns through of . Since partitions into block diagonal form we know that any submatrices to the right of and below are zero (if such submatrices exist).
The requirement that all submatrices to the right of be zero then means that we must have if and , and the requirement that all submatrices below be zero means that we must also have if and .
From the way we selected we have , which means that we also have if and , and if and .
But recall from the definition of that was chosen to be the smallest such that if either and , or if and ; alternatively was set to if no such existed. In the former case we must have , which contradicts our assumption that . In the latter case our assumption that implies that there is indeed a fulfilling the criteria above, namely , which contradicts our assumption about how was defined.
We therefore conclude that given for some (where ), there exists such that (where ). Combined with the fact that this is true for , we conclude that for any (where ) there exists such that and , so that any partition boundary specified by is also a partition boundary specified by .
In part 5 of this series I use this result to complete the task of showing that the vector is maximal and unique.