block matrix multiplication

Question

If $A,B$ are $2 \times 2$ matrices of real or complex numbers, then

$$AB = \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]\cdot \left[ \begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array} \right] = \left[ \begin{array}{cc} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} \\ a_{21}b_{11}+a_{22}b_{21} & a_{22}b_{12}+a_{22}b_{22} \end{array} \right] $$

What if the entries $a_{ij}, b_{ij}$ are themselves $2 \times 2$ matrices? Does matrix multiplication hold in some sort of "block" form ?

$$AB = \left[ \begin{array}{c|c} A_{11} & A_{12} \\\hline A_{21} & A_{22} \end{array} \right]\cdot \left[ \begin{array}{c|c} B_{11} & B_{12} \\\hline B_{21} & B_{22} \end{array} \right] = \left[ \begin{array}{c|c} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\\hline A_{21}B_{11}+A_{22}B_{21} & A_{22}B_{12}+A_{22}B_{22} \end{array} \right] $$ This identity would be very useful in my research.

Answer 1

It depends on how you partition it, not all partitions work. For example, if you partition these two matrices

$$\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}, \begin{bmatrix} a' & b' & c' \\ d' & e' & f' \\ g' & h' & i' \end{bmatrix} $$

in this way

$$ \left[\begin{array}{c|cc}a&b&c\\ d&e&f\\ \hline g&h&i \end{array}\right], \left[\begin{array}{c|cc}a'&b'&c'\\ d'&e'&f'\\ \hline g'&h'&i' \end{array}\right] $$

and then multiply them, it won't work. But this would

$$\left[\begin{array}{c|cc}a&b&c\\ \hline d&e&f\\ g&h&i \end{array}\right] ,\left[\begin{array}{c|cc}a'&b'&c'\\ \hline d'&e'&f'\\ g'&h'&i' \end{array}\right] $$

What's the difference? Well, in the first case, all submatrix products are not defined, like $\begin{bmatrix} a \\ d \\ \end{bmatrix}$ cannot be multiplied with $\begin{bmatrix} a' \\ d' \\ \end{bmatrix}$

So, what is the general rule? (Taken entirely from the Wiki page on Block matrix)

Given, an $(m \times p)$ matrix $\mathbf{A}$ with $q$ row partitions and $s$ column partitions $$\begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \cdots &\mathbf{A}_{1s}\\ \mathbf{A}_{21} & \mathbf{A}_{22} & \cdots &\mathbf{A}_{2s}\\ \vdots & \vdots & \ddots &\vdots \\ \mathbf{A}_{q1} & \mathbf{A}_{q2} & \cdots &\mathbf{A}_{qs}\end{bmatrix}$$

and a $(p \times n)$ matrix $\mathbf{B}$ with $s$ row partitions and $r$ column parttions

$$\begin{bmatrix} \mathbf{B}_{11} & \mathbf{B}_{12} & \cdots &\mathbf{B}_{1r}\\ \mathbf{B}_{21} & \mathbf{B}_{22} & \cdots &\mathbf{B}_{2r}\\ \vdots & \vdots & \ddots &\vdots \\ \mathbf{B}_{s1} & \mathbf{B}_{s2} & \cdots &\mathbf{B}_{sr}\end{bmatrix}$$

that are compatible with the partitions of $\mathbf{A}$, the matrix product

$ \mathbf{C}=\mathbf{A}\mathbf{B} $

can be formed blockwise, yielding $\mathbf{C}$ as an $(m\times n)$ matrix with $q$ row partitions and $r$ column partitions.

Answer 2

It is always suspect with a very late answer to a popular question, but I came here looking for what a compatible block partitioning is and did not find it:

For $\mathbf{AB}$ to work by blocks the important part is that the partition along the columns of $\mathbf A$ must match the partition along the rows of $\mathbf{B}$. This is analogous to how, when doing $\mathbf{AB}$ without blocks—which is of course just a partitioning into $1\times 1$ blocks—the number of columns in $\mathbf A$ must match the number of rows in $\mathbf B$.

Example: Let $\mathbf{M}_{mn}$ denote any matrix of $m$ rows and $n$ columns irrespective of contents. We know that $\mathbf{M}_{mn}\mathbf{M}_{nq}$ works and yields a matrix $\mathbf{M}_{mq}$. Split $\mathbf A$ by columns into a block of size $a$ and a block of size $b$, and do the same with $\mathbf B$ by rows. Then split $\mathbf A$ however you wish along its rows, same for $\mathbf B$ along its columns. Now we have $$ A = \begin{bmatrix} \mathbf{M}_{ra} & \mathbf{M}_{rb} \\ \mathbf{M}_{sa} & \mathbf{M}_{sb} \end{bmatrix}, B = \begin{bmatrix} \mathbf{M}_{at} & \mathbf{M}_{au} \\ \mathbf{M}_{bt} & \mathbf{M}_{bu} \end{bmatrix}, $$

and $$ AB = \begin{bmatrix} \mathbf{M}_{ra}\mathbf{M}_{at} + \mathbf{M}_{rb}\mathbf{M}_{bt} & \mathbf{M}_{ra}\mathbf{M}_{au} + \mathbf{M}_{rb}\mathbf{M}_{bu} \\ \mathbf{M}_{sa}\mathbf{M}_{at} + \mathbf{M}_{sb}\mathbf{M}_{bt} & \mathbf{M}_{sa}\mathbf{M}_{au} + \mathbf{M}_{sb}\mathbf{M}_{bu} \end{bmatrix} = \begin{bmatrix} \mathbf{M}_{rt} & \mathbf{M}_{ru} \\ \mathbf{M}_{st} & \mathbf{M}_{su} \end{bmatrix}. $$

All multiplications conform, all sums work out, and the resulting matrix is the size you'd expect. There is nothing special about splitting in two so long as you match any column split of $\mathbf A$ with a row split in $\mathbf B$ (try removing a block row from $\mathbf A$ or further splitting a block column of $\mathbf B$).

The nonworking example from the accepted answer is nonworking because the columns of $\mathbf A$ are split into $(1, 2)$ while the rows of $\mathbf B$ are split into $(2, 1)$.

Answer 3

The recipe for multiplication of (scalar) matrices $$ (AB)_{i,j}=\sum_k A_{i,k}B_{k,j}\tag1 $$ is saying: to obtain the $(i,j)$ element of $AB$, form the dot product as you walk along row $i$ of $A$ while simultaneously walking down column $j$ of $B$. In other words,

The element at row $i$, column $j$ of $AB$ is the product of row $i$ of $A$ with column $j$ of $B$.

Using the notation $A_{i,\ast}$ to denote row $i$ of $A$ and $B_{\ast,j}$ to denote column $j$ of $B$, this can be restated symbolically as $$(AB)_{i,j}=A_{i,\ast}B_{\ast, j}\ .\tag2$$

This all works provided you can match up any row of $A$ with any column of $B$, which means the number of columns of $A$ must equal the number of rows of $B$. (This is what it means for $A$ and $B$ to be conformable.)

You can generalize (1) to block matrices, i.e., the formula still works when every $A_{i,k}$ and $B_{k,j}$ is itself a matrix [and the subscripts enumerate rows and columns of blocks], provided every product on the RHS of (1) makes sense. This means the number of columns of $A_{i,k}$ must equal the number of rows of $B_{k,j}$.

---

Example: Partition matrix $A$ into $A:=\pmatrix{A_1 &A_2}$ and $B$ into $B:=\pmatrix{B_1\\ B_2}$, where #columns($A_1$) = #rows($B_1$), and #columns($A_2$) = #rows($B_2$). Then $$ AB=\pmatrix{A_1 & A_2}\pmatrix{B_1\\ B_2}=A_1B_1 + A_2 B_2\ .\tag3 $$ To see this, consider the element at row $i$, column $j$ of $AB$. This element is computed as the product of row $i$ of $A$ with column $j$ of $B$. But row $i$ of $A$ is just row $i$ of $A_1$ followed by row $i$ of $A_2$. Similarly, column $j$ of $B$ is column $j$ of $B_1$ atop column $j$ of $B_2$. Assuming conformability, the product of row $i$ of $A$ with column $j$ of $B$ is the sum of two pieces: one piece is the product of row $i$ of $A_1$ with column $j$ of $B_1$, and the other is the product of row $i$ of $A_2$ with column $j$ of $B_2$. In symbols we've argued that $$(AB)_{i,j}=A_{i,\ast}B_{\ast,j}=(A_1)_{i,\ast}(B_1)_{\ast,j}+(A_2)_{i,\ast}(B_2)_{\ast,j}=(A_1B_1)_{i,j} + (A_2B_2)_{i,j},\tag4$$ and we're done.

---

Example: Consider conformable partitioned matrices $C:=\pmatrix{C_1\\ C_2}$ and $D:=\pmatrix{D_1 & D_2}$. Then $$CD=\pmatrix{C_1\\ C_2}\pmatrix{D_1 & D_2} =\pmatrix{C_1D_1 & C_1D_2\\C_2D_1&C_2 D_2}.\tag5 $$ Again, this can be seen by considering what happens when you multiply row $i$ of $C$ with column $j$ of $D$.