18
$\begingroup$

In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.

Question : How to prove that it is impossible to multiply two 2 x 2 matrices in 6 multiplications?

Please note that matrices are over integers.

$\endgroup$
  • $\begingroup$ There are other matrix multiplication algorithms that can be faster. This web article from a Stanford CME 323 class provides details about Strassen's algorithm, Matrix multiplication: Strassen's algorithm. There is a Wikipedia topic, Strassen algorithm that goes into details and has links to additional information. $\endgroup$ – Richard Chambers Nov 29 '17 at 14:00
  • $\begingroup$ @RichardChambers Notice that Strassen’s algorithm has $7$ multiplications. It seems plausible to me that this lower bound is true. $\endgroup$ – Stella Biderman Nov 29 '17 at 14:10
  • $\begingroup$ As worded this question is wrong. There are plenty of matrices that can be multiplied with $6$ multiplications. You mean to ask for a proof that, in the worst case, it takes 7 aka there exists some matrix that requires 7 $\endgroup$ – Stella Biderman Nov 29 '17 at 14:15
  • $\begingroup$ @StellaBiderman yes I saw that Strassen's has 7 multiplications. I did not look at the other, faster and algorithms with a lower complexity. From what I can tell they use the same sub-matrix approach as Strassen's but I am not sure. I was just adding some additional information about Strassen's specifically. $\endgroup$ – Richard Chambers Nov 29 '17 at 14:16
  • 5
    $\begingroup$ There seems to be something missing from your question. I can easily give an algorithm which can multiply at least some matrices with 0 multiplications. There's probably a constraint that you are not mentioning. $\endgroup$ – Jörg W Mittag Nov 29 '17 at 19:50
24
$\begingroup$

This is a classical result of Winograd: On multiplication of 2x2 matrices.

Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix multiplication tensors: the algebraic complexity of $n\times n$ matrix multiplication is $O(n^\alpha)$ iff the tensor rank of $\langle n,n,n \rangle$ (the matrix multiplication tensor corresponding to the multiplication of two $n\times n$ matrices) is $O(n^\alpha)$. Strassen's algorithm uses the easy direction to deduce an $O(n^{\log_27})$ from the upper bound $R(\langle 2,2,2 \rangle) \leq 7$.

Winograd's result implies that $R(\langle 2,2,2 \rangle)=7$. Landsberg showed that the border rank of $\langle 2,2,2 \rangle$ is also 7, and Bläser et al. recently extended that to support rank and border support rank. Border rank and support rank are weaker (=smaller) notions of rank that have been used (in the case of border rank) or proposed (in the case of support rank) in the fast matrix multiplication algorithms.

$\endgroup$
7
$\begingroup$

You can find the result at:

S.Winograd, On multiplication of 2×2 matrices, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.