Design and analysis of algorithms

Type in answer

Problem 3. The square of a matrix is its product with itself, AA. (a) Show that five multipl cations 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 n matrix? "Use a divide and conquer approach as in Strassen's algorithm, except that instead of getting 7 sub-problems of n/2, we now get 5 sub-problems of size n/2 thanks to part (a). Using the same analysis in Strassen's algorithm, we can conclude that the algorithm runs in time O(nlos25). (c) In fact, squaring matrices is no easier than matrix multiplication. Show that if n x n matrices can be squared in time O(nc), then any two n x n matrices can be multiplied in time O(n)