Partitioning a matrix into block diagonal form, part 1

In my previous post I offered a more formal definition of a block diagonal matrix, and claimed that we can partition an arbitrary $n$ by $n$ square matrix $A$ into block diagonal form in a way that is both maximal (i.e., no partitioning with more partitions exists) and unique (only one partitioning exists with that exact number of partitions). In this post I lay the groundwork for a formal proof of this by working through an example of partitioning such a matrix into block diagonal form.

Let’s start with an example matrix:

$A = \begin{bmatrix} 0&x&0&0&0 \\ x&0&0&0&0 \\ 0&x&0&0&0 \\ 0&0&0&0&0 \\ 0&0&0&0&x \end{bmatrix}$

and then consider alternative choices for the first partition:

$\begin{bmatrix} 0&\vline&x&0&0&0 \\ \hline x&\vline&0&0&0&0 \\ 0&\vline&x&0&0&0 \\ 0&\vline&0&0&0&0 \\ 0&\vline&0&0&0&x \end{bmatrix} \quad \begin{bmatrix} 0&x&\vline&0&0&0 \\ x&0&\vline&0&0&0 \\ \hline 0&x&\vline&0&0&0 \\ 0&0&\vline&0&0&0 \\ 0&0&\vline&0&0&x \end{bmatrix} \quad \begin{bmatrix} 0&x&0&\vline&0&0 \\ x&0&0&\vline&0&0 \\ 0&x&0&\vline&0&0 \\ \hline 0&0&0&\vline&0&0 \\ 0&0&0&\vline&0&x \end{bmatrix}$

In each alternative partition we move the partitioning lines down one row and right one column, each time considering a candidate for the first diagonal submatrix $A_1$ . We stop at the point when there are only zeroes below and to the right of the candidate submatrix. Our first submatrix $A_1$ is then the 3 by 3 matrix in the upper left.

We then repeat the process, drawing new partitioning lines down one row and right one column:

$\begin{bmatrix} 0&x&0&\vline&0&\vline&0 \\ x&0&0&\vline&0&\vline&0 \\ 0&x&0&\vline&0&\vline&0 \\ \hline 0&0&0&\vline&0&\vline&0 \\ \hline 0&0&0&\vline&0&\vline&x \end{bmatrix}$

Since the 1 by 1 matrix containing zero as its only entry has only zeroes below it and to the right of it, we choose it as our second submatrix $A_2$ .

At this point we cannot draw any further partitioning lines, so we choose as our last submatrix $A_3$ the 1 by 1 matrix in the lower right. We have thus partitioned $A$ into block diagonal form with three submatrices on the diagonal.

Based on the process we followed it is apparent (or at least very plausible) that this is the only way to partition $A$ into block diagonal form with three submatrices on the diagonal, and also that we could not have partitioned $A$ into more than three submatrices on the diagonal and still have it be block diagonal according to the definition above.

Next we look at two extreme examples. In our first matrix the process of partitioning fails on the first step, in the sense that we cannot find suitable lines of partition for the first submatrix. No matter the choice of partition lines, the candidate submatrix never has only zeroes below it or to the right of it:

$\begin{bmatrix} 0&\vline&x&0&0&0 \\ \hline x&\vline&0&0&0&0 \\ 0&\vline&x&0&x&0 \\ 0&\vline&0&0&0&0 \\ 0&\vline&0&0&x&x \end{bmatrix} \quad \begin{bmatrix} 0&x&\vline&0&0&0 \\ x&0&\vline&0&0&0 \\ \hline 0&x&\vline&0&x&0 \\ 0&0&\vline&0&0&0 \\ 0&0&\vline&0&x&x \end{bmatrix} \quad \begin{bmatrix} 0&x&0&\vline&0&0 \\ x&0&0&\vline&0&0 \\ 0&x&0&\vline&x&0 \\ \hline 0&0&0&\vline&0&0 \\ 0&0&0&\vline&x&x \end{bmatrix} \quad \begin{bmatrix} 0&x&0&0&\vline&0 \\ x&0&0&0&\vline&0 \\ 0&x&0&x&\vline&0 \\ 0&0&0&0&\vline&0 \\ \hline 0&0&0&x&\vline&x \end{bmatrix}$

We conclude that this matrix can be considered to be in block diagonal form, but with only a single partition; in other words, $r = 1$ and $A = A_1$ . As with the previous example this partitioning appears to be maximal, in that we can see no way to partition the matrix into two submatrices and have it be in block diagonal form. The partitioning is also obviously unique.

With the next example matrix the very first pair of partitioning lines we try produces a suitable submatrix with zeroes to the right and below, and each subsequent pair of lines does as well:

$\begin{bmatrix} 0&\vline&0&0&0&0 \\ \hline 0&\vline&x&0&0&0 \\ 0&\vline&0&x&0&0 \\ 0&\vline&0&0&0&0 \\ 0&\vline&0&0&0&x \end{bmatrix} \quad \begin{bmatrix} 0&\vline&0&\vline&0&0&0 \\ \hline 0&\vline&x&\vline&0&0&0 \\ \hline 0&\vline&0&\vline&x&0&0 \\ 0&\vline&0&\vline&0&0&0 \\ 0&\vline&0&\vline&0&0&x \end{bmatrix} \quad \begin{bmatrix} 0&\vline&0&\vline&0&\vline&0&0 \\ \hline 0&\vline&x&\vline&0&\vline&0&0 \\ \hline 0&\vline&0&\vline&x&\vline&0&0 \\ \hline 0&\vline&0&\vline&0&\vline&0&0 \\ 0&\vline&0&\vline&0&\vline&0&x \end{bmatrix} \quad \begin{bmatrix} 0&\vline&0&\vline&0&\vline&0&\vline&0 \\ \hline 0&\vline&x&\vline&0&\vline&0&\vline&0 \\ \hline 0&\vline&0&\vline&x&\vline&0&\vline&0 \\ \hline 0&\vline&0&\vline&0&\vline&0&\vline&0 \\ \hline 0&\vline&0&\vline&0&\vline&0&\vline&x \end{bmatrix}$

This matrix is a diagonal matrix with all entries off the diagonal being zero. We conclude that every diagonal matrix is also a block diagonal matrix with the number of partitions $r = n$ , and with each diagonal submatrix $A_{\alpha} = \begin{bmatrix} a_{\alpha \alpha} \end{bmatrix}$ . The partitioning is clearly both maximal and unique, since we cannot have more than $n$ partitions of the rows and columns of an $n$ by $n$ matrix, and only one way exists to partition an $n$ by $n$ matrix into $n$ partitions.