A fact about complexity of algorithms for computing the product of matrices was brought up to me that was very interesting I was not aware of. I still am not sure what the optimal bound is on the minimum number of scalar multiplications to compute a product of $n \times n$ matrices (maybe it is a simple result in the $2 \times 2$ case?) but I was told there is at least a basic proof for the following case. After playing around for a while I was not sure what the best route to take was so I thought I would just ask what is the easiest way to show the following result:

How do you prove that if $A,B$ are two $2 \times 2$ matrices then the product $AB$ can be computed using only 7 scalar multiplications?


1 Answer 1


This is the Strassen algorithm. You only use 7 scalar multiplications, and use 18 scalar additions (the standard method uses 8 scalar multiplications and 4 scalar additions).

Since addition is $O(n)$ (where $n$ is the number of bits of the two numbers) and multiplication is $O(n^2)$ (in the naive way; but there are better methods that are $O(n\log n 2^{\log_*n})$), for large enough numbers it is more efficient.

You can also iterate Strassen's algorithm to compue products of matrices by using the same formulas but with blocks instead of entries.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .