## Partitioning a matrix into block diagonal form, part 3

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

For the case where $r = 1$ and $v = \begin{bmatrix} 0&n \end{bmatrix}$ we have $A = A_{11}$ (as previously discussed) and $A$ is in block diagonal form by the convention we’ve adopted.

Suppose $r > 1$, i.e., $A$ has been partitioned into at least two partitions by the vector $v$. We consider $A_{\alpha \beta}$ where $\alpha \ne \beta$, beginning with the case where $\alpha < \beta$ (i.e., we are in the upper right part of the matrix, and the submatrix $A_{\alpha \beta}$ is to the right of submatrix $A_{\alpha \alpha}$ on the diagonal).

Since $v$ defines a valid partitioning of $A$ we have

$A_{\alpha \beta} = \begin{bmatrix} a_{v_\alpha+1, v_\beta+1}&a_{v_\alpha+1,v_\beta + 2}&\cdots&a_{v_\alpha+1,v_{\beta+1}} \\ a_{v_\alpha+2, v_\beta+1}&a_{v_\alpha+2,v_\beta+2}&\cdots&a_{v_\alpha+2,v_{\beta+1}} \\ \vdots&\vdots&\ddots&\vdots \\ a_{v_{\alpha+1}, v_\beta+1}&a_{v_{\alpha+1},v_\beta+2}&\cdots&a_{v_{\alpha+1},v_{\beta+1}} \end{bmatrix}$

Since $\alpha < \beta$ (as assumed) and $\beta \le r$ (because $\beta$ references a partition of the columns of $A$, and the columns of $A$ have been divided into $r$ partitions), we have $\alpha < r$. That means that $v_{\alpha+1}$ was not assigned on the last step of the process described in the previous post (that step being the $r^{th}$ step, and the value assigned being $v_{r+1}$), and that in turn means that $v_{\alpha+1}$ was chosen so that $a_{ij} = 0$ if $v_{\alpha} + 1 \le i \le v_{\alpha+1}$ and $j > v_{\alpha+1}$.

As noted above, the entries in the rows of $A_{\alpha \beta}$ are drawn from  rows $v_{\alpha} + 1$ through $v_{\alpha+1}$ of A. Since $\alpha < \beta$ we also have

$\beta \ge \alpha+1 \rightarrow v_{\beta} \ge v_{\alpha+1} \rightarrow v_{\beta} + 1 > v_{\alpha+1}$

All entries of $A_{\alpha \beta}$ are thus of the form $a_{ij}$ where $v_{\alpha} + 1 \le i \le v_{\alpha+1}$ (from the definition of $A_{\alpha \beta}$ above) and $j > v_{\alpha+1}$ (since the first column of $A_{\alpha \beta}$ is taken from column $v_{\beta} + 1$ of $A$, and $v_{\beta} + 1 > v_{\alpha+1}$). As noted above all such entries are zero by the definition of $v_{\alpha+1}$. We therefore have $A_{\alpha \beta} = 0$ if $\alpha < \beta$.

We next consider the case where $\alpha > \beta$ (i.e., we are in the lower left part of the matrix, and the submatrix $A_{\alpha \beta}$ is below the submatrix $A_{\beta \beta}$ on the diagonal). Since $\beta < \alpha$ (as assumed) and $\alpha \le r$ (because $\alpha$ references a partition of the rows of $A$, and the rows of $A$ have been divided into $r$ partitions), we have $\beta < r$. That means that $v_{\beta+1}$ was not assigned on the last step of the process described above, and that in turn means that $v_{\beta}$  and $v_{\beta+1}$ were chosen so that $a_{ij} = 0$ if $i > v_{\beta+1}$ and $v_{\beta} + 1 \le j \le v_{\beta+1}$.

As noted above, the entries in the columns of $A_{\alpha \beta}$ are drawn from  columns $v_{\beta} + 1$ through $v_{\beta+1}$ of $A$. Since $\alpha > \beta$ we also have

$\alpha \ge \beta+1 \rightarrow v_{\alpha} \ge v_{\beta+1} \rightarrow v_{\alpha} + 1 > v_{\beta+1}$

All entries of $A_{\alpha \beta}$ are thus of the form $a_{ij}$ where $v_{\beta} + 1 \le j \le v_{\beta+1}$ (from the definition of $A_{\alpha \beta}$ above) and $i > v_{\beta+1}$ (since the first row of $A_{\alpha \beta}$ is taken from row $v_{\alpha} + 1$ of $A$, and $v_{\alpha} + 1 > v_{\beta+1}$). As noted above all such entries are zero by the definition of $v_{\beta+1}$. We therefore have $A_{\alpha \beta} = 0$ if $\alpha > \beta$.

Since $A_{\alpha \beta} = 0$ if $\alpha < \beta$ and also if $\alpha > \beta$ we then have $A_{\alpha \beta} = 0$ if $\alpha \ne \beta$, so that $A$ as partitioned by $v$ is in block diagonal form if $r > 1$.

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

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

This entry was posted in linear algebra. Bookmark the permalink.