¿Por qué el producto de dos matrices es el producto de sus particiones?

Question

Estoy repasando Introducción a los Algoritmos (CLRS), y presenta un algoritmo recursivo de divide y vencerás para multiplicar dos cualesquiera $n \times n$ (donde $n$ es una potencia entera de $2$ ) del siguiente modo:

Para calcular el producto $C = A \cdot B$ dividimos cada una de $A, B, C$ en cuatro $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}$$ para que $$\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} \ $$

Obviamente, esto funciona cuando $A_{ij}, B_{ij}, C_{ij}$ son sólo escalares (es la definición de multiplicación de matrices), pero ¿por qué es esto necesariamente válido para cualquier matriz cuadrada (si $A_{ij}, B_{ij}, C_{ij}$ son a su vez matrices)? ¿Cómo sabemos que podemos simplemente particionar cada una de las matrices $A$ y $B$ en cuatro $n/2 \ \times \ n/2$ matrices, y que multiplicando estas matrices obtendremos las entradas de la respuesta?

¿Existe un nombre para este teorema? El libro no lo menciona y lo da por supuesto, pero a mí no me parece tan obvio. ¿Hay alguna intuición/prueba de por qué funciona como se pretende?

Answer 1

Abundando en mi comentario:

Si $c_{ij}$ es el $i,j$ entrada de $C$ entonces $$c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}$$ Se puede reescribir el lado derecho como $$\sum_{k=1}^{n/2} a_{ik} b_{kj} + \sum_{k=n/2+1}^n a_{ik} b_{kj}.$$

Esto corresponderá a la multiplicación mediante submatrices. Si, por ejemplo $c_{ij}$ se encuentra en $C_{11}$ entonces lo anterior corresponde a cómo $C_{11} = A_{11}B_{11} + A_{12} B_{21}$ contribuye a la entrada $c_{ij}$ .

---

En términos más generales, véase este básicamente cualquier partición de $A$ , $B$ y $C$ en matrices de bloques es válida, siempre que las dimensiones coincidan para que la multiplicación de las submatrices sea válida.

Answer 2

Fundamentalmente, la multiplicación de dos matrices depende de la multiplicación de una fila por una columna o, lo que es lo mismo, de un vector fila por un vector columna. Esto no es más que el producto escalar de dos vectores, que es una suma de los productos de los elementos correspondientes de los dos vectores. Esta suma se puede dividir de muchas maneras, particionando el conjunto de índices en una colección de subconjuntos. Por ejemplo $$(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$$ también puede calcularse como $$(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).$$ Esto demuestra la idea de que se pueden particionar matrices en bloques rectangulares y multiplicar matrices particionadas con respecto a los bloques como si fueran ellos mismos elementos de la matriz.