Theproductoftwon$\backslash$times nmatricesX andY isX$\backslash$times Y $=$XY$,$whereXY is also an n $\backslash$times n matrix. $($XY $)$ij $($that is$,$ the element at index i$,$ j$)$ can be computed as the dot product of the i$-$th row of X and the j$-$th column of Y $.$

The standard $($brute$-$force$)$ algorithm for matrix multiplication performs $\backslash$Theta $($n$3)$ operations: each of the n$2$ values in XY must be computed, and each dot product takes $\backslash$Theta $($n$)$ time to compute. Can we do better by using Divide and Conquer, $$ la Karatsuba?

Matrix multiplication lends itself nicely to divide and conquer, because we can perform it blockwise. That is$,$ we can carve X into $4($ n$2)\backslash$times $($ n$2)$ blocks as follows:

$[]$

X$=$AB CD

where A represents all values in the top left quadrant of the matrix, B represents all values in the top right quadrant, etc.

Let$$s carve Y into similar blocks: $[]$

Y$=$EF GH

Now, we can express their product XY as follows: $[][][]$

XY$=$ A B E F $=$ AE$+$BG AF$+$BH C D G H CE$+$DG CF$+$DH

Also, as a reminder, adding two n $\backslash$times n matrices X $+$ Y takes $\backslash$Theta $($n$2)$ time because for each pair of indices i$,$j$,($X $+$ Y$)$ij $=$ Xij $+$ Yij. Subtractin