Strassen-algorithm/2x2/Exercise

Let ${}2\times 2$-matrices ${}A={\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}}$ and ${}B={\begin{pmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{pmatrix}}$ be given. The product ${}A\cdot B$ is usually computed by the multiplication rule "row x column“; for this, we have to perform altogether ${}8$ multiplications in the field ${}K$. We describe a procedure for the matrix multiplication, in which only ${}7$ multiplications (but more additions) are necessary. We set

${}m_{1}={\left(a_{11}+a_{22}\right)}\cdot {\left(b_{11}+b_{22}\right)}\,,$

${}m_{2}={\left(a_{21}+a_{22}\right)}\cdot b_{11}\,,$

${}m_{3}=a_{11}\cdot {\left(b_{12}-b_{22}\right)}\,,$

${}m_{4}=a_{22}\cdot {\left(b_{21}-b_{11}\right)}\,,$

${}m_{5}={\left(a_{11}+a_{12}\right)}\cdot b_{22}\,,$

${}m_{6}={\left(a_{21}-a_{11}\right)}\cdot {\left(b_{11}+b_{12}\right)}\,,$

${}m_{7}={\left(a_{12}-a_{22}\right)}\cdot {\left(b_{21}+b_{22}\right)}\,.$

Show that the coefficients of the product matrix

${}AB=C={\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}}\,$

satisfy the equations

${}c_{11}=m_{1}+m_{4}-m_{5}+m_{7}\,,$

${}c_{12}=m_{3}+m_{5}\,,$

${}c_{21}=m_{2}+m_{4}\,,$

${}c_{22}=m_{1}-m_{2}+m_{3}+m_{6}\,.$

Create a solution