In previous posts in this series I informally explored how to partition a matrix into block diagonal form (part 1), described a method for constructing a partitioning vector for an by square matrix (part 2), showed that the vector thus constructed partitions into block diagonal form (part 3), and proved a preliminary result about the relationship between that vector and any other vector partitioning into block diagonal form (part 4). In this post I complete 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 if we have a vector that also partitions A into block diagonal form, using partitions:
then for all where we have for some where . In other words, any partition boundary specified by is also a partition boundary specified by .
Note in addition that if for some and , and also for some , then . This follows from the fact that and are partition vectors: Assume that ; then we have and thus , which in turn implies that . (The proof of this last statement is by contradiction: If we instead had then because is a partition vector we would have .) Similarly implies that . So each entry of corresponds to a unique entry of .
I’m now ready to prove that is a maximal partitioning of into block diagonal form with partitions. Assume that also partitions into block diagonal form with partitions. We know from above that each entry of corresponds to a unique entry of . But there are only entries in , so that the number of entries in must be less than or equal to . (Otherwise two or more entries of would be equal to the same entry of .) We thus have . The vector is therefore a maximal partitioning of into block diagonal form.
My final task is to prove that is a unique partitioning of into block diagonal form with partitions. Suppose that also partitions into block diagonal form with partitions:
Since has entries, each equal to a unique entry of , and also has entries, each of the entries of is in turn equal to a entry of . In other words, for all , where , there exists a such that . (The proof is this is by contradiction: Suppose for there was no such that . Then since has entries, the same number as , at least two of the entries of would have to be equal to the same entry of , and hence equal to each other. But this is impossible since is a partition vector.)
Moreover, if for some and , and for some , then . (The proof of this again follows directly from the fact that and are partition vectors: Assume without loss of generality that ; then we have and thus , which in turn implies that .) So each entry of corresponds to a unique entry of .
I nw claim that for ). We already have by the definition of a partition vector. Now suppose for some , and consider and (assuming they exist, that is where ).
We know that for some where . Suppose . Then we would have and thus . But this cannot be, since is a partition vector and we are guaranteed that . So we must have . We also know that for some where . By a similar argument we must also have .
Now since we have , and since we have . But we also have . Since we have both and we must have . This in turn implies that and thus .
We thus have , and given for we have . By induction we have for . Since both and have only entries we therefore have .
Since partitions into block diagonal form with partitions, and since as just shown, for any diagonal submatrix where we have
Since for , the vector uniquely partitions into block diagonal form with partitions. Combined with the result above this concludes the proof: For any by square matrix we can uniquely and maximally partition into block diagonal form with one or more diagonal submatrices, using a vector constructed according to the method outlined in part 2 of this series.