Multiplying block diagonal matrices

In a previous post I discussed the general problem of multiplying block matrices (i.e., matrices partitioned into multiple submatrices). I then discussed block diagonal matrices (i.e., block matrices in which the off-diagonal submatrices are zero) and in a multipart series of posts showed that we can uniquely and maximally partition any square matrix into block diagonal form. (See part 1, part 2, part 3, part 4, and part 5.) With this as background I now discuss the general problem of multiplying two block diagonal matrices. In particular I want to prove the following claim:

If A and B are n by n square matrices identically partitioned into block diagonal form:

A = \begin{bmatrix} A_{1}&0&\cdots&0 \\ 0&A_{2}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&A_{q} \end{bmatrix} \qquad B = \begin{bmatrix} B_{1}&0&\cdots&0 \\ 0&B_{2}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&B_{q} \end{bmatrix}

then their product C = AB is also a block diagonal matrix, identically partitioned to A and B:

C = \begin{bmatrix} C_{1}&0&\cdots&0 \\ 0&C_{2}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&C_{q} \end{bmatrix}

with C_{\alpha} = A_{\alpha}B_{\alpha}.

Proof: Let A and B be n by n square matrices identically partitioned into block diagonal form with q row and column partitions. In our framework identically partitioned means that the q partitions of A and B can be described by a partition vector u of length q+1, with both A_{\alpha} and B_{\alpha} containing u_{\alpha+1} - u_{\alpha} rows and columns.

From the previous discussion on multiplying block matrices we know that the n by n matrix product C = AB can be described as a block matrix with q row partitions and q column partitions:

C = \begin{bmatrix} C_{11}&C_{12}&\cdots&C_{1q} \\ C_{21}&C_{22}&\cdots&C_{2q} \\ \vdots&\vdots&\ddots&\vdots \\ C_{q1}&C_{q2}&\cdots&C_{qq} \end{bmatrix}

with submatrices computed as follows:

C_{\alpha \beta} = \sum_{\gamma = 1}^{q} A_{\alpha \gamma} B_{\gamma \beta}

Note that since A_{\alpha \gamma} contains u_{\alpha+1} - u_\alpha rows and u_{\gamma+1} - u_\gamma columns, and B_{\gamma \beta} contains u_{\gamma+1} - u_\gamma rows and u_{\beta+1} - u_\beta columns, C_{\alpha \beta} contains u_{\alpha+1} - u_\alpha rows and u_{\beta+1} - u_\beta columns.

We can rewrite the above expression for  C_{\alpha \beta} as follows:

C_{\alpha \beta} = \sum_{\gamma = 1}^{\alpha-1} A_{\alpha \gamma} B_{\gamma \beta} + A_{\alpha \alpha}B_{\alpha \beta} + \sum_{\gamma = \alpha+1}^{q} A_{\alpha \gamma} B_{\gamma \beta}

For both sums we have \gamma \ne \alpha for all terms in the sums, and since A is in block diagonal form we have A_{\alpha \gamma} = 0 for all terms in the sums, so that

C_{\alpha \beta} = \sum_{\gamma = 1}^{\alpha-1} 0 \cdot B_{\gamma \beta} + A_{\alpha \alpha}B_{\alpha \beta} + \sum_{\gamma = \alpha+1}^{q} 0 \cdot B_{\gamma \beta} = A_{\alpha \alpha}B_{\alpha \beta}

Since B is also in block diagonal form, if \alpha \ne \beta we have B_{\alpha \beta} = 0 and

C_{\alpha \beta} = A_{\alpha \alpha}B_{\alpha \beta} = A_{\alpha \alpha} \cdot 0 = 0

Since C_{\alpha \beta} = 0 if \alpha \ne \beta, C is also in block diagonal form.

We then have C_{\alpha \alpha} = A_{\alpha \alpha}B_{\alpha \alpha} or in our shorthand notation C_{\alpha} = A_{\alpha}B_{\alpha} so that

C = AB = \begin{bmatrix} C_{1}&0&\cdots&0 \\ 0&C_{2}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&C_{q} \end{bmatrix} = \begin{bmatrix} A_{1}B_{1}&0&\cdots&0 \\ 0&A_{2}B_{2}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&A_{q}B_{q} \end{bmatrix}

Note that if A and B are in maximal block diagonal form with only one partition then A = A_1 and B = B_1 so that this reduces to C_1 = A_1B_1 = AB = C.

On the other hand, if A and B are in maximal block diagonal form with n partitions, such that

A = \begin{bmatrix} a_1&0&\cdots&0 \\ 0&a_2&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&a_n \end{bmatrix} \qquad B = \begin{bmatrix} b_1&0&\cdots&0 \\ 0&b_2&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&b_n \end{bmatrix}

then A_\alpha = \begin{bmatrix} a_{\alpha} \end{bmatrix} and B_\alpha = \begin{bmatrix} b_{\alpha} \end{bmatrix} so that

C = AB = \begin{bmatrix} C_{1}&0&\cdots&0 \\ 0&C_{2}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&C_{n} \end{bmatrix} = \begin{bmatrix} a_1b_1&0&\cdots&0 \\ 0&a_2b_2&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&a_nb_n \end{bmatrix}

In my next post I discuss inverting block diagonal matrices.

 Buy me a snack to sponsor more posts like this!

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

One Response to Multiplying block diagonal matrices

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