91影视

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.

(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}脳\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.

(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.

(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}$

(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.