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!

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s