## 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.

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

### One Response to Multiplying block diagonal matrices

1. Varun Reddy says:

Elegant proof!