View Question
 ```How would you modify Strassen's theorem of multiplying (n x n) matrices where n is a power of 2 to accomodate arbitrary choices of (positive integers) n so that the algorithm still has a running time of Theta(n^lg(7))?```
 ```Hi, nerd17-ga: If N is the least power of 2 greater than or equal to n, extend the (n x n) matrices to (N x N) matrices by extending the diagonal with an (N-n) by (N-n) identity block and elsewhere zeros. The (N x N) product of the extended matrics is then the corresponding extension of the (n x n) product of the two original matrices, and (if one wishes to be careful about it) introducing and removing the extra entries is an O(n^2) operation. Now the original Strassen algorithm handles the multiplication of two (N x N) matrices in (according to Strassen's theorem) a running time of Theta(N^lg(7)). But n <= N < 2n, so: n^lg(7) <= N^lg(7) < (2^lg(7))*(n^lg(7) = 7(n^lg(7)) Thus Theta(N^lg(7)) is the same as Theta(n^lg(7)) by virtue of this pair of upper and lower bounds. Because lg(7) > 2, the extra O(n^2) operations involved in constructing those extensions doesn't change the dominate term in the "running time". Please let me know if any part of my answer requires further clarification. regards, mathtalk-ga``` Request for Answer Clarification by nerd17-ga on 30 Oct 2003 11:36 PST ```it's been a while and my matrix theory is quite hazy, so i apologize if this sounds elementary, but when you say you have to extend the diagonal with an (N-n) by (N-n) identity block and elsewhere zeros, i'm not entirely sure what you mean... say you have the following 3 x 3 matrix: a b c d e f g h i are you saying to extend it like so: a b c 0 d e f 0 g h i 0 0 0 0 0 or am i missing something (like a 1 at the bottom right)?``` Clarification of Answer by mathtalk-ga on 30 Oct 2003 12:25 PST ```Hi, nerd17-ga: I was thinking about putting 1's on the diagonal, but now I think your suggestion will work just as well and is simpler (since one adds only zeros). Suppose we want to multiply: a b c r s t d e f and u v w g h i x y z Then one may "border" each with zeros: a b c 0 d e f 0 g h i 0 0 0 0 0 and r s t 0 u v w 0 x y z 0 0 0 0 0 The product of these bordered-with-zeros matrices works out to be the same as bordering with zeros the product of the original matrices. One way to think about this is to write the matrix multiplication in block form. Let A,B be the original matrices, and let these be "bordered" with blocks of arbitrary (but compatible) dimensions: A 0 and B 0 0 0 0 0 Now "block multipication" (which is used extensively in the proof of Strassen's theorem) says we can write the extended product like this: (AB+00) (A0+00) (0B+00) (00+00) which of course simplifies to: AB 0 0 0 [I've omitted the dirty details of showing you that all the dimensions of these blocks, the nxn, the (N-n)xn, the nx(N-n), and the (N-n)x(N-n), all match up just as they need to in order for the resulting formula to make sense. Left to the reader!] In some contexts there might be an advantage to using 1's on the diagonal (it would preserve the singularity/nonsingularity of the matrix), but we're doing multiplication here (not "division"), so the zeros are a good idea. regards, mathtalk-ga``` Clarification of Answer by mathtalk-ga on 31 Oct 2003 06:51 PST ```By contrast, if we use 1's on the diagonal as I originally suggested, then: A 0 B 0 AB 0 0 I times 0 I equals 0 I Either way, one easily recovers the original (n x n) product AB from the product of the "extended" (N x N) matrices, and the computational complexity is the same. regards, mathtalk-ga```