21
$\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$
5
  • $\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$ Nov 29, 2017 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$ Nov 29, 2017 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$ Nov 29, 2017 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$ Nov 29, 2017 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$ Nov 29, 2017 at 19:50

2 Answers 2

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$
8
$\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 and acknowledge you have read our privacy policy.

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