In part 2 of this series I described a method to construct a vector that partitions an by square matrix into row and column partitions. In this post I show that the vector thus constructed partitions into block diagonal form.

For the case where and we have (as previously discussed) and is in block diagonal form by the convention we’ve adopted.

Suppose , i.e., has been partitioned into at least two partitions by the vector . We consider where , beginning with the case where (i.e., we are in the upper right part of the matrix, and the submatrix is to the right of submatrix on the diagonal).

Since defines a valid partitioning of we have

Since (as assumed) and (because references a partition of the columns of , and the columns of have been divided into partitions), we have . That means that was not assigned on the last step of the process described in the previous post (that step being the step, and the value assigned being ), and that in turn means that was chosen so that if and .

As noted above, the entries in the rows of are drawn from rows through of A. Since we also have

All entries of are thus of the form where (from the definition of above) and (since the first column of is taken from column of , and ). As noted above all such entries are zero by the definition of . We therefore have if .

We next consider the case where (i.e., we are in the lower left part of the matrix, and the submatrix is below the submatrix on the diagonal). Since (as assumed) and (because references a partition of the rows of , and the rows of have been divided into partitions), we have . That means that was not assigned on the last step of the process described above, and that in turn means that and were chosen so that if and .

As noted above, the entries in the columns of are drawn from columns through of . Since we also have

All entries of are thus of the form where (from the definition of above) and (since the first row of is taken from row of , and ). As noted above all such entries are zero by the definition of . We therefore have if .

Since if and also if we then have if , so that as partitioned by is in block diagonal form if .

Since by convention is also in block diagonal form when , the vector as constructed in the previous post always partitions into block diagonal form. (For the vector would contain only the entries 0 and .)

In part 4 of this series I take up the problem of showing that uniquely and maximally partitions into block diagonal form with partitions.