2

I'm working through Introduction to Algorithms (CLRS), and it presents a recursive divide-and-conquer algorithm for multiplying any two $n \times n$ matrices (where $n$ is an integer power of $2$) as follows:

To compute the product $C = A \cdot B$, we partition each of $A, B, C$ into four $n/2 \ \times \ n/2$ matrices $$A = \begin{bmatrix}{} A_{11} \ A_{12} \\ A_{21}\ A_{22}\end{bmatrix}, \ B = \begin{bmatrix}{} B_{11} \ B_{12} \\ B_{21}\ B_{22}\end{bmatrix}, \ C = \begin{bmatrix}{} C_{11} \ C_{12} \\ C_{21}\ C_{22}\end{bmatrix}$$ so that $$\begin{bmatrix}{} C_{11} \ C_{12} \\ C_{21}\ C_{22}\end{bmatrix} = \begin{bmatrix}{} A_{11} \ A_{12} \\ A_{21}\ A_{22}\end{bmatrix} \cdot \begin{bmatrix}{} B_{11} \ B_{12} \\ B_{21}\ B_{22}\end{bmatrix} \ $$

Obviously, this works when $A_{ij}, B_{ij}, C_{ij}$ are just scalars (it's the definition of matrix multiplication), but why is this necessarily valid for any square matrix (if $A_{ij}, B_{ij}, C_{ij}$ are themselves matrices)? How do we know that we can just partition each of matrices $A$ and $B$ into four $n/2 \ \times \ n/2$ matrices, and that multiplying these matrices will give us the entries for the answer?

Is there a name for this theorem? The book doesn't mention it and assumes that it's a given, but I don't find it quite as obvious. Is there any intuition/ proof of why this works as intended?

Spongebob
  • 25
  • 1
    For each individual entry of $C$, write down how it is computed in terms of the entries of $A$ and $B$. For the particular sub-matrix $C_{ij}$ that contains this entry, you can also write down an expression for this entry in terms of the entries of submatrices of $A$ and $B$. Showing these two are equal amounts to some rearranging/grouping of terms. – angryavian Jul 13 '17 at 21:33
  • The formula for the product is valid for matrices with coefficients in any ring, in particular if the coefficient ring is the ring of $n/2\times n/2$ matrices. – Bernard Jul 13 '17 at 21:42
  • @angryavian I've got $$C_{11} = A_{11} B_{21}+A_{12}B_{21}+\cdots + A_{1n}B_{n1}$$, but in order to compare this to the $C_{11}$ as claimed in the formula, I'd have to divide each of $A_{ij}$ and $B_{ij}$ into four $n/2 \ \times \ n/2$ matrices, and multiply each of those submatrices, but in order to do that, I'd have to split each of those into submatrices. I would then have to do this for every index. I don't know how I'd do this. Is there a name for the theorem that makes the claim in question? – Spongebob Jul 13 '17 at 21:52
  • @Bernard What do you mean by "ring" in this context? Could you give me an example of a non-square matrix (or a square matrix that is not a power of two) for which this applies? How would you even split such a matrix up into equal-sized submatrices? – Spongebob Jul 13 '17 at 21:55
  • Your submatrices are not square matrices? – Bernard Jul 13 '17 at 21:59

2 Answers2

0

Elaborating on my comment:

If $c_{ij}$ is the $i,j$ entry of $C$, then $$c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}$$ You can rewrite the right-hand side as $$\sum_{k=1}^{n/2} a_{ik} b_{kj} + \sum_{k=n/2+1}^n a_{ik} b_{kj}.$$

This will correspond to the multiplication via sub-matrices. If for example $c_{ij}$ lies in $C_{11}$, then the above corresponds to how $C_{11} = A_{11}B_{11} + A_{12} B_{21}$ contributes to the entry $c_{ij}$.

More generally, see this; basically any partitioning of $A$, $B$, and $C$ into block matrices is valid, as long as the dimensions match up so that multiplication of the sub-matrices is valid.

angryavian
  • 89,882
  • Shouldn't the LHS of your sum be from $k=1$ to $n/4$, not $n/2$, as you're computing four separate matrices?

    I'm finding it really hard to understand why this is the case. Is there an intuitive explanation as to why this is? I've tried proving the "theorem" by induction, but there's lots of messy algebra and as I said, I'm stuck computing loads and loads of submatrices.

     – Spongebob Jul 13 '17 at 22:18
  • @Spongebob My answer is a proof. All I have done is split the sum $\sum_{k=1}^n$ into two pieces: $\sum_{k=1}^{n/2}$ and $\sum_{k=n/2+1}^n$. The sub-matrix multiplication is $C_{11} = A_{11} B_{11} + A_{12} B_{21}$, which involves multiplication of $n/2 \times n/2$ matrices. There is no $n/4$. – angryavian Jul 13 '17 at 22:28
  • What does each of the sums correspond to (which submatrices in $C$)? – Spongebob Jul 13 '17 at 22:29
  • @Spongebob The sums are an expression for one entry in $C$, namely $c_{ij}$. It lies in one submatrix of $C$. If it lies in $C_{11}$, then note that $C_{11} = A_{11} B_{11} + A_{12} B_{21}$, and the first sum represents the contribution of the matrix $A_{11} B_{11}$ to the entry $c_{ij}$ while the second sum represents the contribution of the matrix $A_{12} B_{21}$ to the entry $c_{ij}$; if it lies in $C_{12}$, then note that $C_{12} = A_{11} B_{12} + A_{12} B_{22}$; etc. – angryavian Jul 13 '17 at 22:38
  • I get that, but what does $$\sum_{k=1}^{n/2}a_{ik}b_{kj}$$ respresent, and what does $$\sum_{k=n/2+1}^{n}a_{ik}b_{kj}$$ respresent? Surely, you're splitting the matrix into four submatrices, each of length $n/2$, not two, so there must be four summations? – Spongebob Jul 13 '17 at 22:54
  • @Spongebob Think about matrix multiplication, and how you compute a particular entry $c_{ij}$ of $C$. You take the "dot product" of the $i$th row of $A$ with the $j$ column of $B$. The first summation is just computing the dot product of the first half of the row of $A$ with the first half of the column of $B$, while the second summation is just computing the dot product of the second half of the row of $A$ with the second half of the column of $B$. – angryavian Jul 14 '17 at 00:10
0

Fundamentally, the multiplication of two matrices depends on the multiplication of a row by a column, or, in other words, a row vector by a column vector. This is just the dot product of two vectors which is a sum of the products of corresponding elements of the two vectors. This summation can be split in many ways by partitioning the index set into a collection of subsets. For exmaple, $$(a_1,a_2,a_3,a_4,a_5)\cdot(b_1,b_2,b_3,b_4,b_5) = a_1b_1+a_2b_2+a_3b_3+a_4b_4+a_5b_5$$ can also be computed as $$(a_1,a_3,a_5)\cdot(b_1,b_3,b_5)+(a_2,a_4)\cdot(b_2,b_4)=(a_1b_1+a_3b_3+a_5b_5)+(a_2b_2+a_4b_4).$$ This demonstrates the idea that you can partition matrices into rectangular blocks and multiply partitioned matrices regarding the blocks as if they were themselves matrix elements.

Somos
  • 35,251
  • 3
  • 30
  • 76