Why is the product of two matrices the product of their partitions? 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?
 A: 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.
A: 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.
