1
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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