In fact, squaring matrices is no easier than matrix multiplication. In this part

Question

In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n Times n matrices can be squared in time S(n) = 0(n^c), then any two n Times n matrices can be multiplied in time 0(n^c). Given two n Times n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n^2). Given two n Times n matrices X and Y, define the 2n Times 2n matrices A and B as follows: A = [X 0 0 0] and B = [0 Y 0 0] What is AB + BA, in terms of X and Y? Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n^2). Conclude that matrix multiplication takes time O(n^c).

Explanation / Answer

b.) AB = [ 0 XY ]

[ 0 0 ]

BA = [0 0 ]

[0 0]

So, AB + BA = [ 0 XY

0 0]

a.) To find AB + BA

what we are doing is:

First we are computing AB.

By given condition, it will take time O(n^c)

And for computing BA,

it will take time O(n^c)

So, multiplying of 2 will take 2O(n^c)

which is equal to 2 S(n)

Now next task is finding sum of both, AB + BA

time for finding sum is O(n^c) + O(n^2) for worst case.

So, total time is 3S(n) + O(n^2)

c.) If matrix is 2n*2n

then using 1 and 2,

sum is 3S(2n) + O(n^2)

Hence Proved

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---