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.

Buy me a snack to sponsor more posts like this!

Partitioning a matrix into block diagonal form, part 3

Leave a Reply Cancel reply

Archives

Meta

Partitioning a matrix into block diagonal form, part 3

Share this:

Like this:

Related

Leave a Reply Cancel reply

Archives

Meta