2.27. The square of a matrix A is its product with itself, AA. (a) Show that...

 

Transcribed Image Text:

2.27. The square of a matrix A is its product with itself, AA. (a) Show that five multiplications are sufficient to compute the square of a 2 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 in- stead of getting 7 subproblems of size n/2, we now get 5 subproblems of size n/2 thanks to part (a). Using the same analysis as in Strassen's algorithm, we can conclude that the algorithm runs in time O(nlog25)." (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(nc), then any two n x n matrices can be multiplied in time O(nc). i. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n). ii. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B as follows: X 0 A = [ and B = 0 0 0 Y 0 0 [ 8 X ]. What is AB + BA, in terms of X and Y? iii. 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). 2.27. The square of a matrix A is its product with itself, AA. (a) Show that five multiplications are sufficient to compute the square of a 2 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 in- stead of getting 7 subproblems of size n/2, we now get 5 subproblems of size n/2 thanks to part (a). Using the same analysis as in Strassen's algorithm, we can conclude that the algorithm runs in time O(nlog25)." (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(nc), then any two n x n matrices can be multiplied in time O(nc). i. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n). ii. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B as follows: X 0 A = [ and B = 0 0 0 Y 0 0 [ 8 X ]. What is AB + BA, in terms of X and Y? iii. 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).