# How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

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.

• 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. – Richard Chambers Nov 29 '17 at 14:00
• @RichardChambers Notice that Strassen’s algorithm has $7$ multiplications. It seems plausible to me that this lower bound is true. – Stella Biderman Nov 29 '17 at 14:10
• 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 – Stella Biderman Nov 29 '17 at 14:15
• @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. – Richard Chambers Nov 29 '17 at 14:16
• 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. – Jörg W Mittag Nov 29 '17 at 19:50

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.