22. a) If $A$ and $B$ are $n \times n$ matrices, with entries $a_{i j}$ and $b_{i j}$ for $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant n$, then $A B$ is the $n \times n$ matrix with entries $c_{i j}=\sum_{k=1}^{n} a_{i k} b_{k j}$. Show that $n^{3}$ multiplications of integers are used to find $A B$ directly from its definition.
b) Show it is possible to multiply two $2 \times 2$ matrices using only seven multiplications of integers by using the identity
where $x=a_{11} b_{11}-\left(a_{11}-a_{21}-a_{22}\right)\left(b_{11}-b_{12}+b_{22}\right)$.
c) Using an inductive argument, and splitting $2 n \times 2 n$ matrices into four $n \times n$ matrices, show that it is possible to multiply two $2^{k} \times 2^{k}$ matrices using only $7^{k}$ multiplications, and less than $7^{k+1}$ additions.
d) Conclude from part (c) that two $n \times n$ matrices can be multiplied using $O\left(n^{\log _{2} 7}\right)$ bit operations when all entries of the matrices have less than $c$ bits, where $c$ is a constant.
$$\begin{array}{l} \left(\begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array}\right) \quad\left(\begin{array}{ll} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array}\right)= \\ \left(\begin{array}{cc} a_{11} b_{11}+a_{12} b_{21} & x+\left(a_{21}+a_{22}\right)\left(b_{12}-b_{11}\right)+ \\ & \left(a_{11}+a_{12}-a_{21}-a_{22}\right) b_{22} \\ x+\left(a_{11}-a_{21}\right)\left(b_{22}-b_{12}\right)- & x+\left(a_{11}-a_{21}\right)\left(b_{22}-b_{12}\right)+ \\ a_{22}\left(b_{11}-b_{21}-b_{12}+b_{22}\right) & \left(a_{21}+a_{22}\right)\left(b_{12}-b_{11}\right) \end{array}\right) \end{array}$$