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