Exercise 2.

We consider the following 4 square matrices of order 2 with coefficients in $ {\mathbb{Q}}$ :

$\displaystyle A = \left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \...
...left( \begin{array}{cc} d_{11} & d_{12} \\ d_{21} & d_{22} \end{array} \right).$    

Then we consider the following polynomials of degree 1 in $ X$ and with square matrices of order 2 for coefficients:

$\displaystyle p = A X + B \ \ {\rm and} \ \ q = C X + D.$    

  1. How many additions and multiplications in $ {\mathbb{Q}}$ are needed in order to compute the product $ p q$ in a naive way.
  2. Check that Karatsuba's trick applies here (despite of the fact that matrix multiplication is not commutative).
  3. Explain briefly why we can compute $ p q$ using only 21 multiplications in $ {\mathbb{Q}}$ . How many additions in $ {\mathbb{Q}}$ are needed in this case?
  4. Explain briefly in which circumstances using the multiplication scheme of the previous question makes sense.

\begin{minipage}{15 cm}
\item[1.] We have:
... applies to polynomials with matrix coefficients.

\begin{minipage}{13 cm}
\item[3.] Applying Karatsuba's ...
The GCD computations dominane both costs.

Marc Moreno Maza