Strassen Algorithm 7 multiplications Strassen Algoritm is a well-known matrix multiplication divide and conquer algorithm.
The trick of the algorithm is reducing the number of multiplications to 7 instead of 8. I was wondering, can we reduce any further? Can we only do 6 multiplications?
Also, what happens if we divide the NxN arrays into 9 arrays each of (N/3)x(N/3) instead of 4 arrays of (N/2)x(N/2). Can we then do less multiplications?
 A: Of possible relevance to your question (though it might go into more geometric considerations than you care to read):
Generalizations of Strassen's equations for secant varieties of Segre varieties (J. Landsberg and  L. Manivel, Comm. Algebra 2008)
A: You may be interested to know that there's a way to multiply $3\times3$ matrices using only 23 multiplications (where the naive method uses $27$). See Julian D. Laderman, A noncommutative algorithm for multiplying $3\times3$ matrices using $23$ muliplications, Bull. Amer. Math. Soc. 82 (1976) 126–128, MR0395320 (52 #16117). 
As for doing $2\times2$ with fewer than $7$ multiplications, this was proved impossible just a few years ago. See J M Landsberg, The border rank of the multiplication of $2\times2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), 447–459, MR2188132 (2006j:68034). 
EDIT: As Mariano points out, Landsberg acknowledged a gap in the proof. But don't panic. The review, and my preceding paragraph, were based on the electronic version of Landsberg's paper. The print version (which is freely available on the AMS website) is different. It says, "Hopcroft and Kerr [12] and Winograd [22] proved independently that there is no algorithm for multiplying $2\times2$ matrices using only six multiplications." 
Those references are 
J. E. Hopcroft and L. R. Kerr, On minimizing the number of multiplications necessary for
matrix multiplication, SIAM J. Appl. Math. 20 (1971), 30–36, MR0274293 (43:58). 
S.Winograd, On multiplication of $2\times2$ matrices, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173). 
A: Everything you ever wanted to know can be gleaned from:
http://en.wikipedia.org/wiki/Matrix_multiplication
A: Best solution is in page 481, lines -1,-2, -3 and -4 of 
The art of Computer Programming, Volume two, Second Edition
of Donald E. Knuth.
Also interesting to take a look to page 482.
He also references the original paper of Strassen as Numer. Math. 13 (1969),
354-356 in lines -5,-6,-7,-8 of the same page (481).
A: I am not an expert in this field, but can hardly recall that:
- Strassen algorithm is optimal for divisions on 4 submatrices
- there are algorithms using a much larger number of submatrices and behaving slightly better.
If you are really interested in these results I can search for references, but be aware that the algorithms are of a very little practical use --- they just have big constant factors (and it is not the usual case that we are given a large dense matrix), and are not that robust (in the sense of numerical stability).
