Question

Thesquare of a matrix A is its product with itself, AA.

(a) Show that five multiplications are sufficient to compute the square of a 2 x 2 matrix.

(b) What is wrong with the following algorithm for computing the square of an n x n matrix?

“Use a divide-and-conquer approach as in Strassen’s algorithm, except that instead of getting 7 subproblems of size $\frac{\mathbf{n}}{\mathbf{2}}$, we now get 5 subproblems of size $\frac{\mathbf{n}}{\mathbf{2}}$ thanks to part (a). Using the same analysis as in Strassen’s algorithm, we can conclude that the algorithm runs in time O (n^c) .”

(c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(n^c), then any two n x n matrices can be multiplied in time O(n^c) .

1. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n² ) .
2. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B,L as follows:
   $A=\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]andB=\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]$
   What is AB + BA, in terms of X and Y?
3. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n² ). Conclude that matrix multiplication takes time O(n^c ).

Short answer

1. $\left[\begin{array}{cc}m& n\\ o& p\end{array}\right]\left[\begin{array}{cc}m& n\\ o& p\end{array}\right]=\left[\begin{array}{cc}{m}^2+no& n(m+p)\\ 0(m+p)& no+p^2\end{array}\right]$,5
2. The suggested algorithm has insufficient run time to perform the square of the matrix.
3. 
   (i) Given matrix can be computed in 3S(n) +O(n² )
   (ii) $AB+BA=\left[\begin{array}{cc}0& XY\\ 0& 0\end{array}\right]$
   (iii) The product XYneeds only 2S (2n) + O(n² )computation time and the matrix multiplication takes O(n^c)time.

Step-by-step solution

Number of multiplications required to compute the square of matrix:

Consider the 2 x 2 matrix, $\left[\begin{array}{cc}m& n\\ o& p\end{array}\right]$,

Compute the square of the above matrix,

$\left[\begin{array}{cc}m& n\\ o& p\end{array}\right]\left[\begin{array}{cc}m& n\\ o& p\end{array}\right]=\left[\begin{array}{cc}{m}^2+no& n(m+p)\\ 0(m+p)& no+p^2\end{array}\right]$

In the computation, the multiplications involved are m², n (m + p), o (m + p), p² , and no.

Therefore, the five multiplications are sufficient to calculate the square of 2 x 2 matrix.

What is wrong with the given algorithm

(b)

A matrix squaring problem of size n xn has 5 sub-problems of size $\frac{n}{2}$. The half of the sub-problems (that is, three of the five sub-problems) are engaged in the product of $\frac{n}{2}\times \frac{n}{2}$matrices, according to the divide and conquer approach. There are five sub-problems in all, each of which is $\frac{n}{2}$ in size. Each sub-operation of a problem has been denoted by T Because the two sets of matrices are divided and conquered, this procedure will take O(n²) time to run. As a result, this method does not execute in "O(n O(n^log₂3) time.

As a result, the suggested algorithm's running time is insufficient for computing the square of a n x n matrix.

show that the matrix AB + BA can be computed in time 3S(n) + O(n2).

(c)

i.

Consider the two n x n matrices, A and B .

Calculate, AB + BA as follows,

$AB+BA=(A+B)(A+B)-AA-BB$ ,

The computation involves three squared terms, that can be computed in 3S(n) times. The other arithmetic operations can be computed in O(n²) time.

Therefore, the computation of AB + BA can be computed in 3S(n) + O(n²) time.

show the matrix AB + BA in terms of X and Y 

(c)

ii.

Consider the two n x n matrices, A and B .

$\begin{array}{rcl}A& =& \left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right],B=\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]\\ AB+BA& =& \left(\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]+\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]\right)\left(\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]+\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]\right)-\left(\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]+\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]\right)\left(\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]+\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]\right)\\ & =& \left[\begin{array}{cc}0& XY\\ 0& 0\end{array}\right]\end{array}$ ,

Therefore, the representation of AB + BA , in terms of X and Y is$\begin{array}{rcl}& & \left[\begin{array}{cc}0& XY\\ 0& 0\end{array}\right]\end{array}$

show the matrix AB + BA in terms of X and Y 

(c)

iii.

Consider the product of XY as follows,

$\left[\begin{array}{cc}0& XY\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}X& Y\\ 0& 0\end{array}\right]\left[\begin{array}{cc}X& Y\\ 0& 0\end{array}\right]-\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]-\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]$

Since, $\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]=0$,

The product will be,$\left[\begin{array}{cc}0& XY\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}X& Y\\ 0& 0\end{array}\right]\left[\begin{array}{cc}X& Y\\ 0& 0\end{array}\right]-\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]$

The product has two squares and a arithmetic opertation.

Therefore,The product XYneeds only 2S(2n) + O(n²)computation time and the matrix multiplication takes O(n^c)time.