Algorithms hw

Need complete solution

4 Matrix multiplication: a special case This problem is about matrix operation. In class, I presented the Strassen's algorithm for multi- plying two square matrices. Now, we consider a special case of multiplying two square matrices: given an n by n matrix A, compute the product A A. That is, we want to compute the product of A and A itself. Note that A B is often written as AB. a First show that you only need five multiplications for computing A A when n = 2 (so let b After knowing how to do the previous part, Tom thought he can use the following approach to obtain a faster algorithin for computing A A: Just like the Strassen's algorithm, except that using 7 subproblems of size n/2, I can now only use 5 subproblems of size n/2 based on my observation in step (a). Then I get an algorithm runs in time O(nlogz5)." Now, tell me what is wrong with Tom's approach c Now let me convince you that computing A x.A ls no easier than than the general square matrix multiplication in terms of algorithm efficiency. For this purpose, let us suppose that you can conpute A A for a square matrix A with S(n) = 0(nc) time (for some constant c 2). Then I claim that any two n by n matrices can be multiplied in time O(n). Your task is to fill in the missing parts of the following argument. (i) Given two n by n matrices A and B, show me that you can compute the matrix AB+BA in time 3S(n) +O(n2) (ii) Given two n by n matrices X andY, we consider the 2n by 2n matrices A and B, where and B = [0 Y Tell me what is AB+BA in terms of X and Y. (iii) Using (i) and (ii), argue that XY can be computed in 35 (2n) O(n2. Then conclude that miatrix moltiplication takes time 0(nc)